Problem Statement

How many integers not less than A and not more than B are there?

Constraints

• 1 \leq A \leq 100
• 1 \leq B \leq 100
• A and B are integers.

Sample Input 1

2 4

Sample Output 1

3

We have three integers not less than 2 and not more than 4: 2, 3, 4, so we should print 3.

Sample Input 2

10 100

Sample Output 2

91

Sample Input 3

3 2

Sample Output 3

0

We have no integers not less than 3 and not more than 2, so we should print 0.

Problem Statement

Takahashi's shop sells N products. The usual price of the i-th product is A_i yen (Japanese currency).
It has a bargain sale today, with a discount of 1 yen off the usual prices for the 2-nd, 4-th, and the subsequent even-indexed products. The 1-st, 3-rd, and the subsequent odd-indexed products are sold for their usual prices.
You have X yen. Can you buy all the N products with this money?

Constraints

• 1 \leq N \leq 100
• 1 \leq X \leq 10000
• 1 \leq A_i \leq 100
• All values in input are integers.

Sample Input 1

2 3
1 3

Sample Output 1

Yes

You can buy the 1-st product for 1 yen and the 2-nd product for 2 yen, 1 yen off the usual price. You have just enough money, 3 yen, to buy both of them.

Sample Input 2

4 10
3 3 4 4

Sample Output 2

No

You can buy these four products for 3 yen, 2 yen, 4 yen, and 3 yen, respectively. You need 12 yen to buy all of them, and since you have only 10 yen, you cannot buy all of them.

Sample Input 3

8 30
3 1 4 1 5 9 2 6

Sample Output 3

Yes

Problem Statement

You are given a sequence C of N integers. Find the number of sequences A of N integers satisfying all of the following conditions.

• 1 \leq A_i \leq C_i\, (1 \leq i \leq N)
• A_i \neq A_j\, (1 \leq i < j \leq N)

Since the count may be enormous, print it modulo (10^9+7).

Constraints

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

Sample Input 1

2
1 3

Sample Output 1

2

We have two sequences A satisfying all of the conditions: (1,2) and (1,3).
On the other hand, A=(1,1), for example, does not satisfy the second condition.

Sample Input 2

4
3 3 4 4

Sample Output 2

12

Sample Input 3

2
1 1

Sample Output 3

0

We have no sequences A satisfying all of the conditions, so we should print 0.

Sample Input 4

10
999999917 999999914 999999923 999999985 999999907 999999965 999999914 999999908 999999951 999999979

Sample Output 4

405924645

Be sure to print the count modulo (10^9+7).

Problem Statement

The Kingdom of Takahashi is made up of N towns and N-1 roads, where the towns are numbered 1 through N. The i-th road (1 \leq i \leq N-1) connects Town a_i and Town b_i, so that you can get from every town to every town by using some roads. All the roads have the same length.

You will be given Q queries. In the i-th query (1 \leq i \leq Q), given integers c_i and d_i, solve the following problem:

• Takahashi is now at Town c_i and Aoki is now at Town d_i. They will leave the towns simultaneously and start traveling at the same speed, Takahashi heading to Town d_i and Aoki heading to Town c_i. Determine whether they will meet at a town or halfway along a road. Here, assume that both of them travel along the shortest paths, and the time it takes to pass towns is negligible.

Constraints

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 10^5
• 1 \leq a_i < b_i \leq N\, (1 \leq i \leq N-1)
• 1 \leq c_i < d_i \leq N\, (1 \leq i \leq Q)
• All values in input are integers.
• It is possible to get from every town to every town by using some roads.

Sample Input 1

4 1
1 2
2 3
2 4
1 2

Sample Output 1

Road

In the first and only query, Takahashi and Aoki simultaneously leave Town 1 and Town 2, respectively, and they will meet halfway along the 1-st road, so we should print Road.

Sample Input 2

5 2
1 2
2 3
3 4
4 5
1 3
1 5

Sample Output 2

Town
Town

In the first query, Takahashi and Aoki simultaneously leave Town 1 and Town 3, respectively, and they will meet at Town 2, so we should print Town.

In the first query, Takahashi and Aoki simultaneously leave Town 1 and Town 5, respectively, and they will meet at Town 3, so we should print Town.

Sample Input 3

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

Sample Output 3

Town
Road
Town
Town
Town
Town
Road
Road
Road

Problem Statement

The Takahashi Dictionary lists N words; the i-th word (1 \leq i \leq N) is s_i.

Using this dictionary, Takahashi and Aoki will play 3-shiritori, which goes as follows.

• Takahashi and Aoki alternately say words, with Takahashi going first.
• Each player must say a word beginning with the last three characters of the previous word. For example, if a player says Takahashi, the next player can say ship or shield along with other choices, but not Aoki, sing, or his.
• Uppercase and lowercase are distinguished. For example, a player cannot say ShIp following Takahashi.
• A player who becomes unable to say a word loses.
• A player cannot say a word not listed in the dictionary.
• The same word can be used multiple times.

For each i (1 \leq i \leq N), determine who will win when Takahashi starts the game by saying the word s_i. Here, we assume that both players play optimally. More specifically, each player gives first priority to avoiding his loss and second priority to defeating the opponent.

Constraints

• N is an integer between 1 and 2 \times 10^5 (inclusive).
• s_i is a string of length between 3 and 8 (inclusive) consisting of lowercase and uppercase English letters.

Sample Input 1

3
abcd
bcda
ada

Sample Output 1

Aoki
Takahashi
Draw

When Takahashi starts the game by saying abcd, Aoki will say bcda next, and Takahashi will then have no word to say, resulting in Aoki's win. Thus, we should print Aoki.

When Takahashi starts the game by saying bcda, Aoki will have no word to say, resulting in Takahashi win. Thus, we should print Takahashi.

When Takahashi starts the game by saying ada, both players will repeat ada and never end the game. Thus, we should print Draw. Note that they can use the same word any number of times.

Sample Input 2

1
ABC

Sample Output 2

Draw

Sample Input 3

5
eaaaabaa
eaaaacaa
daaaaaaa
eaaaadaa
daaaafaa

Sample Output 3

Takahashi
Takahashi
Takahashi
Aoki
Takahashi

Problem Statement

There are N trees standing in a row from left to right. The i-th tree (1 \leq i \leq N) from the left, Tree i, has the height of H_i.

You will now cut down all these N trees in some order you like. Formally, you will choose a permutation P of (1, 2, \ldots, N) and do the operation below for each i=1, 2, 3, ..., N in this order.

• Cut down Tree P_i, that is, set H_{P_i} to 0, at a cost of H_{P_i-1}+H_{P_i}+H_{P_i+1}.

Here, we assume H_0=0,H_{N+1}=0.

In other words, the cost of cutting down a tree is the total height of the tree and the neighboring trees just before doing so.

Find the number of permutations P that minimize the total cost of cutting down the trees. Since the count may be enormous, print it modulo (10^9+7).

Constraints

• 1 \leq N \leq 4000
• 1 \leq H_i \leq 10^9
• All values in input are integers.

Sample Input 1

3
4 2 4

Sample Output 1

2

There are two permutations P that minimize the total cost: (1,3,2) and (3,1,2).

Below, we will show the process of cutting down the trees for P=(1,3,2), for example.

• First, Tree 1 is cut down at a cost of H_0+H_1+H_2=6.
• Next, Tree 3 is cut down at a cost of H_2+H_3+H_4=6.
• Finally, Tree 2 is cut down at a cost of H_1+H_2+H_3=2.

The total cost incurred is 14.

Sample Input 2

3
100 100 100

Sample Output 2

6

Sample Input 3

15
804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422 25202363 350490028 783368691 102520060 44897764

Sample Output 3

54537651

Be sure to print the count modulo (10^9+7).