Problem Statement

You are given a string S of length N consisting only of lowercase English letters.

Find the number of strings obtained by permuting the characters of S (including the string S itself) that do not contain a palindrome of length K as a substring.

Here, a string T of length N is said to "contain a palindrome of length K as a substring" if and only if there exists a non-negative integer i not greater than (N-K) such that T_{i+j} = T_{i+K+1-j} for every integer j with 1 \leq j \leq K.
Here, T_k denotes the k-th character of the string T.

Constraints

• 2 \leq K \leq N \leq 10
• N and K are integers.
• S is a string of length N consisting only of lowercase English letters.

Sample Input 1

3 2
aab

Sample Output 1

1

The strings obtained by permuting aab are aab, aba, and baa. Among these, aab and baa contain the palindrome aa of length 2 as a substring.
Thus, the only string that satisfies the condition is aba, so print 1.

Sample Input 2

5 3
zzyyx

Sample Output 2

16

There are 30 strings obtained by permuting zzyyx, 16 of which do not contain a palindrome of length 3. Thus, print 16.

Sample Input 3

10 5
abcwxyzyxw

Sample Output 3

440640

Problem Statement

There is a grid with N horizontal rows and N vertical columns, where each square is painted white or black.
The state of the grid is represented by N strings, S_i. If the j-th character of S_i is #, the square at the i-th row from the top and the j-th column from the left is painted black. If the character is ., then the square is painted white.

Takahashi can choose at most two of these squares that are painted white, and paint them black.
Determine if it is possible to make the grid contain 6 or more consecutive squares painted black aligned either vertically, horizontally, or diagonally.
Here, the grid is said to be containing 6 or more consecutive squares painted black aligned diagonally if the grid with N rows and N columns completely contains a subgrid with 6 rows and 6 columns such that all the squares on at least one of its diagonals are painted black.

Constraints

• 6 \leq N \leq 1000
• \lvert S_i\rvert =N
• S_i consists of # and ..

Sample Input 1

8
........
........
.#.##.#.
........
........
........
........
........

Sample Output 1

Yes

By painting the 3-rd and the 6-th squares from the left in the 3-rd row from the top, there will be 6 squares painted black aligned horizontally.

Sample Input 2

6
######
######
######
######
######
######

Sample Output 2

Yes

While Takahashi cannot choose a square to paint black, the grid already satisfies the condition.

Sample Input 3

10
..........
#..##.....
..........
..........
....#.....
....#.....
.#...#..#.
..........
..........
..........

Sample Output 3

No

Problem Statement

There are N people numbered 1 to N on a coordinate plane.
Person 1 is at the origin.

You are given M pieces of information in the following form:

• From person A_i's perspective, person B_i is X_i units away in the positive x-direction and Y_i units away in the positive y-direction.

Determine the coordinates of each person. If the coordinates of a person cannot be uniquely determined, report that fact.

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq M \leq 2\times 10^5
• 1\leq A_i, B_i \leq N
• A_i \neq B_i
• -10^9 \leq X_i,Y_i \leq 10^9
• All input values are integers.
• The given information is consistent.

Sample Input 1

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

Sample Output 1

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 2

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

Sample Output 2

0 0
2 1
-1 -2

The figure below shows the positional relationship of the three people.

Sample Input 3

5 7
1 2 0 0
1 2 0 0
2 3 0 0
3 1 0 0
2 1 0 0
3 2 0 0
4 5 0 0

Sample Output 3

0 0
0 0
0 0
undecidable
undecidable

The same piece of information may be given multiple times, and multiple people may be at the same coordinates.

Problem Statement

You are given a sequence A = (A_1, A_2, \dots, A_N) of length N and an integer K.
There are 2^{N-1} ways to divide A into several contiguous subsequences. How many of these divisions have no subsequence whose elements sum to K? Find the count modulo 998244353.

Here, "to divide A into several contiguous subsequences" means the following procedure.

• Freely choose the number k (1 \leq k \leq N) of subsequences and an integer sequence (i_1, i_2, \dots, i_k, i_{k+1}) satisfying 1 = i_1 \lt i_2 \lt \dots \lt i_k \lt i_{k+1} = N+1.
• For each 1 \leq n \leq k, the n-th subsequence is formed by taking the i_n-th through (i_{n+1} - 1)-th elements of A, maintaining their order.

Here are some examples of divisions for A = (1, 2, 3, 4, 5):

• (1, 2, 3), (4), (5)
• (1, 2), (3, 4, 5)
• (1, 2, 3, 4, 5)

Constraints

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

Sample Input 1

3 3
1 2 3

Sample Output 1

2

There are two divisions that satisfy the condition in the problem statement:

• (1), (2, 3)
• (1, 2, 3)

Sample Input 2

5 0
0 0 0 0 0

Sample Output 2

0

Sample Input 3

10 5
-5 -1 -7 6 -6 -2 -5 10 2 -10

Sample Output 3

428

Problem Statement

You are given N integers A_1, A_2, \dots, A_N.
Find the number of triples of integers (i, j, k) that satisfy the following conditions:

• 1 \le i, j, k \le N
• A_i \times A_j = A_k

Constraints

• 1 \le N \le 1000
• \color{red}{1 \le A_i < 10^{1000}}

Sample Input 1

5
2
3
6
12
24

Sample Output 1

6

The following six triples (i, j, k) satisfy the conditions in the problem statement:

• (1, 2, 3)
• (1, 3, 4)
• (1, 4, 5)
• (2, 1, 3)
• (3, 1, 4)
• (4, 1, 5)

Sample Input 2

11
1
2
3
4
5
6
123456789123456789
123456789123456789
987654321987654321
987654321987654321
121932631356500531347203169112635269

Sample Output 2

40

Note that the values of each integer A_i can be huge.

Sample Input 3

9
4
4
4
2
2
2
1
1
1

Sample Output 3

162

Note that there may be duplicates among the values of A_i.