Problem Statement

Given a positive integer K, find the number of triples of positive integers (A, B, C) such that ABC \leq K. Two triples that only differ in the order of numbers are also distinguished.

Constraints

• 1\leq K\leq 2\times 10^5
• K is an integer.

Sample Input 1

2

Sample Output 1

4

We have the following triples: (1,1,1),(1,1,2),(1,2,1),(2,1,1).

Sample Input 2

10

Sample Output 2

53

Sample Input 3

31415

Sample Output 3

1937281

Problem Statement

Given positive integers A, B, C, find the digit at the ones place in the decimal notation of A^{B^C}.

Constraints

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

Sample Input 1

4 3 2

Sample Output 1

4

The ones digit in the decimal notation of 4^{3^2}=4^9=262144 is 4.

Sample Input 2

1 2 3

Sample Output 2

1

Sample Input 3

3141592 6535897 9323846

Sample Output 3

2

Problem Statement

Given is a string S of length N. Let s_i denote the i-th character of S. Find the maximum number of times the following operation can be done.

• Choose three consecutive characters in S, s_i,s_{i+1},s_{i+2}\quad (1\leq i\leq |S|-2), such that s_i=s_{i+1}\neq s_{i+2}, and replace s_{i+2} with s_i.

Constraints

• 3 \leq |S| \leq 2\times 10^5
• S consists of lowercase English letters.

Sample Input 1

accept

Sample Output 1

3

We can do the operation three times, as follows:

• do it with i=2, changing the string to acccpt;
• do it with i=3, changing the string to acccct;
• do it with i=4, changing the string to accccc.

Sample Input 2

atcoder

Sample Output 2

0

Sample Input 3

anerroroccurred

Sample Output 3

16

Problem Statement

In a grid with N horizontal rows and M vertical columns of squares, we will write an integer between 1 and K (inclusive) on each square and define sequences A, B as follows:

• for each i=1,\dots, N, A_i is the minimum value written on a square in the i-th row;
• for each j=1,\dots, M, B_j is the maximum value written on a square in the j-th column.

Given N, M, K, find the number of different pairs of sequences that can be (A, B), modulo 998244353.

Constraints

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

Sample Input 1

2 2 2

Sample Output 1

7

(A_1,A_2,B_1,B_2) can be (1,1,1,1), (1,1,1,2), (1,1,2,1), (1,1,2,2), (1,2,2,2), (2,1,2,2), or (2,2,2,2) - there are seven candidates.

Sample Input 2

1 1 100

Sample Output 2

100

Sample Input 3

31415 92653 58979

Sample Output 3

469486242

Problem Statement

Given is a string S consisting of a and b. Find the lexicographically greatest string that can be obtained by applying the following operation to S zero or more times:

• Choose two characters of S that are the same letter. Reverse the string between them and delete the chosen two characters. In other words: let s_i denote the i-th character of S. Choose i < j such that s_i = s_j and replace S with s_1\dots s_{i-1}s_{j-1}\dots s_{i+1}s_{j+1}\dots s_{|S|}.

In this problem, you are given T test cases. The i-th test case is represented as S_i and asks you to solve the problem above for S = S_i.

Constraints

• 1 \leq T \leq 2\times 10^5
• 1 \leq |S_i|\quad (i=1,\dots, T)
• 1 \leq |S_1| + \dots + |S_T| \leq 2\times 10^5
• S_i consists of a and b.

Sample Input 1

20
abbaa
babbb
aabbabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbabaaaaabbaababaaabbabbbbbaaaaa
babbbaaaabaababbbabaabaaaaababaa
bbaababababbbaaabaabababaabbabab
abaabbabaabaaaaabaaaabbaabaaaaab
aabababbabbabbabbaaaabbabbbabaab
aabababbabbbbaaaabbaaaaabbaaaabb
abbbbaabaaabababaaaababababbaabb
aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb
aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb
abababaaababaaabbbbbaaaaaaabbbbb
aabbaaaaababaabbbbbbbbbaabaaabbb
babababbababbbababbbbbababbbabbb
bbbbababbababbbabababbabbabbbbbb
aaaaaaaaaaaaaaaaababababbbabbbbb
aabababbabbabababababababbbbabbb

Sample Output 1

bba
bba
bbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbaaaaaaaa
bbbbbbbbbbbbbaaaaaaa
bbbbbbbbbbbbbbbb
bbbbbbbbbb
bbbbbbbbbbbbbbbbab
bbbbbbbbbbbbbb
bbbbbbbbbbbbbabb
abbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbaaaaaaaaa
bbbbbbbbbbbbbbbaaaaa
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbba

• In the 1-st test case, we can do the operation for the 1-st and 4-th characters to make S bba.
• In the 2-nd test case, we can do the operation for the 1-st and 5-th characters to make S bba.
• In the 3-rd test case, we can do the operation for the 1-st and 2-nd characters to make S bbabaa, then do it for the 3-rd and 5-th characters to make S bbba.

Problem Statement

Given is an integer sequence of length N+1: X_0,X_1,\ldots,X_N, where 0=X_0 < X_1 < \ldots < X_N holds.

Now, N people numbered 1 through N will appear on a number line. Person i will appear at a real coordinate chosen uniformly at random from the interval [X_{i-1},X_i].

Find the expected value of the smallest distance between two people, modulo 998244353.

Constraints

• 2 \leq N \leq 20
• 0=X_0 < X_1 < \cdots < X_N \leq 10^6

Sample Input 1

2
0 1 3

Sample Output 1

499122178

There are just two people, so the expected value of the smallest distance between two people is just the expected value of the distance between Person 1 and Person 2. The answer is 3/2.

Sample Input 2

5
0 3 4 8 9 14

Sample Output 2

324469854

The answer is 196249/172800.

Sample Input 3

20
0 38927 83112 125409 165053 204085 246405 285073 325658 364254 406395 446145 485206 525532 563762 605769 644863 683453 722061 760345 798556

Sample Output 3

29493181