Problem Statement

Takahashi has two integers X and Y.

He computed X + Y and X - Y, and the results were A and B, respectively.

Now he cannot remember what X and Y were. Find X and Y for him.

Constraints

• -100 \leq A, B \leq 100
• For the given integers A and B, there uniquely exist integers X and Y such that X + Y = A and X - Y = B.
• All values in input are integers.

Sample Input 1

2 -2

Sample Output 1

0 2

If X = 0 and Y = 2, they match the situation: 0 + 2 = 2 and 0 - 2 = -2.

Sample Input 2

3 1

Sample Output 2

2 1

Problem Statement

We have a string S of length N consisting of A, T, C, and G.

Strings T_1 and T_2 of the same length are said to be complementary when, for every i (1 \leq i \leq l), the i-th character of T_1 and the i-th character of T_2 are complementary. Here, A and T are complementary to each other, and so are C and G.

Find the number of non-empty contiguous substrings T of S that satisfies the following condition:

• There exists a string that is a permutation of T and is complementary to T.

Here, we distinguish strings that originate from different positions in S, even if the contents are the same.

Constraints

• 1 \leq N \leq 5000
• S consists of A, T, C, and G.

Sample Input 1

4 AGCT

Sample Output 1

2

The following two substrings satisfy the condition:

• GC (the 2-nd through 3-rd characters) is complementary to CG, which is a permutation of GC.
• AGCT (the 1-st through 4-th characters) is complementary to TCGA, which is a permutation of AGCT.

Sample Input 2

4 ATAT

Sample Output 2

4

The following four substrings satisfy the condition:

• AT (the 1-st through 2-nd characters) is complementary to TA, which is a permutation of AT.
• TA (the 2-st through 3-rd characters) is complementary to AT, which is a permutation of TA.
• AT (the 3-rd through 4-th characters) is complementary to TA, which is a permutation of AT.
• ATAT (the 1-st through 4-th characters) is complementary to TATA, which is a permutation of ATAT.

Sample Input 3

10 AAATACCGCG

Sample Output 3

6

Problem Statement

There is a building with 2N floors, numbered 1, 2, \ldots, 2N from bottom to top.

The elevator in this building moved from Floor 1 to Floor 2N just once.

On the way, N persons got on and off the elevator. Each person i (1 \leq i \leq N) got on at Floor A_i and off at Floor B_i. Here, 1 \leq A_i < B_i \leq 2N, and just one person got on or off at each floor.

Additionally, because of their difficult personalities, the following condition was satisfied:

• Let C_i (= B_i - A_i - 1) be the number of times, while Person i were on the elevator, other persons got on or off. Then, the following holds:
  • If there was a moment when both Person i and Person j were on the elevator, C_i = C_j.

We recorded the sequences A and B, but unfortunately, we have lost some of the records. If the record of A_i or B_i is lost, it will be given to you as -1.

Additionally, the remaining records may be incorrect.

Determine whether there is a pair of A and B that is consistent with the remaining records.

Constraints

• 1 \leq N \leq 100
• A_i = -1 or 1 \leq A_i \leq 2N.
• B_i = -1 or 1 \leq B_i \leq 2N.
• All values in input are integers.

Sample Input 1

3
1 -1
-1 4
-1 6

Sample Output 1

Yes

For example, if B_1 = 3, A_2 = 2, and A_3 = 5, all the requirements are met.

In this case, there is a moment when both Person 1 and Person 2 were on the elevator, which is fine since C_1 = C_2 = 1.

Sample Input 2

2
1 4
2 3

Sample Output 2

No

There is a moment when both Person 1 and Person 2 were on the elevator. Since C_1 = 2, C_2 = 0, some of the information is incorrect.

Sample Input 3

2
4 1
2 4

Sample Output 3

No

The records are seemingly intact but clearly are incorrect.

Problem Statement

Given positive integers N, K and M, solve the following problem for every integer x between 1 and N (inclusive):

• Find the number, modulo M, of non-empty multisets containing between 0 and K (inclusive) instances of each of the integers 1, 2, 3 \cdots, N such that the average of the elements is x.

Constraints

• 1 \leq N, K \leq 100
• 10^8 \leq M \leq 10^9 + 9
• M is prime.
• All values in input are integers.

Sample Input 1

3 1 998244353

Sample Output 1

1
3
1

Consider non-empty multisets containing between 0 and 1 instance(s) of each of the integers between 1 and 3. Among them, there are:

• one multiset such that the average of the elements is k = 1: \{1\};
• three multisets such that the average of the elements is k = 2: \{2\}, \{1, 3\}, \{1, 2, 3\};
• one multiset such that the average of the elements is k = 3: \{3\}.

Sample Input 2

1 2 1000000007

Sample Output 2

2

Consider non-empty multisets containing between 0 and 2 instances of each of the integers between 1 and 1. Among them, there are:

• two multisets such that the average of the elements is k = 1: \{1\}, \{1, 1\}.

Sample Input 3

10 8 861271909

Sample Output 3

8
602
81827
4054238
41331779
41331779
4054238
81827
602
8

Problem Statement

Given is an integer sequence of length N: A_1, A_2, \cdots, A_N.

An integer sequence X, which is also of length N, will be chosen randomly by independently choosing X_i from a uniform distribution on the integers 1, 2, \ldots, A_i for each i (1 \leq i \leq N).

Compute the expected value of the length of the longest increasing subsequence of this sequence X, modulo 1000000007.

More formally, under the constraints of the problem, we can prove that the expected value can be represented as a rational number, that is, an irreducible fraction \frac{P}{Q}, and there uniquely exists an integer R such that R \times Q \equiv P \pmod {1000000007} and 0 \leq R < 1000000007, so print this integer R.

Notes

A subsequence of a sequence X is a sequence obtained by extracting some of the elements of X and arrange them without changing the order. The longest increasing subsequence of a sequence X is the sequence of the greatest length among the strictly increasing subsequences of X.

Constraints

• 1 \leq N \leq 6
• 1 \leq A_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
1 2 3

Sample Output 1

2

X becomes one of the following, with probability 1/6 for each:

• X = (1,1,1), for which the length of the longest increasing subsequence is 1;
• X = (1,1,2), for which the length of the longest increasing subsequence is 2;
• X = (1,1,3), for which the length of the longest increasing subsequence is 2;
• X = (1,2,1), for which the length of the longest increasing subsequence is 2;
• X = (1,2,2), for which the length of the longest increasing subsequence is 2;
• X = (1,2,3), for which the length of the longest increasing subsequence is 3.

Thus, the expected value of the length of the longest increasing subsequence is (1 + 2 + 2 + 2 + 2 + 3) / 6 \equiv 2 \pmod {1000000007}.

Sample Input 2

3
2 1 2

Sample Output 2

500000005

X becomes one of the following, with probability 1/4 for each:

• X = (1,1,1), for which the length of the longest increasing subsequence is 1;
• X = (1,1,2), for which the length of the longest increasing subsequence is 2;
• X = (2,1,1), for which the length of the longest increasing subsequence is 1;
• X = (2,1,2), for which the length of the longest increasing subsequence is 2.

Thus, the expected value of the length of the longest increasing subsequence is (1 + 2 + 1 + 2) / 4 = 3 / 2. Since 2 \times 500000005 \equiv 3 \pmod {1000000007}, we should print 500000005.

Sample Input 3

6
8 6 5 10 9 14

Sample Output 3

959563502

Problem Statement

There are N buildings under construction arranged in a row, numbered 1, 2, \ldots, N from left to right.

Given is an integer sequence X of length N. The height of Building i, H_i, can be one of the integers between 1 and X_i (inclusive).

For each i such that 1 \leq i \leq N, let us define P_i as follows:

• If there is an integer j (1 \leq j < i) such that H_j > H_i, P_i is the maximum such j. Otherwise, P_i is -1.

Considering all possible combinations of the buildings' heights, find the number of integer sequences that P can be, modulo 1000000007.

Constraints

• 1 \leq N \leq 100
• 1 \leq X_i \leq 10^5
• All values in input are integers.

Sample Input 1

3
3 2 1

Sample Output 1

4

We have six candidates for H, as follows:

• H = (1, 1, 1), for which P is (-1, -1, -1);
• H = (1, 2, 1), for which P is (-1, -1, 2);
• H = (2, 1, 1), for which P is (-1, 1, 1);
• H = (2, 2, 1), for which P is (-1, -1, 2);
• H = (3, 1, 1), for which P is (-1, 1, 1);
• H = (3, 2, 1), for which P is (-1, 1, 2).

Thus, there are four integer sequences that P can be: (-1, -1, -1), (-1, -1, 2), (-1, 1, 1), and (-1, 1, 2).

Sample Input 2

3
1 1 2

Sample Output 2

1

We have two candidates for H, as follows:

• H = (1, 1, 1), for which P is (-1, -1, -1);
• H = (1, 1, 2), for which P is (-1, -1, -1).

Thus, there is one integer sequence that P can be.

Sample Input 3

5
2 2 2 2 2

Sample Output 3

16

Sample Input 4

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

Sample Output 4

31155