Problem Statement

You are given a string S of length N and another string T of length M. These strings consist of lowercase English letters.

A string X is called a good string when the following conditions are all met:

• Let L be the length of X. L is divisible by both N and M.
• Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.
• Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.

Determine if there exists a good string. If it exists, find the length of the shortest such string.

Constraints

• 1 \leq N,M \leq 10^5
• S and T consist of lowercase English letters.
• |S|=N
• |T|=M

Sample Input 1

3 2
acp
ae

Sample Output 1

6

For example, the string accept is a good string. There is no good string shorter than this, so the answer is 6.

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45

Problem Statement

There are N blocks arranged in a row, numbered 1 to N from left to right. Each block has a weight, and the weight of Block i is A_i. Snuke will perform the following operation on these blocks N times:

• Choose one block that is still not removed, and remove it. The cost of this operation is the sum of the weights of the blocks that are connected to the block being removed (including itself). Here, two blocks x and y ( x \leq y ) are connected when, for all z ( x \leq z \leq y ), Block z is still not removed.

There are N! possible orders in which Snuke removes the blocks. For all of those N! orders, find the total cost of the N operations, and calculate the sum of those N! total costs. As the answer can be extremely large, compute the sum modulo 10^9+7.

Constraints

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

Sample Input 1

2
1 2

Sample Output 1

9

First, we will consider the order "Block 1 -> Block 2". In the first operation, the cost of the operation is 1+2=3, as Block 1 and 2 are connected. In the second operation, the cost of the operation is 2, as only Block 2 remains. Thus, the total cost of the two operations for this order is 3+2=5.

Then, we will consider the order "Block 2 -> Block 1". In the first operation, the cost of the operation is 1+2=3, as Block 1 and 2 are connected. In the second operation, the cost of the operation is 1, as only Block 1 remains. Thus, the total cost of the two operations for this order is 3+1=4.

Therefore, the answer is 5+4=9.

Sample Input 2

4
1 1 1 1

Sample Output 2

212

Sample Input 3

10
1 2 4 8 16 32 64 128 256 512

Sample Output 3

880971923

Problem Statement

We have a directed weighted graph with N vertices. Each vertex has two integers written on it, and the integers written on Vertex i are A_i and B_i.

In this graph, there is an edge from Vertex x to Vertex y for all pairs 1 \leq x,y \leq N, and its weight is {\rm min}(A_x,B_y).

We will consider a directed cycle in this graph that visits every vertex exactly once. Find the minimum total weight of the edges in such a cycle.

Constraints

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

Sample Input 1

3
1 5
4 2
6 3

Sample Output 1

7

Consider the cycle 1→3→2→1. The weights of those edges are {\rm min}(A_1,B_3)=1, {\rm min}(A_3,B_2)=2 and {\rm min}(A_2,B_1)=4, for a total of 7. As there is no cycle with a total weight of less than 7, the answer is 7.

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

10

Sample Input 3

6
19 92
64 64
78 48
57 33
73 6
95 73

Sample Output 3

227

Problem Statement

There are 2N points evenly spaced on the circumference of a circle. These points are numbered 1 to 2N in clockwise order, starting from some of them.

Snuke will divide these points into N pairs, then for each pair, he will draw a line segment connecting the two points. After the line segments are drawn, two points are connected when one can reach from one of those points to the other by traveling only on the line segments. The number of the connected parts here is the number of the connected components in the graph with 2N vertices, corresponding to the 2N points, where every pair of vertices corresponding to two connected points is connected with an edge.

Snuke has already decided K of the pairs, and the i-th of them is a pair of Point A_i and Point B_i.

He is thinking of trying all possible ways to make the remaining N-K pairs and counting the number of the connected parts for each of those ways. Find the sum of those numbers of the connected parts. As the answer can be extremely large, compute the sum modulo 10^9+7.

Constraints

• 1 \leq N \leq 300
• 0 \leq K \leq N
• 1 \leq A_i,B_i \leq 2N
• A_1,\ A_2,\ ...\ A_K,\ B_1,\ B_2,\ ...\ B_K are all distinct.
• All values in input are integers.

Sample Input 1

2 0

Sample Output 1

5

There are three ways to draw line segments, as shown below, and the number of the connected parts for these ways are 2, 2 and 1, respectively. Thus, the answer is 2+2+1=5.

Sample Input 2

4 2
5 2
6 1

Sample Output 2

6

Sample Input 3

20 10
10 18
11 17
14 7
4 6
30 28
19 24
29 22
25 32
38 34
36 39

Sample Output 3

27087418

Problem Statement

You are given P, a permutation of (1,\ 2,\ ...\ N).

A string S of length N consisting of 0 and 1 is a good string when it meets the following criterion:

• The sequences X and Y are constructed as follows:
  • First, let X and Y be empty sequences.
  • For each i=1,\ 2,\ ...\ N, in this order, append P_i to the end of X if S_i= 0, and append it to the end of Y if S_i= 1.
• If X and Y have the same number of high elements, S is a good string. Here, the i-th element of a sequence is called high when that element is the largest among the elements from the 1-st to i-th element in the sequence.

Determine if there exists a good string. If it exists, find the lexicographically smallest such string.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq N
• P_1,\ P_2,\ ...\ P_N are all distinct.
• All values in input are integers.

Sample Input 1

6
3 1 4 6 2 5

Sample Output 1

001001

Let S= 001001. Then, X=(3,\ 1,\ 6,\ 2) and Y=(4,\ 5). The high elements in X is the first and third elements, and the high elements in Y is the first and second elements. As they have the same number of high elements, 001001 is a good string. There is no good string that is lexicographically smaller than this, so the answer is 001001.

Sample Input 2

5
1 2 3 4 5

Sample Output 2

-1

Sample Input 3

7
1 3 2 5 6 4 7

Sample Output 3

0001101

Sample Input 4

30
1 2 6 3 5 7 9 8 11 12 10 13 16 23 15 18 14 24 22 26 19 21 28 17 4 27 29 25 20 30

Sample Output 4

000000000001100101010010011101

Problem Statement

Problem F and F2 are the same problem, but with different constraints and time limits.

We have a board divided into N horizontal rows and N vertical columns of square cells. The cell at the i-th row from the top and the j-th column from the left is called Cell (i,j). Each cell is either empty or occupied by an obstacle. Also, each empty cell has a digit written on it. If A_{i,j}= 1, 2, ..., or 9, Cell (i,j) is empty and the digit A_{i,j} is written on it. If A_{i,j}= #, Cell (i,j) is occupied by an obstacle.

Cell Y is reachable from cell X when the following conditions are all met:

• Cells X and Y are different.
• Cells X and Y are both empty.
• One can reach from Cell X to Cell Y by repeatedly moving right or down to an adjacent empty cell.

Consider all pairs of cells (X,Y) such that cell Y is reachable from cell X. Find the sum of the products of the digits written on cell X and cell Y for all of those pairs.

Constraints

• 1 \leq N \leq 500
• A_{i,j} is one of the following characters: 1, 2, ... 9 and #.

Sample Input 1

2
11
11

Sample Output 1

5

There are five pairs of cells (X,Y) such that cell Y is reachable from cell X, as follows:

• X=(1,1), Y=(1,2)
• X=(1,1), Y=(2,1)
• X=(1,1), Y=(2,2)
• X=(1,2), Y=(2,2)
• X=(2,1), Y=(2,2)

The product of the digits written on cell X and cell Y is 1 for all of those pairs, so the answer is 5.

Sample Input 2

4
1111
11#1
1#11
1111

Sample Output 2

47

Sample Input 3

10
76##63##3#
8445669721
75#9542133
3#285##445
749632##89
2458##9515
5952578#77
1#3#44196#
4355#99#1#
#298#63587

Sample Output 3

36065

Sample Input 4

10
4177143673
7#########
5#1716155#
6#4#####5#
2#3#597#6#
6#9#8#3#5#
5#2#899#9#
1#6#####6#
6#5359657#
5#########

Sample Output 4

6525

Problem Statement

Problem F and F2 are the same problem, but with different constraints and time limits.

We have a board divided into N horizontal rows and N vertical columns of square cells. The cell at the i-th row from the top and the j-th column from the left is called Cell (i,j). Each cell is either empty or occupied by an obstacle. Also, each empty cell has a digit written on it. If A_{i,j}= 1, 2, ..., or 9, Cell (i,j) is empty and the digit A_{i,j} is written on it. If A_{i,j}= #, Cell (i,j) is occupied by an obstacle.

Cell Y is reachable from cell X when the following conditions are all met:

• Cells X and Y are different.
• Cells X and Y are both empty.
• One can reach from Cell X to Cell Y by repeatedly moving right or down to an adjacent empty cell.

Consider all pairs of cells (X,Y) such that cell Y is reachable from cell X. Find the sum of the products of the digits written on cell X and cell Y for all of those pairs.

Constraints

• 1 \leq N \leq 1500
• A_{i,j} is one of the following characters: 1, 2, ... 9 and #.

Sample Input 1

2
11
11

Sample Output 1

5

There are five pairs of cells (X,Y) such that cell Y is reachable from cell X, as follows:

• X=(1,1), Y=(1,2)
• X=(1,1), Y=(2,1)
• X=(1,1), Y=(2,2)
• X=(1,2), Y=(2,2)
• X=(2,1), Y=(2,2)

The product of the digits written on cell X and cell Y is 1 for all of those pairs, so the answer is 5.

Sample Input 2

4
1111
11#1
1#11
1111

Sample Output 2

47

Sample Input 3

10
76##63##3#
8445669721
75#9542133
3#285##445
749632##89
2458##9515
5952578#77
1#3#44196#
4355#99#1#
#298#63587

Sample Output 3

36065

Sample Input 4

10
4177143673
7#########
5#1716155#
6#4#####5#
2#3#597#6#
6#9#8#3#5#
5#2#899#9#
1#6#####6#
6#5359657#
5#########

Sample Output 4

6525