問題文

選手 1, 2, \dots, N の N 人の選手が参加する大会が行われます。

会場には列 0, 1, \dots, N-1 の N 個の列が用意されており、列 i\ (0 \le i \le N - 1) に並んでいる選手はその時点で i 連勝中であることを表します。

大会開始時点では、選手は列 0 の先頭から順に選手 1, 2, \dots, N の順で並んでいます。

大会では、次の手順に従って各選手の順位を決めます。

1. どの列にもちょうど 1 人の選手が並んでいるとき、列 i に並んでいる選手の順位は N-i 位である。このとき手順を終了する。
2. 2 人以上の選手が並んでいる列の中で最も番号の小さい列を列 l とする。
3. 列 l の先頭 2 人は列から抜け、その 2 人で試合を行う。試合に勝った方は列 l+1 の後ろに並び、負けた方は列 0 の後ろに並ぶ。
4. 手順 1. に戻る。

この大会で行われる試合の回数を 998244353 で割ったあまりを求めてください。

ただし、試合に引き分けはないものとします。また、各試合の結果に依らず答えは一意に定まることが証明できます。

制約

• N は整数
• 1 \le N \le 10^5

入力例 1

3

出力例 1

4

番号の小さい選手が試合に勝つものとすると、以下のように大会が進行します。

試合は 4 回行われるので、4 を出力します。

入力例 2

5

出力例 2

26

入力例 3

100000

出力例 3

538161387

問題文

大きさ N の非負整数の集合 S = \{S_1, S_2, \dots, S_N\} が与えられます。

変数 x があり、はじめ x = S_1 です。あなたは以下の操作を何度でも行うことができます。

• y \in S を 1 つ選ぶ。y が以下の条件を満たすとき、x に y を代入する。
  • 条件 : x と y をそれぞれ三進数表記したときの 3^j の位の数字を X_j と Y_j とする。このとき、X_j \gt Y_j なる j の個数は 1 個以下である。

この操作を何回か行って x = S_N にできるかどうか判定してください。

制約

• 2 \le N \le 2 \times 10^5
• 0 \le S_i \lt 3^{12}
• i \ne j ならば S_i \ne S_j
• 入力はすべて整数

入力例 1

2
21 14

出力例 1

Yes

以下のようにして x = 21 の状態から x = 14 にすることができます。

• はじめ、x = 21 である。y = 14 を選んで操作を行う。
  • x と y をそれぞれ三進数表記すると、(X_2, X_1, X_0) = (2, 1, 0),\ (Y_2, Y_1, Y_0) = (1, 1, 2) である。
  • X_j \gt Y_j なる j は j = 2 の 1 個であるから、x に 14 を代入する。

入力例 2

2
12 1

出力例 2

No

x = 12 と y = 1 をそれぞれ三進数表記すると、(X_2, X_1, X_0) = (1, 1, 0),\ (Y_2, Y_1, Y_0) = (0, 0, 1) です。

X_j \gt Y_j なる j は j = 1, 2 の 2 個であるので、x = 12 の状態から 1 を代入することはできません。

入力例 3

5
5 15 45 135 405

出力例 3

Yes

問題文

整数 N が与えられます。次の 2 条件をともに満たす正整数の組 (a, b) の個数を求めてください。

• 1 \leq a, b \leq N
• ある正整数の組 (x, y) が存在して、 x + y^2 = a と x^2 + y = b がともに成り立つ

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 1 \leq T \leq 10^5
• 1 \leq N \leq 10^{18}
• 入力はすべて整数

入力例 1

3
6
1
101

出力例 1

4
0
83

1 番目のテストケースでは、条件を満たす (a, b) の組は (a, b) = (2, 2), (3, 5), (5, 3), (6, 6) の 4 つです。
例えば、 (a, b) = (3, 5) に対しては、 (x, y) = (2, 1) とすれば x + y^2 = 3 = a 、 x^2 + y = 5 = b が成り立ち、条件が満たされます。

2 番目のテストケースでは、条件を満たす (a, b) の組は存在しません。

問題文

3 次元空間上の相異なる座標に N 個の星が輝いています。 i 番目の星は点 P_i(x_i,y_i,z_i) に存在します。また、半径 R の球状の宇宙船が原点を中心に浮かんでいます。

空間上の点 p が 素敵な点 であるとは、i = 1, 2, \dots, N に対して次の条件が同時に成り立つことを言います。

• 点 p から i 番目の星が観測できる。すなわち、 p と P_i を端点とする線分が宇宙船の周及び内部を通らない。

素敵な点が存在する領域の連結成分の個数を求めてください。すなわち、素敵な点全体の集合を L としたとき、L を以下の同値関係 \sim で割ったときの商集合の大きさを求めてください。

• p_1, p_2 \in L に対し、p_1 と p_2 を端点とする L 上の曲線が存在するとき、かつそのときに限り p_1 \sim p_2 である。

なお、この値は 10^{18} 以下の整数になることが証明できます。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力はすべて整数
• 1\le T\le 10
• 1 \le N \le 500
• 1 \le R \lt \sqrt{x_i^2+y_i^2+z_i^2} \le 10^3 \ (1\le i\le N)
• (x_i,y_i,z_i) \neq (x_j,y_j,z_j)\ (1 \le i < j \le N)
• 以下の操作によって答えは変わらない
  • i=1,2,\dots ,N について、原点を通る直線 l_i と実数 \theta _i\ (|\theta _i|\le 10^{-6}) をそれぞれ独立に選ぶ。星 i の位置を l_i を軸に角度 \theta _i だけ回転させた位置に移動させる。

入力例 1

3
4 12
13 0 0
0 15 0
0 -15 0
0 0 15
6 100
0 0 101
0 0 -101
0 101 0
0 -101 0
101 0 0
-101 0 0
20 333
328 -160 -572
-165 417 -847
-319 -45 271
359 -467 -625
-355 -451 658
-280 -424 687
-65 -224 573
475 -371 373
-246 -54 -903
595 -196 -305
622 -570 -250
386 -541 -566
647 455 -424
734 117 -405
830 -10 -393
-334 137 154
74 459 -92
-651 -93 -131
879 148 45
-48 126 -660

出力例 1

1
0
3

1 つめのテストケースでは、素敵な点が存在します。

• 例えば (0,0,100) は素敵な点です。この点と与えられた 4 点のうちどの点と結んだ線分も、宇宙船の内部を通りません。

• 他にも (21,0,0) は素敵な点です。

• これらの 2 点は同じ連結成分に属しています。

2 つめのテストケースでは、素敵な点が存在しません。

問題文

正整数 R に対し、以下の無限無向グラフの連結成分数を f(R) と定義します。

• 頂点集合は \mathbb Z^2 である。すなわち、任意の 2 つの整数 x, y に対し、頂点 (x, y) が存在する。
• 頂点 (x_1, y_1) と頂点 (x_2, y_2) の間には、|x_1 - x_2|^2 + |y_1 - y_2|^2 = R であるとき、かつそのときに限り辺が存在する。

正整数 R が与えられるので、f(R) を出力してください。ただし、f(R) が有限でないときは、inf を出力してください。

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

• 1 \le T \le 100
• 1 \le R \le 10^9
• 入力はすべて整数

部分点

• 追加の制約 R \le 10^3 を満たすデータセットに正解した場合は 25 点が与えられる。

入力例 1

3
1
2
3

出力例 1

1
2
inf

1 個目のテストケースでは、R=1 です。以下のように辺が張られるので、連結成分の個数は 1 個です。

2 個目のテストケースでは、R=2 です。以下のように辺が張られるので、連結成分の個数は 2 個です。

3 個目のテストケースでは、R=3 です。このグラフには辺がなく、連結成分の個数は有限ではありません。

問題文

正の整数 N についての関数 F(N) が次の BNF 表記 の <expr> シンボルに従う文字列 F として与えられます。

<expr> ::= <term> | <expr> "+" <term>
<term> ::= <factor> | <term> "*" <factor>
<factor> ::= "N" | "N^" <number> | "log(" <expr> ")" | "log(" <expr> ")^" <number> | "(" <expr> ")"
<number> ::= <non_zero_digit> | <non_zero_digit> <digit_string>
<digit_string> ::= <digit> | <digit> <digit_string>
<non_zero_digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<digit> ::= "0" | <non_zero_digit>

記号はそれぞれ以下の意味を表します。

• N : N
• + : 足し算 +
• * : 掛け算 \times
• log : 自然対数 \log
• (, ) : 括弧、ただし足し算 + や掛け算 * よりも先に計算される
• ^ : 累乗、ただし足し算 + や掛け算 * よりも先に計算される

<number> は十進表記の整数を表し、 1 以上 10^9 以下であることが保証されます。また、 "log(" <expr> ")^" <number> は (\log( \text{<expr>} ))^{ \text{<number>} } を表すものとします。

例えば、以下の文字列は <expr> シンボルになり得ます。

• N+log(N)*N
  • N + \log(N) \times N を表します。
• N^1+N^2+log(N)+log(N)^1000000000
  • N^1 + N^2 + \log(N) + (\log(N))^{1000000000} を表します。
• N*(N+(log(N+N)^2*N))+(((N)))
  • N \times (N + (\log(N+N))^2 \times N) +(((N))) を表します。
• (log((N)))
  • (\log((N))) を表します。

また、以下の文字列は <expr> シンボルになり得ません。

• (log(N)+N)^2
  • <factor> において、 "(" <expr> ")^" <number> は使われません。
• (log(N))^2
• (N
• )N(
• N^1000000001
• N^02
• N^0
• N^N
• 2
• log(3)
• N-log(N)
• log(N)/N

正の整数 N によっては F(N) が定義されるとは限りませんが、どのような入力でも、ある正の整数 N_0 が存在して、 N \geq N_0 を満たす全ての正の整数 N で F(N) が定義されることが証明できます。

そこで、極限

\[ \lim_{N \to \infty} \frac{F(N)}{N^a(\log N)^b} \]

が有限の値（ 0 を含む）に収束するような非負整数の組 (a, b) 全体の集合を S とします。 S の辞書順最小の組を出力してください。

ただし、非負整数の組 (a, b) が S の辞書順最小の組であるとは、 (a, b) が S に属し、さらに S に属する任意の組 (a', b') について次のいずれかが成り立つこととします。

• a < a'
• a = a' かつ b \le b'

ここで、 S は空集合でなく、さらに S の辞書順最小の組が存在することが証明されます。

制約

• 関数 F(N) は問題文に示した BNF 記法の <expr> シンボルに従う文字列 F として与えられる
• 1 \leq |F| \leq 10^5

部分点

• 追加の制約「F は部分文字列として log を含まない」を満たすデータセットに正解した場合は 30 点が与えられる。

入力例 1

N*log(N^2)*log(N)+N+log(N^1+N)^2*N

出力例 1

1 2

F(N) = N \times \log(N^2) \times \log(N) + N + (\log(N^1+N))^2 \times N です。

このとき、問題文に示した極限が有限の値に収束するような非負整数の組 (a, b) は (a, b) = (1, 2), (1, 3), (2, 0) などがあります。これらに対して、極限は以下のようになります。

\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^2} = 3 \]

\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^3} = 0 \]

\[ \lim_{N \to \infty} \frac{F(N)}{N^2 (\log N)^0} = 0 \]

0 も有限の値とすることにご注意ください。一方、例えば (a, b) = (1, 1) に対しては

\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^1} = \infty \]

となり、有限の値に収束しません。

条件を満たす組全体の集合 S の中で (a, b) = (1, 2) が辞書順最小であることが示せます。このケースは部分点の制約を満たしていません。

入力例 2

N*log(log(N))

出力例 2

1 1

F(N) = N \times \log( \log(N)) です。 (a, b) = (1, 1) に対して

\[ \lim_{N \to \infty} \frac{F(N)}{N^1 (\log N)^1} = 0 \]

であり、有限の値に収束します。

条件を満たす組全体の集合 S の中で (a, b) = (1, 1) が辞書順最小であることが示せます。このケースは部分点の制約を満たしていません。

入力例 3

(((N))*N^234567890+N^2)

出力例 3

234567891 0

F(N) = \left(((N))\times N^{234567890}+N^2\right) です。このケースは部分点の制約を満たしています。

問題文

Alice は (1,2,\dots,N) の順列 P=(P_{1},P_{2},\dots,P_{N}) がお気に入りです。P を当てたら Alice からコーラがもらえることを知った Bob は、Alice に質問をして P を当てることにしました。

Bob は以下の質問を M 回まで行うことができます。

• (1,2,\dots,N) の順列 Q=(Q_{1},Q_{2},\dots,Q_{N}) をひとつ決め、Alice にお気に入りの順列が Q であるかを聞く。

ここで M \leq N が成り立ちます。

Alice は Bob の質問に対して以下の行動を行います。

• P = Q であるなら、Alice は Bob にコーラをあげる。
• P \neq Q であるなら、Alice は P_{i}\neq Q_{i} となる最小の i を Bob に教える。

例えば、P=(4,3,2,1) であるときに Q=(4,3,1,2) として質問すると、Alice は Bob に「P_{i}\neq Q_{i} となる i が存在して、その i のうち最も小さいものは 3 である」ことを教えます。

M 回目の質問の後に P を特定したとしてもコーラはもらえないことに注意してください。

はじめ、Bob は P についての情報を持っていません。Bob が Alice からコーラをもらえる確率を最大化したときのその確率を \text{mod} \;998244353 で求めてください。

制約

• 1 \leq M \leq N \leq 10^{7}
• 入力は全て整数

部分点

• 追加の制約 M \leq 10^{5} を満たすデータセットに正解した場合は 70 点が与えられる。

入力例 1

2 1

出力例 1

499122177

質問 1 回に対し P として考えられる順列は 2 種類あるので、\frac{1}{2} の確率でコーラがもらえます。

1 回目の質問で外しても P を特定できますが、コーラはもらえないことに注意してください。

入力例 2

1 1

出力例 2

1

1 回目の質問で必ずコーラがもらえます。

入力例 3

167 91

出力例 3

469117530

問題文

N 個の文字列 S_1, S_2, \dots, S_N が与えられます。空でない文字列 T であって、以下の条件を満たすものの個数を求めてください。

• 文字列 S_1, S_2, \dots, S_N のうち、T を (連続する) 部分文字列として含むものはちょうど 1 個である。

制約

• 1 \le N \le 10^5
• 1 \le |S_i| \le 10^6\ (1 \le i \le N)
• \left(\sum_{i=1}^{N} |S_i|\right) \le 10^6
• S_i\ (1 \le i \le N) は英小文字からなる文字列

入力例 1

2
abc
ca

出力例 1

5

T = {}a の場合を考えると、S_1 = {}abc と S_2 = {}ca の 2 個が a を部分文字列として含むので、条件を満たしません。

T = {}ab の場合を考えると、S_1 = {}abc のみが ab を部分文字列として含むので、条件を満たします。

T = {}d の場合を考えると、S_1 = {}abc も S_2 = {}ca も d を部分文字列として含まないので、条件を満たしません。

条件を満たす文字列は T = {}b, ab, bc, ca, abc の 5 個です。

入力例 2

2
aab
aab

出力例 2

0

T = {}ab の場合を考えると、S_1 = {}aab と S_2 = {}aab の 2 個が ab を部分文字列として含むので、条件を満たしません。

条件を満たす文字列はありません。

入力例 3

1
aba

出力例 3

5

条件を満たす文字列は T = {}a, b, ab, ba, aba の 5 個です。

入力例 4

3
tokyoinstituteoftechnology
tokyomedicalanddentaluniversity
instituteofsciencetokyo

出力例 4

905

問題文

H 行 W 列のマス目を図に示すような 4 マス分を占める T 字のタイルで敷き詰める方法の個数を 998244353 で割ったあまりを求めてください。

ただし、タイルをマス目に敷き詰めるとき、次の条件を満たす必要があります。

• タイルはマス目に沿って置かれなければならない
• タイルはマス目からはみ出してはならない
• 異なるタイルが同じマスを覆ってはならない
• どのタイルにも覆われていないマスが存在してはならない

また、タイルは回転させて使っても良いですが、裏表の区別はなく、タイル同士の区別もありません。 さらに、回転や反転によってはじめて一致するようなタイルの敷き詰め方は区別します。

制約

• 入力はすべて整数
• 1\le H\le 30
• 1\le W\le 10^{18}

入力例 1

4 4

出力例 1

2

タイルの敷き詰め方は次の 2 通りがあります。

入力例 2

2 8

出力例 2

0

タイルを敷き詰める方法が存在しない場合もあります。

入力例 3

12 3456

出力例 3

491051233

998244353 で割ったあまりを出力してください。

問題文

2 以上の整数 N と、 2 以上 \frac{N(N+1)}{2} 以下の整数 M が与えられます。非負整数からなる集合 A であって、以下の条件をすべて満たすものが存在するので、それを 1 つ構築してください。

• 0 \in A
• 2^N - 1 \in A
• 集合 A の要素はすべて 0 以上 2^N - 1 以下の非負整数である（16:08 修正）
• x, y \in A ならば x ~ \mathrm{AND} ~ y \in A
• x, y \in A ならば x ~ \mathrm{OR} ~ y \in A
• A の要素数 |A| は M に等しい

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 1 \leq T \leq 30
• 2 \leq N \leq 60
• 2 \leq M \leq \frac{N(N+1)}{2}
• 入力はすべて整数

部分点

• 追加の制約 N \leq 5 を満たすデータセットに正解した場合は 25 点が与えられる。

入力例 1

3
3 5
4 8
60 2

出力例 1

0 1 3 5 7
0 1 3 7 8 9 11 15
0 1152921504606846975

1 番目のテストケースにおいて、 A = \{0, 1, 3, 5, 7\} とすると、問題文の条件をすべて満たします。例えば、3 ~ \mathrm{AND} ~ 5 = 1 \in A 、 3 ~ \mathrm{OR} ~ 5 = 7 \in A となります。

条件を満たす A なら何でもよく、以下の出力も認められます。出力する要素が昇順でなくても構いません。

7 1 4 0 5

以下の出力は認められません。 0 \not \in A であるためです。

1 2 3 5 7

以下の出力は認められません。 3, 5 \in A である一方、 3 ~ \mathrm{AND} ~ 5 = 1 \not \in A であるためです。

0 3 4 5 7

また、以下の出力も認められません。集合は多重集合ではないことに注意してください。

7 7 7 0 0

3 番目のテストケースにおいて、出力が 32bit 整数型に収まらない場合があることに注意してください。また、入出力例は部分点の制約を満たさないことに注意してください。

問題文

整数 K が与えられます。以下の条件を満たすできるだけ辺の少ない無向グラフを 1 つ構築してください。

• 頂点の数 N は 1 以上 100 以下
• 辺の数 M は 10^5 以下
• 辺はすべて区別できるものとしたとき、グラフの全域木がちょうど K 個存在する。すなわち、M 本の辺からいくつかの辺を選ぶ方法 2^M 通りのうち、それら以外の辺を削除するとグラフが木になるようなものがちょうど K 通り存在する。

制約

• K は整数
• 1 \le K \le 10^9

得点

プログラムがすべてのテストケースで問題文の条件を満たす出力を行ったとき、その提出は AC となる。このとき、すべてのテストケースにおける M の最大値を M_{\max} として以下の点数が与えられる。

入力例 1

11

出力例 1

3 6
1 2
1 3
1 3
2 3
2 3
2 3

出力のグラフは以下の図で表されます。

例えば、以下の 2 辺を選ぶとこのグラフの全域木になります。

• 辺 1 - 2 と辺 1 - 3 からなる全域木が 2 通り
• 辺 1 - 2 と辺 2 - 3 からなる全域木が 3 通り
• 辺 1 - 3 と辺 2 - 3 からなる全域木が 6 通り

あるので、全部で 11 個の全域木が存在します。

また、以下のようなグラフにも全域木が 11 個存在するため、次の出力も正解とみなされます。

2 11
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2

入力例 2

54

出力例 2

4 10
1 2
2 3
2 3
2 3
3 4
3 4
3 4
4 1
4 1
4 1

制約

• 1 \le N \le 10^6
• 1 \le |S_i| \le 10^3\ (1 \le i \le 4)
• N は整数
• S_i は英大文字のみからなる文字列

部分点

• 追加の制約 |S_i| \leq 50\ (1 \le i \le 4) を満たすデータセットに正解した場合は 15 点が与えられる。

入力例 1

3
TTPC
TLE
P
AC

出力例 1

34

1 回目に略称が TTPC となるのは 10 年後、 2 回目に略称が TTPC となるのは 22 年後、 3 回目に略称が TTPC となるのは 34 年後なので、答えは 34 です。

入力例 2

670055
TF
OITFKONTO
GFPPNPWTZP
CCZFB

出力例 2

-1

略称が TTPC となることはありません。

入力例 3

910359
TOKYO
TECH
PROGRAMMING
CONTEST

出力例 3

1401951321

問題文

2N 個の正整数 (p_1,q_1,p_2,q_2,\dots ,p_N,q_N) が与えられます。

1\le l\le r\le N を満たす整数の組 (l,r) であって、次の条件を満たすものの個数を求めてください。

• \displaystyle\sum_{i=l}^{r}\dfrac{p_i}{q_i} は整数である。

制約

• 入力はすべて整数
• 1\le N\le 2\times 10^5
• 1\le p_i\le q_i\le 10^5\ (1\le i\le N)

部分点

• 追加の制約 q_i \le 30\ (1\le i\le N) を満たすデータセットに正解した場合は 20 点が与えられる。

入力例 1

4
1 6
1 3
1 2
1 2

出力例 1

2

条件を満たす (l,r) は (1,3),(3,4) の 2 つです。実際、

• \displaystyle\sum_{i=1}^{3}\dfrac{p_i}{q_i}=\dfrac{1}{6}+\dfrac{1}{3}+\dfrac{1}{2}=1
• \displaystyle\sum_{i=3}^{4}\dfrac{p_i}{q_i}=\dfrac{1}{2}+\dfrac{1}{2}=1

となっています。このケースは部分点の制約を満たしています。

入力例 2

5
1 1
2 2
3 3
4 4
5 5

出力例 2

15

1\le l\le r\le 5 を満たすすべての整数の組 (l,r) が条件を満たします。このケースも部分点の制約を満たしています。

入力例 3

2
1 99999
99999 100000

出力例 3

0

\displaystyle\sum_{i=1}^{2}\dfrac{p_i}{q_i}=\dfrac{1}{99999}+\dfrac{99999}{100000}=\dfrac{9999900001}{9999900000}=1.00000000010000100001... は整数ではありません。

このケースは部分点の制約を満たしていません。

問題文

正整数 N と素数 M が与えられます。

(, ?, ) からなる文字列で以下の条件を満たすものを 良い文字列 と定義します。

• 文字列に含まれる ? をそれぞれ ( あるいは ) に置き換えることで バランスの取れた括弧列 にすることができる。

長さ 2N の良い文字列の個数を M で割ったあまりを求めてください。

ただし、バランスの取れた括弧列 とは以下のいずれかの条件を満たす文字列のことです。

• 空文字列
• あるバランスの取れた括弧列 A が存在して、(, A, ) をこの順に連結した文字列
• ある空でないバランスの取れた括弧列 A,B が存在して、A,B をこの順に連結した文字列

制約

• 1\leq N\leq 9\times 10^{8}
• 9\times 10^{8}\leq M\leq 10^{9}
• M は素数
• 入力は全て整数

部分点

• 追加の制約 N\leq 5\times 10^{6} を満たすデータセットに正解した場合は 70 点が与えられる。

入力例 1

1 998244353

出力例 1

4

長さが 2N=2 の良い文字列は (), (?, ?), ?? の 4 つです。

入力例 2

2 900000011

出力例 2

28

入力例 3

999937 999999937

出力例 3

170733195

入力例 4

167167924 924924167

出力例 4

596516682

入力例 4 のケースは部分点には含まれません。

問題文

2 次元平面上に開きカッコと閉じカッコがそれぞれ N 個ずつあります。 i 番目の開きカッコの座標は (x_{1, i}, y_{1, i}) 、 i 番目の閉じカッコの座標は (x_{2, i}, y_{2, i}) です。

x_{1, i} < x_{2, j} かつ y_{1, i} < y_{2, j} であるときに限り、 i 番目の開きカッコと j 番目の閉じカッコを平面上から削除し、代わりに 4 点 (x_{1, i}, y_{1, i}), (x_{1, i}, y_{2, j}), (x_{2, j}, y_{2, j}), (x_{2, j}, y_{1, i}) を頂点とする長方形を平面に配置することができます。

任意の異なる 2 つの長方形の共通部分が、面積が 0 となるか、または一方の長方形に一致するように N 個の長方形を平面に配置することができるかを判定し、できるならばそのような配置の方法を 1 つ求めてください。

制約

• 1 \leq N \leq 2 \times 10^5
• -10^9 \leq x_{p, i}, y_{p, i} \leq 10^9
• (p, i) \neq (q, j) ならば (x_{p, i}, y_{p, i}) \neq (x_{q, j}, y_{q, j})
• 入力は全て整数

入力例 1

3
0 0
2 -2
1 1
2 2
3 1
2 3

出力例 1

Yes
3
2
1

下図のように長方形を配置すると、条件を満たします。

ただし、図において、丸は開きカッコ、バツ印は閉じカッコを表します。

入力例 2

2
1 0
0 1
2 3
3 2

出力例 2

No

図のように、どのように長方形を配置しても、条件を満たすことができません。

入力例 3

1
1 1
0 0

出力例 3

No

残念ながら、そもそも長方形を配置することができません。

問題文

N 頂点の無向グラフがあります。このグラフの頂点には 1 から N までの番号がつけられており、頂点 i\ (1 \le i \le N) には整数 A_i が書かれています。このグラフには辺がありませんが、あなたが自由に辺を張ることができます。

このグラフが単純グラフとなるような辺の張り方は 2^{\frac{N(N-1)}{2}} 通り存在しますが、そのすべてについて以下の スコア を計算し、その総和を 998244353 で割った余りを求めてください。

• グラフが連結でないとき、その スコア は 0 である。
• グラフが連結なとき、グラフから橋である辺を取り除いたグラフを G とする。G の各連結成分について頂点に書かれた整数の和を考え、その総積を スコア とする。

制約

• 1 \le N \le 400
• 0 \le A_i \lt 998244353\ (1 \le i \le N)
• 入力はすべて整数

入力例 1

3
8 5 9

出力例 1

1102

3 頂点の単純連結無向グラフは、次の 4 通りです。

スコアは左からそれぞれ 360, 360, 360, 22 なので、答えは 1102 です。

入力例 2

5
4 2 1 3 10

出力例 2

63860

入力例 3

7
229520041 118275986 281963154 784360383 478705114 655222915 970715006

出力例 3

35376232

答えを 998244353 で割った余りを出力してください。