Problem Statement

You are given strings S and T. S consists of lowercase English letters, and T is obtained by inserting a lowercase English letter into S.

Find the position of the inserted character in T.
If there are multiple candidates, find any of them.

Constraints

• 1 \leq |S| \leq 5\times 10^5
• S consists of lowercase English letters.
• T is obtained by inserting a lowercase English letter into S.

Sample Input 1

atcoder
atcorder

Sample Output 1

5

The 5-th character from the beginning of T, r, is inserted.

Sample Input 2

million
milllion

Sample Output 2

5

One of the 3-rd, 4-th, and 5-th characters from the beginning of T is inserted. Thus, printing any one of 3, 4, and 5 is accepted.

Sample Input 3

vvwvw
vvvwvw

Sample Output 3

3

Problem Statement

N people numbered 1 through N tossed a coin several times. We know that person i's tosses resulted in A_i heads and B_i tails.

Person i's success rate of the tosses is defined by \displaystyle\frac{A_i}{A_i+B_i}. Sort people 1,\ldots,N in descending order of their success rates, with ties broken in ascending order of their assigned numbers.

Constraints

• 2\leq N \leq 2\times 10^5
• 0\leq A_i, B_i\leq 10^9
• A_i+B_i \geq 1
• All input values are integers.

Sample Input 1

3
1 3
3 1
2 2

Sample Output 1

2 3 1

Person 1's success rate is 0.25, person 2's is 0.75, and person 3's is 0.5.

Sort them in descending order of their success rates to obtain the order in Sample Output.

Sample Input 2

2
1 3
2 6

Sample Output 2

1 2

Note that person 1 and 2 should be printed in ascending order of their numbers, as they have the same success rates.

Sample Input 3

4
999999999 1000000000
333333333 999999999
1000000000 999999997
999999998 1000000000

Sample Output 3

3 1 4 2

Problem Statement

N cards, numbered 1 through N, are arranged in a line. For each i\ (1\leq i < N), card i and card (i+1) are adjacent to each other. Card i has A_i written on its front, and B_i written on its back. Initially, all cards are face up.

Consider flipping zero or more cards chosen from the N cards. Among the 2^N ways to choose the cards to flip, find the number, modulo 998244353, of such ways that:

• when the chosen cards are flipped, for every pair of adjacent cards, the integers written on their face-up sides are different.

Constraints

• 1\leq N \leq 2\times 10^5
• 1\leq A_i,B_i \leq 10^9
• All values in the input are integers.

Sample Input 1

3
1 2
4 2
3 4

Sample Output 1

4

Let S be the set of card numbers to flip.

For example, when S=\{2,3\} is chosen, the integers written on their visible sides are 1,2, and 4, from card 1 to card 3, so it satisfies the condition.

On the other hand, when S=\{3\} is chosen, the integers written on their visible sides are 1,4, and 4, from card 1 to card 3, where the integers on card 2 and card 3 are the same, violating the condition.

Four S satisfy the conditions: \{\},\{1\},\{2\}, and \{2,3\}.

Sample Input 2

4
1 5
2 6
3 7
4 8

Sample Output 2

16

Sample Input 3

8
877914575 602436426
861648772 623690081
476190629 262703497
971407775 628894325
822804784 450968417
161735902 822804784
161735902 822804784
822804784 161735902

Sample Output 3

48

Problem Statement

You have an integer 1 and a die that shows integers between 1 and 6 (inclusive) with equal probability.
You repeat the following operation while your integer is strictly less than N:

• Cast a die. If it shows x, multiply your integer by x.

Find the probability, modulo 998244353, that your integer ends up being N.

Constraints

• 2 \leq N \leq 10^{18}
• N is an integer.

Sample Input 1

6

Sample Output 1

239578645

One of the possible procedures is as follows.

• Initially, your integer is 1.
• You cast a die, and it shows 2. Your integer becomes 1 \times 2 = 2.
• You cast a die, and it shows 4. Your integer becomes 2 \times 4 = 8.
• Now your integer is not less than 6, so you terminate the procedure.

Your integer ends up being 8, which is not equal to N = 6.

The probability that your integer ends up being 6 is \frac{7}{25}. Since 239578645 \times 25 \equiv 7 \pmod{998244353}, print 239578645.

Sample Input 2

7

Sample Output 2

0

No matter what the die shows, your integer never ends up being 7.

Sample Input 3

300

Sample Output 3

183676961

Sample Input 4

979552051200000000

Sample Output 4

812376310

Problem Statement

You are given a string S consisting of lowercase English letters. Print the number of non-empty strings T that satisfy the following condition, modulo 998244353.

The concatenation TT of two copies of T is a subsequence of S (not necessarily contiguous).

Constraints

• S is a string consisting of lowercase English letters whose length is between 1 and 100, inclusive.

Sample Input 1

ababbaba

Sample Output 1

8

The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.

Sample Input 2

zzz

Sample Output 2

1

The only string satisfying the condition is z. Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from S = S_1S_2S_3 = zzz: S_1S_2 = zz, S_1S_3 = zz, and S_2S_3 = zz.

Sample Input 3

ppppqqppqqqpqpqppqpqqqqpppqppq

Sample Output 3

580