AtCoder Daily Training ALL 2024/05/22 18:00start

A - Lexicographic Order

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

相異なる二つの文字列 S, T が与えられます。
S が T よりも辞書順で小さい場合は Yes を、大きい場合は No を出力してください。

辞書順とは？

辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。

以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。

S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。

なお、主要なプログラミング言語の多くでは、文字列の辞書順による比較は標準ライブラリに含まれる関数や演算子として実装されています。詳しくは各言語のリファレンスをご参照ください。

制約

S, T は英小文字からなる長さ 1 以上 10 以下の相異なる文字列である。

入力

入力は以下の形式で標準入力から与えられる。

S T

出力

S が T より辞書順で小さい場合は Yes を、大きい場合は No を出力せよ。

入力例 1

abc atcoder

出力例 1

Yes

abc と atcoder は 1 文字目が同じで 2 文字目が異なります。アルファベットの b は t よりもアルファベット順で先に来るので、 abc の方が atcoder よりも辞書順で小さいことがわかります。

入力例 2

arc agc

出力例 2

No

入力例 3

a aa

出力例 3

Yes

Score : 100 points

Problem Statement

You are given two different strings S and T.
If S is lexicographically smaller than T, print Yes; otherwise, print No.

What is the lexicographical order?

Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.

Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.

Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.

Note that many major programming languages implement lexicographical comparison of strings as operators or functions in standard libraries. For more detail, see your language's reference.

Constraints

S and T are different strings, each of which consists of lowercase English letters and has a length of between 1 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:

S T

Output

If S is lexicographically smaller than T, print Yes; otherwise, print No.

Sample Input 1

abc atcoder

Sample Output 1

Yes

abc and atcoder begin with the same character, but their second characters are different. Since b comes earlier than t in alphabetical order, we can see that abc is lexicographically smaller than atcoder.

Sample Input 2

arc agc

Sample Output 2

No

Sample Input 3

a aa

Sample Output 3

Yes

B - Intersection

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

X=L_1 から X=R_1 までをすべて赤色で塗る。
X=L_2 から X=R_2 までをすべて青色で塗る。

数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。

制約

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

L_1 R_1 L_2 R_2

出力

両方の色で塗られている部分の長さを整数で出力せよ。

入力例 1

0 3 1 5

出力例 1

X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。

よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。

入力例 2

0 1 4 5

出力例 2

両方の色で塗られている部分はありません。

入力例 3

0 3 3 7

出力例 3

赤色と青色で塗られている部分が接している場合でも、両方の色で塗られている部分の長さは 0 となります。

Score : 100 points

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

First, he painted the part from X=L_1 to X=R_1 red.
Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L_1 R_1 L_2 R_2

Output

Print the length of the part of the line painted both red and blue, as an integer.

Sample Input 1

0 3 1 5

Sample Output 1

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

C - Misjudge the Time

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は置き時計を買いました。
この時計は、現在の時刻が 24 時制で \mathrm{AB} 時 \mathrm{CD} 分であるときに図 1 のように時刻を表します。
例えば図 2 では、時計は 7 時 58 分を示しています。

時刻の表示方法をより形式的に説明すると次のようになります。
現在の時刻が 24 時制で h 時 m 分であるとします。ここで 24 時制とは、時間を 0 以上 23 以下の整数で、分を 0 以上 59 以下の整数で表す時刻の表現方法を言います。
h の 10 の位を A, 1 の位を B, m の 10 の位を C, 1 の位を D とします。(ただし h, m が 1 桁である場合は先行ゼロを追加して考えます。)
このとき時計は左上に A を、左下に B を、右上に C を、右下に D を表示します。

高橋君は、次の条件を満たす時刻を 見間違えやすい時刻 と呼ぶことにしました。

時計の表示の右上と左下を入れ替えても、それに対応する 24 時制の時刻が存在する。

例えば図 3 は 20 時 13 分を示していますが、時計の表示の右上と左下を入れ替えると 21 時 3 分を意味する表示になります。よって 20 時 13 分は見間違えやすい時刻です。

今、時計は H 時 M 分を示しています。
(現時点も含めて)以降はじめて訪れる見間違えやすい時刻を 24 時制で答えてください。

制約

0 \leq H \leq 23
0 \leq M \leq 59
H, M は整数

入力

入力は以下の形式で標準入力から与えられる。

H M

出力

答えを h 時 m 分とする。ここで h, m は 0 \leq h \leq 23, 0 \leq m \leq 59 である必要がある。
このとき h, m を以下の形式で出力せよ。

h m

なお、h, m を 2 桁に揃えるために先行ゼロをつけた形式で出力しても正答と見なされる。

入力例 1

1 23

出力例 1

1 23

1 時 23 分は見間違えやすい時刻です。なぜならば、時計の表示の右上と左下を入れ替えると 2 時 13 分を意味する表示になるからです。
よって答えは 1 時 23 分です。
なお、01 23 のように先行ゼロをつけた形式で出力しても正答として扱われます。

入力例 2

19 57

出力例 2

20 0

19 時 57 分以降ではじめて訪れる見間違えやすい時刻は 20 時 0 分です。

入力例 3

20 40

出力例 3

21 0

24 時制では 24 時 0 分という表記は合法でないのに注意してください。

Score : 200 points

Problem Statement

Takahashi bought a table clock.
The clock shows the time as shown in Figure 1 at \mathrm{AB}:\mathrm{CD} in the 24-hour system.
For example, the clock in Figure 2 shows 7:58.

The format of the time is formally described as follows.
Suppose that the current time is m minutes past h in the 24-hour system. Here, the 24-hour system represents the hour by an integer between 0 and 23 (inclusive), and the minute by an integer between 0 and 59 (inclusive).
Let A be the tens digit of h, B be the ones digit of h, C be the tens digit of m, and D be the ones digit of m. (Here, if h has only one digit, we consider that it has a leading zero; the same applies to m.)
Then, the clock shows A in its top-left, B in its bottom-left, C in its top-right, and D in its bottom-right.

Takahashi has decided to call a time a confusing time if it satisfies the following condition:

after swapping the top-right and bottom-left digits on the clock, it still reads a valid time in the 24-hour system.

For example, the clock in Figure 3 shows 20:13. After swapping its top-right and bottom-left digits, it reads 21:03. Thus, 20:13 is a confusing time.

The clock now shows H:M.
Find the next confusing time (including now) in the 24-hour system.

Constraints

0 \leq H \leq 23
0 \leq M \leq 59
H and M are integers.

Input

The input is given from Standard Input in the following format:

H M

Output

Let h:m be the answer, where h and m must satisfy 0 \leq h \leq 23 and 0 \leq m \leq 59.
Print h and m in the following format:

h m

Your answer is considered correct even if h contains a leading zero to represent it as a 2-digit integer; the same applies to m.

Sample Input 1

1 23

Sample Output 1

1 23

1:23 is a confusing time because, after swapping its top-right and bottom-left digits on the clock, it reads 2:13.
Thus, the answer is 1:23.
Your answer is considered correct even if you print 01 23 with a leading zero.

Sample Input 2

19 57

Sample Output 2

20 0

The next confusing time after 19:57 is 20:00.

Sample Input 3

20 40

Sample Output 3

21 0

Note that 24:00 is an invalid notation in the 24-hour system.

D - Distance Between Tokens

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

H 行 W 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。

マス目の状態は H 個の長さ W の文字列 S_1, \dots, S_H で表されます。S_{i, j} = o ならば i 行目 j 列目のマスに駒が置かれていることを、S_{i, j} = - ならばそのマスには駒が置かれていないことを表します。なお、S_{i, j} は文字列 S_i の j 文字目を指します。

一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？

制約

2 \leq H, W \leq 100
H, W は整数
S_i \, (1 \leq i \leq H) は o および - のみからなる長さ W の文字列
S_{i, j} = o となる整数 1 \leq i \leq H, 1 \leq j \leq W の組がちょうど二つ存在する

入力

入力は以下の形式で標準入力から与えられる。

H W
S_1
\vdots
S_H

出力

答えを出力せよ。

入力例 1

2 3
--o
o--

出力例 1

1 行目 3 列目に置かれている駒を下 \rightarrow 左 \rightarrow 左と移動すると 3 回でもう一方の駒と同じマスに移動させることができます。2 回以下で移動させることはできないので、3 を出力します。

入力例 2

5 4
-o--
----
----
----
-o--

出力例 2

Score : 200 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

2 \leq H, W \leq 100
H and W are integers.
S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Input

Input is given from Standard Input in the following format:

H W
S_1
\vdots
S_H

Output

Print the answer.

Sample Input 1

2 3
--o
o--

Sample Output 1

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

5 4
-o--
----
----
----
-o--

Sample Output 2

E - Extra Character

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

文字列 S,T が与えられます。S は英小文字からなり、T は S に英小文字を 1 つ挿入して作られたことがわかっています。

挿入された文字は T の先頭から何番目の文字であるか求めてください。
複数の候補が考えられる場合はいずれか 1 つを求めてください。

制約

1 \leq |S| \leq 5\times 10^5
S は英小文字からなる
T は S に英小文字を 1 つ挿入して作られた文字列である

入力

入力は以下の形式で標準入力から与えられる。

S
T

出力

答えを出力せよ。なお、答えが複数考えられる場合はどれを出力しても正解となる。

入力例 1

atcoder
atcorder

出力例 1

T の先頭から 5 番目の文字 r が挿入された文字です。

入力例 2

million
milllion

出力例 2

T の先頭から 3,4,5 番目の文字のいずれかが挿入された文字です。
よって、3,4,5 のいずれかを出力すると正解となります。

入力例 3

vvwvw
vvvwvw

出力例 3

Score : 300 points

Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

1 \leq |S| \leq 5\times 10^5
S consists of lowercase English letters.
T is obtained by inserting a lowercase English letter into S.

Input

The input is given from Standard Input in the following format:

S
T

Output

Print an integer i, representing that the inserted character is the i-th character from the beginning of T. If there are multiple possible answers, printing any of them is accepted.

Sample Input 1

atcoder
atcorder

Sample Output 1

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

F - Count Connected Components

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
グラフに含まれる連結成分の個数を求めてください。

注釈

単純無向グラフ とは、単純で辺に向きの無いグラフのことをいいます。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが連結であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

制約

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
入力で与えられるグラフは単純
入力される値はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

出力例 1

与えられるグラフに含まれる連結成分は次の 2 個です。

頂点 1, 2, 3 および辺 1, 2 からなる部分グラフ
頂点 4, 5 および辺 3 からなる部分グラフ

入力例 2

5 0

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
The given graph is simple.
All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print the answer.

Sample Input 1

Sample Output 1

The given graph contains the following two connected components:

a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

Sample Input 3

Sample Output 3

G - Pair of Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

2N 個のボールがあります。各ボールには 1 以上 N 以下の整数によって表される色が塗られており、各色で塗られたボールはちょうど 2 個ずつ存在します。

これらのボールが、底が地面と平行になるように置かれた M 本の筒に入れられています。はじめ、i \ (1 \leq i \leq M) 本目の筒には k_i 個のボールが入っており、上から j \ (1 \leq j \leq k_i) 番目のボールの色は a_{i, j} です。

あなたの目標は、以下の操作を繰り返すことで M 本の筒全てを空にすることです。

異なる 2 本の空でない筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。ここで、取り出して捨てた 2 つのボールは同じ色で塗られている必要がある。

目標が達成可能かを判定してください。

制約

1 \leq N \leq 2 \times 10^5
2 \leq M \leq 2 \times 10^5
1 \leq k_i\ (1 \leq i \leq M)
1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
\sum_{i=1}^{M} k_i = 2N
全ての x\ (1 \leq x \leq N) について、1 \leq i \leq M かつ 1 \leq j \leq k_i かつ a_{i,j}=x なる整数の組 (i,j) はちょうど 2 つ存在する
入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}

出力

目標が達成可能なら Yes を、達成不可能なら No を出力せよ。

入力例 1

出力例 1

Yes

以下のように操作を行えばよいです。

1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 1 であり等しいので、この操作は有効である。
1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 2 であり等しいので、この操作は有効である。

入力例 2

出力例 2

No

そもそも一度も操作を行うことができないため、目標を達成する、すなわち M 本の筒全てを空にすることは不可能です。

Score : 400 points

Problem Statement

We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.

These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.

Your objective is to empty all M cylinders by repeating the following operation.

Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.

Determine whether the objective is achievable.

Constraints

1 \leq N \leq 2 \times 10^5
2 \leq M \leq 2 \times 10^5
1 \leq k_i\ (1 \leq i \leq M)
1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
\sum_{i=1}^{M} k_i = 2N
For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}

Output

If the objective is achievable, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The objective can be achieved as follows.

Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.

Sample Input 2

Sample Output 2

No

No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.

H - Distinct Adjacent

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

1 から N の番号がついた N 人の人が輪になってならんでいます。人 1 の右隣には人 2 が、人 2 の右隣には人 3 が、……、人 N の右隣には人 1 がいます。

N 人の人にそれぞれ 0 以上 M 未満の整数を 1 つずつ渡します。
M^N 通りの渡し方のうち、どの隣り合う 2 人が渡された数も異なるものの数を、998244353 で割ったあまりを求めてください。

制約

2 \leq N,M \leq 10^6
N,M は整数である

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

答えを出力せよ。

入力例 1

3 3

出力例 1

人 1,2,3 に渡す整数がそれぞれ (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0) のときの 6 通りです。

入力例 2

4 2

出力例 2

人 1,2,3,4 に渡す整数がそれぞれ (0,1,0,1),(1,0,1,0) のときの 2 通りです。

入力例 3

987654 456789

出力例 3

778634319

998244353 で割ったあまりを求めてください。

Score : 475 points

Problem Statement

There are N people numbered from 1 to N standing in a circle. Person 1 is to the right of person 2, person 2 is to the right of person 3, ..., and person N is to the right of person 1.

We will give each of the N people an integer between 0 and M-1, inclusive.
Among the M^N ways to distribute integers, find the number, modulo 998244353, of such ways that no two adjacent people have the same integer.

Constraints

2 \leq N,M \leq 10^6
N and M are integers.

Input

The input is given from Standard Input in the following format:

N M

Output

Print the answer.

Sample Input 1

3 3

Sample Output 1

There are six desired ways, where the integers given to persons 1,2,3 are (0,1,2),(0,2,1),(1,0,2),(1,2,0),(2,0,1),(2,1,0).

Sample Input 2

4 2

Sample Output 2

There are two desired ways, where the integers given to persons 1,2,3,4 are (0,1,0,1),(1,0,1,0).

Sample Input 3

987654 456789

Sample Output 3

778634319

Be sure to find the number modulo 998244353.

I - Make 10 Again

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

N 個のサイコロがあります。 i = 1, 2, \ldots, N について、i 番目のサイコロを振ると 1 以上 A_i 以下の整数の出目がそれぞれ等確率でランダムにでます。

N 個のサイコロすべてを同時に振るとき、その結果が下記の条件を満たす確率を \text{mod } 998244353 で求めてください。

N 個のサイコロの中からいくつか（ N 個全部でも良い）を選ぶ方法であって、選んだサイコロの出目の和がちょうど 10 であるようなものが存在する。

確率 \text{mod } 998244353 の定義

この問題で求める確率は必ず有理数になることが証明できます。また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。

このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。

制約

1 \leq N \leq 100
1 \leq A_i \leq 10^6
入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

4
1 7 2 9

出力例 1

942786334

例えば、1, 2, 3, 4 個目のサイコロの出目が順に 1, 3, 2, 7 だった場合、この結果は問題文中の条件を満たします。実際、2, 4 番目のサイコロを選択すると、選んだサイコロの出目の和が 3 + 7 = 10 になります。また、1, 3, 4 番目のサイコロを選択しても、選んだサイコロの出目の和が 1 + 2 + 7 = 10 になります。

一方、1, 2, 3, 4 個目のサイコロの出目が順に 1, 6, 1, 5 だった場合、どのようにサイコロを選んでも選んだサイコロの出目の和が 10 にならないため、この結果は問題文中の条件を満たしません。

この入力例では、N 個のサイコロを振った結果が問題文中の条件を満たす確率は \frac{11}{18} です。よって、その \text{mod } 998244353 における値である 942786334 を出力します。

入力例 2

7
1 10 100 1000 10000 100000 1000000

出力例 2

996117877

Score : 500 points

Problem Statement

We have N dice. For each i = 1, 2, \ldots, N, when the i-th die is thrown, it shows a random integer between 1 and A_i, inclusive, with equal probability.

Find the probability, modulo 998244353, that the following condition is satisfied when the N dice are thrown simultaneously.

There is a way to choose some (possibly all) of the N dice so that the sum of their results is 10.

How to find a probability modulo 998244353

It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction \frac{y}{x}, then x is not divisible by 998244353.

Here, there is a unique integer z such that xz \equiv y \pmod{998244353}. Report this z.

Constraints

1 \leq N \leq 100
1 \leq A_i \leq 10^6
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

4
1 7 2 9

Sample Output 1

942786334

For instance, if the first, second, third, and fourth dice show 1, 3, 2, and 7, respectively, these results satisfy the condition. In fact, if the second and fourth dice are chosen, the sum of their results is 3 + 7 = 10. Alternatively, if the first, third, and fourth dice are chosen, the sum of their results is 1 + 2 + 7 = 10.

On the other hand, if the first, second, third, and fourth dice show 1, 6, 1, and 5, respectively, there is no way to choose some of them so that the sum of their results is 10, so the condition is not satisfied.

In this sample input, the probability of the results of the N dice satisfying the condition is \frac{11}{18}. Thus, print this value modulo 998244353, that is, 942786334.

Sample Input 2

7
1 10 100 1000 10000 100000 1000000

Sample Output 2

996117877