問題文

非負整数 N,K,X が与えられます。以下の「問題 A'」の答えが X になるような非負整数列 A=(A_1,A_2,\dots,A_N) としてありうるものの個数を 998244353 で割った余りを求めてください。なお、このような A の個数は有限であることが証明できます。

問題 A'

4096 年の CatCoder では、CatCoder Binary Contest（以下、CBC と略します）を開催することになりました。

いま、問題案を持っている writer が N 人います。i 人目の writer は A_i 個の問題案を持っています。

各 CBC では \text{Div.}0, \text{Div.}1, \dots ,\text{Div.}(K-1) の K 個の部門を同時に 1 つずつ開催します。\text{Div.}i の開催には同じ writer の問題案が 2^i 個必要です。

ここで、別の部門の writer は必ずしも同じである必要がない点に注意してください。 また、各問題案は高々 1 回の CBC の 1 つの部門にしか使用出来ません。

CBC を最大で何回開催出来るかを求めてください。

制約

• 1 \le N \le 256
• 1 \le K \le 256
• 0 \le X \le 256
• 入力される値は全て整数

入力例 1

2 2 1

出力例 1

15

問題 A' の答えが 1 になるような A は A = (0,3),(0,4),(0,5),(1,2),(1,3),(1,4),(2,1),(2,2),(2,3),(3,0),(3,1),(3,2),(4,0),(4,1),(5,0) の 15 個です。

入力例 2

2 3 2

出力例 2

126

例えば A = (10,5) のとき、以下のように問題案を使用することにより CBC を 2 回開催出来ます。

入力例 3

256 255 254

出力例 3

739506516

問題文

4097 年の CatCoder では、CatCoder Knapsack Contest（以下、CKC と略します）を開催することになりました。

各問題案にはそれぞれ難しさと面白さの 2 つのパラメータが 1,2 の 2 段階で割り振られており、難しさが i\ (i = 1,2) で面白さが j\ (j = 1,2) である問題案は A_{i,j} 個あります。

CKC を 1 回開催するためには、難しさの和と面白さの和がそれぞれちょうど X,Y であるような問題案の集合を使用する必要があります。 各問題案は高々 1 回の CKC にしか使用出来ません。

CKC を最大で何回開催出来るかを求めてください。

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

制約

• 1 \le T \le 10^5
• 1 \le X,Y \le 10^9
• 0 \le A_{i,j} \le 10^9
• 入力される値は全て整数

入力例 1

3
5 6
3 3 3 3
1 1
0 1 2 3
3 3
1000000000 1000000000 1000000000 1000000000

出力例 1

2
0
2000000000

1 つ目のテストケースについて、以下のように問題案を使用することにより、CKC を 2 回開催出来ます。

問題文

正整数 N,M と素数 P と (1,2,\dots ,N) の順列 Y=(Y_1,Y_2,\dots ,Y_N) が与えられます。

(1,2,\dots ,N) の順列 X=(X_1,X_2,\dots ,X_N) に対して、f(X) を以下のように定義します。

• 2 以上 N 以下の整数 k について以下の値を B_k としたときの \max(B_2,B_3,\dots ,B_N)
  • 座標が (X_1,Y_1), (X_2,Y_2), \dots ,(X_k,Y_k) であるような 2 次元平面上の k 個の点の集合 S に対するバウンディングボックスの面積を M で割った余り

f(X) が最小となるような X の個数を P で割った余りを求めてください。

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

制約

• 1 \le T \le 100
• 2 \le N \le 3000
• 1 \le M \le 10^7
• 10^4 \le P \le 10^9
• P は素数
• Y は (1,2, \dots ,N) の順列
• 全てのテストケースにおける N の総和は 3000 以下
• 入力される値は全て整数

入力例 1

4
4 6 998244353
2 3 4 1
13 1 10007
1 10 6 5 13 12 8 11 9 2 7 3 4
2 10000000 999999937
1 2
24 101 20250101
13 18 12 8 16 11 2 10 9 4 6 23 22 14 3 17 7 19 1 21 5 15 24 20

出力例 1

12
4938
2
888752

1 つ目のテストケースについて、例えば X=(3,1,4,2) のとき (B_2,B_3,B_4)=(2,0,3) であり f(X)=3 です。f(X) の最小値は 3 であり、f(X)=3 となるような X は 12 個存在します。

2 つ目のテストケースについて、全ての X について f(X)=0 であり、答えは 13! を P=10007 で割った余りとなります。

問題文

素数 P が与えられます。 以下の「問題 C'」の答えが 0 になるような N,M,Y を構成してください。

問題 C'

（C 問題との相違点を赤字で示しています。）

2000 \le N \le 2025, 1 \le M \le 10^7 を満たす 正整数 N,M と (1,2,\dots ,N) の順列 Y=(Y_1,Y_2,\dots ,Y_N) が与えられます。

(1,2,\dots ,N) の順列 X=(X_1,X_2,\dots ,X_N) に対して、f(X) を以下のように定義します。

• 2 以上 N 以下の整数 k について以下の値を B_k としたときの \max(B_2,B_3,\dots ,B_N)
  • 座標が (X_1,Y_1), (X_2,Y_2), \dots ,(X_k,Y_k) であるような 2 次元平面上の k 個の点の集合 S に対するバウンディングボックスの面積を M で割った余り

f(X) が最小となるような X の個数を P で割った余りを求めてください。

制約

• 10^9 \le P \le 10^9+1000
• P は素数

入力例 1

3

出力例 1

4 6
2 3 4 1

この入出力例は入出力形式を示すためのものであり、実際には制約を満たさない無効な入力・出力です。

問題文

AtCoder 社と BatCoder 社が企業対抗戦を行います。 AtCoder 社には 1 から N までの番号がついた N 人の社員がおり、社員 i の強さは A_i、礼儀正しさは P_i です。 BatCoder 社にも 1 から N までの番号がついた N 人の社員がおり、社員 i の強さは B_i です。

企業対抗戦とは、以下の手順で行われるイベントです。

• まず、AtCoder 社が 0 以上 N 以下の整数 k を宣言する。
• その後両社とも、強さが大きいほうから k 人の社員を対戦メンバーとして選ぶ（タイブレークは任意である）。
• この企業対抗戦のスコアは、(AtCoder社の対戦メンバーの強さの総和)-(BatCoder社の対戦メンバーの強さの総和) となる。

ところで、AtCoder 社はこれから Q 回の採用面接を予定しています。 i 回目の面接では、強さ X_i、礼儀正しさ Y_i の候補者が現れます。 この面接の直前における AtCoder 社の社員の礼儀正しさの最小値を z とします。 もし Y_i < z ならば、この候補者を採用せずに面接を終わります。 もし z < Y_i ならば、この候補者を採用し、礼儀正しさ z の社員を解雇します。 なおこの問題では、登場するすべての人物の礼儀正しさが異なる値であるような入力のみが与えられます。

各 t=0,1,\ldots,Q について、ちょうど t 回の面接が終了したタイミングで企業対抗戦が行われます。 各 t について、企業対抗戦のスコアとしてあり得る最大値を求めてください。

なおこの問題では、X_i,Y_i の値は t=i-1 での答えを求めるまでわかりません。 詳しくは入力セクションを確認してください。

制約

• 1 \leq N \leq 250000
• 1 \leq Q \leq 250000
• 0 \leq A_i,B_i,P_i,X_i,Y_i < 2^{30}
• P_1,\ldots,P_N,Y_1,\ldots,Y_Q の値はすべて異なる
• 入力はすべて整数

入力例 1

3 1
3 0
1 1
4 2
3 0 3
3 1

出力例 1

2
1

• t=0: AtCoder 社が k=3 を宣言するのが最適である。 AtCoder 社の対戦メンバーの強さの総和は 4+3+1=8、BatCoder 社の対戦メンバーの強さの総和は 3+3+0=6 となり、スコアは 8-6=2 になる。
• 1 回目の面接: (X_i,Y_i)=(1,3) である。AtCoder 社は、強さ 3、礼儀正しさ 0 の社員を解雇し、強さ 1、礼儀正しさ 3 の社員を採用する。
• t=1: AtCoder 社が k=1 を宣言するのが最適である。 AtCoder 社の対戦メンバーの強さの総和は 4、BatCoder 社の対戦メンバーの強さの総和は 3 となり、スコアは 4-3=1 になる。

入力例 2

6 5
12 4
11 15
0 6
4 0
8 5
4 8
2 8 8 13 7 6
9 1
5 8
0 9
15 12
4 2

出力例 2

2
6
2
0
5
5

入力例 3

10 13
92788721 542214255
293089679 516436321
669808382 626939225
238515753 666162008
242072611 97945595
466154699 275263259
1060112845 48898052
226548347 163247932
916132312 319810611
305065449 33194413
675278910 810708817 766536096 776055247 74986938 522734573 95413623 815637961 455070319 641005226
559678870 63240180
190319444 640573455
820546404 426868109
801203381 602683328
1028200997 844428795
592163827 328798860
890167861 914517637
1020849514 15202582
759333575 276170982
277756469 655405268
172240995 894346766
1012534420 985317173
392457922 844853509

出力例 3

349898379
471883737
187826139
415877835
572657577
572657577
572657577
335086730
209706130
195009665
195009665
107677877
273259909
273259909

問題文

整数 N,A,B,C が与えられます。 (1,2,\ldots,N) の順列 p=(p_1,p_2,\ldots,p_N) のスコアを、以下のように定義します。

• \min(p_1,p_2,\ldots,p_i)=p_i を満たす i をすべて並べた列を (i_1,i_2,\ldots,i_k) とする。 このとき、p のスコアを \prod_{1 \leq j \leq k} (A \times i_j+B \times p_{i_j} + C) とする。

(1,2,\ldots,N) の順列 p すべてに対するスコアの総和を 998244353 で割ったあまりを求めてください。

制約

• 1 \leq N \leq 250000
• 0 \leq A,B,C < 998244353
• 入力はすべて整数

入力例 1

2 1 1 1

出力例 1

19

すべての順列 p とそれに対するスコアは以下のとおりです。

• p=(1,2): 条件を満たす i は (1) であり、スコアは (A \times 1 + B \times p_1 + C)=3 となる。
• p=(2,1): 条件を満たす i は (1,2) であり、スコアは (A \times 1 + B \times p_1 + C) \times (A \times 2 + B \times p_2 + C)=4 \times 4 = 16 となる。

よって、すべての順列に対するスコアの総和は 19 になります。

入力例 2

3 0 0 1

出力例 2

6

入力例 3

8 4 2 1

出力例 3

917435224

入力例 4

100000 200000 300000 400000

出力例 4

247303361