Problem Statement

This problem is output-only. No input is given.

Present one pair (X, S) of a positive integer X and a string S that satisfies all of the following conditions.

• X is a positive integer at least 10^{50} and less than 10^{5000}.
• S is a string of length at most 5000, consisting of digits from 0 to 9.
• For every integer i such that 1 \leq i \leq 1000, the following condition is satisfied:
  • The decimal representation of X multiplied by i is a (contiguous) substring of S.

Problem Statement

You are given a rooted tree T with N vertices labeled from 1 to N. The root is the vertex 1, and the parent of vertex i (2 \leq i \leq N) is p_i (p_i \lt i).

Consider a directed graph G with N vertices labeled from 1 to N. We call G good if it satisfies all of the following conditions (here, let u \to v denote an edge from vertex u to vertex v):

• Every vertex in G has outdegree 1.
• G has no cycle of even length.
• For every i (2 \leq i \leq N), G does not contain the edge i \to p_i.

Find the sum, modulo 998244353, of 2^{(\text{number of cycles in }G)} over all good graphs G.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq p_i \lt i
• All values given in the input are integers.

Sample Input 1

2
1

Sample Output 1

6

Here are the two possible good graphs:

• The graph with edges 1 \to 1 and 2 \to 2.
• The graph with edges 1 \to 2 and 2 \to 2.

The number of cycles in these graphs are 2 and 1, respectively. Thus, the answer is (2^2 + 2^1) \bmod{998244353} = 6.

Sample Input 2

3
1 2

Sample Output 2

34

For example, the graph with edges 1 \to 2, 2 \to 3, and 3 \to 1 is a good graph, whose number of cycle is 1.

Sample Input 3

5
1 2 1 1

Sample Output 3

3104

Sample Input 4

20
1 2 2 2 5 3 5 1 7 9 4 6 4 12 8 2 5 16 6

Sample Output 4

784973196

Remember to find the sum modulo 998244353.

Problem Statement

Alice and Bob played rock-paper-scissors N times. Each round of rock-paper-scissors results in “Alice’s win,” “Bob’s win,” or “Draw.”
Among all possible sequences of results of N rounds, how many satisfy the following conditions? Find the count modulo \bf{1000000007 = 10^9 + 7}.

• Among the N rounds, Alice won exactly A times and Bob won exactly B times.
• Alice never won twice in a row without intervening draws.
• Bob never won twice in a row without intervening draws.
• At no point did Bob’s number of wins exceed Alice’s number of wins. Formally, for all 1 \leq i \leq N, “the number of times Alice has won up through round i” is at least “the number of times Bob has won up through round i.”

Constraints

• 2 \leq N \leq 2 \times 10^7
• 1 \leq B \leq A
• A + B \leq N
• N, A, and B are integers.

Sample Input 1

5 2 2

Sample Output 1

5

For example, the following sequence of N rounds satisfies the conditions:

• Round 1: Alice wins.
• Round 2: Bob wins.
• Round 3: Alice wins.
• Round 4: Draw.
• Round 5: Bob wins.

On the other hand, the following sequence of N rounds does not satisfy the conditions, because after round 4, Alice’s number of wins (=1) is less than Bob’s number of wins (=2):

• Round 1: Alice wins.
• Round 2: Bob wins.
• Round 3: Draw.
• Round 4: Bob wins.
• Round 5: Alice wins.

There are five sequences in total that satisfy the conditions.

Sample Input 2

70 29 12

Sample Output 2

693209192

Remember to find the count modulo (10^9 + 7).

Sample Input 3

20000000 1234567 890123

Sample Output 3

566226457

Problem Statement

You are given positive integers N and K, and two permutations A = (A_1, A_2, \dots, A_{N+K}) and B = (B_1, B_2, \dots, B_{N+K}) of (1, 2, \dots, N+K).
Process Q queries.

For each query, given a pair of integers (X, Y), solve the following problem. (All queries are independent.)

There are N + K + X cards labeled from 1 to N + K + X.
Each card has a pair of integers written on it. Specifically,

• For 1 \leq i \leq N+K, card i has (A_i, B_i).
• For N + K + 1 \leq i \leq N + K + X, card i has (i, Y).

At the beginning, you have the N cards 1 to N in your hand, and the K + X cards from N+1 to N + K + X are on the table.
You may perform the following sequence of operations any number of times, possibly zero.

• First, choose one card from your hand and one card from the table, calling them card i and card j. Here, the following condition must hold:
  • Let (a_i, b_i) be the pair of integers written on card i, and (a_j, b_j) be the pair on card j. You must have a_i < a_j and b_i < b_j.
• Then, remove card j from the table and place card i on the table (the removed card is no longer available).

What is the minimum number of cards you can end up holding in your hand after performing these operations?

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq A_i \leq N + K
• 1 \leq B_i \leq N + K
• A and B are permutations of (1, 2, \dots, N+K).
• 1 \leq X \leq 10
• 1 \leq Y \leq N + K
• All input values are integers.

Sample Input 1

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

Sample Output 1

4
3
3
3
2
1

Taking the query (X, Y) = (2, 2) (the second query) as an example:

Initially, the cards in your hand and on the table are as follows:

• In your hand: (1, 4), (2, 2), (3, 5), (4, 1), (6, 6)
• On the table: (5, 3), (7, 2), (8, 2)

You can achieve holding three cards in your hand, which is the minimum, by performing the following operations:

• Choose card 2 in your hand with (2, 2) and card 6 on the table with (5, 3). Remove card 6 from the table and place card 2 on the table. Now, the following cards are remaining.
  • In your hand: (1, 4), (3, 5), (4, 1), (6, 6)
  • On the table: (2, 2), (7, 2), (8, 2)
• Choose card 4 in your hand with (4, 1) and card 8 on the table with (8, 2). Remove card 8 from the table and place card 4 on the table. Now, the following cards are remaining.
  • In your hand: (1, 4), (3, 5), (6, 6)
  • On the table: (2, 2), (7, 2), (4, 1)

Sample Input 2

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

Sample Output 2

4
5
5
4
2
4
1
6
3
4

Sample Input 3

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

Sample Output 3

13
15
6
11
9
13
8
12
3
15

Problem Statement

You are given positive integers N and K. Consider an undirected tree T with (2K + 1)N + 1 vertices labeled from 1 to (2K + 1)N + 1. Among all such trees, find the number, modulo 998244353, of trees that satisfy the following condition.

• It is possible to remove all edges from T by repeating the following operation:
  • Choose a path of length 2K + 1 and remove all edges in it.
    Formally, choose a sequence of distinct vertices v_0, v_1, \dots, v_{2K+1} such that there exists an edge (v_i, v_{i+1}) for all i such that 0 \leq i \leq 2K, and remove the edge (v_i, v_{i+1}) for all i such that 0 \leq i \leq 2K.

Constraints

• 1 \leq N \leq 1.3 \times 10^5
• 1 \leq K \leq 50
• All input values are integers.

Sample Input 1

2 1

Sample Output 1

8820

For example, consider a tree with edges (1, 2), (2, 3), (2, 4), (2, 6), (3, 7), and (4, 5). By doing the following steps, one can remove all edges from the tree, so it satisfies the condition in the problem statement:

• Choose the path (1,2,4,5) and remove edges (1,2), (2,4), (4,5).
• Choose the path (6,2,3,7) and remove edges (6,2), (2,3), (3,7).

There are 8820 such trees in total.

Sample Input 2

70 1

Sample Output 2

273892456

Remember to print the count modulo 998244353.

Sample Input 3

12 29

Sample Output 3

898069699

Sample Input 4

100000 50

Sample Output 4

158600909