Problem Statement

Takahashi is designing an encryption system that transmits data through N servers.

In this system, N servers are connected in a line, numbered 1, 2, \ldots, N from left to right. Each server i (1 \leq i \leq N) has an encryption key A_i (a non-negative integer) assigned to it.

Prior to data transmission, the encryption key B_i that each server actually uses is determined by the following rules. The value of B_i is determined solely based on the original encryption keys A_1, A_2, \ldots, A_N, and is finalized simultaneously for all servers.

• A server j (2 \leq j \leq N-1) is called a "sandwiched anomalous server" if it satisfies the following condition: A_{j-1} = A_{j+1} and A_{j-1} \neq A_j. In other words, the encryption keys of both neighboring servers are equal, and its own encryption key differs from theirs.
• For a server j that is determined to be a "sandwiched anomalous server", B_j = 0.
• For all other servers j (server 1, server N, and servers that do not satisfy the above condition), B_j = A_j.

Next, non-negative integer data X is transmitted from left to right according to the following rules. Let D_0 = X, and each server i (in order i = 1, 2, \ldots, N) receives data D_{i-1} and computes D_i = D_{i-1} \oplus B_i (\oplus denotes the bitwise exclusive OR). The data D_0 received by server 1 is the data X sent by Takahashi, and D_N computed by server N is the final output data.

Given the data X that Takahashi sends to server 1 and the encryption key of each server, find the final output data D_N.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 0 \leq X \leq 10^9
• 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
• All input values are integers

Sample Input 1

5 10
1 2 1 3 3

Sample Output 1

10

Sample Input 2

3 5
7 7 7

Sample Output 2

2

Sample Input 3

8 123
8 1 8 3 3 5 7 5

Sample Output 3

123

Sample Input 4

20 999999999
0 1000000000 0 5 5 7 8 7 3 3 3 9 1 9 4 6 4 2 2 2

Sample Output 4

999999998

Sample Input 5

1 0
0

Sample Output 5

0

Problem Statement

Takahashi is developing a book search system for a library. The library has N bookshelves, and the i-th bookshelf (1 \leq i \leq N) contains K_i books. The title of the j-th book on the i-th bookshelf is denoted by S_{i,j}. All titles are strings consisting only of lowercase English letters.

In this search system, when a user inputs a string as a search query, the system finds bookshelves that contain books related to the query. Since users often do not remember the exact title of a book, they may pick some characters from the title in order (not necessarily consecutive) and input them as a search. Therefore, this system adopts search by subsequence.

Here, a string T is a subsequence of a string S if T can be obtained by removing 0 or more characters from S (without changing the order of the remaining characters). For example, ace is a subsequence of abcde, but aec is not a subsequence of abcde.

The i-th bookshelf hits a query string T if T is a subsequence of at least one of S_{i,1}, S_{i,2}, \ldots, S_{i,K_i}. In other words, there exists at least one book on that bookshelf whose title contains T as a subsequence.

You are given Q search queries. Let T_j be the string of the j-th query. For each query, find the number of bookshelves that hit the query T_j.

Constraints

• 1 \leq N \leq 100
• 1 \leq K_i \leq 5000
• 1 \leq \displaystyle\sum_{i=1}^{N} K_i \leq 5000
• The length of each title S_{i,j} is between 1 and 1000, inclusive
• \displaystyle\sum_{i=1}^{N}\sum_{j=1}^{K_i} |S_{i,j}| \leq 10^5
• 1 \leq Q \leq 200
• The length of each query T_j is between 1 and 1000, inclusive
• \displaystyle\sum_{j=1}^{Q} |T_j| \leq 10^5
• S_{i,j} and T_j are strings consisting only of lowercase English letters

Here, |X| denotes the length of string X.

Sample Input 1

2
2 algorithm data
2 string graph
3
ag
ri
zz

Sample Output 1

1
2
0

Sample Input 2

3
1 programming
2 problem process
2 apple application
4
po
pin
pp
rm

Sample Output 2

3
2
1
2

Sample Input 3

5
3 binary search tree
2 dynamic programming
1 graph
2 stack queue
3 linked list array
5
ar
ra
i
zzz
ee

Sample Output 3

2
3
3
0
2

Problem Statement

Takahashi is investing in N stock issues. The current valuation of the i-th stock is L_i yen.

Takahashi will use K investment chances one by one in order. In each chance, he chooses any one of the N stocks and doubles its current valuation. He may choose the same stock multiple times.

Determine the maximum possible total valuation of all N stocks after all K investment chances have been used, when he chooses the stock in each chance to maximize this total.

Since the answer can be extremely large, output the maximum value modulo 10^9 + 7. Note that the modulo operation is applied only after determining the true maximum value. That is, you should not compare values based on intermediate results taken modulo 10^9 + 7; instead, find the maximum value as a true (unmodded) number, and then output that value modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq K \leq 10^{18}
• 1 \leq L_i \leq 10^9
• All input values are integers.

Sample Input 1

3 2
3 1 2

Sample Output 1

15

Sample Input 2

5 10
4 8 2 5 1

Sample Output 2

8204

Sample Input 3

4 1000000000000000000
1000000000 999999999 999999998 999999997

Sample Output 3

963666195

Problem Statement

Takahashi is trying to create a flower bed in his garden.

A gardening shop sells seedlings of N types of flowers, each numbered from 1 to N. Takahashi examined the appearance of each flower and assigned a beauty value S_i to flower i (beauty values can be negative).

Takahashi will select some of these N types of flowers to plant in the flower bed. However, the number of types of flowers he can select is between 0 and K, inclusive. For each flower, he decides either to "select it and plant one" or "not select it."

Additionally, M gardening contests are held in the town where Takahashi lives. The participation condition for contest j is that at least one type of flower with a number between L_j and R_j (inclusive) is planted in the flower bed. He must participate in all contests whose conditions are satisfied (he cannot decline participation), and by participating in contest j, he receives a prize of P_j.

Takahashi wants to choose the set of flowers to plant in order to maximize (the sum of beauty values of the selected flowers) + (the sum of prizes from all contests he participates in).

Find the maximum value of this quantity. Note that it is allowed to select no flowers at all, in which case both the sum of beauty values and the sum of prizes are 0.

Constraints

• 1 \leq N \leq 15
• 1 \leq K \leq N
• 1 \leq M \leq 15
• -1000 \leq S_i \leq 1000 (1 \leq i \leq N)
• 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
• 1 \leq P_j \leq 1000 (1 \leq j \leq M)
• All input values are integers

Sample Input 1

3 2 1
5 3 -2
1 2 10

Sample Output 1

18

Sample Input 2

3 1 2
-10 -10 -10
1 1 3
2 3 2

Sample Output 2

0

Sample Input 3

6 3 4
10 -5 8 -3 7 -1
1 3 15
2 5 20
4 6 10
1 6 5

Sample Output 3

75

Sample Input 4

10 5 8
100 -50 80 -30 70 -10 60 -40 90 -20
1 3 200
2 5 150
4 7 180
6 10 120
1 5 100
3 8 90
5 10 110
1 10 50

Sample Output 4

1400

Sample Input 5

1 1 1
-1000
1 1 1

Sample Output 5

0

Problem Statement

Takahashi is commentating a marathon with N runners participating.

The runners are running along an infinitely long straight course, all in the same direction. The greater the distance from the starting point, the further ahead a runner is considered to be. Initially (at time 0), runner i (1 \leq i \leq N) is at a position P_i meters from the starting point. Each runner continues running at a constant speed thereafter, and the speed of runner i is V_i meters per second. That is, at time t seconds, the position of runner i is P_i + V_i \times t meters from the starting point.

Takahashi wants to count how many "overtakes" occur during the race to use in his commentary. An "overtake" is defined as follows: for a pair of two distinct runners \{i, j\}, if runner i is behind runner j at time 0 (i.e., P_i < P_j), yet at some time t > 0 runner i is ahead of runner j (i.e., P_i + V_i \times t > P_j + V_j \times t), this counts as one overtake.

All runners have distinct initial positions, and all runners have distinct speeds. Because of this, for any pair of two runners, at most one overtake can occur. Specifically, exactly one overtake occurs if and only if the runner who starts further behind has a greater speed than the runner who starts further ahead.

Find the total number of overtakes that occur from time 0 to the infinite future.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq 10^9
• 1 \leq V_i \leq 10^9
• P_i \neq P_j (i \neq j)
• V_i \neq V_j (i \neq j)
• All input values are integers

Sample Input 1

3
1 3
2 1
3 2

Sample Output 1

2

Sample Input 2

5
10 5
30 1
20 4
50 2
40 3

Sample Output 2

8

Sample Input 3

8
100 80
200 30
150 90
400 10
300 50
250 70
500 20
350 60

Sample Output 3

22