Problem Statement

Gotou just received a dictionary. However, he doesn't recognize the language used in the dictionary. He did some analysis on the dictionary and realizes that the dictionary contains all possible diverse words in lexicographical order.

A word is called diverse if and only if it is a nonempty string of English lowercase letters and all letters in the word are distinct. For example, atcoder, zscoder and agc are diverse words while gotou and connect aren't diverse words.

Given a diverse word S, determine the next word that appears after S in the dictionary, i.e. the lexicographically smallest diverse word that is lexicographically larger than S, or determine that it doesn't exist.

Let X = x_{1}x_{2}...x_{n} and Y = y_{1}y_{2}...y_{m} be two distinct strings. X is lexicographically larger than Y if and only if Y is a prefix of X or x_{j} > y_{j} where j is the smallest integer such that x_{j} \neq y_{j}.

Constraints

• 1 \leq |S| \leq 26
• S is a diverse word.

Sample Input 1

atcoder

Sample Output 1

atcoderb

atcoderb is the lexicographically smallest diverse word that is lexicographically larger than atcoder. Note that atcoderb is lexicographically smaller than b.

Sample Input 2

abc

Sample Output 2

abcd

Sample Input 3

zyxwvutsrqponmlkjihgfedcba

Sample Output 3

-1

This is the lexicographically largest diverse word, so the answer is -1.

Sample Input 4

abcdefghijklmnopqrstuvwzyx

Sample Output 4

abcdefghijklmnopqrstuvx

Problem Statement

Nagase is a top student in high school. One day, she's analyzing some properties of special sets of positive integers.

She thinks that a set S = \{a_{1}, a_{2}, ..., a_{N}\} of distinct positive integers is called special if for all 1 \leq i \leq N, the gcd (greatest common divisor) of a_{i} and the sum of the remaining elements of S is not 1.

Nagase wants to find a special set of size N. However, this task is too easy, so she decided to ramp up the difficulty. Nagase challenges you to find a special set of size N such that the gcd of all elements are 1 and the elements of the set does not exceed 30000.

Constraints

• 3 \leq N \leq 20000

Sample Input 1

3

Sample Output 1

2 5 63

\{2, 5, 63\} is special because gcd(2, 5 + 63) = 2, gcd(5, 2 + 63) = 5, gcd(63, 2 + 5) = 7. Also, gcd(2, 5, 63) = 1. Thus, this set satisfies all the criteria.

Note that \{2, 4, 6\} is not a valid solution because gcd(2, 4, 6) = 2 > 1.

Sample Input 2

4

Sample Output 2

2 5 20 63

\{2, 5, 20, 63\} is special because gcd(2, 5 + 20 + 63) = 2, gcd(5, 2 + 20 + 63) = 5, gcd(20, 2 + 5 + 63) = 10, gcd(63, 2 + 5 + 20) = 9. Also, gcd(2, 5, 20, 63) = 1. Thus, this set satisfies all the criteria.

Problem Statement

Aoki is playing with a sequence of numbers a_{1}, a_{2}, ..., a_{N}. Every second, he performs the following operation :

• Choose a positive integer k. For each element of the sequence v, Aoki may choose to replace v with its remainder when divided by k, or do nothing with v. The cost of this operation is 2^{k} (regardless of how many elements he changes).

Aoki wants to turn the sequence into b_{1}, b_{2}, ..., b_{N} (the order of the elements is important). Determine if it is possible for Aoki to perform this task and if yes, find the minimum cost required.

Constraints

• 1 \leq N \leq 50
• 0 \leq a_{i}, b_{i} \leq 50
• All values in the input are integers.

Sample Input 1

3
19 10 14
0 3 4

Sample Output 1

160

Here's a possible sequence of operations :

• Choose k = 7. Replace 19 with 5, 10 with 3 and do nothing to 14. The sequence is now 5, 3, 14.

• Choose k = 5. Replace 5 with 0, do nothing to 3 and replace 14 with 4. The sequence is now 0, 3, 4.

The total cost is 2^{7} + 2^{5} = 160.

Sample Input 2

3
19 15 14
0 0 0

Sample Output 2

2

Aoki can just choose k = 1 and turn everything into 0. The cost is 2^{1} = 2.

Sample Input 3

2
8 13
5 13

Sample Output 3

-1

The task is impossible because we can never turn 8 into 5 using the given operation.

Sample Input 4

4
2 0 1 8
2 0 1 8

Sample Output 4

0

Aoki doesn't need to do anything here. The cost is 0.

Sample Input 5

1
50
13

Sample Output 5

137438953472

Beware of overflow issues.

Problem Statement

Yui loves shopping. She lives in Yamaboshi City and there is a train service in the city. The city can be modelled as a very long number line. Yui's house is at coordinate 0.

There are N shopping centres in the city, located at coordinates x_{1}, x_{2}, ..., x_{N} respectively. There are N + 2 train stations, one located at coordinate 0, one located at coordinate L, and one located at each shopping centre.

At time 0, the train departs from position 0 to the positive direction. The train travels at a constant speed of 1 unit per second. At time L, the train will reach the last station, the station at coordinate L. The train immediately moves in the opposite direction at the same speed. At time 2L, the train will reach the station at coordinate 0 and it immediately moves in the opposite direction again. The process repeats indefinitely.

When the train arrives at a station where Yui is located, Yui can board or leave the train immediately. At time 0, Yui is at the station at coordinate 0.

Yui wants to go shopping in all N shopping centres, in any order, and return home after she finishes her shopping. She needs to shop for t_{i} seconds in the shopping centre at coordinate x_{i}. She must finish her shopping in one shopping centre before moving to the next shopping centre. Yui can immediately start shopping when she reaches a station with a shopping centre and she can immediately board the train when she finishes shopping.

Yui wants to spend the minimum amount of time to finish her shopping. Can you help her determine the minimum number of seconds required to complete her shopping?

Constraints

• 1 \leq N \leq 300000
• 1 \leq L \leq 10^{9}
• 0 < x_{1} < x_{2} < ... < x_{N} < L
• 1 \leq t_{i} \leq 10^{9}
• All values in the input are integers.

Partial Score

• 1000 points will be awarded for passing the testset satisfying 1 \leq N \leq 3000.

Sample Input 1

2 10
5 8
10 4

Sample Output 1

40

Here's one possible way for Yui to finish her shopping :

• Travel to the station at coordinate 8 with the train. She arrives at coordinate 8 at time 8.

• Shop in the shopping centre at coordinate 8. She finishes her shopping at time 12.

• The train arrives at coordinate 8 at time 12. She boards the train which is currently moving in the negative direction.

• She arrives at coordinate 5 at time 15. She finishes her shopping at time 25.

• The train arrives at coordinate 5 at time 25. She boards the train which is currently moving in the positive direction.

• She arrives at coordinate L = 10 at time 30. The train starts moving in the negative direction immediately.

• She arrives at coordinate 0 at time 40, ending the trip.

Sample Input 2

2 10
5 8
10 5

Sample Output 2

60

Sample Input 3

5 100
10 19 28 47 68
200 200 200 200 200

Sample Output 3

1200

Sample Input 4

8 1000000000
2018 123456 1719128 1929183 9129198 10100101 77777777 120182018
99999999 1000000000 1000000000 11291341 1 200 1 123812831

Sample Output 4

14000000000

Beware of overflow issues.

Problem Statement

Taichi thinks a binary string X of odd length N is beautiful if it is possible to apply the following operation \frac{N-1}{2} times so that the only character of the resulting string is 1 :

• Choose three consecutive bits of X and replace them by their median. For example, we can turn 00110 into 010 by applying the operation to the middle three bits.

Taichi has a string S consisting of characters 0, 1 and ?. Taichi wants to know the number of ways to replace the question marks with 1 or 0 so that the resulting string is beautiful, modulo 10^{9} + 7.

Constraints

• 1 \leq |S| \leq 300000
• |S| is odd.
• All characters of S are either 0, 1 or ?.

Sample Input 1

1??00

Sample Output 1

2

There are 4 ways to replace the question marks with 0 or 1 :

• 11100 : This string is beautiful because we can first perform the operation on the last 3 bits to get 110 and then on the only 3 bits to get 1.

• 11000 : This string is beautiful because we can first perform the operation on the last 3 bits to get 110 and then on the only 3 bits to get 1.

• 10100 : This string is not beautiful because there is no sequence of operations such that the final string is 1.

• 10000 : This string is not beautiful because there is no sequence of operations such that the final string is 1.

Thus, there are 2 ways to form a beautiful string.

Sample Input 2

?

Sample Output 2

1

In this case, 1 is the only beautiful string.

Sample Input 3

?0101???10???00?1???????????????0????????????1????0

Sample Output 3

402589311

Remember to output your answer modulo 10^{9} + 7.

Problem Statement

Let X = 10^{100}. Inaba has N checker pieces on the number line, where the i-th checker piece is at coordinate X^{i} for all 1 \leq i \leq N.

Every second, Inaba chooses two checker pieces, A and B, and move A to the symmetric point of its current position with respect to B. After that, B is removed. (It is possible that A and B occupy the same position, and it is also possible for A to occupy the same position as another checker piece after the move).

After N - 1 seconds, only one checker piece will remain. Find the number of distinct possible positions of that checker piece, modulo 10^{9} + 7.

Constraints

• 1 \leq N \leq 50
• N is an integer.

Sample Input 1

3

Sample Output 1

12

There are 3 checker pieces, positioned at 10^{100}, 10^{200}, 10^{300} respectively. Call them A, B, C respectively.

Here are two (of the 12) possible sequence of moves :

• Let A jump over B in the first second, and let A jump over C in the second second. The final position of A is 2 \times 10^{300} - 2 \times 10^{200} + 10^{100}.

• Let C jump over A in the first second, and let B jump over C in the second second. The final position of B is -2 \times 10^{300} - 10^{200} + 4 \times 10^{100}.

There are a total of 3 \times 2 \times 2 = 12 possible sequence of moves, and the final piece are in different positions in all of them.

Sample Input 2

4

Sample Output 2

84

Sample Input 3

22

Sample Output 3

487772376

Remember to output your answer modulo 10^{9} + 7.