Problem Statement

We have a directed graph with N vertices numbered 1 to N. N strings of length N each, S_1,S_2,\ldots,S_N, represent the edges in the graph. Specifically, S_{i,j} is 1 if there is an edge from Vertex i to Vertex j, and 0 otherwise. The graph has no self-loops and no multi-edges.

Until the graph becomes empty, AtCobear will repeat the following operation:

• Choose one (unerased) vertex uniformly at random (independently from the previous choices). Then, erase that vertex and all vertices that are reachable from the chosen vertex by traversing some edges. Erasing a vertex will also erase the edges incident to it.

Find the expected value of the number of times the operation is done.

Constraints

• 1 \leq N \leq 100
• S_i is a string of length N consisting of 0 and 1.
• S_{i,i}=0

Sample Input 1

3
010
001
010

Sample Output 1

1.66666666666666666667

We have the following three scenarios happening with equal probability:

• Choose Vertex 1 in the first operation, erasing Vertex 1, 2, and 3. The graph is now empty, so we are done.

• Choose Vertex 2 in the first operation, erasing Vertex 2 and 3. Then, choose Vertex 1 in the second operation, erasing Vertex 1. The graph is now empty, so we are done.

• Choose Vertex 3 in the first operation, erasing Vertex 2 and 3. Then, choose Vertex 1 in the second operation, erasing Vertex 1. The graph is now empty, so we are done.

Thus, the expected value of the number of times the operation is done is (1+2+2)/3=5/3.

Sample Input 2

3
000
000
000

Sample Output 2

3.00000000000000000000

There will always be three operations.

Sample Input 3

3
011
101
110

Sample Output 3

1.00000000000000000000

There will always be one operation.

Problem Statement

Given are length-N strings S and T consisting of 0 and 1. You can do the following operation on S any number of times:

• Choose i (2 \leq i \leq N) such that S_i=1, and replace S_i with 0. Additionally, invert S_{i-1}, that is, change it to 1 if it is 0 now and vice versa.

Is it possible to make S exactly match T? If it is possible, how many operations does it take at least?

Constraints

• 1 \leq N \leq 5 \times 10^5
• S is a string of length N consisting of 0 and 1.
• T is a string of length N consisting of 0 and 1.

Sample Input 1

3
001
100

Sample Output 1

2

We can do as follows: 001 → (choose i=3) → 010 → (choose i=2) → 100.

Sample Input 2

3
001
110

Sample Output 2

-1

Sample Input 3

5
10111
01010

Sample Output 3

5

Problem Statement

There are robots on a number line. Specifically, for each i=0,1,2,\cdots,10^{100}, there is exactly one robot called Robot i at coordinate i.

We have many balls. Each of the balls has a positive integer written on it. Integer sequences A and B, each of length N, describe these balls. Specifically, for each i (1 \leq i \leq N), there are B_i balls with A_i written on them.

Now, Snuke will do the following sequence of operations:

• Step 1: Choose zero or more balls and replace the integers written on those balls with positive integers of his choice between 1 and 10^{100} (inclusive). (The new integers can be chosen independently from each other.)

• Step 2: Eat the balls one by one in any order of his choice. Each time he eats a ball, he should do the following:

  • Let v be the integer written on the ball he has just eaten. If Robot v exists, move it so that its coordinate decreases by 1. Here, if there is another robot at the destination, that robot (not Robot v) will be destroyed.

Snuke wants to eat all the balls without destroying Robot 0. Find the minimum number of balls Snuke must choose in Step 1 to achieve his objective.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq A_1 < A_2 < \ldots < A_N \leq 10^9
• 1 \leq B_i \leq 10^9

Sample Input 1

3
1 2 3
1 2 1

Sample Output 1

1

We can achieve the objective by choosing one ball with 2 written on it, rewriting 3 on it, and then eating the balls in the following order:

• Eat the ball with 2 written on it, moving Robot 2 from coordinate 2 to coordinate 1 and destroying Robot 1.

• Eat the ball with 3 written on it, moving Robot 3 from coordinate 3 to coordinate 2.

• Eat the ball with 3 written on it, moving Robot 3 from coordinate 2 to coordinate 1 and destroying Robot 2.

• Eat the ball with 1 written on it. Robot 1 is already destroyed, so nothing happens.

Sample Input 2

4
1 3 5 7
3 1 4 1

Sample Output 2

0

Problem Statement

Given are integers N and M. Find the number, modulo (10^9+7), of length-N sequences (A_1,A_2,\ldots,A_N) that consist of non-negative integers and satisfy the following conditions:

• A_1+A_2+\ldots +A_N = M;
• For every i (2 \leq i \leq N-1), 2 A_i \leq A_{i-1} + A_{i+1}.

Constraints

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

Sample Input 1

3 3

Sample Output 1

7

The following seven sequences satisfy the conditions.

• 0,0,3
• 0,1,2
• 1,0,2
• 1,1,1
• 2,0,1
• 2,1,0
• 3,0,0

Sample Input 2

10 100

Sample Output 2

10804516

Sample Input 3

10000 100000

Sample Output 3

694681734

Problem Statement

Maroon came up with the following problem:

Snuke has an integer sequence a of length N. Initially, a_i=0 for every i (1 \leq i \leq N).

Snuke will repeat the following two operations any number of times in any order:

• Operation 1: Replace a_i with a_i+x, where i (1 \leq i \leq N) and x (x=1 or x=-1) are integers of his choice. The cost of doing this operation once is 1.

• Operation 2: Replace a_i with a_i+x for every i (l \leq i \leq r), where l, r (1 \leq l \leq r \leq N) and x (x=1 or x=-1) are integers of his choice. The cost of doing this operation once is C.

You are given an integer sequence A of length N. Snuke wants to make a_i=A_i for every i. Find the minimum total cost needed to achieve his objective.

However, during the preparation of this problem, too many unexpected solutions were found, so Maroon changed the problem into the following:

Snuke has N integer sequences B_1,B_2,\cdots,B_N and integers C and K. The length of every sequence B_i (1 \leq i \leq N) is K.

Now, he wants to make an integer sequence A of length N and find the answer to the problem above. The value of A_i will be chosen from B_{i,1},B_{i,2},\cdots,B_{i,K}. Here, even if there are duplicated values in B_{i,1},B_{i,2},\cdots,B_{i,K}, we still distinguish those values. That is, there are K^N ways to make A.

Find the sum of the answers to the problem above over all the ways to make A, modulo (10^9+7).

Solve this problem.

Constraints

• 1 \leq N \leq 50
• 1 \leq C \leq N
• 1 \leq K \leq 50
• 1 \leq B_{i,j} \leq 10^9
• All values in input are integers.

Sample Input 1

5 2 1
2
3
1
2
1

Sample Output 1

6

We have A=(2,3,1,2,1). Below is one optimal sequence of operations:

• Let l=1,r=5,x=1 and do Operation 2, resulting in a=(1,1,1,1,1).
• Let l=1,r=4,x=1 and do Operation 2, resulting in a=(2,2,2,2,1).
• Let i=2,x=1 and do Operation 1, resulting in a=(2,3,2,2,1).
• Let i=3,x=-1 and do Operation 1, resulting in a=(2,3,1,2,1).

Sample Input 2

3 2 3
1 2 3
1 2 3
1 2 3

Sample Output 2

126

Sample Input 3

10 4 1
8
10
10
1
5
9
5
5
9
1

Sample Output 3

45

Sample Input 4

10 5 10
79 48 35 56 16 26 37 6 75 23
39 99 57 100 49 90 18 9 12 91
29 97 49 86 30 94 78 63 49 22
100 27 48 91 66 14 6 20 23 84
12 60 99 75 88 95 61 58 20 46
10 11 30 38 55 94 9 52 92 75
27 22 46 85 83 88 50 63 95 91
49 59 19 37 53 27 11 26 2 91
95 36 20 76 84 41 59 95 67 66
52 60 17 11 28 57 75 69 95 24

Sample Output 4

877826779

Problem Statement

Integer sequences A, B and C, each of length N, are given. Snuke is happy if and only if the following condition is met.

• For every integer x, \sum_{1 \leq i \leq N} |A_i-x| \leq \sum_{1 \leq i \leq N} |B_i-x| holds.

He decided to change at least 0 elements of A to become happy. It costs him C_i \times (A_i-t)^2 to change A_i to t. Here, t, the value after the change, should be an integer as well.

Find the minimum possible sum of costs in order for Snuke to become happy.

Constraints

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

Sample Input 1

3
0 1 4
1 2 3
1 3 2

Sample Output 1

6

After the following operations, the sum of costs is 6.

• Change A_1 to 2. This change costs 1 \times (0-2)^2=4.
• Change A_3 to 3. This change costs 2 \times (4-3)^2=2.

After the operations, A=(2,1,3) holds, which makes Snuke happy. It is impossible to achieve the goal with sum of costs less than 6, so the answer is 6.

Sample Input 2

20
185 89 216 105 56 383 193 161 75 196 322 180 390 15 206 78 275 338 225 167
161 77 294 117 22 382 218 140 57 231 343 160 397 8 264 68 301 349 295 157
3 1 3 5 2 1 3 4 1 4 2 2 2 2 5 1 1 5 4 3

Sample Output 2

3758

Sample Input 3

1
0
0
1

Sample Output 3

0