Problem Statement

We have a grid with H horizontal rows and W vertical columns. We denote by (i, j) the cell at the i-th row from the top and j-th column from the left of the grid.
Each cell in the grid has a symbol # or . written on it. Let C[i][j] be the character written on (i, j). For integers i and j such that at least one of 1 \leq i \leq H and 1 \leq j \leq W is violated, we define C[i][j] to be ..

(4n+1) squares, consisting of (a, b) and (a+d,b+d),(a+d,b-d),(a-d,b+d),(a-d,b-d) (1 \leq d \leq n, 1 \leq n), are said to be a cross of size n centered at (a,b) if and only if all of the following conditions are satisfied:

• C[a][b] is #.
• C[a+d][b+d],C[a+d][b-d],C[a-d][b+d], and C[a-d][b-d] are all #, for all integers d such that 1 \leq d \leq n,
• At least one of C[a+n+1][b+n+1],C[a+n+1][b-n-1],C[a-n-1][b+n+1], and C[a-n-1][b-n-1] is ..

For example, the grid in the following figure has a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

The grid has some crosses. No # is written on the cells except for those comprising a cross.
Additionally, no two squares that comprise two different crosses share a corner. The two grids in the following figure are the examples of grids where two squares that comprise different crosses share a corner; such grids are not given as an input. For example, the left grid is invalid because (3, 3) and (4, 4) share a corner.

Let N = \min(H, W), and S_n be the number of crosses of size n. Find S_1, S_2, \dots, S_N.

Constraints

• 3 \leq H, W \leq 100
• C[i][j] is # or ..
• No two different squares that comprise two different crosses share a corner.
• H and W are integers.

Sample Input 1

5 9
#.#.#...#
.#...#.#.
#.#...#..
.....#.#.
....#...#

Sample Output 1

1 1 0 0 0

As described in the Problem Statement, there are a cross of size 1 centered at (2, 2) and another of size 2 centered at (3, 7).

Sample Input 2

3 3
...
...
...

Sample Output 2

0 0 0

There may be no cross.

Sample Input 3

3 16
#.#.....#.#..#.#
.#.......#....#.
#.#.....#.#..#.#

Sample Output 3

3 0 0

Sample Input 4

15 20
#.#..#.............#
.#....#....#.#....#.
#.#....#....#....#..
........#..#.#..#...
#.....#..#.....#....
.#...#....#...#..#.#
..#.#......#.#....#.
...#........#....#.#
..#.#......#.#......
.#...#....#...#.....
#.....#..#.....#....
........#.......#...
#.#....#....#.#..#..
.#....#......#....#.
#.#..#......#.#....#

Sample Output 4

5 0 1 0 0 0 1 0 0 0 0 0 0 0 0

Problem Statement

There are M sets, called S_1, S_2, \dots, S_M, consisting of integers between 1 and N.
S_i consists of C_i integers a_{i, 1}, a_{i, 2}, \dots, a_{i, C_i}.

There are (2^M-1) ways to choose one or more sets from the M sets.
How many of them satisfy the following condition?

• For all integers x such that 1 \leq x \leq N, there is at least one chosen set containing x.

Constraints

• 1 \leq N \leq 10
• 1 \leq M \leq 10
• 1 \leq C_i \leq N
• 1 \leq a_{i,1} \lt a_{i,2} \lt \dots \lt a_{i,C_i} \leq N
• All values in the input are integers.

Sample Input 1

3 3
2
1 2
2
1 3
1
2

Sample Output 1

3

The sets given in the input are S_1 = \lbrace 1, 2 \rbrace, S_2 = \lbrace 1, 3 \rbrace, S_3 = \lbrace 2 \rbrace.
The following three ways satisfy the conditions in the Problem Statement:

• choosing S_1, S_2;
• choosing S_1, S_2, S_3;
• choosing S_2, S_3.

Sample Input 2

4 2
2
1 2
2
1 3

Sample Output 2

0

There may be no way to choose sets that satisfies the conditions in the Problem Statement.

Sample Input 3

6 6
3
2 3 6
3
2 4 6
2
3 6
3
1 5 6
3
1 3 6
2
1 4

Sample Output 3

18

Problem Statement

There is a grid with H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and the j-th column from the left.

Each cell contains one of the characters o, x, and .. The characters written in each cell are represented by H strings S_1, S_2, \ldots, S_H of length W; the character written in cell (i, j) is the j-th character of the string S_i.

For this grid, you may repeat the following operation any number of times, possibly zero:

• Choose one cell with the character . and change the character in that cell to o.

Determine if it is possible to have a sequence of K horizontally or vertically consecutive cells with o written in all cells (in other words, satisfy at least one of the following two conditions). If it is possible, print the minimum number of operations required to achieve this.

• There is an integer pair (i, j) satisfying 1 \leq i \leq H and 1 \leq j \leq W-K+1 such that the characters in cells (i, j), (i, j+1), \ldots, (i, j+K-1) are all o.
• There is an integer pair (i, j) satisfying 1 \leq i \leq H-K+1 and 1 \leq j \leq W such that the characters in cells (i, j), (i+1, j), \ldots, (i+K-1, j) are all o.

Constraints

• H, W, and K are integers.
• 1 \leq H
• 1 \leq W
• H \times W \leq 2 \times 10^5
• 1 \leq K \leq \max\lbrace H, W \rbrace
• S_i is a string of length W consisting of the characters o, x, and ..

Sample Input 1

3 4 3
xo.x
..o.
xx.o

Sample Output 1

2

By operating twice, for example, changing the characters in cells (2, 1) and (2, 2) to o, you can satisfy the condition in the problem statement, and this is the minimum number of operations required.

Sample Input 2

4 2 3
.o
.o
.o
.o

Sample Output 2

0

The condition is satisfied without performing any operations.

Sample Input 3

3 3 3
x..
..x
.x.

Sample Output 3

-1

It is impossible to satisfy the condition, so print -1.

Sample Input 4

10 12 6
......xo.o..
x...x.....o.
x...........
..o...x.....
.....oo.....
o.........x.
ox.oox.xx..x
....o...oox.
..o.....x.x.
...o........

Sample Output 4

3

Problem Statement

In the world where Takahashi lives, a week has N days.

Takahashi, the king of the Kingdom of AtCoder, assigns "weekday" or "holiday" to each day of week. The assignments should be the same for all weeks. At least one day of week should be assigned "holiday".

Under such conditions, the productivity of the i-th day of week is defined by a sequence A of length N as follows:

• if the i-th day of week is "holiday", its productivity is 0;
• if the i-th day of week is "weekday", its productivity is A_{\min(x,y)}, if the last holiday is x days before and the next one is y days after.
  • Note that the last/next holiday may belong to a different week due to the periodic assignments. For details, see the Samples.

Find the maximum productivity per week when the assignments are chosen optimally.
Here, the productivity per week refers to the sum of the productivities of the 1-st, 2-nd, \dots, and N-th day of week.

Constraints

• All values in the input are integers.
• 1 \le N \le 5000
• 1 \le A_i \le 10^9

Sample Input 1

7
10 10 1 1 1 1 1

Sample Output 1

50

For example, we can assign "holiday" to the 2-nd and 4-th day of week and "weekday" to the rest to achieve a productivity of 50 per week:

• the 1-st day of week ... x=4 and y=1, so its productivity is A_1 = 10.
• the 2-nd day of week ... it is holiday, so its productivity is 0.
• the 3-st day of week ... x=1 and y=1, so its productivity is A_1 = 10.
• the 4-th day of week ... it is holiday, so its productivity is 0.
• the 5-th day of week ... x=1 and y=4, so its productivity is A_1 = 10.
• the 6-th day of week ... x=2 and y=3, so its productivity is A_2 = 10.
• the 7-th day of week ... x=3 and y=2, so its productivity is A_2 = 10.

It is impossible to make the productivity per week 51 or greater.

Sample Input 2

10
200000000 500000000 1000000000 800000000 100000000 80000000 600000 900000000 1 20

Sample Output 2

5100000000

Sample Input 3

20
38 7719 21238 2437 8855 11797 8365 32285 10450 30612 5853 28100 1142 281 20537 15921 8945 26285 2997 14680

Sample Output 3

236980

Problem Statement

Takahashi is participating in a lottery.

Each time he takes a draw, he gets one of the N prizes available. Prize i is awarded with probability \frac{W_i}{\sum_{j=1}^{N}W_j}. The results of the draws are independent of each other.

What is the probability that he gets exactly M different prizes from K draws? Find it modulo 998244353.

Note

To print a rational number, start by representing it as a fraction \frac{y}{x}. Here, x and y should be integers, and x should not be divisible by 998244353 (under the Constraints of this problem, such a representation is always possible). Then, print the only integer z between 0 and 998244352 (inclusive) such that xz\equiv y \pmod{998244353}.

Constraints

• 1 \leq K \leq 50
• 1 \leq M \leq N \leq 50
• 0 < W_i
• 0 < W_1 + \ldots + W_N < 998244353
• All values in input are integers.

Sample Input 1

2 1 2
2
1

Sample Output 1

221832079

Each draw awards Prize 1 with probability \frac{2}{3} and Prize 2 with probability \frac{1}{3}.

He gets Prize 1 at both of the two draws with probability \frac{4}{9}, and Prize 2 at both draws with probability \frac{1}{9}, so the sought probability is \frac{5}{9}.

The modulo 998244353 representation of this value, according to Note, is 221832079.

Sample Input 2

3 3 2
1
1
1

Sample Output 2

0

It is impossible to get three different prizes from two draws, so the sought probability is 0.

Sample Input 3

3 3 10
499122176
499122175
1

Sample Output 3

335346748

Sample Input 4

10 8 15
1
1
1
1
1
1
1
1
1
1

Sample Output 4

755239064