Problem Statement

In CODE FESTIVAL XXXX, there are ~N+1~ participants from all over the world, including Takahashi.

Takahashi checked and found that the time gap (defined below) between the local times in his city and the ~i~ -th person's city was ~D_i~ hours. The time gap between two cities is defined as follows. For two cities A and B, if the local time in city B is ~d~ o'clock at the moment when the local time in city A is ~0~ o'clock, then the time gap between these two cities is defined to be ~min(d,24-d)~ hours. Here, we are using ~24~ -hour notation. That is, the local time in the ~i~ -th person's city is either ~d~ o'clock or ~24-d~ o'clock at the moment when the local time in Takahashi's city is ~0~ o'clock, for example.

Then, for each pair of two people chosen from the ~N+1~ people, he wrote out the time gap between their cities. Let the smallest time gap among them be ~s~ hours.

Find the maximum possible value of ~s~ .

Constraints

• ~1 \leq N \leq 50~
• ~0 \leq D_i \leq 12~
• All input values are integers.

Input

Input is given from Standard Input in the following format:

~N~

~D_1~ ~D_2~ ~...~ ~D_N~

Output

Print the maximum possible value of ~s~ .

Sample Input 1

3
7 12 8

Sample Output 1

4

For example, consider the situation where it is ~7~ , ~12~ and ~16~ o'clock in each person's city at the moment when it is ~0~ o'clock in Takahashi's city. In this case, the time gap between the second and third persons' cities is ~4~ hours.

Sample Input 2

2
11 11

Sample Output 2

2

Sample Input 3

1
0

Sample Output 3

0

Note that Takahashi himself is also a participant.

Problem Statement

Consider the following game:

• The game is played using a row of ~N~ squares and many stones.
• First, ~a_i~ stones are put in Square ~i\ (1 \leq i \leq N)~ .
• A player can perform the following operation as many time as desired: "Select an integer ~i~ such that Square ~i~ contains exactly ~i~ stones. Remove all the stones from Square ~i~ , and add one stone to each of the ~i-1~ squares from Square ~1~ to Square ~i-1~ ."
• The final score of the player is the total number of the stones remaining in the squares.

For a sequence ~a~ of length ~N~ , let ~f(a)~ be the minimum score that can be obtained when the game is played on ~a~ .

Find the sum of ~f(a)~ over all sequences ~a~ of length ~N~ where each element is between ~0~ and ~K~ (inclusive). Since it can be extremely large, find the answer modulo ~1000000007 (= 10^9+7)~ .

Constraints

• ~1 \leq N \leq 100~
• ~1 \leq K \leq N~

Input

Input is given from Standard Input in the following format:

~N~ ~K~

Output

Print the sum of ~f(a)~ modulo ~1000000007 (= 10^9+7)~ .

Sample Input 1

2 2

Sample Output 1

10

There are nine sequences of length ~2~ where each element is between ~0~ and ~2~ . For each of them, the value of ~f(a)~ and how to achieve it is as follows:

• ~f(\\{0,0\\})~ : ~0~ (Nothing can be done)
• ~f(\\{0,1\\})~ : ~1~ (Nothing can be done)
• ~f(\\{0,2\\})~ : ~0~ (Select Square ~2~ , then Square ~1~ )
• ~f(\\{1,0\\})~ : ~0~ (Select Square ~1~ )
• ~f(\\{1,1\\})~ : ~1~ (Select Square ~1~ )
• ~f(\\{1,2\\})~ : ~0~ (Select Square ~1~ , Square ~2~ , then Square ~1~ )
• ~f(\\{2,0\\})~ : ~2~ (Nothing can be done)
• ~f(\\{2,1\\})~ : ~3~ (Nothing can be done)
• ~f(\\{2,2\\})~ : ~3~ (Select Square ~2~ )

Sample Input 2

20 17

Sample Output 2

983853488

Problem Statement

Ringo has a string ~S~ .

He can perform the following ~N~ kinds of operations any number of times in any order.

• Operation ~i~ : For each of the characters from the ~L_i~ -th through the ~R_i~ -th characters in ~S~ , replace it with its succeeding letter in the English alphabet. (That is, replace a with b , replace b with c and so on.) For z , we assume that its succeeding letter is a .

Ringo loves palindromes and wants to turn ~S~ into a palindrome. Determine whether this is possible.

Constraints

• ~1 \leq |S| \leq 10^5~
• ~S~ consists of lowercase English letters.
• ~1 \leq N \leq 10^5~
• ~1 \leq L_i \leq R_i \leq |S|~

Input

Input is given from Standard Input in the following format:

~S~

~N~

~L_1~ ~R_1~

~L_2~ ~R_2~

~:~

~L_N~ ~R_N~

Output

Print YES if it is possible to turn ~S~ into a palindrome; print NO if it is impossible.

Sample Input 1

bixzja
2
2 3
3 6

Sample Output 1

YES

For example, if we perform Operation ~1~ , ~2~ and ~1~ in this order, ~S~ changes as bixzja → bjyzja → bjzakb → bkaakb and becomes a palindrome.

Sample Input 2

abc
1
2 2

Sample Output 2

NO

Sample Input 3

cassert
4
1 2
3 4
1 1
2 2

Sample Output 3

YES

Problem Statement

Snuke received two matrices ~A~ and ~B~ as birthday presents. Each of the matrices is an ~N~ by ~N~ matrix that consists of only ~0~ and ~1~ .

Then he computed the product of the two matrices, ~C = AB~ . Since he performed all computations in modulo two, ~C~ was also an ~N~ by ~N~ matrix that consists of only ~0~ and ~1~ . For each ~1 ≤ i, j ≤ N~ , you are given ~c_{i, j}~ , the ~(i, j)~ -element of the matrix ~C~ .

However, Snuke accidentally ate the two matrices ~A~ and ~B~ , and now he only knows ~C~ . Compute the number of possible (ordered) pairs of the two matrices ~A~ and ~B~ , modulo ~10^9+7~ .

Constraints

• ~1 ≤ N ≤ 300~
• ~c_{i, j}~ is either ~0~ or ~1~ .

Input

The input is given from Standard Input in the following format:

~N~

~c_{1, 1}~ ~...~ ~c_{1, N}~

~c_{N, 1}~ ~...~ ~c_{N, N}~

Output

Print the number of possible (ordered) pairs of two matrices ~A~ and ~B~ (modulo ~10^9+7~ ).

Sample Input 1

2
0 1
1 0

Sample Output 1

6

Sample Input 2

10
1 0 0 1 1 1 0 0 1 0
0 0 0 1 1 0 0 0 1 0
0 0 1 1 1 1 1 1 1 1
0 1 0 1 0 0 0 1 1 0
0 0 1 0 1 1 1 1 1 1
1 0 0 0 0 1 0 0 0 0
1 1 1 0 1 0 0 0 0 1
0 0 0 1 0 0 1 0 1 0
0 0 0 1 1 1 0 0 0 0
1 0 1 0 0 1 1 1 1 1

Sample Output 2

741992411

Problem Statement

Snuke has a string ~S~ consisting of three kinds of letters: a , b and c .

He has a phobia for palindromes, and wants to permute the characters in ~S~ so that ~S~ will not contain a palindrome of length ~2~ or more as a substring. Determine whether this is possible.

Constraints

• ~1 \leq |S| \leq 10^5~
• ~S~ consists of a , b and c .

Input

Input is given from Standard Input in the following format:

~S~

Output

If the objective is achievable, print YES ; if it is unachievable, print NO .

Sample Input 1

abac

Sample Output 1

YES

As it stands now, ~S~ contains a palindrome aba , but we can permute the characters to get acba , for example, that does not contain a palindrome of length ~2~ or more.

Sample Input 2

aba

Sample Output 2

NO

Sample Input 3

babacccabab

Sample Output 3

YES

Problem Statement

Snuke received ~N~ intervals as a birthday present. The ~i~ -th interval was ~[-L_i, R_i]~ . It is guaranteed that both ~L_i~ and ~R_i~ are positive. In other words, the origin is strictly inside each interval.

Snuke doesn't like overlapping intervals, so he decided to move some intervals. For any positive integer ~d~ , if he pays ~d~ dollars, he can choose one of the intervals and move it by the distance of ~d~ . That is, if the chosen segment is ~[a, b]~ , he can change it to either ~[a+d, b+d]~ or ~[a-d, b-d]~ .

He can repeat this type of operation arbitrary number of times. After the operations, the intervals must be pairwise disjoint (however, they may touch at a point). Formally, for any two intervals, the length of the intersection must be zero.

Compute the minimum cost required to achieve his goal.

Constraints

• ~1 ≤ N ≤ 5000~
• ~1 ≤ L_i, R_i ≤ 10^9~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~

~L_1~ ~R_1~

~L_N~ ~R_N~

Output

Print the minimum cost required to achieve his goal.

Sample Input 1

4
2 7
2 5
4 1
7 5

Sample Output 1

22

One optimal solution is as follows:

• Move the interval ~[-2, 7]~ to ~[6, 15]~ with ~8~ dollars
• Move the interval ~[-2, 5]~ to ~[-1, 6]~ with ~1~ dollars
• Move the interval ~[-4, 1]~ to ~[-6, -1]~ with ~2~ dollars
• Move the interval ~[-7, 5]~ to ~[-18, -6]~ with ~11~ dollars

The total cost is ~8 + 1 + 2 + 11 = 22~ dollars.

Sample Input 2

20
97 2
75 25
82 84
17 56
32 2
28 37
57 39
18 11
79 6
40 68
68 16
40 63
93 49
91 10
55 68
31 80
57 18
34 28
76 55
21 80

Sample Output 2

7337

Problem Statement

You are given a string ~S~ .

Takahashi can insert the character A at any position in this string any number of times.

Can he change ~S~ into AKIHABARA ?

Constraints

• ~1 \leq |S| \leq 50~
• ~S~ consists of uppercase English letters.

Input

Input is given from Standard Input in the following format:

~S~

Output

If it is possible to change ~S~ into AKIHABARA , print YES ; otherwise, print NO .

Sample Input 1

KIHBR

Sample Output 1

YES

Insert one A at each of the four positions: the beginning, immediately after H , immediately after B and the end.

Sample Input 2

AKIBAHARA

Sample Output 2

NO

The correct spell is AKIHABARA .

Sample Input 3

AAKIAHBAARA

Sample Output 3

NO

Problem Statement

In some place in the Arctic Ocean, there are ~H~ rows and ~W~ columns of ice pieces floating on the sea. We regard this area as a grid, and denote the square at the ~i~ -th row and ~j~ -th column as Square ~(i,j)~ . The ice piece floating in each square is either thin ice or an iceberg, and a penguin lives in one of the squares that contain thin ice. There are no ice pieces floating outside the grid.

The ice piece at Square ~(i,j)~ is represented by the character ~S_{i,j}~ . ~S_{i,j}~ is + , # or P , each of which means the following:

• + : Occupied by thin ice.
• # : Occupied by an iceberg.
• P : Occupied by thin ice. The penguin lives here.

When summer comes, unstable thin ice that is not held between some pieces of ice collapses one after another. Formally, thin ice at Square ~(i,j)~ will collapse when it does NOT satisfy either of the following conditions:

• Both Square ~(i-1,j)~ and Square ~(i+1,j)~ are occupied by an iceberg or uncollapsed thin ice.
• Both Square ~(i,j-1)~ and Square ~(i,j+1)~ are occupied by an iceberg or uncollapsed thin ice.

When a collapse happens, it may cause another. Note that icebergs do not collapse.

Now, a mischievous tourist comes here. He will do a little work so that, when summer comes, the thin ice inhabited by the penguin will collapse. He can smash an iceberg with a hammer to turn it to thin ice. At least how many icebergs does he need to smash?

Constraints

• ~1 \leq H,W \leq 40~
• ~S_{i,j}~ is + , # or P .
• ~S~ contains exactly one P .

Input

Input is given from Standard Input in the following format:

~H~ ~W~

~S_{1,1}~ ~S_{1,2}~ ~...~ ~S_{1,W}~

~S_{2,1}~ ~S_{2,2}~ ~...~ ~S_{2,W}~

~:~

~S_{H,1}~ ~S_{H,2}~ ~...~ ~S_{H,W}~

Output

Print the minimum number of icebergs that needs to be changed to thin ice in order to cause the collapse of the thin ice inhabited by the penguin when summer comes.

Sample Input 1

3 3
+#+
#P#
+#+

Sample Output 1

2

For example, when the right and bottom icebergs are changed to thin ice, collapses happen as follows:

+#+    .#.    .#.    .#.
#P+ -> #P+ -> #P. -> #..
+++    .+.    ...    ...

Sample Input 2

6 6
#+++++
+++#++
#+++++
+++P+#
+##+++
++++#+

Sample Output 2

1

Sample Input 3

40 40
#++#+++++#+#+#+##+++++++##+#+++#++##++##
+##++++++++++#+###+##++++#+++++++++#++##
+++#+++++#++#++####+++#+#+###+++##+++#++
+++#+######++##+#+##+#+++#+++++++++#++#+
+++##+#+#++#+++#++++##+++++++++#++#+#+#+
#++#+++#+#++++##+#+#+++##+#+##+#++++##++
++#+##+++#++####+#++##++#+++#+#+#++++#++
+#+###++++++##++++++#++##+#####++#++##++
##+##+#+++#+#+##++#+###+######++++#+###+
+++#+++##+#####+#+#++++#+#+++++#+##++##+
#+++#+##+++++++#++#++++++++++###+#++#+#+
##+++##++#+++++#++++#++#+##++#+#+#++##+#
##+++#+###+++++##++#+#+++####+#+++++#+++
+++#++#++#+++++++++#++###++++++++###+##+
++#+++#++++++#####++##++#+++#+++++#++++#
++#++#+##++++#####+###+++####+#+#+######
++++++##+++++##+++++#++###++#++##+++++++
+#++++##++++++#++++#+#++++#++++##+++##+#
+++++++#+#++##+##+#+++++++###+###++##+++
++++++#++###+#+#+++##+#++++++#++#+#++#+#
##+##++++++#+++++#++#+#++##+++#+#+++##+#
#+++#+#+##+#+##++#P#++#++++++##++#+#++##
#+++#++##+##+#++++#++#++##++++++#+#+#+++
++++####+#++#####+++#+###+#++###++++#++#
#+#++####++##++#+#+#+##+#+#+##++++##++#+
+###+###+#+##+++#++++++#+#++++###+#+++++
+++#+++++#+++#+++++##++++++++###++#+#+++
+#+#++#+#++++++###+#++##+#+##+##+#+#####
#++++++++#+#+###+######++#++#+++++++++++
##+++##+#+#++#++#++#++++++#++##+#+#++###
+#+#+#+++++++#+++++++######+##++#++##+##
++#+++#+###+#++###+++#+++#+#++++#+###+++
#+#+###++#+#####+++++#+####++#++#+###+++
+#+##+#++#++##+++++++######++#++++++++++
+####+#+#+++++##+#+#++#+#++#+++##++++#+#
#++##++#+#+++++##+#++++####+++++###+#+#+
##+#++#++#+##+#+#++##++###+###+#+++++##+
##++###+###+#+#++#++#########+++###+#+##
+++#+++#++++++++++#+#+++#++#++###+####+#
++##+###+++++++##+++++#++#++++++++++++++

Sample Output 3

151

Sample Input 4

1 1
P

Sample Output 4

0

Problem Statement

Consider all integers between ~1~ and ~2N~ , inclusive. Snuke wants to divide these integers into ~N~ pairs such that:

• Each integer between ~1~ and ~2N~ is contained in exactly one of the pairs.
• In exactly ~A~ pairs, the difference between the two integers is ~1~ .
• In exactly ~B~ pairs, the difference between the two integers is ~2~ .
• In exactly ~C~ pairs, the difference between the two integers is ~3~ .

Note that the constraints guarantee that ~N = A + B + C~ , thus no pair can have the difference of ~4~ or more.

Compute the number of ways to do this, modulo ~10^9+7~ .

Constraints

• ~1 ≤ N ≤ 5000~
• ~0 ≤ A, B, C~
• ~A + B + C = N~

Input

The input is given from Standard Input in the following format:

~N~ ~A~ ~B~ ~C~

Output

Print the answer.

Sample Input 1

3 1 2 0

Sample Output 1

2

There are two possibilities: ~1-2, 3-5, 4-6~ or ~1-3, 2-4, 5-6~ .

Sample Input 2

600 100 200 300

Sample Output 2

522158867

Problem Statement

In the final of CODE FESTIVAL in some year, there are ~N~ participants. The height and power of Participant ~i~ is ~H_i~ and ~P_i~ , respectively.

Ringo is hosting a game of stacking zabuton (cushions).

The participants will line up in a row in some order, and they will in turn try to add zabuton to the stack of zabuton. Initially, the stack is empty. When it is Participant ~i~ 's turn, if there are ~H_i~ or less zabuton already stacked, he/she will add exactly ~P_i~ zabuton to the stack. Otherwise, he/she will give up and do nothing.

Ringo wants to maximize the number of participants who can add zabuton to the stack. How many participants can add zabuton to the stack in the optimal order of participants?

Constraints

• ~1 \leq N \leq 5000~
• ~0 \leq H_i \leq 10^9~
• ~1 \leq P_i \leq 10^9~

Input

Input is given from Standard Input in the following format:

~N~

~H_1~ ~P_1~

~H_2~ ~P_2~

~:~

~H_N~ ~P_N~

Output

Print the maximum number of participants who can add zabuton to the stack.

Sample Input 1

3
0 2
1 3
3 4

Sample Output 1

2

When the participants line up in the same order as the input, Participants ~1~ and ~3~ will be able to add zabuton.

On the other hand, there is no order such that all three participants can add zabuton. Thus, the answer is ~2~ .

Sample Input 2

3
2 4
3 1
4 1

Sample Output 2

3

When the participants line up in the order ~2~ , ~3~ , ~1~ , all of them will be able to add zabuton.

Sample Input 3

10
1 3
8 4
8 3
9 1
6 4
2 3
4 2
9 2
8 3
0 1

Sample Output 3

5

Problem Statement

Ringo has a tree with ~N~ vertices. The ~i~ -th of the ~N-1~ edges in this tree connects Vertex ~A_i~ and Vertex ~B_i~ and has a weight of ~C_i~ . Additionally, Vertex ~i~ has a weight of ~X_i~ .

Here, we define ~f(u,v)~ as the distance between Vertex ~u~ and Vertex ~v~ , plus ~X_u + X_v~ .

We will consider a complete graph ~G~ with ~N~ vertices. The cost of its edge that connects Vertex ~u~ and Vertex ~v~ is ~f(u,v)~ . Find the minimum spanning tree of ~G~ .

Constraints

• ~2 \leq N \leq 200,000~
• ~1 \leq X_i \leq 10^9~
• ~1 \leq A_i,B_i \leq N~
• ~1 \leq C_i \leq 10^9~
• The given graph is a tree.
• All input values are integers.

Input

Input is given from Standard Input in the following format:

~N~

~X_1~ ~X_2~ ~...~ ~X_N~

~A_1~ ~B_1~ ~C_1~

~A_2~ ~B_2~ ~C_2~

~:~

~A_{N-1}~ ~B_{N-1}~ ~C_{N-1}~

Output

Print the cost of the minimum spanning tree of ~G~ .

Sample Input 1

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

Sample Output 1

22

We connect the following pairs: Vertex ~1~ and ~2~ , Vertex ~1~ and ~4~ , Vertex ~3~ and ~4~ . The costs are ~5~ , ~8~ and ~9~ , respectively, for a total of ~22~ .

Sample Input 2

6
44 23 31 29 32 15
1 2 10
1 3 12
1 4 16
4 5 8
4 6 15

Sample Output 2

359

Sample Input 3

2
1000000000 1000000000
2 1 1000000000

Sample Output 3

3000000000