Problem Statement

We have N+M balls, each of which has an integer written on it.
It is known that:

• The numbers written on N of the balls are even.
• The numbers written on M of the balls are odd.

Find the number of ways to choose two of the N+M balls (disregarding order) so that the sum of the numbers written on them is even.
It can be shown that this count does not depend on the actual values written on the balls.

Constraints

• 0 \leq N,M \leq 100
• 2 \leq N+M
• All values in input are integers.

Sample Input 1

2 1

Sample Output 1

1

For example, let us assume that the numbers written on the three balls are 1,2,4.

• If we choose the two balls with 1 and 2, the sum is odd;
• If we choose the two balls with 1 and 4, the sum is odd;
• If we choose the two balls with 2 and 4, the sum is even.

Thus, the answer is 1.

Sample Input 2

4 3

Sample Output 2

9

Sample Input 3

1 1

Sample Output 3

0

Sample Input 4

13 3

Sample Output 4

81

Sample Input 5

0 3

Sample Output 5

3

Problem Statement

A string S of an odd length is said to be a strong palindrome if and only if all of the following conditions are satisfied:

• S is a palindrome.
• Let N be the length of S. The string formed by the 1-st through ((N-1)/2)-th characters of S is a palindrome.
• The string consisting of the (N+3)/2-st through N-th characters of S is a palindrome.

Determine whether S is a strong palindrome.

Constraints

• S consists of lowercase English letters.
• The length of S is an odd number between 3 and 99 (inclusive).

Sample Input 1

akasaka

Sample Output 1

Yes

• S is akasaka.
• The string formed by the 1-st through the 3-rd characters is aka.
• The string formed by the 5-th through the 7-th characters is aka. All of these are palindromes, so S is a strong palindrome.

Sample Input 2

level

Sample Output 2

No

Sample Input 3

atcoder

Sample Output 3

No

Problem Statement

Given is a positive integer L. Find the maximum possible volume of a rectangular cuboid whose sum of the dimensions (not necessarily integers) is L.

Constraints

• 1 ≤ L ≤ 1000
• L is an integer.

Sample Input 1

3

Sample Output 1

1.000000000000

For example, a rectangular cuboid whose dimensions are 0.8, 1, and 1.2 has a volume of 0.96.

On the other hand, if the dimensions are 1, 1, and 1, the volume of the rectangular cuboid is 1, which is greater.

Sample Input 2

999

Sample Output 2

36926037.000000000000

Problem Statement

We have N balls. The i-th ball has an integer A_i written on it.
For each k=1, 2, ..., N, solve the following problem and print the answer.

• Find the number of ways to choose two distinct balls (disregarding order) from the N-1 balls other than the k-th ball so that the integers written on them are equal.

Constraints

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

Sample Input 1

5
1 1 2 1 2

Sample Output 1

2
2
3
2
3

Consider the case k=1 for example. The numbers written on the remaining balls are 1,2,1,2.
From these balls, there are two ways to choose two distinct balls so that the integers written on them are equal.
Thus, the answer for k=1 is 2.

Sample Input 2

4
1 2 3 4

Sample Output 2

0
0
0
0

No two balls have equal numbers written on them.

Sample Input 3

5
3 3 3 3 3

Sample Output 3

6
6
6
6
6

Any two balls have equal numbers written on them.

Sample Input 4

8
1 2 1 4 2 1 4 1

Sample Output 4

5
7
5
7
7
5
7
5

Problem Statement

We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.

The square (i, j) at the i-th row from the top and the j-th column from the left is dark if S_{i,j} is 0, and white if S_{i,j} is 1.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has K or less white squares?

Constraints

• 1 \leq H \leq 10
• 1 \leq W \leq 1000
• 1 \leq K \leq H \times W
• S_{i,j} is 0 or 1.

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2

For example, cutting between the 1-st and 2-nd rows and between the 3-rd and 4-th columns - as shown in the figure to the left - works.

Note that we cannot cut the bar in the ways shown in the two figures to the right.

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0

No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3

Problem Statement

Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.
For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:

• f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Constraints

• All values in input are integers.
• 1 \leq N \leq 3000
• 1 \leq S \leq 3000
• 1 \leq A_i \leq 3000

Sample Input 1

3 4
2 2 4

Sample Output 1

5

The value of f(L, R) for each pair is as follows, for a total of 5.

• f(1,1) = 0
• f(1,2) = 1 (for the sequence (1, 2))
• f(1,3) = 2 (for (1, 2) and (3))
• f(2,2) = 0
• f(2,3) = 1 (for (3))
• f(3,3) = 1 (for (3))

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

152