Problem Statement

You are given a string S of length N consisting of A and B.

You can repeat the following operation zero or more times:

• choose a pair of adjacent characters in S and replace them with AB.

Determine whether S can be turned into a palindrome.

Constraints

• 2 \leq N \leq 2\times 10^5
• S is a string of length N consisting of A and B.

Sample Input 1

3
BBA

Sample Output 1

Yes

Replacing the 2-nd and 3-rd characters, BA, with AB will turn S into BAB, a palindrome.

Sample Input 2

4
ABAB

Sample Output 2

No

No sequence of operations can turn S into a palindrome.

Problem Statement

The following game is called Game n:

The game is played by Alice and Bob. Initially, there are n stones.

The players alternate turns, making a move described below, with Alice going first. The player who becomes unable to make a move loses.

• In Alice's turn, she must remove a number of stones that is a positive multiple of A.
• In Bob's turn, he must remove a number of stones that is a positive multiple of B.

In how many of Game 1, Game 2, ..., Game N does Alice win when both players play optimally?

Constraints

• 1 \leq N ,A,B \leq 10^{18}
• All values in input are integers.

Sample Input 1

4 2 1

Sample Output 1

2

In Game 1, Alice cannot make a move and thus loses.

In Game 2, Alice removes 2 stones, and then Bob cannot make a move: Alice wins.

In Game 3, Alice removes 2 stones, Bob removes 1 stone, and then Alice cannot make a move and loses.

In Game 4, Alice removes 2 \times 2 = 4 stones, and then Bob cannot make a move: Alice wins.

Therefore, Alice wins in two of the four games.

Sample Input 2

27182818284 59045 23356

Sample Output 2

10752495144

Problem Statement

The score of a permutation P=(P_1,P_2,\ldots,P_{2N}) of (1,2,\ldots,2N) is defined as follows:

Consider dividing P into two (not necessarily contiguous) subsequences A = (A_1,A_2,\ldots,A_N) and B = (B_1,B_2,\ldots,B_N). The score of P is the maximum possible value of \displaystyle\sum_{i=1}^{N}A_i B_i in such a division.

Let M be the maximum among the scores of all permutations of (1,2,\ldots,2N). Find the number, modulo 998244353, of permutations of (1,2,\ldots,2N) with the score of M.

Constraints

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

Sample Input 1

2

Sample Output 1

16

The maximum among the scores of the 24 possible permutations, M, is 14, and there are 16 permutations with the score of 14.

For instance, the permutation (1,2,3,4) achieves \sum _{i=1}^{N}A_i B_i = 14 in the division A=(1,3), B=(2,4).

Sample Input 2

10000

Sample Output 2

391163238

Print the count modulo 998244353.

Problem Statement

Construct a set S of integers satisfying all of the conditions below. It can be proved that at least one such set S exists under the Constraints of this problem.

• S has exactly N elements.
• The element of S are distinct integers between -10^7 and 10^7 (inclusive).
• \displaystyle \sum _{s \in S} s = M.
• y-x\neq z-y for every triple x,y,z (x < y < z) of distinct elements in S.

Constraints

• 1 \leq N \leq 10^4
• |M| \leq N\times 10^6
• All values in input are integers.

Sample Input 1

3 9

Sample Output 1

1 2 6

We have 2-1 \neq 6-2 and 1+2+6=9, so this output satisfies the conditions. Many other solutions exist.

Sample Input 2

5 -15

Sample Output 2

-15 -5 0 2 3

M may be negative.

Problem Statement

You are given two sequences, each of length N, consisting of non-negative integers: A=(A_1,A_2,\ldots,A_{N}) and B=(B_1,B_2,\ldots,B_{N}).

Determine whether it is possible to make A equal to B by performing the operation below at most 70000 times. If it is possible, present a specific sequence of operations that achieves it.

• Choose an integer K\ (1\le K \le N). For every integer i\ (2\leq i \leq K), simultaneously replace the value of A_i with A_{i-1} \oplus A_i.

Here, \oplus denotes bitwise \mathrm{XOR}.

Constraints

• 2 \leq N \leq 1000
• 0 \leq A_i, B_i < 2^{60}
• All values in input are integers.

Sample Input 1

3
1 2 0
1 2 3

Sample Output 1

Yes
2
2 3

In this output, the sequence A is changed as follows:

• Initially: A=(1, 2, 0).
• After the 1-st operation: A=(1, 3, 0).
• After the 2-nd operation: A=(1, 2, 3).

After the two operations, A and B are equal, achieving the objective.

Sample Input 2

2
10 100
1 0

Sample Output 2

No

Sample Input 3

2
1152921504606846975 0
1152921504606846975 0

Sample Output 3

Yes
0

Problem Statement

Find the number, modulo 998244353, of non-decreasing sequences A=(A_1,A_2,\ldots,A_N) of length N consisting of integers between 0 and M (inclusive) that satisfy the following, for each K=0,1,\ldots,\mathrm{MOD}-1:

• the sum of the elements in A is congruent to K modulo \mathrm{MOD}.

Constraints

• 1 \leq N ,M\leq 10^6
• 1\leq \mathrm{MOD}\leq 500
• All values in input are integers.

Sample Input 1

2 2 4

Sample Output 1

2 1 2 1

There are 6 non-decreasing sequences of length 2 consisting of integers between 0 and 2: (0, 0), (0, 1),(0,2), (1,1),(1,2),(2,2). Here, we have:

• 2 sequences whose sums are congruent to 0 modulo 4: (0,0),(2,2);

• 1 sequence whose sum is congruent to 1 modulo 4: (0,1);

• 2 sequences whose sums are congruent to 2 modulo 4: (0,2),(1,1);

• 1 sequence whose sum is congruent to 3 modulo 4: (1,2).

Sample Input 2

3 45 3

Sample Output 2

5776 5760 5760

Sample Input 3

1000000 1000000 6

Sample Output 3

340418986 783857865 191848859 783857865 340418986 635287738

Print the counts modulo 998244353.