Problem Statement

Have you noticed this part of AtCoder website?

Here the numbers are carefully chosen so that we can jump from any page to any page in small number of steps, while each page doesn't contain too many links. In this task you are asked to do a similar thing with only two links on each page!

Snuke made a website with $N$ pages numbered $1$ through $N$. For each $i$ ($1 \leq i \leq N$), choose two integers $a_i$ and $b_i$ ($1 \leq a_i, b_i \leq N$), and add two links on Page $i$: a link to Page $a_i$ and a link to Page $b_i$. The website must satisfy the following constraint:

• You must be able to jump from any page to any other page by clicking at most $10$ links.

Under the constraints of the problem, we can prove that this is always possible.

Constraints

• $1 \leq N \leq 1000$

Sample Input 1

1

Sample Output 1

1 1

Snuke made an excellent website with only one page. It even contains two links to itself!

Sample Input 2

3

Sample Output 2

2 3
1 3
1 2

Here we can jump from any page to any other page by a direct link.

Problem Statement

$N$ cells are arranged in a row. The cells are numbered $1$ through $N$ from left to right.

Initially, all cells are empty. You can perform the following two types of operation arbitrary number of times in arbitrary order:

• Choose three consecutive empty cells, and put a coin on each of the three cells.
• Choose three consecutive cells with coins, and remove all three coins on the chosen cells.

After you finish performing operations, if the $i$-th cell contains a coin, you get $a_i$ points. Your score is the sum of all points you get from the cells with coins.

Compute the maximum possible score you can earn.

Constraints

• $3 \leq N \leq 500$
• $-100 \leq a_i \leq 100$
• All values in the input are integers.

Sample Input 1

4
1
2
3
4

Sample Output 1

9

We represent a cell with a coin as o and a cell without a coin as . (a dot). One optimal way is as follows:

.... $\rightarrow$ .ooo

We get $2 + 3 + 4 = 9$ points this way.

Sample Input 2

6
3
-2
-1
0
-1
4

Sample Output 2

6

One optimal way is as follows:

...... $\rightarrow$ ooo... $\rightarrow$ oooooo $\rightarrow$ o...oo

We get $3 + (-1) + 4 = 6$ points this way.

Sample Input 3

10
-84
-60
-41
-100
8
-8
-52
-62
-61
-76

Sample Output 3

0

Problem Statement

There is a sequence of cells that extends infinitely to both directions. You and Snuke play the following game:

• The judge chooses a string $t$ consisting of B and S, called turn string, and show it to both players.
• First, Snuke stands on one of the cells.
• Then, for each $i = 1, ..., |t|$ in this order, the following happens:
  • If the $i$-th letter of $t$ is B, it is your turn. You choose a cell that contains neither other blocks nor Snuke, and put a block on the cell. After that, if both of the two cells adjacent to Snuke's cell are blocked, you win and the game ends.
  • If the $i$-th letter of $t$ is S, it is Snuke's turn. He may move to an adjacent unblocked cell, or doesn't do anything.
• If the game still hasn't ended, Snuke wins and the game ends.

You are given a string $s$ consisting of B, S, and ?. If $s$ contains $Q$ ?s, there are $2^Q$ ways to replace each ? with B or S and get a turn string. Among those $2^Q$ strings, how many will end up with your winning, in case both players play optimally? Find the answer modulo $998,244,353$.

Constraints

• $1 \leq |s| \leq 10^6$
• $s$ consists of B, S, and ?.

Sample Input 1

BSSBS

Sample Output 1

0

You take the $1$st and the $4$th turn, and Snuke takes the $2$nd, the $3$rd, and the $5$th turn. In this case, if both players play optimally, it turns out that Snuke wins.

Sample Input 2

?S?B????S????????B??????B??S??

Sample Output 2

16777197

Problem Statement

There are $N$ people numbered $1$ through $N$, and $K$ items numbered $1$ through $K$. They play a turn-based game. Person $1$ takes the first turn, Person $2$ takes the next turn, then Person $3$, $\ldots$, Person $N$, then Person $1$ again, $\ldots$, Person $N$, Person $1$ again, $\ldots$, and so on, until all items are taken.

In each turn, the following happens:

• If the person already wins an item, nothing happens.
• Otherwise, he chooses one of the items he hasn't chosen yet uniformly at random, and secretly tells it to Snuke, the judge of the game. If the item is already taken by someone else, nothing happens; otherwise he wins the item.

For each $i$, compute the probability that Person $i$ wins an item, modulo $998,244,353$ (as described in the Notes section).

Notes

• All random choices are made independently.
• We can prove that the game always ends in finite number of steps.
• We can also prove that, whenever a player is asked to choose an item, he has at least one item he hasn't chosen yet.
• We can also prove that the probabilities are rational numbers. When you print a probability, first write it as a fraction $\frac{y}{x}$, where $x, y$ are integers and $x$ is not divisible by $P = 998,244,353$ (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer $z$ between $0$ and $P - 1$, inclusive, that satisfies $xz \equiv y \pmod{P}$.

Constraints

• $1 \leq K \leq N \leq 40$
• All values in the input are integers.

Sample Input 1

3 2

Sample Output 1

1
249561089
748683265

• First, Person $1$ chooses an item (call it Item $p$), and wins it.
  • Then, with $1/2$ probability, Person $2$ chooses the other item in the next turn and wins it, and the game ends.
  • With $1/2$ probability, Person $2$ chooses $p$, he doesn't win it, and Person $3$ takes the next turn.
    • With $1/4$ probability, Person $3$ chooses the other item, wins it, and the game ends.
    • With $1/4$ probability, Person $3$ chooses $p$ again. Then, next turn is Person $1$'s and nothing happens because he has already won an item. Then, in the next turn, Person $2$ chooses the other item for sure because he has already chosen $p$ in his previous turn, so he wins an item this time, and the game ends.

To summarize, Person $1, 2, 3$ will get an item with probability $1, \frac{3}{4}, \frac{1}{4}$, respectively.

Sample Input 2

4 3

Sample Output 2

1
314262112
767169272
915057324

The probabilities are $1, \frac{47}{54}, \frac{77}{108}, \frac{5}{12}$.

Sample Input 3

40 10

Sample Output 3

1
868517173
27621563
837064957
222682471
512462123
662169358
927654899
421237429
47896491
462367772
888812171
300869511
63754652
144548024
358216674
895724239
274552277
722622637
946769993
579325471
777654313
142897955
607284898
8038340
863909530
63295741
862961672
335905745
944425523
358698956
299986928
847582651
197657467
180361665
412489246
762713624
410322243
646538576
79047758

Problem Statement

There are three traffic lights numbered $1, 2, 3$. Traffic Light $i$ eternally repeats the following pattern: green for $g_i$ seconds, red for $r_i$ seconds, green for $g_i$ seconds, red for $r_i$ seconds, and so on.

All three lights have turned green just now. During the next $(g_1 + r_1)(g_2 + r_2)(g_3 + r_3)$ seconds, what is the total duration of the time when all lights are green? Compute the answer modulo $998,244,353$.

Constraints

• $1 \leq g_1, r_1, g_2, r_2, g_3, r_3 \leq 10^{12}$
• All values in the input are integers.

Sample Input 1

1 1 2 1 3 1

Sample Output 1

8

During the next $24$ seconds,

• Light $1$ is green during time intervals $[0, 1], [2, 3], [4, 5], [6, 7], [8, 9], [10, 11], [12, 13], [14, 15], [16, 17], [18, 19], [20, 21], [22, 23]$.
• Light $2$ is green during time intervals $[0, 2], [3, 5], [6, 8], [9, 11], [12, 14], [15, 17], [18, 20], [21, 23]$.
• Light $3$ is green during time intervals $[0, 3], [4, 7], [8, 11], [12, 15], [16, 19], [20, 23]$.

Thus, all lights are green during time intervals $[0, 1], [4, 5], [6, 7], [10, 11], [12, 13], [16, 17], [18, 19], [22, 23]$.

The total duration is $8$ seconds.

Sample Input 2

7 3 5 7 11 4

Sample Output 2

420

Sample Input 3

999999999991 999999999992 999999999993 999999999994 999999999995 999999999996

Sample Output 3

120938286

Problem Statement

There is a tree whose vertices are labelled with either $0$ or $1$. The tree has $N$ vertices numbered $1$ through $N$. For each $i$, there is an edge connecting Vertex $a_i$ and Vertex $b_i$. The label of Vertex $i$ is $c_i$.

Snuke wants to repeat performing the following operation on the tree:

• Choose an edge, contract it, and label the new vertex with the NAND of the labels of two old vertices.

After performing $N - 1$ operations, the tree ends up with a single vertex. Among $(N-1)!$ ways to do so, how many will result in a vertex labelled with $1$? Compute the answer modulo $2$.

Notes

• NAND operation is defined as follows: $NAND(0, 0) = NAND(0, 1) = NAND(1, 0) = 1, NAND(1, 1) = 0$.
• When we contract an edge between Vertex $s$ and Vertex $t$, we remove the edge, and simultaneously merge the two vertices. There is an edge between the merged vertex and Vertex $u$ in the new tree iff there is an edge between $s$ and $u$, or an edge between $t$ and $u$, in the old tree.

Constraints

• $2 \leq N \leq 300$
• $1 \leq a_i < b_i \leq N$
• The input represents a valid tree.
• $0 \leq c_i \leq 1$
• All values in the input are integers.

Sample Input 1

4
1 2
2 3
2 4
0 1 1 0

Sample Output 1

0

It turns out that in $4$ of all $6$ ways the final label will be $1$, so the answer is $4 \ mod \ 2 = 0$.

Sample Input 2

4
1 2
2 3
3 4
1 1 0 1

Sample Output 2

1

Sample Input 3

20
3 15
1 12
10 16
3 19
5 20
1 9
6 13
14 19
2 4
8 11
12 16
6 20
2 17
16 18
17 19
7 10
16 20
2 20
8 20
1 0 0 1 1 0 1 1 1 0 0 1 0 1 0 1 1 1 0 0

Sample Output 3

0