Problem Statement

There is a grid with H horizontal rows and W vertical columns. For two integers i and j such that 1 \leq i \leq H and 1 \leq j \leq W, the square at the i-th row from the top and j-th column from the left (which we denote by (i, j)) has an integer A_{i, j} written on it.

Takahashi is currently at (1,1). From now on, he repeats moving to an adjacent square to the right of or below his current square until he reaches (H, W). When he makes a move, he is not allowed to go outside the grid.

Takahashi will be happy if the integers written on the squares he visits (including initial (1, 1) and final (H, W)) are distinct. Find the number of his possible paths that make him happy.

Constraints

• 2 \leq H, W \leq 10
• 1 \leq A_{i, j} \leq 10^9
• All values in the input are integers.

Sample Input 1

3 3
3 2 2
2 1 3
1 5 4

Sample Output 1

3

There are six possible paths:

• (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 2, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 3, 4, so he will not be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.
• (1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3): the integers written on the squares he visits are 3, 2, 1, 5, 4, so he will be happy.

Thus, the third, fifth, and sixth paths described above make him happy.

Sample Input 2

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

Sample Output 2

48620

In this example, every possible path makes him happy.

Problem Statement

We have HW cards arranged in a matrix with H rows and W columns.
For each i=1, \ldots, N, the card at the A_i-th row from the top and B_i-th column from the left has a number i written on it. The other HW-N cards have nothing written on them.

We will repeat the following two kinds of operations on these cards as long as we can.

• If there is a row without a numbered card, remove all the cards in that row and fill the gap by shifting the remaining cards upward.
• If there is a column without a numbered card, remove all the cards in that column and fill the gap by shifting the remaining cards to the left.

Find the position of each numbered card after the end of the process above. It can be proved that these positions are uniquely determined without depending on the order in which the operations are done.

Constraints

• 1 \leq H,W \leq 10^9
• 1 \leq N \leq \min(10^5,HW)
• 1 \leq A_i \leq H
• 1 \leq B_i \leq W
• All pairs (A_i,B_i) are distinct.
• All values in input are integers.

Sample Input 1

4 5 2
3 2
2 5

Sample Output 1

2 1
1 2

Let * represent a card with nothing written on it. The initial arrangement of cards is:

*****
****2
*1***
*****

After the end of the process, they will be arranged as follows:

*2
1*

Here, the card with 1 is at the 2-nd row from the top and 1-st column from the left, and the card with 2 is at the 1-st row from the top and 2-nd column from the left.

Sample Input 2

1000000000 1000000000 10
1 1
10 10
100 100
1000 1000
10000 10000
100000 100000
1000000 1000000
10000000 10000000
100000000 100000000
1000000000 1000000000

Sample Output 2

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

Problem Statement

We have a sequence of N integers between 0 and 9 (inclusive): A=(A_1, \dots, A_N), arranged from left to right in this order.

Until the length of the sequence becomes 1, we will repeatedly do the operation F or G below.

• Operation F: delete the leftmost two values (let us call them x and y) and then insert (x+y)\%10 to the left end.
• Operation G: delete the leftmost two values (let us call them x and y) and then insert (x\times y)\%10 to the left end.

Here, a\%b denotes the remainder when a is divided by b.

For each K=0,1,\dots,9, answer the following question.

Among the 2^{N-1} possible ways in which we do the operations, how many end up with K being the final value of the sequence?
Since the answer can be enormous, find it modulo 998244353.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq A_i \leq 9
• All values in input are integers.

Sample Input 1

3
2 7 6

Sample Output 1

1
0
0
0
2
1
0
0
0
0

If we do Operation F first and Operation F second: the sequence becomes (2,7,6)→(9,6)→(5).
If we do Operation F first and Operation G second: the sequence becomes (2,7,6)→(9,6)→(4).
If we do Operation G first and Operation F second: the sequence becomes (2,7,6)→(4,6)→(0).
If we do Operation G first and Operation G second: the sequence becomes (2,7,6)→(4,6)→(4).

Sample Input 2

5
0 1 2 3 4

Sample Output 2

6
0
1
1
4
0
1
1
0
2

Problem Statement

A graph with (k+1) vertices and k edges is called a level-k\ (k\geq 2) star if and only if:

• it has a vertex that is connected to each of the other k vertices with an edge, and there are no other edges.

At first, Takahashi had a graph consisting of stars. He repeated the following operation until every pair of vertices in the graph was connected:

• choose two vertices in the graph. Here, the vertices must be disconnected, and their degrees must be both 1. Add an edge that connects the chosen two vertices.

He then arbitrarily assigned an integer from 1 through N to each of the vertices in the graph after the procedure. The resulting graph is a tree; we call it T. T has (N-1) edges, the i-th of which connects u_i and v_i.

Takahashi has now forgotten the number and levels of the stars that he initially had. Find them, given T.

Constraints

• 3\leq N\leq 2\times 10^5
• 1\leq u_i, v_i\leq N
• The given graph is an N-vertex tree obtained by the procedure in the problem statement.
• All values in the input are integers.

Sample Input 1

6
1 2
2 3
3 4
4 5
5 6

Sample Output 1

2 2

Two level-2 stars yield T, as the following figure shows:

Sample Input 2

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

Sample Output 2

2 2 2

Sample Input 3

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

Sample Output 3

2 3 4 7

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 M. Find the number, modulo 998244353, of non-empty and not necessarily contiguous subsequences of A such that the least common multiple (LCM) of the elements in the subsequence is M. Two subsequences are distinguished if they are taken from different positions in the sequence, even if they coincide as sequences. Also, the LCM of a sequence with a single element is that element itself.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 10^{16}
• 1 \leq A_i \leq 10^{16}
• All input values are integers.

Sample Input 1

4 6
2 3 4 6

Sample Output 1

5

The subsequences of A whose elements have an LCM of 6 are (2,3),(2,3,6),(2,6),(3,6),(6); there are five of them.

Sample Input 2

5 349
1 1 1 1 349

Sample Output 2

16

Note that even if some subsequences coincide as sequences, they are distinguished if they are taken from different positions.

Sample Input 3

16 720720
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Sample Output 3

2688