Problem Statement

For D days, each day you choose exactly one of the following four actions:

• Pay 1 yen and buy gum.
• Pay 3 yen and buy candy.
• Pay 4 yen and buy chocolate.
• Pay 6 yen and buy wheat gluten snack.

After D days, you have paid a total of N yen.
How many possible sequences of D days satisfy this condition? Output the answer modulo 998244353.

Two sequences are considered different if there exists at least one day on which the purchased item is different.

Constraints

• 1 \leq D \leq 2 \times 10^5
• 1 \leq N \leq 10^6
• D, N are integers

Sample Input 1

2 7

Sample Output 1

4

There are 4 valid action sequences for 2 days:

• On day 1, pay 1 yen for gum; on day 2, pay 6 yen for wheat gluten snack.
• On day 1, pay 3 yen for candy; on day 2, pay 4 yen for chocolate.
• On day 1, pay 4 yen for chocolate; on day 2, pay 3 yen for candy.
• On day 1, pay 6 yen for wheat gluten snack; on day 2, pay 1 yen for gum.

Sample Input 2

200000 1000000

Sample Output 2

688682037

Problem Statement

You are given an integer N.
Find the number of non-negative integer quadruples (a, b, c, d) that satisfy all of the following conditions, and output the result modulo 998244353:

• a + b + c + d = N
• a is 0 or 1
• b is 0, 1, or 2
• c is even
• d is a multiple of 3

Constraints

• 0 \leq N \leq 10^9
• N is an integer

Sample Input 1

5

Sample Output 1

6

The following 6 quadruples (a,b,c,d) satisfy the conditions:

• (0,0,2,3)
• (0,1,4,0)
• (0,2,0,3)
• (1,0,4,0)
• (1,1,0,3)
• (1,2,2,0)

Sample Input 2

1000000000

Sample Output 2

1755648

Problem Statement

Among integer sequences of length N consisting of non-negative integers not greater than M, find the number of sequences whose total sum is exactly S.
Output the result modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq S \leq 2 \times 10^5
• N, M, S are integers

Sample Input 1

3 2 4

Sample Output 1

6

There are 6 sequences that satisfy the condition:

• (0,2,2)
• (1,1,2)
• (1,2,1)
• (2,0,2)
• (2,1,1)
• (2,2,0)

Sample Input 2

12345 678 90123

Sample Output 2

226012779

Problem Statement

Consider integer sequences A=(a_1,a_2,\dots,a_N) of length N, where each element is a non-negative integer not greater than M.
Count how many such sequences satisfy the following condition, and output the result modulo 998244353.

• Let B=(b_1,b_2,\dots,b_N) be the sequence obtained by sorting A in ascending order.
  For every i such that 1 \leq i \leq N-1, the parity of b_i and b_{i+1} must be different.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• N, M are integers

Sample Input 1

2 3

Sample Output 1

8

There are 8 sequences that satisfy the condition:

• (0,1)
• (0,3)
• (1,0)
• (1,2)
• (2,1)
• (2,3)
• (3,0)
• (3,2)

Sample Input 2

12345 67890

Sample Output 2

761484871

Problem Statement

Consider integer sequences A = (a_1,a_2,\dots,a_N) of length N, where each element is a positive integer not greater than M.
Count how many such sequences satisfy the following condition, and output the result modulo 998244353.

• For every integer m such that 1 \leq m \leq M, the number of times m appears in A is at most m.

Constraints

• 1 \leq N \leq 300
• 1 \leq M \leq 300
• N, M are integers

Sample Input 1

2 3

Sample Output 1

8

There are 8 sequences that satisfy the condition:

• (1, 2)
• (1, 3)
• (2, 1)
• (2, 2)
• (2, 3)
• (3, 1)
• (3, 2)
• (3, 3)

Sample Input 2

300 300

Sample Output 2

478329414

Problem Statement

There are N sheets of paper, numbered from 1 to N.
Each sheet can be painted in one of three colors: red, blue, or yellow.
The coloring must satisfy the following conditions:

• Each sheet must be painted in exactly one color.
• The number of sheets painted blue must be even.
• The number of sheets painted yellow must be odd.

Find the number of valid colorings that satisfy the conditions, and output the result modulo 998244353.

Two colorings are considered different if there exists at least one sheet that is painted in different colors.

Constraints

• 1 \leq N \leq 10^9
• N is an integer

Sample Input 1

3

Sample Output 1

7

There are 7 valid colorings.
Here, (c_1, c_2, c_3) means that sheet 1 is painted in color c_1, sheet 2 in c_2, and sheet 3 in c_3.

• (red, red, yellow)
• (red, yellow, red)
• (yellow, red, red)
• (blue, blue, yellow)
• (blue, yellow, blue)
• (yellow, blue, blue)
• (yellow, yellow, yellow)

Sample Input 2

1000000000

Sample Output 2

224965629

Problem Statement

You have an unlimited number of coins of denominations 1, 2, \dots, M yen.
Coins of the same denomination are indistinguishable.

You are given integers N and L. For each m = 1, 2, \dots, M-L+1, solve the following problem:

• You may use coins of denominations m, m+1, \dots, m+L-1 freely.
  (Formally, you may use coins of denomination x for all x satisfying m \leq x \leq m+L-1.)
  Find the number of ways to pay exactly N yen using these coins, modulo 998244353.

Two payment methods are considered different if there exists at least one denomination for which the number of coins used differs.

Constraints

• 1 \leq L \leq M \leq N \leq 5000
• N, M, L are integers

Sample Input 1

5 3 2

Sample Output 1

3
1

For m=1, using coins of denominations 1 and 2, there are 3 ways to pay exactly 5 yen:

• Pay 5 coins of 1 yen.
• Pay 3 coins of 1 yen and 1 coin of 2 yen.
• Pay 1 coin of 1 yen and 2 coins of 2 yen.

For m=2, using coins of denominations 2 and 3, there is 1 way to pay exactly 5 yen:

• Pay 1 coin of 2 yen and 1 coin of 3 yen.

Sample Input 2

5000 2500 2495

Sample Output 2

878712345
520404421
886134625
125526485
307727973
257205353

Problem Statement

On a 2D coordinate plane, a piece is placed at (0, 0).
You may perform the following operation any number of times (including zero):

• Choose an integer pair (a, b) such that 0 \leq a \leq 1, 0 \leq b, and (a, b) \neq (0, 0).
• If the current position of the piece is (x, y), move it to (x+a, y+b).

Find the number of operation sequences that result in the piece being at (N, M) after all operations, and output the answer modulo 998244353.

Constraints

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

Sample Input 1

2 1

Sample Output 1

5

For each valid operation sequence, the visited coordinates are as follows (5 possibilities):

• (0, 0) \to (0, 1) \to (1, 1) \to (2, 1)
• (0, 0) \to (1, 0) \to (1, 1) \to (2, 1)
• (0, 0) \to (1, 0) \to (2, 0) \to (2, 1)
• (0, 0) \to (1, 0) \to (2, 1)
• (0, 0) \to (1, 1) \to (2, 1)

Sample Input 2

12345 67890

Sample Output 2

824829859

Problem Statement

You are given N distinct integers A_1, A_2, \dots, A_N.
You will choose K of them. The score of a choice is defined as the product of the chosen integers.
There are \binom{N}{K} possible ways to choose K integers.
Find the sum of their scores, and output the result modulo 998244353.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq A_i \leq 10^8
• If i \neq j, then A_i \neq A_j
• All input values are integers

Sample Input 1

3 2
2 3 5

Sample Output 1

31

The possible ways to choose K integers and their scores are:

• Choose A_1 = 2 and A_2 = 3. The score is 2 \times 3 = 6.
• Choose A_1 = 2 and A_3 = 5. The score is 2 \times 5 = 10.
• Choose A_2 = 3 and A_3 = 5. The score is 3 \times 5 = 15.

Sample Input 2

10 5
1 2 3 4 5 6 7 8 9 10

Sample Output 2

902055

Problem Statement

There is a board game with N+1 squares numbered 0, 1, \dots, N.
You also have an M-sided die, where each side shows a distinct positive integer A_1, A_2, \dots, A_M with equal probability.
Additionally, there are traps on squares B_1, B_2, \dots, B_L. Here, 1 \leq B_i \leq N-1, and all B_i are distinct.

You will play the following game:

• Place your piece on square 0 at the beginning. While the game continues, repeat:
  • Roll the die. If your piece is on square x and the die shows y, move the piece to square \min(N, x+y).
• If the piece lands on a trap square, you lose immediately.
• If the piece reaches square N without landing on a trap, you win immediately.

Compute the probability that you win the game, modulo 998244353.

Constraints

• 2 \leq N \leq 2.5 \times 10^5
• 1 \leq M \leq N
• 1 \leq L \leq N-1
• 1 \leq A_1 < A_2 < \dots < A_M \leq N
• 1 \leq B_1 < B_2 < \dots < B_L \leq N-1
• All input values are integers

Sample Input 1

2 2 1
1 2
1

Sample Output 1

499122177

You can only win if the die shows 2. Thus, the probability is \tfrac{1}{2}.

Sample Input 2

250000 10 8
1 2 3 4 5 6 7 8 9 100000
21994 47718 98917 104184 160670 204838 205220 207793

Sample Output 2

718440495

Problem Statement

You are given an integer N.
Consider permutations p = (p_1, p_2, \dots, p_N) of (1, 2, \dots, N).
Count how many such permutations satisfy the following condition, and output the result modulo 998244353.

• For every integer i such that 1 \leq i \leq N-1, it must hold that \max(p_1, p_2, \dots, p_i) \neq i.

Constraints

• 1 \leq N \leq 2.5 \times 10^5
• N is an integer

Sample Input 1

3

Sample Output 1

3

The following 3 permutations p satisfy the condition:

• (2,3,1)
• (3,1,2)
• (3,2,1)

Sample Input 2

123456

Sample Output 2

923416117

Problem Statement

You are given an integer N.
Consider permutations p = (p_1, p_2, \dots, p_N) of (1, 2, \dots, N).
Count how many such permutations satisfy the following condition, and output the result modulo 998244353.

• For every integer i such that 1 \leq i \leq N, it must hold that p_{p_i} \neq i.

Constraints

• 1 \leq N \leq 2.5 \times 10^5
• N is an integer

Sample Input 1

3

Sample Output 1

2

The following 2 permutations p satisfy the condition:

• (2,3,1)
• (3,1,2)

Sample Input 2

123456

Sample Output 2

916370671

Problem Statement

Count the number of simple connected undirected graphs with N vertices labeled 1 through N.
Output the result modulo 998244353.

Constraints

• 1 \leq N \leq 2.5 \times 10^5
• N is an integer

Sample Input 1

3

Sample Output 1

4

For N=3, the simple connected undirected graphs are:

• 3 graphs with 2 edges,
• 1 graph with 3 edges,

for a total of 4.

Sample Input 2

123456

Sample Output 2

317059543

Problem Statement

You have coins of denominations 1, 2, \dots, N yen. For each denomination i, you have A_i coins.
Coins of the same denomination are indistinguishable.

Find the number of ways to pay exactly N yen using these coins, and output the result modulo 998244353.
Two payment methods are considered different if there exists at least one denomination for which the number of coins used differs.

Constraints

• 1 \leq N \leq 2.5 \times 10^5
• 1 \leq A_i \leq N
• All input values are integers

Sample Input 1

3
1 2 3

Sample Output 1

2

There are 2 ways to pay exactly 3 yen:

• Use one 1-yen coin and one 2-yen coin.
• Use one 3-yen coin.

Sample Input 2

10
3 1 4 1 5 9 2 6 5 3

Sample Output 2

20

Problem Statement

Consider rooted trees with N vertices, where the vertices are labeled 1 through N, and vertex 1 is the root.
Count how many such rooted trees satisfy the following condition, and output the result modulo 998244353.

• For every integer i such that 1 \leq i \leq N, the number of children of vertex i is either 0 or a prime number.

Constraints

• 3 \leq N \leq 2.5 \times 10^5
• N is an integer

Sample Input 1

3

Sample Output 1

1

For example, consider the rooted tree where both vertex 2 and vertex 3 have parent 1.
This satisfies the condition because vertex 1 has 2 children (a prime number), and vertices 2 and 3 both have 0 children.
This is the only rooted tree that satisfies the condition.

Sample Input 2

123456

Sample Output 2

607180670

Problem Statement

You are given integers N, M, K.
For each m = 1, 2, \dots, M, solve the following problem:

There are N balls numbered 1 through N, and m+1 boxes numbered 0 through m.
Box 0 can hold at most K balls. The other boxes have no upper limit.
Find the number of ways to place all N balls into the boxes, modulo 998244353.
Two placements are considered different if there exists at least one ball that is placed in different boxes between the two placements.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq N
• All input values are integers

Sample Input 1

3 2 1

Sample Output 1

4
20

Consider the case m=1. There are 4 valid placements of the balls:

• Put balls 1,2,3 into box 1.
• Put ball 1 into box 0, and balls 2,3 into box 1.
• Put ball 2 into box 0, and balls 1,3 into box 1.
• Put ball 3 into box 0, and balls 1,2 into box 1.

Sample Input 2

12345 5 6789

Sample Output 2

583034791
982161077
613932842
770852810
194914198

Problem Statement

There are two dice, called die 1 and die 2.

• Die 1 is an N-sided die, where each side shows a distinct positive integer A_1, A_2, \dots, A_N with equal probability.
• Die 2 is an M-sided die, where each side shows a distinct positive integer B_1, B_2, \dots, B_M with equal probability.

You are also given a positive integer K.
For each k = 1, 2, \dots, K, solve the following problem:

• When rolling die 1 and die 2 simultaneously, compute the expected value of (\text{sum of the outcomes})^k modulo 998244353.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^5
• 1 \leq K \leq 10^5
• 1 \leq A_1 < A_2 < \dots < A_N \leq 10^8
• 1 \leq B_1 < B_2 < \dots < B_M \leq 10^8
• All input values are integers

Sample Input 1

3 2 3
1 2 3
4 5

Sample Output 1

499122183
166374102
499122469

For example, if die 1 shows 3 and die 2 shows 5, then the cube of the sum is (3+5)^3 = 512.

Sample Input 2

8 9 5
26056440 37770730 49119845 54471601 59187620 86450214 95205990 97771081
12521133 14054302 19786177 21524935 39265456 53591023 65158870 86176948 87221915

Sample Output 2

981084750
45312313
562611236
522662310
196292405

Problem Statement

There is a simple undirected graph with 2^N+1 vertices and 2^N edges, where the vertices are numbered 1, 2, \dots, 2^N+1.
The i-th edge connects vertex i and vertex i+1.

You place a piece on vertex 1. Then you repeat the following operation exactly T times:

• Let the current vertex be v. Choose one adjacent vertex of v uniformly at random, and move the piece to that vertex.

After T operations, compute the probability that the piece is on vertex X, modulo 998244353.

Constraints

• 1 \leq N \leq 20
• 1 \leq T \leq 10^{18}
• 1 \leq X \leq 2^N+1
• All input values are integers

Partial Score

This problem has partial scoring:

• If you solve all datasets with N \leq 14, you will earn 3 points.

Sample Input 1

2 3 2

Sample Output 1

249561089

The possible moves and their probabilities are:

• Move 1 \to 2 \to 3 \to 2 with probability \tfrac{1}{4}.
• Move 1 \to 2 \to 1 \to 2 with probability \tfrac{1}{2}.

Thus, the answer is \tfrac{3}{4}.

Sample Input 2

10 12345 678

Sample Output 2

530802129

Problem Statement

We define the following as a subproblem:

You are given a tree with N vertices labeled 1 through N, and an integer K where K=1 or K=N.
Alice and Bob play a game with the following rules:

• First, Alice places a piece on one of the vertices 1, 2, \dots, K.
• Then, starting with Bob, they alternately perform the following operation:
  • Choose a vertex adjacent to the current piece that has not yet been visited, and move the piece there.
• The player who cannot make a move on their turn loses, and the other player wins.

Assuming both play optimally, determine who wins the game.

You are given an integer U and a value \mathrm{type} \in {1, 2}.
For each N = 2, 3, \dots, U, solve the following problem:

• You are given integers N and K, where
  K = 1 if \mathrm{type} = 1, and K = N if \mathrm{type} = 2.
  Suppose these values match the N and K of the subproblem above. There are N^{N-2} possible trees with N vertices labeled 1 through N.
  Among them, count how many trees yield the answer "Alice" for the subproblem, and output the result modulo 998244353.

Constraints

• 2 \leq U \leq 2.5 \times 10^5
• \mathrm{type} \in {1, 2}
• All input values are integers

Scoring

This problem has the following scoring rules:

• If you solve all datasets with \mathrm{type} = 1, you will earn 3 points.
• If you solve all datasets with \mathrm{type} = 2, you will earn 3 points.

Sample Input 1

4 1

Sample Output 1

0
2
3

When \mathrm{type} = 1, K = 1 always holds.
For N = 3, there are 2 valid trees: one with edges 1-2-3, and another with edges 1-3-2.

Sample Input 2

10 2

Sample Output 2

0
3
4
125
576
16807
154624
4782969
69760000

When \mathrm{type} = 2, K = N always holds.

Problem Statement

You are given a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N, and a positive integer T.

There are \sum_{i=1}^N A_i distinct locations. Each location is painted with a color represented by an integer, and there are exactly A_i locations painted with color i.

Initially, you choose one of the locations painted with color 1, move to that location, and mark it. Then, you repeat the following operation exactly T times:

• Choose any location with a different color from your current one, and move there.

Count the number of ways such that after all T operations, you are back at the location you initially marked. Output the result modulo 998244353.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq T \leq 10^{18}
• 1 \leq A_i \leq 10^9
• All input values are integers

Partial Score

This problem has partial scoring:

• If you solve all datasets with N \leq 3 \times 10^3, you will earn 5 points.

Sample Input 1

3 3
2 1 2

Sample Output 1

4

Let us label the locations as follows:

• The initially marked location: location 1
• The other location painted with color 1: location 2
• The location painted with color 2: location 3
• The two locations painted with color 3: locations 4 and 5

Then, there are 4 valid sequences of moves:

• 1 \to 3 \to 4 \to 1
• 1 \to 3 \to 5 \to 1
• 1 \to 4 \to 3 \to 1
• 1 \to 5 \to 3 \to 1

Sample Input 2

10 31415926535897932
766294630 440423914 59187620 725560241 585990757 965580536 623321126 550925214 122410709 549392045

Sample Output 2

66487687

Problem Statement

We define the following as a subproblem:

There are N programs numbered 1 through N. Program i is broadcast from time A_i to time B_i.
You want to record all programs using 2 recorders.

For a set of programs S, the condition that all programs in S can be recorded by a single recorder is that no two programs in S overlap in time. (It is acceptable if they only touch at the endpoints.)

• More formally, all programs in S can be recorded if there are no distinct i, j \in S such that \max(A_i, A_j) < \min(B_i, B_j) holds.

The question is whether it is possible to record all programs using 2 recorders.
More precisely, does there exist a partition S_1, S_2 of {1, 2, \dots, N} such that both S_1 and S_2 can each be recorded by a single recorder?
Output Yes if it is possible, otherwise output No.

Constraints:

• 0 \leq A_i < B_i \leq T
• N, T, A_i, B_i are integers

You are given N and U.
For each T = 1, 2, \dots, U, solve the following problem:

• Suppose N, T are the same as in the subproblem. Then, the number of possible inputs (A_1, B_1), \dots, (A_N, B_N) is \left(\dfrac{T(T+1)}{2}\right)^N.
  Among them, count how many yield the answer Yes in the subproblem, and output the result modulo 998244353.

Constraints

• 1 \leq N \leq 6 \times 10^4
• 1 \leq U \leq 6 \times 10^4
• N, U are integers

Partial Score

This problem has partial scoring:

• If you solve all datasets with N \leq 5 \times 10^3 and U \leq 5 \times 10^3, you will earn 4 points.

Sample Input 1

3 4

Sample Output 1

0
12
114
558

For example, when T=2, an input such as (A_1, B_1) = (0, 2), (A_2, B_2) = (0, 1), (A_3, B_3) = (1, 2) satisfies the condition.

Sample Input 2

7 10

Sample Output 2

0
0
0
6300
260820
4161780
39414060
265208580
398083867
112841142

Problem Statement

On a 2D coordinate plane, there is a piece placed at (0, 0).
You will perform the following operation N times:

• Choose an integer i such that 0 \leq i \leq 11.
  If the current position of the piece is (x, y), move it to (x + \cos(30i)^\circ, y + \sin(30i)^\circ).

Count the number of operation sequences that result in the piece being back at (H, W) after N operations, and output the result modulo 998244353.

Constraints

• 1 \leq N \leq 2.5 \times 10^5
• -N \leq H \leq N
• -N \leq W \leq N
• N, H, W are integers

Partial Score

This problem has partial scoring:

• If you solve all datasets with (H, W) = (0, 0), you will earn 5 points.

Sample Input 1

2 0 0

Sample Output 1

12

For every integer n such that 0 \leq n \leq 11, if the first operation chooses i = n and the second operation chooses i = (n+6) \bmod 12, the condition is satisfied. Thus, there are 12 valid sequences.

Sample Input 2

123456 0 0

Sample Output 2

352845935

Sample Input 3

50 -12 34

Sample Output 3

391874286

Sample Input 4

234567 89012 -34567

Sample Output 4

523418763

Problem Statement

You are given a simple undirected graph G with N vertices and M edges, where the vertices are numbered 1 through N.
The i-th edge connects vertex A_i and vertex B_i.
Among all spanning subgraphs of G(that is, subgraphs covering all vertices of G), count how many satisfy the following condition, and output the result modulo 998244353:

• There exists a cycle that contains both vertex 1 and vertex N.

Constraints

• 3 \leq N \leq 16
• 3 \leq M \leq \binom{N}{2}
• 1 \leq A_i < B_i \leq N
• If i \neq j, then (A_i, B_i) \neq (A_j, B_j)
• All input values are integers

Partial Score

This problem has partial scoring:

• If you solve all datasets with N \leq 10, you will earn 4 points.

Sample Input 1

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

Sample Output 1

8

For example, the spanning subgraph consisting of edges 1, 2, 3, and 5 satisfies the condition, because edges 2, 3, and 5 form a cycle that contains both vertex 1 and vertex 4.

Sample Input 2

6 15
1 2
1 3
2 3
1 4
2 4
3 4
1 5
2 5
3 5
4 5
1 6
2 6
3 6
4 6
5 6

Sample Output 2

20448

Note

This problem is a hard challenge intended for those who have finished all other problems and still have time left.
The score is set relatively low compared to its difficulty.
If you have not solved the other problems yet, it is recommended to do those first.

Problem Statement

You are given a formal power series F(x) = \sum_{i=0}^{N-1} f_i x^i over \mathbb{F} _ {998244353}, where N \geq 2 and F(x) \bmod{x^2} = x.

It can be proven that there exists a unique formal power series G(x) = \sum_{i=0}^{N-1} g_i x^i over \mathbb{F} _ {998244353} such that:

• G(G(x)) \equiv F(x) \pmod{x^N}, and
• G(x) \bmod{x^2} = x.

Your task is to find this G(x).

Constraints

• 2 \leq N \leq 8000
• f_0 = 0
• f_1 = 1
• 0 \leq f_i < 998244353 for 2 \leq i \leq N-1
• All input values are integers

Sample Input 1

3
0 1 4

Sample Output 1

0 1 2

G(x) = x + 2x^2 satisfies the conditions.

Sample Input 2

7
0 1 766294629 440423913 59187619 725560240 585990756

Sample Output 2

0 1 882269491 824730961 772850352 694658399 134447547