Problem Statement

We have a string S of length N, where each character is < or >.

A non-negative integer sequence of N+1 elements, X_0,X_1,\ldots,X_N, is said to be good when it satisfies the following for every 1 \leq i \leq N:

• X_{i-1}<X_i, if S_i is <;
• X_{i-1}>X_i, if S_i is >.

Given a good non-negative integer sequence A, divide it into as many good non-negative integer sequences as possible. That is, find a positive integer k and k good non-negative integer sequences B_1,B_2,\ldots, B_k satisfying the following with the maximum possible value of k:

• For every 0 \leq i \leq N, the sum of the i-th elements of B_1,\ldots,B_k equals A_i.

Constraints

• 1 \leq N \leq 100
• 0 \leq A_i \leq 10^4
• S is a string of length N consisting of < and >.
• A is a good non-negative integer sequence. Particularly, A has N+1 elements.

Sample Input 1

3
<><
3 8 6 10

Sample Output 1

2
1 5 4 7
2 3 2 3

Problem Statement

We have 2N cards, with ID numbers from 1 through 2N. Card i has a value of V_i. Takahashi and Aoki will do the following procedure N times so that each of them gets N cards.

• First, Takahashi chooses one card that is not yet chosen and gets it. Then, Aoki chooses the card whose ID number is the median of those of the cards not yet chosen and gets it.

Find the maximum possible sum of the values of cards Takahashi has in the end.

Constraints

• 1\leq N\leq 2\times 10^5
• 0\leq V_i\leq 10^9
• V_i is an integer.

Sample Input 1

3
1 2 3 4 5 6

Sample Output 1

15

Takahashi can get Cards 4, 5, and 6 as follows:

• First, Takahashi chooses Card 6, which makes Aoki choose Card 3.
• Next, Takahashi chooses Card 5, which makes Aoki choose Card 2.
• Lastly, Takahashi chooses Card 4, which makes Aoki choose Card 1.

Sample Input 2

4
1 4 5 8 7 6 3 2

Sample Output 2

20

Problem Statement

We have 2N cards, with ID numbers from 1 through 2N. Consider the following game using them.

First, the dealer randomly split the cards into two piles of N cards each. Here, the dealer also randomly chooses the order of cards in each pile. Then, the player repeatedly does the operation below until one pile becomes empty, and the number of operations done will be the score.

• Choose a positive integer k and compare the k-th cards from the top in the two piles. (k should not exceed the number of each pile.) Then, remove the card with the smaller ID number from the pile that contains it.

Assume that a cheater plays this game. That is, assume that the player can always see the ID numbers of all cards in both piles. Find the expected value of the score when the player plays optimally to minimize it, modulo (10^9 + 7) (see Notes).

Notes

• The expected value in question will be a rational number. If we express it as a fractional number \frac{y}{x} where x and y are coprime positive integers, x will be coprime with P=10^9+7, so print the only integer z between 0 and P-1 (inclusive) such that xz \equiv y \pmod P.

Constraints

• 1 \leq N \leq 10^6

Sample Input 1

1

Sample Output 1

1

Sample Input 2

3

Sample Output 2

486111118

Problem Statement

We have a contest with N participants and N problems. The participants are numbered 1 through N. For each pair of a participant and a problem, we know the time it takes for the participant to solve the problem, and it is 1, 2, or 3 minutes. Among the N problems, there are A_i problems that Participant i takes 1 minute to solve, B_i problems that s/he takes 2 minutes to solve, and C_i problems that s/he takes 3 minutes to solve.

Determine whether it is possible for the following to hold for every 1 \leq i, j \leq N when the participants can freely decide the order they solve the problems.

• Let S be the total time Participant i takes to solve the first i problems, and T be the total time Participant j takes to solve the first i problems. Then, we have S \leq T.

In other words, determine whether it is possible that Participant i places first (possibly with ties) when they have solved the first i problems, ignoring the time it takes for them to switch between problems.

Given T test cases, solve each of them.

Constraints

• 1 \leq T \leq 2\times 10^5
• 1 \leq N \leq 2\times 10^5
• 0 \leq A_i,B_i,C_i \leq N
• A_i+B_i+C_i=N
• The sum of N over all test cases is at most 2\times 10^5.

Sample Input 1

2
3
0 2 1
0 1 2
1 1 1
3
0 2 1
0 0 3
1 1 1

Sample Output 1

Yes
No

In the first test case, one scenario that satisfies the condition is as follows:

• Participant 1 solves the first problem in 3 minutes, the second in 2 minutes, and the third in 2 minutes;
• Participant 2 solves the first problem in 3 minutes, the second in 2 minutes, and the third in 3 minutes;
• Participant 3 solves the first problem in 3 minutes, the second in 2 minutes, and the third in 1 minutes.

Problem Statement

We have 2N cards and N boxes. The cards are numbered 1 through 2N, and the boxes are numbered 1 through N. Each box contains two cards; Box i contains Card A_i and Card B_i.

Find, modulo (10^9+7), the number of ways to arrange the N boxes in a row that satisfies the following condition.

• Consider getting a sequence of 2N cards as follows: for each box, from left to right, open it and append the two cards in it to the end of the sequence in an order we like. In this way, it is possible to get a sequence P_1,P_2,\ldots, P_{2N} with N-1 peaks.

Here, a peak in a sequence P_1,P_2,\ldots, P_{2N} is an integer j satisfying 2 \leq j < 2N such that P_{j-1} < P_j and P_j > P_{j+1}.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq A_i, B_i \leq 2N
• A_1,\ldots,A_N,B_1,\ldots,B_N are pairwise distinct.

Sample Input 1

3
1 3
2 4
5 6

Sample Output 1

4

For example, if we arrange Boxes 1, 2, 3 in this order, we can arrange the cards as follows to get a sequence P with 2 peaks:

• first, arrange the cards in Box 1 in the order 1, 3;
• next, append the cards in Box 2 at the end in the order 2, 4;
• lastly, append the cards in Box 3 at the end in the order 6, 5.

Here, we have P=(1,3,2,4,6,5) with peaks j=2,5.

Sample Input 2

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

Sample Output 2

492

Sample Input 3

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

Sample Output 3

1411200

Problem Statement

2N+1 players will play a game called Majority Vote. Each player casts a vote to one of the two options given, and the players choosing the option that ends up with the greater number of votes will win. The detailed progression of the vote is as follows:

1. If everyone has already voted, the vote ends. Otherwise, proceed to step 2.
2. One player is chosen randomly among the players who have not voted, and s/he casts a vote. Then, go back to step 1.

K of the players are ESPers, who can know the number of votes cast to each option when they cast votes. Thus, the players choose the option to cast as follows:

• A player who is an ESPer chooses the option with the greater number of votes at the moment. If the two options have the same number of votes, s/he chooses one option randomly and votes for it.
• A player who is not an ESPer randomly chooses one option and votes for it.

X is a player of the game who is also an ESPer. Find the probability that X wins, modulo (10^9+7) (see Notes).

Notes

• The expected value in question will be a rational number. If we express it as a fractional number \frac{y}{x} where x and y are coprime positive integers, x will be coprime with P=10^9+7, so print the only integer z between 0 and P-1 (inclusive) such that xz \equiv y \pmod P.

Constraints

• 1 \leq N \leq 2\times 10^6
• 1 \leq K \leq 2N+1

Sample Input 1

1 1

Sample Output 1

916666674

X wins with probability \frac{11}{12}.

Sample Input 2

1 2

Sample Output 2

958333341

X wins with probability \frac{23}{24}.

Sample Input 3

8 5

Sample Output 3

582281799

Sample Input 4

100 100

Sample Output 4

196654831

Sample Input 5

2000000 2000000

Sample Output 5

768385859