Problem Statement

Determine if we can choose K different integers between 1 and N (inclusive) so that no two of them differ by 1.

Constraints

• 1\leq N,K\leq 100
• N and K are integers.

Sample Input 1

3 2

Sample Output 1

YES

We can choose 1 and 3.

Sample Input 2

5 5

Sample Output 2

NO

Sample Input 3

31 10

Sample Output 3

YES

Sample Input 4

10 90

Sample Output 4

NO

Problem Statement

There are four towns, numbered 1,2,3 and 4. Also, there are three roads. The i-th road connects different towns a_i and b_i bidirectionally. No two roads connect the same pair of towns. Other than these roads, there is no way to travel between these towns, but any town can be reached from any other town using these roads.

Determine if we can visit all the towns by traversing each of the roads exactly once.

Constraints

• 1 \leq a_i,b_i \leq 4(1\leq i\leq 3)
• a_i and b_i are different. (1\leq i\leq 3)
• No two roads connect the same pair of towns.
• Any town can be reached from any other town using the roads.

Sample Input 1

4 2
1 3
2 3

Sample Output 1

YES

We can visit all the towns in the order 1,3,2,4.

Sample Input 2

3 2
2 4
1 2

Sample Output 2

NO

Sample Input 3

2 1
3 2
4 3

Sample Output 3

YES

Problem Statement

Snuke has one biscuit and zero Japanese yen (the currency) in his pocket. He will perform the following operations exactly K times in total, in the order he likes:

• Hit his pocket, which magically increases the number of biscuits by one.
• Exchange A biscuits to 1 yen.
• Exchange 1 yen to B biscuits.

Find the maximum possible number of biscuits in Snuke's pocket after K operations.

Constraints

• 1 \leq K,A,B \leq 10^9
• K,A and B are integers.

Sample Input 1

4 2 6

Sample Output 1

7

The number of biscuits in Snuke's pocket after K operations is maximized as follows:

• Hit his pocket. Now he has 2 biscuits and 0 yen.
• Exchange 2 biscuits to 1 yen. his pocket. Now he has 0 biscuits and 1 yen.
• Hit his pocket. Now he has 1 biscuits and 1 yen.
• Exchange 1 yen to 6 biscuits. his pocket. Now he has 7 biscuits and 0 yen.

Sample Input 2

7 3 4

Sample Output 2

8

Sample Input 3

314159265 35897932 384626433

Sample Output 3

48518828981938099

Problem Statement

Snuke stands on a number line. He has L ears, and he will walk along the line continuously under the following conditions:

• He never visits a point with coordinate less than 0, or a point with coordinate greater than L.
• He starts walking at a point with integer coordinate, and also finishes walking at a point with integer coordinate.
• He only changes direction at a point with integer coordinate.

Each time when Snuke passes a point with coordinate i-0.5, where i is an integer, he put a stone in his i-th ear.

After Snuke finishes walking, Ringo will repeat the following operations in some order so that, for each i, Snuke's i-th ear contains A_i stones:

• Put a stone in one of Snuke's ears.
• Remove a stone from one of Snuke's ears.

Find the minimum number of operations required when Ringo can freely decide how Snuke walks.

Constraints

• 1 \leq L \leq 2\times 10^5
• 0 \leq A_i \leq 10^9(1\leq i\leq L)
• All values in input are integers.

Sample Input 1

4
1
0
2
3

Sample Output 1

1

Assume that Snuke walks as follows:

• He starts walking at coordinate 3 and finishes walking at coordinate 4, visiting coordinates 3,4,3,2,3,4 in this order.

Then, Snuke's four ears will contain 0,0,2,3 stones, respectively. Ringo can satisfy the requirement by putting one stone in the first ear.

Sample Input 2

8
2
0
0
2
1
3
4
1

Sample Output 2

3

Sample Input 3

7
314159265
358979323
846264338
327950288
419716939
937510582
0

Sample Output 3

1

Problem Statement

There is a square grid with N rows and M columns. Each square contains an integer: 0 or 1. The square at the i-th row from the top and the j-th column from the left contains a_{ij}.

Among the 2^{N+M} possible pairs of a subset A of the rows and a subset B of the columns, find the number of the pairs that satisfy the following condition, modulo 998244353:

• The sum of the |A||B| numbers contained in the intersection of the rows belonging to A and the columns belonging to B, is odd.

Constraints

• 1 \leq N,M \leq 300
• 0 \leq a_{i,j} \leq 1(1\leq i\leq N,1\leq j\leq M)
• All values in input are integers.

Sample Input 1

2 2
0 1
1 0

Sample Output 1

6

For example, if A consists of the first row and B consists of both columns, the sum of the numbers contained in the intersection is 0+1=1.

Sample Input 2

2 3
0 0 0
0 1 0

Sample Output 2

8

Problem Statement

There are N Snukes lining up in a row. You are given a string S of length N. The i-th Snuke from the front has two red balls if the i-th character in S is 0; one red ball and one blue ball if the i-th character in S is 1; two blue balls if the i-th character in S is 2.

Takahashi has a sequence that is initially empty. Find the number of the possible sequences he may have after repeating the following procedure 2N times, modulo 998244353:

• Each Snuke who has one or more balls simultaneously chooses one of his balls and hand it to the Snuke in front of him, or hand it to Takahashi if he is the first Snuke in the row.
• Takahashi receives the ball and put it to the end of his sequence.

Constraints

• 1 \leq |S| \leq 2000
• S consists of 0,1 and 2.

Note that the integer N is not directly given in input; it is given indirectly as the length of the string S.

Sample Input 1

02

Sample Output 1

3

There are three sequences that Takahashi may have: rrbb, rbrb and rbbr, where r and b stand for red and blue balls, respectively.

Sample Input 2

1210

Sample Output 2

55

Sample Input 3

12001021211100201020

Sample Output 3

543589959