Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

You can rearrange A freely. Find the maximum value that \sum_{i=1}^{N-1} ((A_{i+1} - A_i) \bmod K) can take after rearranging.

Here, x \bmod K denotes the integer y such that 0 \le y < K and x - y is a multiple of K. For example, -3 \bmod 8 = 5, and 9 \bmod 6 = 3.

Constraints

• 2 \le N \le 2 \times 10^5
• 1 \le K \le 10^9
• 0 \le A_i < K

Sample Input 1

3 4
0 1 2

Sample Output 1

6

One optimal solution is to rearrange A into (2,1,0) to achieve (1 - 2) \bmod 4 + (0 - 1) \bmod 4 = 3 + 3 = 6.

Sample Input 2

7 123
11 34 56 0 32 100 78

Sample Output 2

638

Problem Statement

You are given a permutation P of (1,2,\dots,N). There is also a permutation Q=(1,2,\dots,N) of (1,2,\dots,N).

Perform the following operation on Q for i=1,2,\dots,N in this order.

• Remove i from Q and insert i into any one position in Q.

Find the number, modulo (10^9+7), of ways to perform N operations such that P and Q are equal after all operations.

Constraints

• 1 \le N \le 5000
• P is a permutation of (1,2,\dots,N).

Sample Input 1

3
1 2 3

Sample Output 1

5

For example, the following operations result in Q = (1,2,3).

• Remove 1 from Q=(1,2,3) and insert it between 2 and 3, making Q = (2,1,3).
• Remove 2 from Q=(2,1,3) and insert it at the end of Q, making Q = (1,3,2).
• Remove 3 from Q=(1,3,2) and insert it at the end of Q, making Q = (1,2,3).

Including this example, five ways to perform operations result in Q=(1,2,3).

Sample Input 2

4
2 4 1 3

Sample Output 2

11

Sample Input 3

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

Sample Output 3

306264

Sample Input 4

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

Sample Output 4

33525150

Problem Statement

You are given a sequence of non-negative integers A=(A_1,A_2,\dots,A_N) of length N. Here, S=\sum_{i=1}^{N} A_i is even.

Determine whether there is a pair of sequences of non-negative integers of length N, B=(B_1,B_2,\dots,B_N) and C=(C_1,C_2,\dots,C_N), that satisfy the following conditions:

• B_i+C_i=A_i for i=1,2,\dots,N.
• \sum_{i=1}^{N} X_i \neq \frac{S}{2} for every sequence of integers X=(X_1,X_2,\dots,X_N) of length N where X_i=B_i or X_i=C_i for i=1,2,\dots,N.

Solve T test cases.

Constraints

• 1 \leq T
• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^9
• \sum_{i=1}^{N} A_i is even.
• The sum of N over all test cases in a single input is at most 2 \times 10^5.
• All input values are integers.

Sample Input 1

3
3
1 2 3
6
1 1 2 2 3 3
4
1 1 1000000000 1000000000

Sample Output 1

Yes
No
Yes

For the first test case, B=(1,1,3) and C=(0,1,0) satisfy the conditions.

For the second test case, no pair of B and C satisfies the conditions.

Problem Statement

There is a circle on a plane. It has N distinct points on its circumference, numbered 1,2,\dots,N in clockwise order.

There are \frac{N(N-1)}{2} line segments that can be drawn by connecting two different points among the N points; you will choose and draw M of these segments. Find the number, modulo (10^9+7), of ways to draw M segments such that no two of them intersect at a point other than their endpoints.

Constraints

• 1 \le N \le 10^7
• 0 \le M \le \frac{N(N-1)}{2}

Sample Input 1

4 2

Sample Output 1

14

The following examples on the left and in the middle satisfy the conditions. (Note that it is acceptable for the segments to intersect at their endpoints.)

The example on the right is unsuitable because two edges intersect at a point other than their endpoints. All other \binom{6}{2} - 1 = 14 ways satisfy the conditions.

Sample Input 2

6 3

Sample Output 2

295

Sample Input 3

2023 1217

Sample Output 3

10811951

Sample Input 4

1234321 2345432

Sample Output 4

789452255

Problem Statement

You are given two sequences of positive integers of length N, A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N).

Find the minimum possible inversion number of a sequence of positive integers C=(C_1,C_2,\dots,C_N) such that the i-th element C_i is A_i or B_i.

Solve T test cases.

Constraints

• 1 \le T
• 1 \le N \le 5 \times 10^5
• 1 \le A_i,B_i \le \color{red}{\boldsymbol{3}}
• The sum of N for all test cases in a single input is at most 5 \times 10^5.

Sample Input 1

8
3
2 1 1
3 3 2
5
2 1 3 2 2
1 2 1 2 3
8
2 1 3 3 3 1 2 2
1 2 3 1 2 1 3 2
10
1 3 2 1 1 3 2 2 2 2
2 3 1 1 1 1 3 1 3 3
12
2 1 1 3 3 1 3 3 2 2 2 1
3 1 1 3 3 1 3 2 3 2 1 2
15
1 3 1 3 3 2 2 1 2 3 3 3 1 1 3
3 3 3 2 3 2 1 3 2 1 2 2 3 3 3
18
3 1 1 3 3 2 1 1 2 3 2 1 3 3 3 2 2 3
1 1 3 2 1 3 1 2 1 2 3 2 2 1 3 1 3 3
20
2 2 3 1 1 3 2 3 3 1 3 1 2 1 2 2 1 2 3 2
1 1 1 3 3 1 1 3 2 2 1 1 1 1 1 2 2 2 2 1

Sample Output 1

1
0
6
6
20
9
5
17

For the first test case, an optimal solution is C=(2,3,2) with the inversion number of 1.

For the second test case, an optimal solution is C=(1,1,1,2,3) with the inversion number of 0.

Problem Statement

You are given an even number N and a prime number M.

Find the number, modulo M, of simple connected undirected graphs G with N vertices numbered 1 to N that satisfy the following condition:

• For every spanning tree T of G, there is a perfect matching in T.

Constraints

• 2 \leq N \leq 500
• 10^8 \leq M \leq 10^9
• N is even.
• M is prime.
• All input values are integers.

Sample Input 1

4 998244353

Sample Output 1

15

For example, among the two graphs shown in the figure below, the graph on the left satisfies the condition. On the other hand, the graph on the right does not because there is no perfect matching in the spanning tree with the three edges shown in bold red.

Sample Input 2

10 998244353

Sample Output 2

128792160

Sample Input 3

300 923223991

Sample Output 3

359143490