Problem Statement

Given are three positive integers A, B, and C. Compute the following value modulo 998244353:

\sum_{a=1}^{A} \sum_{b=1}^{B} \sum_{c=1}^{C} abc

Constraints

• 1 \leq A, B, C \leq 10^9

Sample Input 1

1 2 3

Sample Output 1

18

We have: (1 \times 1 \times 1) + (1 \times 1 \times 2) + (1 \times 1 \times 3) + (1 \times 2 \times 1) + (1 \times 2 \times 2) + (1 \times 2 \times 3) = 1 + 2 + 3 + 2 + 4 + 6 = 18.

Sample Input 2

1000000000 987654321 123456789

Sample Output 2

951633476

Be sure to compute the value modulo 998244353.

Problem Statement

Given are integers N and K. How many quadruples of integers (a,b,c,d) satisfy both of the following conditions?

• 1 \leq a,b,c,d \leq N
• a+b-c-d=K

Constraints

• 1 \leq N \leq 10^5
• -2(N-1) \leq K \leq 2(N-1)
• All numbers in input are integers.

Sample Input 1

2 1

Sample Output 1

4

Four quadruples below satisfy the conditions:

• (a,b,c,d)=(2,1,1,1)
• (a,b,c,d)=(1,2,1,1)
• (a,b,c,d)=(2,2,2,1)
• (a,b,c,d)=(2,2,1,2)

Sample Input 2

2525 -425

Sample Output 2

10314607400

Problem Statement

Given are an N \times N matrix and an integer K. The entry in the i-th row and j-th column of this matrix is denoted as a_{i, j}. This matrix contains each of 1, 2, \dots, N^2 exactly once.

Sigma can repeat the following two kinds of operation arbitrarily many times in any order.

• Pick two integers x, y (1 \leq x < y \leq N) that satisfy a_{i, x} + a_{i, y} \leq K for all i (1 \leq i \leq N) and swap the x-th and the y-th columns.
• Pick two integers x, y (1 \leq x < y \leq N) that satisfy a_{x, i} + a_{y, i} \leq K for all i (1 \leq i \leq N) and swap the x-th and the y-th rows.

How many matrices can he obtain by these operations? Find it modulo 998244353.

Constraints

• 1 \leq N \leq 50
• 1 \leq K \leq 2 \times N^2
• a_{i, j}'s are a rearrangement of 1, 2, \dots, N^2.
• All values in input are integers.

Sample Input 1

3 13
3 2 7
4 8 9
1 6 5

Sample Output 1

12

For example, Sigma can swap two columns, by setting x = 1, y = 2. After that, the resulting matrix will be:

2 3 7
8 4 9
6 1 5

After that, he can swap two row vectors by setting x = 1, y = 3, resulting in the following matrix:

6 1 5
8 4 9
2 3 7

Sample Input 2

10 165
82 94 21 65 28 22 61 80 81 79
93 35 59 85 96 1 78 72 43 5
12 15 97 49 69 53 18 73 6 58
60 14 23 19 44 99 64 17 29 67
24 39 56 92 88 7 48 75 36 91
74 16 26 10 40 63 45 76 86 3
9 66 42 84 38 51 25 2 33 41
87 54 57 62 47 31 68 11 83 8
46 27 55 70 52 98 20 77 89 34
32 71 30 50 90 4 37 95 13 100

Sample Output 2

348179577

Problem Statement

You are given two positive integers N and K. How many multisets of rational numbers satisfy all of the following conditions?

• The multiset has exactly N elements and the sum of them is equal to K.
• Each element of the multiset is one of 1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \dots. In other words, each element can be represented as \frac{1}{2^i}\ (i = 0,1,\dots).

The answer may be large, so print it modulo 998244353.

Constraints

• 1 \leq K \leq N \leq 3000
• All values in input are integers.

Sample Input 1

4 2

Sample Output 1

2

The following two multisets satisfy all of the given conditions:

• {1, \frac{1}{2}, \frac{1}{4}, \frac{1}{4}}
• {\frac{1}{2}, \frac{1}{2}, \frac{1}{2}, \frac{1}{2}}

Sample Input 2

2525 425

Sample Output 2

687232272

Problem Statement

Consider an N \times N matrix. Let us denote by a_{i, j} the entry in the i-th row and j-th column. For a_{i, j} where i=1 or j=1 holds, its value is one of 0, 1 and 2 and given in the input. The remaining entries are defined as follows:

• a_{i,j} = \mathrm{mex}(a_{i-1,j}, a_{i,j-1}) (2 \leq i, j \leq N) where \mathrm{mex}(x, y) is defined by the following table:

How many entries of the matrix are 0, 1, and 2, respectively?

Constraints

• 1 \leq N \leq 500{,}000
• a_{i,j}'s given in input are one of 0, 1 and 2.

Sample Input 1

4
1 2 0 2
0
0
0

Sample Output 1

7 4 5

The matrix is as follows:

1 2 0 2
0 1 2 0
0 2 0 1
0 1 2 0

Problem Statement

Given is a simple undirected graph with N vertices and M edges. Its vertices are numbered 1, 2, \ldots, N and its edges are numbered 1, 2, \ldots, M. On Vertex i (1 \leq i \leq N) two integers A_i and B_i are written. Edge i (1 \leq i \leq M) connects Vertices U_i and V_i.

Snuke picks zero or more vertices and delete them. Deleting Vertex i costs A_i. When a vertex is deleted, edges that are incident to the vertex are also deleted. The score after deleting vertices is calculated as follows:

• The score is the sum of the scores of all connected components.
• The score of a connected component is the absolute value of the sum of B_i of the vertices in the connected component.

Snuke's profit is (score) - (the sum of costs). Find the maximum possible profit Snuke can gain.

Constraints

• 1 \leq N \leq 300
• 1 \leq M \leq 300
• 1 \leq A_i \leq 10^6
• -10^6 \leq B_i \leq 10^6
• 1 \leq U_i,V_i \leq N
• The given graph does not contain self loops or multiple edges.
• All values in input are integers.

Sample Input 1

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

Sample Output 1

1

Deleting Vertex 2 costs 1. After that, the graph is separated into two connected components. The score of the component consisting of Vertex 1 is |0| = 0. The score of the component consisting of Vertices 3 and 4 is |(-3) + 1| = 2. Therefore, Snuke's profit is 0 + 2 - 1 = 1. He cannot gain more than 1, so the answer is 1.

Sample Input 2

10 12
733454 729489 956011 464983 822120 364691 271012 762026 751760 965431
-817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880
3 1
4 1
6 9
3 8
1 6
10 5
5 6
1 5
4 3
7 1
7 4
10 3

Sample Output 2

2306209

Sample Input 3

4 2
1 1 1 1
1 1 -1 -1
1 2
3 4

Sample Output 3

4

The given graph is not necessarily connected.