Problem Statement

There are ~N~ bridges in AtCoder Village. The height of the bridge numbered ~i~ is ~H_i~ ( ~i~ is an integer between ~1~ and ~N~ ).
Every two different bridges in the village have different heights.

Print the number representing the highest bridge in the village.

Constraints

• ~1\leq N \leq 100~
• ~1\leq H_i \leq 10^9~
• All ~H_i~ are different.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~

~H_1~ ~H_2~ ~\ldots~ ~H_N~

Output

Print the integer representing the highest bridge in AtCoder village.

Sample Input 1

3
50 80 70

Sample Output 1

2

The village has three bridges.
The first, second, and third bridges have heights of ~50~ , ~80~ , and ~70~ , respectively, so the second bridge is the highest.
Thus, ~2~ should be printed.

Sample Input 2

1
1000000000

Sample Output 2

1

The village has only one bridge, so the first bridge is the highest.

Sample Input 3

10
22 75 26 45 72 81 47 29 97 2

Sample Output 3

9

The village has ten bridges, and the ninth bridge (with a height of ~97~ ) is the highest.

Problem Statement

There are non-negative integers ~A~ , ~B~ , ~C~ , ~D~ , ~E~ , and ~F~ , which satisfy ~A\times B\times C\geq D\times E\times F~ .
Find the remainder when ~(A\times B\times C)-(D\times E\times F)~ is divided by ~998244353~ .

Constraints

• ~0\leq A,B,C,D,E,F\leq 10^{18}~
• ~A\times B\times C\geq D\times E\times F~
• ~A~ , ~B~ , ~C~ , ~D~ , ~E~ , and ~F~ are integers.

Input

The input is given from Standard Input in the following format:

~A~ ~B~ ~C~ ~D~ ~E~ ~F~

Output

Print the remainder when ~(A\times B\times C)-(D\times E\times F)~ is divided by ~998244353~ , as an integer.

Sample Input 1

2 3 5 1 2 4

Sample Output 1

22

Since ~A\times B\times C=2\times 3\times 5=30~ and ~D\times E\times F=1\times 2\times 4=8~ ,
we have ~(A\times B\times C)-(D\times E\times F)=22~ . Divide this by ~998244353~ and print the remainder, which is ~22~ .

Sample Input 2

1 1 1000000000 0 0 0

Sample Output 2

1755647

Since ~A\times B\times C=1000000000~ and ~D\times E\times F=0~ ,
we have ~(A\times B\times C)-(D\times E\times F)=1000000000~ . Divide this by ~998244353~ and print the remainder, which is ~1755647~ .

Sample Input 3

1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000 1000000000000000000

Sample Output 3

0

We have ~(A\times B\times C)-(D\times E\times F)=0~ . Divide this by ~998244353~ and print the remainder, which is ~0~ .

Problem Statement

There is a two-dimensional plane. For integers ~r~ and ~c~ between ~1~ and ~9~ , there is a pawn at the coordinates ~(r,c)~ if the ~c~ -th character of ~S_{r}~ is # , and nothing if the ~c~ -th character of ~S_{r}~ is . .

Find the number of squares in this plane with pawns placed at all four vertices.

Constraints

• Each of ~S_1,\ldots,S_9~ is a string of length ~9~ consisting of # and . .

Input

The input is given from Standard Input in the following format:

~S_1~ ~S_2~ ~\vdots~ ~S_9~

Output

Print the answer.

Sample Input 1

##.......
##.......
.........
.......#.
.....#...
........#
......#..
.........
.........

Sample Output 1

2

The square with vertices ~(1,1)~ , ~(1,2)~ , ~(2,2)~ , and ~(2,1)~ have pawns placed at all four vertices.

The square with vertices ~(4,8)~ , ~(5,6)~ , ~(7,7)~ , and ~(6,9)~ also have pawns placed at all four vertices.

Thus, the answer is ~2~ .

Sample Input 2

.#.......
#.#......
.#.......
.........
....#.#.#
.........
....#.#.#
........#
.........

Sample Output 2

3

Problem Statement

A function ~f(x)~ defined for non-negative integers ~x~ satisfies the following conditions.

• ~f(0) = 1~ .
• ~f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)~ for any positive integer ~k~ .

Here, ~\lfloor A \rfloor~ denotes the value of ~A~ rounded down to an integer.

Find ~f(N)~ .

Constraints

• ~N~ is an integer satisfying ~0 \le N \le 10^{18}~ .

Input

The input is given from Standard Input in the following format:

~N~

Output

Print the answer.

Sample Input 1

2

Sample Output 1

3

We have ~f(2) = f(\lfloor \frac{2}{2}\rfloor) + f(\lfloor \frac{2}{3}\rfloor) = f(1) + f(0) =(f(\lfloor \frac{1}{2}\rfloor) + f(\lfloor \frac{1}{3}\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3~ .

Sample Input 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

Problem Statement

Takahashi is playing sugoroku, a board game.

The board has ~N+1~ squares, numbered ~0~ to ~N~ . Takahashi starts at square ~0~ and goes for square ~N~ .

The game uses a roulette wheel with ~M~ numbers from ~1~ to ~M~ that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square ~N~ , he turns around at square ~N~ and goes back by the excessive number of squares.

For instance, assume that ~N=4~ and Takahashi is at square ~3~ . If the wheel shows ~4~ , the excessive number of squares beyond square ~4~ is ~3+4-4=3~ . Thus, he goes back by three squares from square ~4~ and arrives at square ~1~ .

When Takahashi arrives at square ~N~ , he wins and the game ends.

Find the probability, modulo ~998244353~ , that Takahashi wins when he may spin the wheel at most ~K~ times.

How to print a probability modulo ~998244353~

It can be proved that the sought probability is always a rational number. Additionally, under the Constraints of this problem, when the sought probability is represented as an irreducible fraction ~\frac{y}{x}~ , it is guaranteed that ~x~ is not divisible by ~998244353~ .

Here, there is a unique integer ~z~ between ~0~ and ~998244352~ such that ~xz \equiv y \pmod{998244353}~ . Print this ~z~ .

Constraints

• ~M \leq N \leq 1000~
• ~1 \leq M \leq 10~
• ~1 \leq K \leq 1000~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~ ~M~ ~K~

Output

Print the answer.

Sample Input 1

2 2 1

Sample Output 1

499122177

Takahashi wins in one spin if the wheel shows ~2~ . Therefore, the probability of winning is ~\frac{1}{2}~ .

We have ~2\times 499122177 \equiv 1 \pmod{998244353}~ , so the answer to be printed is ~499122177~ .

Sample Input 2

10 5 6

Sample Output 2

184124175

Sample Input 3

100 1 99

Sample Output 3

0

Problem Statement

You are given an integer array ~A=(a_1,a_2,\ldots,a_N)~ .
You may perform the following operation any number of times (possibly zero).

• Choose a nonempty contiguous subarray of ~A~ , and delete it from the array.

For each ~x=1,2,\ldots,M~ , solve the following problem:

• Find the minimum possible number of operations to make the sum of elements of ~A~ equal ~x~ . If it is impossible to make the sum of elements of ~A~ equal ~x~ , print -1 instead.

Note that the sum of elements of an empty array is ~0~ .

Constraints

• ~1 \leq N,M \leq 3000~
• ~1 \leq a_i \leq 3000~
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

~N~ ~M~ ~a_1~ ~\ldots~ ~a_N~

Output

Print ~M~ lines. The ~i~ -th line should contain the answer for ~x=i~ .

Sample Input 1

4 5
1 2 3 4

Sample Output 1

1
2
1
1
1

The followings are examples of minimum number of operations that achieve the goal.

• For ~x=1~ , delete ~a_2,a_3,a_4~ , and the sum of elements of ~A~ becomes ~x~ .
• For ~x=2~ , delete ~a_3,a_4~ , then delete ~a_1~ , and the sum of elements of ~A~ becomes ~x~ .
• For ~x=3~ , delete ~a_3,a_4~ , and the sum of elements of ~A~ becomes ~x~ .
• For ~x=4~ , delete ~a_1,a_2,a_3~ , and the sum of elements of ~A~ becomes ~x~ .
• For ~x=5~ , delete ~a_2,a_3~ , and the sum of elements of ~A~ becomes ~x~ .

Sample Input 2

1 5
3

Sample Output 2

-1
-1
0
-1
-1

Sample Input 3

12 20
2 5 6 5 2 1 7 9 7 2 5 5

Sample Output 3

2
1
2
2
1
2
1
2
2
1
2
1
1
1
2
2
1
1
1
1