Problem Statement

Given is a string S. Let T be the concatenation of K copies of S. We can repeatedly perform the following operation: choose a character in T and replace it with a different character. Find the minimum number of operations required to satisfy the following condition: any two adjacent characters in T are different.

Constraints

• 1 \leq |S| \leq 100
• S consists of lowercase English letters.
• 1 \leq K \leq 10^9
• K is an integer.

Sample Input 1

issii
2

Sample Output 1

4

T is issiiissii. For example, we can rewrite it into ispiqisyhi, and now any two adjacent characters are different.

Sample Input 2

qq
81

Sample Output 2

81

Sample Input 3

cooooooooonteeeeeeeeeest
999993333

Sample Output 3

8999939997

Problem Statement

Given is a connected undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the edges are described by a grid of characters S. If S_{i,j} is 1, there is an edge connecting Vertex i and j; otherwise, there is no such edge.

Determine whether it is possible to divide the vertices into non-empty sets V_1, \dots, V_k such that the following condition is satisfied. If the answer is yes, find the maximum possible number of sets, k, in such a division.

• Every edge connects two vertices belonging to two "adjacent" sets. More formally, for every edge (i,j), there exists 1\leq t\leq k-1 such that i\in V_t,j\in V_{t+1} or i\in V_{t+1},j\in V_t holds.

Constraints

• 2 \leq N \leq 200
• S_{i,j} is 0 or 1.
• S_{i,i} is 0.
• S_{i,j}=S_{j,i}
• The given graph is connected.
• N is an integer.

Sample Input 1

2
01
10

Sample Output 1

2

We can put Vertex 1 in V_1 and Vertex 2 in V_2.

Sample Input 2

3
011
101
110

Sample Output 2

-1

Sample Input 3

6
010110
101001
010100
101000
100000
010000

Sample Output 3

4

Problem Statement

Given are integers N and X. For each integer k between 0 and X (inclusive), find the answer to the following question, then compute the sum of all those answers, modulo 998244353.

• Let us repeat the following operation on the integer k. Operation: if the integer is currently odd, subtract 1 from it and divide it by 2; otherwise, divide it by 2 and add 2^{N-1} to it. How many operations need to be performed until k returns to its original value? (The answer is considered to be 0 if k never returns to its original value.)

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq X < 2^N
• X is given in binary and has exactly N digits. (In case X has less than N digits, it is given with leading zeroes.)
• All values in input are integers.

Sample Input 1

3
111

Sample Output 1

40

For example, for k=3, the operation changes k as follows: 1,0,4,6,7,3. Therefore the answer for k=3 is 6.

Sample Input 2

6
110101

Sample Output 2

616

Sample Input 3

30
001110011011011101010111011100

Sample Output 3

549320998

Problem Statement

Given are N points on the circumference of a circle centered at (0,0) in an xy-plane. The coordinates of the i-th point are (\cos(\frac{2\pi T_i}{L}),\sin(\frac{2\pi T_i}{L})).

Three distinct points will be chosen uniformly at random from these N points. Find the expected x- and y-coordinates of the center of the circle inscribed in the triangle formed by the chosen points.

Constraints

• 3 \leq N \leq 3000
• N \leq L \leq 10^9
• 0 \leq T_i \leq L-1
• T_i<T_{i+1}
• All values in input are integers.

Sample Input 1

3 4
0
1
3

Sample Output 1

0.414213562373095 -0.000000000000000

The three points have the coordinates (1,0), (0,1), and (0,-1). The center of the circle inscribed in the triangle formed by these points is (\sqrt{2}-1,0).

Sample Input 2

4 8
1
3
5
6

Sample Output 2

-0.229401949926902 -0.153281482438188

Sample Input 3

10 100
2
11
35
42
54
69
89
91
93
99

Sample Output 3

0.352886583546338 -0.109065017701873

Problem Statement

There are 2N points generally positioned on the circumference of a circle, numbered 1,\dots,2N in counterclockwise order. Here, a set of points is said to be generally positioned if, for any six distinct points U, V, W, X, Y, and Z among them, the segments UV, WX, and YZ do not intersect at the same point. Additionally, you will be given a 2N\times 2N matrix A.

Find the number of ways to divide the 2N points into N pairs such that all of the following are satisfied:

• Let us draw a red segment connecting the two points for each pair. Then, those red segments form a tree.
• For each pair (P, Q), A_{P,Q} = A_{Q,P} = 1 holds.

Here, a set of segments is said to form a tree if they are all connected and form no cycles.

For example, see the figure below:

• Upper left: the conditions are satisfied.
• Upper right: the red segments form a cycle, so the conditions are not satisfied.
• Lower left: the red segments are not connected, so the conditions are not satisfied.
• Lower right: some vertices belong to no pair or multiple pairs, so the conditions are not satisfied.

Figure: A division satisfying the conditions (upper left) and divisions violating them (the others)

Notes

It can be proved that, as long as the 2N points are generally positioned, the answer does not depend on their specific positions.

Constraints

• 1 \leq N \leq 20
• A_{i,j} is 0 or 1.
• A_{i,i} is 0.
• A_{i,j}=A_{j,i}
• N is an integer.

Sample Input 1

3
011111
101111
110111
111011
111101
111110

Sample Output 1

3

There are three possible divisions that satisfy the conditions: ((1,4),(2,6),(3,5)), ((1,3),(2,5),(4,6)), and ((1,5),(2,4),(3,6)).

Sample Input 2

4
01111100
10011111
10011100
11101111
11110111
11111011
01011101
01011110

Sample Output 2

6

Sample Input 3

8
0111101111111111
1011101111111111
1101101111011101
1110111111111111
1111011111110111
0001101111111111
1111110111011111
1111111011111111
1111111101111111
1111111110111111
1101110111011111
1111111111101111
1111011111110111
1111111111111011
1101111111111101
1111111111111110

Sample Output 3

4762

Problem Statement

For each of the K^{NM} ways to write an integer between 1 and K (inclusive) in every square in a square grid with N rows and M columns, find the value defined below, then compute the sum of all those K^{NM} values, modulo D.

• For each of the NM squares, find the minimum among the N+M-1 integers written in the square's row or the square's column. The value defined for the grid is the product of all these NM values.

Constraints

• 1 \leq N,M,K \leq 100
• 10^8 \leq D \leq 10^9
• N,M,K, and D are integers.
• D is prime.

Sample Input 1

2 2 2 998244353

Sample Output 1

35

We have 1 way to write integers such that the product of the NM values is 16, 4 ways such that the product is 2, and 11 ways such that the product is 1.

Sample Input 2

2 3 4 998244353

Sample Output 2

127090

Sample Input 3

31 41 59 998244353

Sample Output 3

827794103