Problem Statement

Given are N integers between 2 and 50 (inclusive): X_1, X_2, \cdots, X_N. Find the minimum positive integer Y that satisfies the following for every i = 1, 2, \cdots, N:

• X_i and Y are not coprime.

Constraints

• 1 \leq N \leq 49
• 2 \leq X_i \leq 50
• X_i \neq X_j (i \neq j)
• All values in input are integers.

Sample Input 1

2
4 3

Sample Output 1

6

Being not coprime with 4 requires being even, and being not coprime with 3 requires being a multiple of 3.

Sample Input 2

1
47

Sample Output 2

47

Sample Input 3

7
3 4 6 7 8 9 10

Sample Output 3

42

Problem Statement

Let S be a set composed of all integers from 1 through N.

f is a function from S to S. You are given the values f(1), f(2), \cdots, f(N) as f_1, f_2, \cdots, f_N.

Find the number, modulo 998244353, of non-empty subsets T of S satisfying both of the following conditions:

• For every a \in T, f(a) \in T.

• For every a, b \in T, f(a) \neq f(b) if a \neq b.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq f_i \leq N
• All values in input are integers.

Sample Input 1

2
2 1

Sample Output 1

1

We have f(1) = 2, f(2) = 1. Since f(1) \neq f(2), the second condition is always satisfied, but the first condition requires T to contain 1 and 2 simultaneously.

Sample Input 2

2
1 1

Sample Output 2

1

We have f(1) = f(2) = 1. The first condition requires T to contain 1, and the second condition forbids T to contain 2.

Sample Input 3

3
1 2 3

Sample Output 3

7

We have f(1) = 1, f(2) = 2, f(3) = 3. Both of the conditions are always satisfied, so all non-empty subsets of T count.

Problem Statement

For a sequence A of length N consisting of integers between 1 and M (inclusive), let us define f(A) as follows:

• We have a sequence X of length N, where every element is initially 0. f(A) is the minimum number of operations required to make X equal A by repeating the following operation:
  • Specify 1 \leq l \leq r \leq N and 1 \leq v \leq M, then replace X_i with \max(X_i, v) for each l \leq i \leq r.

Find the sum, modulo 998244353, of f(A) over all M^N sequences that can be A.

Constraints

• 1 \leq N, M \leq 5000
• All values in input are integers.

Sample Input 1

2 3

Sample Output 1

15

The 3 ^ 2 = 9 sequences and the value of f for those are as follows:

• For A = (1, 1), we can make X equal it with one operation with (l = 1, r = 2, v = 1), so f(A) = 1.
• For A = (1, 2), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 2, r = 2, v = 2), so f(A) = 2.
• For A = (1, 3), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 2, r = 2, v = 3), so f(A) = 2.
• For A = (2, 1), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 1, r = 1, v = 2), so f(A) = 2.
• For A = (2, 2), we can make X equal it with one operation with (l = 1, r = 2, v = 2), so f(A) = 1.
• For A = (2, 3), we can make X equal it with two operations with (l = 1, r = 2, v = 2) , (l = 2, r = 2, v = 3), so f(A) = 2.
• For A = (3, 1), we can make X equal it with two operations with (l = 1, r = 2, v = 1) and (l = 1, r = 1, v = 3) so f(A) = 2.
• For A = (3, 2), we can make X equal it with two operations with (l = 1, r = 2, v = 2) and (l = 1, r = 1, v = 3), so f(A) = 2.
• For A = (3, 3), we can make X equal it with one operation with (l = 1, r = 2, v = 3), so f(A) = 1.

The sum of these values is 3 \times 1 + 6 \times 2 = 15.

Sample Input 2

3 2

Sample Output 2

15

Sample Input 3

34 56

Sample Output 3

649717324

Problem Statement

Let X = 10^{100}. We have a graph with a vertex for each integer -X \leq i \leq X, and an undirected edge connecting Vertex i and Vertex i + 1 (we will call it Edge \{ i, i + 1 \}) for each -X \leq i \leq X-1.

All edges in this graph are initially painted red. Additionally, we have N pieces, and the i-th of them is on Vertex a_i.

Maroon can repeat the following operation:

• Choose a piece. If that piece is on Vertex i, move it to Vertex i-1 or Vertex i + 1. Then, if the traversed edge is now painted red, repaint it blue, and vice versa.

During the process, there may be multiple pieces on the same vertex.

Maroon wants to do this operation zero or more times to make the edges painted in his desired combination of colors. The desired combination of colors is represented by an even number K and K integers t_1 < t_2 < \cdots < t_K: it means that Edge \{ i, i + 1 \} is red for i < t_1, blue for t_1 \leq i < t_2, \cdots, red for t_K \leq i. More formally, for each odd number j = 1, 3, \cdots, K-1, Edge \{ i, i + 1 \} is blue for each i such that t_j \leq i < t_{j+1}; all other edges are red.

Find the minimum number of operations required to make the edges painted in the desired combination of colors. If it is impossible to do so, print -1.

Constraints

• 1 \leq N \leq 5000
• 2 \leq K \leq 5000
• K is even.
• |a_i| \leq 10^9
• |t_i| \leq 10^9
• t_i < t_{i+1}
• All values in input are integers.

Sample Input 1

2 2
2 -1
-2 2

Sample Output 1

4

As shown below, we can achieve the desired state in four operations, which is optimal since we need to repaint four edges.

The following is the initial situation. For convenience, we have omitted edges to the left of -3 and the right of 3.

We move the piece on -1 to -2 to get the following:

Then, we move the piece on 2 to 1 to get the following:

Then, we move the piece on 1 to 0 to get the following:

Then, we move the piece on 0 to -1 to get the following, which is the desired state:

Sample Input 2

2 2
2 2
5 8

Sample Output 2

9

There can be multiple pieces on the same vertex already in the beginning.

Sample Input 3

3 4
1 3 5
0 2 4 6

Sample Output 3

-1

Sample Input 4

4 4
3 4 5 6
3 4 5 6

Sample Output 4

2

Problem Statement

We have a rectangular piece of paper divided into H \times W squares, where two of those squares are painted black and the rest are painted white. If we let (i, j) denote the square at the i-th row and j-th column, the squares painted black are (h_1, w_1) and (h_2, w_2).

Maroon will repeat the following operation to cut the piece of paper:

• Assume that we have h \times w squares remaining. There are (h - 1) horizontal lines and (w - 1) vertical lines that are parallel to the edges of the piece and pass the borders of the squares. He chooses one of these lines uniformly at random and cuts the piece into two along that line. Then,
  • if the two black squares are on the same piece, he throws away the other piece and continues the process;
  • otherwise, he ends the process.

Find the expected value of the number of times Maroon cuts a piece of paper until he ends the process, modulo 998244353.

Notes

We can prove that the expected value in question is always a rational number. Additionally, under the constraints of this problem, we can also prove that if we express that value as an irreducible fraction \frac{P}{Q}, we have Q \not \equiv 0 \pmod{998244353}. Thus, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Answer this R.

Constraints

• 1 \leq H, W \leq 10^5
• H \times W \geq 2
• 1 \leq h_1, h_2 \leq H
• 1 \leq w_1, w_2 \leq W
• (h_1, w_1) \neq (h_2, w_2)
• All values in input are integers.

Sample Input 1

2 3
2 2 1 1

Sample Output 1

332748119

In the first cut, the process will end with probability 2/3. For the remaining case with probability 1/3, the process will end in the second cut.

Thus, the expected number of cuts is 1 \times 2/3 + 2 \times 1/3 = 4/3.

Sample Input 2

1 5
1 2 1 3

Sample Output 2

332748120

Sample Input 3

2 1
2 1 1 1

Sample Output 3

1

The process will always end in the first cut.

Sample Input 4

10 10
3 4 5 6

Sample Output 4

831078040

Problem Statement

You are given a permutation P of 1, 2, \cdots, N.

You can divide P into exactly K non-empty contiguous subsequences as you like.

Maroon will rearrange those subsequences you make and concatenate them to make a new permutation Q. Here, he will lexicographically maximize Q.

You want to divide P in a way that lexicographically minimizes Q. Find Q in that case.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq N
• 1 \leq P_i \leq N
• P_i \neq P_j (i \neq j)
• All values in input are integers.

Sample Input 1

3 2
1 2 3

Sample Output 1

2 3 1

You have two ways to divide P: (1, 2),(3) and (1), (2, 3).

In the former case, Maroon will rearrange them in the order (3), (1, 2) to get Q = (3, 1, 2).

In the latter case, Maroon will rearrange them in the order (2, 3), (1) to get Q = (2, 3, 1).

Thus, you should choose the latter.

Sample Input 2

4 3
4 3 1 2

Sample Output 2

4 3 1 2

Sample Input 3

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

Sample Output 3

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