Problem Statement

In a certain programming contest, T-shirts are awarded to participants according to the following rules.

• All participants who ranked A-th or higher get a T-shirt.
• Additionally, from the participants who ranked between (A+1)-th and B-th (inclusive), C participants chosen uniformly at random get a T-shirt.

There were 1000 participants in this contest, and all of them got different ranks.
Iroha-chan, who participated in this contest, ranked X-th.
Find the probability that she gets a T-shirt.

Constraints

• All values in input are integers.
• 1 \le A < B \le 1000
• 1 \le C \le B-A
• 1 \le X \le 1000

Sample Input 1

30 500 20 103

Sample Output 1

0.042553191489

Iroha-chan ranked 103-rd.
She will get a T-shirt if she is among the 20 participants chosen uniformly at random from the 470 participants who ranked between 31-st and 500-th, which happens with probability \frac{20}{470}=0.04255319\dots.

Sample Input 2

50 500 100 1

Sample Output 2

1.000000000000

Iroha-chan ranked 1-st. This time, she is guaranteed to get a T-shirt.

Sample Input 3

1 2 1 1000

Sample Output 3

0.000000000000

Iroha-chan ranked 1000-th. This time, she will never get a T-shirt.

Problem Statement

You are given a string S. Find the lexicographically smallest string S' obtained by permuting the characters of S.

Here, for different two strings s = s_1 s_2 \ldots s_n and t = t_1 t_2 \ldots t_m, s \lt t holds lexicographically when one of the conditions below is satisfied.

• There is an integer i\ (1 \leq i \leq \min(n,m)) such that s_i \lt t_i and s_j=t_j for all integers j\ (1 \leq j \lt i).
• s_i = t_i for all integers i\ (1 \leq i \leq \min(n,m)), and n \lt m.

Constraints

• S is a string of length between 1 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Sample Input 1

aba

Sample Output 1

aab

Three strings can be obtained by permuting aba:

• aba
• aab
• baa

The lexicographically smallest among them is aab.

Sample Input 2

zzzz

Sample Output 2

zzzz

Problem Statement

Given an integer N, find the number of integers X that satisfy all of the following conditions, modulo 998244353.

• X is an N-digit positive integer.
• Let X_1,X_2,\dots,X_N be the digits of X from top to bottom. They satisfy all of the following:
  • 1 \le X_i \le 9 for all integers 1 \le i \le N;
  • |X_i-X_{i+1}| \le 1 for all integers 1 \le i \le N-1.

Constraints

• N is an integer.
• 2 \le N \le 10^6

Sample Input 1

4

Sample Output 1

203

Some of the 4-digit integers satisfying the conditions are 1111,1234,7878,6545.

Sample Input 2

2

Sample Output 2

25

Sample Input 3

1000000

Sample Output 3

248860093

Be sure to find the count modulo 998244353.

Problem Statement

You are given a string S consisting of A, B, C.

Let S^{(0)}:=S. For i=1,2,3,\ldots, let S^{(i)} be the result of simultaneously replacing the characters of S^{(i-1)} as follows: A → BC, B → CA, C → AB.

Answer Q queries. The i-th query is as follows.

• Print the k_i-th character from the beginning of S^{(t_i)}.

Constraints

• S is a string of length between 1 and 10^5 (inclusive) consisting of A, B, C.
• 1 \leq Q \leq 10^5
• 0 \leq t_i \leq 10^{18}
• 1 \leq k_i \leq \min(10^{18}, the length of S^{(t_i)})
• Q, t_i, k_i are integers.

Sample Input 1

ABC
4
0 1
1 1
1 3
1 6

Sample Output 1

A
B
C
B

We have S^{(0)}=ABC, S^{(1)}=BCCAAB.

Thus, the answers to the queries are A, B, C, B in the given order.

Sample Input 2

CBBAACCCCC
5
57530144230160008 659279164847814847
29622990657296329 861239705300265164
509705228051901259 994708708957785197
176678501072691541 655134104344481648
827291290937314275 407121144297426665

Sample Output 2

A
A
C
A
A

Problem Statement

Solve the following problem for T test cases.

Given an integer N and a string S, find the number of strings X that satisfy all of the conditions below, modulo 998244353.

• X is a string of length N consisting of uppercase English letters.
• X is a palindrome.
• X \le S in lexicographical order.
  • That is, X=S or X is lexicographically smaller than S.

Constraints

• 1 \le T \le 250000
• N is an integer between 1 and 10^6 (inclusive).
• In a single input, the sum of N over the test cases is at most 10^6.
• S is a string of length N consisting of uppercase English letters.

Sample Input 1

5
3
AXA
6
ABCZAZ
30
QWERTYUIOPASDFGHJKLZXCVBNMQWER
28
JVIISNEOXHSNEAAENSHXOENSIIVJ
31
KVOHEEMSOZZASHENDIGOJRTJVMVSDWW

Sample Output 1

24
29
212370247
36523399
231364016

This input contains five test cases.

Test case #1:
The 24 strings satisfying the conditions are AAA, ABA, ACA,..., AXA.

Test case #2:
S may not be a palindrome.

Test case #3:
Be sure to find the count modulo 998244353.

Problem Statement

Consider placing B black rooks and W white rooks on a grid with N horizontal rows and M vertical columns.

A placement of the rooks satisfying all of the following conditions is called a good placement.

• All B+W rooks are placed on the grid.
• At most one rook is placed in the same square.
• There is no pair of white rook and black rook attacking each other. That is, there is no pair of white rook and black rook such that one of them can reach the square in which the other is placed in one move.

Here, in one move, a rook can reach any square that is on a horizontal or vertical line from its current position and is reachable without jumping over another rook.

How many good placements are there? Since this count can be enormous, print it modulo 998244353.

Rooks in the same color are not distinguished.

Constraints

• 1 \leq N,M \leq 50
• 1 \leq B,W \leq 2500
• B+W \leq N \times M
• All values in input are integers.

Sample Input 1

2 2 1 1

Sample Output 1

4

There are four good placements as follows.

Sample Input 2

1 2 1 1

Sample Output 2

0

There may be no good placement.

Sample Input 3

40 40 30 30

Sample Output 3

467620384

Be sure to print the count modulo 998244353.

Problem Statement

N people numbered 1,2,\dots,N are standing in a row. Person i wears Color A_i.

Answer Q queries of the format below.

• You are given integers l and r. Considering only Person l,l+1,\dots,r, how many pairs of people wearing the same color can be formed at most?

Constraints

• All values in input are integers.
• 1 \le N \le 10^5
• 1 \le Q \le 10^6
• 1 \le A_i \le N
• 1 \le l \le r \le N in each query.

Sample Input 1

10
1 2 3 2 3 1 3 1 2 3
6
6 10
5 8
3 6
4 4
1 6
1 10

Sample Output 1

2
2
1
0
3
4

We have A=(1,2,3,2,3,1,3,1,2,3). This input contains six queries.

The first query is (l, r) = (6, 10). By pairing Person 6, 8 and paring Person 7, 10, we can form two pairs of people wearing the same color.

The second query is (l, r) = (5, 8). By pairing Person 5, 7 and paring Person 6, 8, we can form two pairs of people wearing the same color.

There can be a query where l=r.

Problem Statement

There are N squares numbered 1 to N. Initially, all squares are painted white.

Additionally, there are M balls numbered 1 to M in a box.

We repeat the procedure below until all squares are painted black.

1. Pick up a ball from a box uniformly at random.
2. Let x be the index of the ball. Paint Squares L_x, L_x+1, \ldots, R_x black.
3. Return the ball to the box.

Find the expected value of the number of times the procedure is done, modulo 998244353 (see Notes).

Notes

It can be proved that the sought expected value is always a rational number. Additionally, under the Constraints of this problem, when that value is represented as \frac{P}{Q} using two coprime integers P and Q, it can be proved that there uniquely exists an integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. You should find this R.

Constraints

• 1 \leq N,M \leq 400
• 1 \leq L_i \leq R_i \leq N
• For every square i, there is an integer j such that L_j \leq i \leq R_j.
• All values in input are integers.

Sample Input 1

3 3
1 1
1 2
2 3

Sample Output 1

499122180

The sought expected value is \frac{7}{2}.

We have 499122180 \times 2 \equiv 7\pmod{998244353}, so 499122180 should be printed.

Sample Input 2

13 10
3 5
5 9
3 12
1 13
9 11
12 13
2 4
9 12
9 11
7 11

Sample Output 2

10

Sample Input 3

100 11
22 43
84 93
12 71
49 56
8 11
1 61
13 80
26 83
23 100
80 85
9 89

Sample Output 3

499122193