Problem Statement

There is a complete graph with four vertices numbered 1, 2, 3, 4.

You will now assign weights to each of the six edges. Each weight should be a positive integer, and the sum of the six weights should be exactly K.
More formally, you choose positive integers x_{i,j} \ (1\leq i<j\leq 4) such that \sum_{1\leq i<j\leq 4}x_{i,j}=K, and assign weight x_{i,j} to the edge connecting i and j.

For this weighted graph G, let f(G) be the minimum sum of edge weights in a cycle that passes through all vertices. Find the sum, modulo 998244353, of f(G) over all possible G.

Constraints

• 6 \le K \le 5000
• All input values are integers.

Sample Input 1

7

Sample Output 1

24

The possible graphs are the ones where one of the six edges has weight 2 and the other edges have weight 1. There are six such graphs G, and we have f(G)=4 for each of them, so the answer is 24.

Sample Input 2

2026

Sample Output 2

513760748

Problem Statement

There is a grid with N rows and N columns. The cell at the i-th row from the top and j-th column from the left is called cell (i,j). You perform the following in order of i=1,2,\ldots,M:

• Operation i : Choose either to place one stone on cell (x_i, y_i) or not. If you place a stone, a cost of c_i is incurred; otherwise, no cost is incurred.

However, you must place a stone in operation 1.

Determine whether the following goal can be achieved, and if it can, find the minimum sum of costs incurred.

• Goal : For every i \ (1 \leq i \leq N), the number of stones placed in the i-th row is equal to the number of stones placed in the i-th column.

Constraints

• 1 \le N, M \le 2 \times 10^5
• 1 \le x_i, y_i \le N
• 1 \le c_i \le 10^9
• (x_i, y_i) are distinct.
• All input values are integers.

Sample Input 1

4 5
2 4 5
4 1 2
2 1 3
3 3 9
1 2 4

Sample Output 1

11

The goal can be achieved by choosing to place a stone in operations 1,2,5.

The sum of costs in this case is 5+2+4=11. The total cost cannot be less than 11 to achieve the goal, so the answer is 11.

Sample Input 2

3 3
1 1 1000000000
2 2 100000000
3 3 10000000

Sample Output 2

1000000000

You must place a stone in operation 1.

Sample Input 3

2 1
1 2 10

Sample Output 3

-1

Problem Statement

There are N white balls. First, you paint each ball red or blue.

Then, you place these N red or blue painted balls in one of M distinguishable boxes.

Let a_i and b_i be the number of red and blue balls in the i-th box, respectively.

Find the sum, modulo 998244353, of \prod_{1\leq i \le M}|a_i-b_i| over all ways to place the balls.

Here, two ways of placing balls are different if and only if at least one of a_i and b_i is different for some i.

Particularly, balls are not distinguished from each other.

Constraints

• 1 \le N,M \le 10^7
• All input values are integers.

Sample Input 1

2 1

Sample Output 1

4

There are three ways to place balls in box 1.
If you place one red ball and one blue ball, |a_1-b_1|=0.
If you place two red balls or two blue balls, |a_1-b_1|=2.
Therefore, the answer is 0 + 2 + 2 = 4.

Sample Input 2

5 7

Sample Output 2

0

Sample Input 3

10000000 5000000

Sample Output 3

965172629

Problem Statement

There are N people numbered 1,2,\ldots,N. For i\neq j, the intimacy between persons i and j is A_{i,j}.

For each of the N people, assign room X or room Y. Each of the N people moves to their assigned room. It is acceptable if there is an empty room.

Person i is in a good state if the following is satisfied:

(Sum of intimacy with person i of all people in the same room as person i) \geq (Sum of intimacy with person i of all people in a different room from person i).

Output one assignment of rooms such that all N people are in a good state.

It can be proved that such an assignment always exists.

Constraints

• 2 \leq N \leq 50
• -50 \leq A_{i,j} \leq 50
• A_{i,j} = A_{j,i}
• A_{i,i}=0
• All input values are integers.

Sample Input 1

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

Sample Output 1

XXYY

Suppose persons 1,2 are assigned to room X and persons 3,4 are assigned to room Y.

For person 1, the sum of intimacy with people in the same room (person 2) is 4, and the sum of intimacy with people in different rooms (persons 3 and 4) is (-2)+(-1)=-3, so they are in a good state.

All other people are also in a good state, so this assignment satisfies the condition.

Outputting YYXX is also correct.

Sample Input 2

3
0 0 0
0 0 0
0 0 0

Sample Output 2

XXX

It is acceptable if there is an empty room.

Problem Statement

There is a permutation P of (1,2,\ldots,N) and an empty array A. Perform the following operation N-1 times on P:

• Choose two adjacent elements. Remove the smaller of the chosen elements from P and concatenate the parts before and after the removed element. Append the removed element to the end of A.

Find the number, modulo 998244353, of possible final sequences A of length N-1.

Constraints

• 2 \le N \le 2\times 10^5
• 1 \le P_i \le N
• P is a permutation of (1,2,\ldots,N).
• All input values are integers.

Sample Input 1

4
1 2 3 4

Sample Output 1

6

All six permutations of (1,2,3) are possible as the final A.

For example, A=(2,1,3) can be obtained as follows:

• Choose 2,3. Remove 2, and now P=(1,3,4), A=(2).
• Choose 1,3. Remove 1, and now P=(3,4), A=(2,1).
• Choose 3,4. Remove 3, and now P=(4), A=(2,1,3).

Sample Input 2

3
3 1 2

Sample Output 2

1

Sample Input 3

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

Sample Output 3

303178128

Problem Statement

You are given integers N,M,X.

Perform the following series of operations to create a sequence A of length N consisting of non-negative integers.

• Freely decide an integer sequence A=(A_1,A_2) of length 2.
• Then, perform the following operation N-2 times on A.
• Let k=|A|. Let x=A_{k-1}, y=A_k. Append either x+y or y-x to the end of A.

A sequence A is a good sequence if and only if it satisfies the following:

• 0 \le A_i \le M \ (1 \le i \le N)
• A_N=X

Find the sum, modulo 998244353, of A_1 \times A_2 over all good sequences that can be obtained by the operations.

Constraints

• 3 \leq N \leq 2 \times 10^5
• 1 \leq X \leq M \leq 2 \times 10^5
• All input values are integers.

Sample Input 1

3 4 3

Sample Output 1

8

Some possible sequences are (0,3,3),(1,4,3),(2,1,3).

The sum of A_1 \times A_2 over all possible sequences is 8.

Sample Input 2

150000 160000 140000

Sample Output 2

791841701