Problem Statement

The following five days are called the five seasonal festivals (gosekku).

• January \color{red}{\mathbf{7}}
• March 3
• May 5
• July 7
• September 9

If month M, day D is one of the five seasonal festivals, output Yes; otherwise, output No.

Constraints

• M and D are integers.
• Month M, day D is a valid date in a leap year in the Gregorian calendar.

Sample Input 1

3 3

Sample Output 1

Yes

March 3 is one of the five seasonal festivals, so output Yes.

Sample Input 2

1 1

Sample Output 2

No

January 1 is not one of the five seasonal festivals, so output No.

Sample Input 3

4 4

Sample Output 3

No

Sample Input 4

11 7

Sample Output 4

No

Problem Statement

There is a grid with H rows and W columns. Takahashi is going to paint each cell of this grid black or white.

He paints all cells on the border of the grid black, and all other cells white. Output the grid after he has painted it.

Constraints

• 3\le H\le10
• 3\le W\le10
• All input values are integers.

Sample Input 1

4 5

Sample Output 1

#####
#...#
#...#
#####

For example, cell (1,1) is on the border. This is because there are only two cells edge-adjacent to cell (1,1): cells (1,2) and (2,1). Thus, cell (1,1) is painted black, so the first character of the first line should be #.

Conversely, for example, cell (3,4) is not on the border. This is because there are four cells edge-adjacent to cell (3,4): cells (2,4), (3,3), (3,5), and (4,4). Thus, cell (3,4) is painted white, so the fourth character of the third line should be ..

Sample Input 2

5 6

Sample Output 2

######
#....#
#....#
#....#
######

Problem Statement

Artist Takasago has created an object in the shape of a fish skeleton.

The object consists of N ribs and one spine. The ribs are numbered 1 through N.

He wants to write one string on each of the N+1 bones, satisfying all of the following conditions.

• The length of the string written on the spine is N.
• For each rib i = 1, \dots, N, the following hold.
  • The length of the string written on rib i is A_i.
  • The B_i-th character of the string written on rib i equals the i-th character of the string written on the spine.
• Each of the strings written on the N+1 bones is one of S_1, \cdots, S_M (duplicates allowed).

S_1, \cdots, S_M are strings consisting of lowercase English letters, and they are all distinct.

For each j = 1, \cdots, M, answer the following question.

• Among the ways to write strings satisfying the conditions, is there one where the string written on the spine is S_j?

Constraints

• N is an integer.
• 1 \leq N \leq 10
• A_i and B_i are integers. (1 \leq i \leq N)
• 1 \leq B_i \leq A_i \leq 10 (1 \leq i \leq N)
• M is an integer.
• 1 \leq M \leq 200\,000
• S_j is a string consisting of lowercase English letters. (1 \leq j \leq M)
• 1 \leq |S_j| \leq 10 (1 \leq j \leq M)
• S_1, \cdots, S_M are pairwise distinct.

Sample Input 1

5
5 3
5 2
4 1
5 1
3 2
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 1

Yes
Yes
No
No
No
No
No
No

By writing chris, retro, tuna, retro, cod on ribs 1,2,3,4,5 respectively, the conditions are satisfied with retro written on the spine.

• The length of retro is 5.
• For each rib, the following hold.
  • The string written on rib 1 is chris, which has length 5. Its third character is r, which equals the first character of retro.
  • The string written on rib 2 is retro, which has length 5. Its second character is e, which equals the second character of retro.
  • The string written on rib 3 is tuna, which has length 4. Its first character is t, which equals the third character of retro.
  • The string written on rib 4 is retro, which has length 5. Its first character is r, which equals the fourth character of retro.
  • The string written on rib 5 is cod, which has length 3. Its second character is o, which equals the fifth character of retro.

By writing itchy, chris, rock, itchy, ash on ribs 1,2,3,4,5 respectively, the conditions are satisfied with chris written on the spine.

Sample Input 2

5
5 1
5 2
5 3
5 4
5 5
8
retro
chris
itchy
tuna
crab
rock
cod
ash

Sample Output 2

Yes
Yes
Yes
No
No
No
No
No

Problem Statement

You are given strings S and T consisting of lowercase English letters.

Among the non-empty substrings s of S, count those that do not contain T as a (not necessarily contiguous) subsequence.

Here, two substrings of S are distinguished if they are taken from different positions, even if they are equal as strings.

Constraints

• S is a string consisting of lowercase English letters.
• 1\le |S|\le2\times10 ^ 5, where |S| is the length of S.
• T is a string consisting of lowercase English letters.
• 1\le |T|\le50, where |T| is the length of T.

Sample Input 1

abrakadabra
aba

Sample Output 1

51

For example, the substring abr consisting of the first through third characters of S does not contain T as a subsequence. Including this, there are 51 substrings satisfying the condition, such as k (only the fifth character of S) and akada (the fourth through eighth characters of S).

Note that the string abr can be obtained both as the substring from the first to third characters of S and as the substring from the eighth to tenth characters of S, but they are taken from different positions, so they are counted separately.

Sample Input 2

aaaaa
a

Sample Output 2

0

All non-empty substrings of S contain T as a subsequence.

Thus, there are no substrings satisfying the condition, so output 0.

Sample Input 3

rdddrdtdcdrrdcredctdordoeecrotet
dcre

Sample Output 3

263

Problem Statement

Your lucky Greek letter for today is sigma. Solve this problem that uses sigma twice, and good fortune will surely come your way.

You are given a sequence of positive integers A = (A_1, \cdots, A_N) of length N and a sequence of positive integers B = (B_1, \cdots, B_M) of length M.

Find the value, modulo 998244353, of \displaystyle \sum_{i=1}^{N} \sum_{j=1}^{M} A_i \cdot B_j \cdot (i \bmod j).

Constraints

• 1 \leq N,M \leq 5 \times 10^5
• 1 \leq A_i, B_j \leq 5 \times 10^5
• All input values are integers.

Sample Input 1

6 4
1 6 9 2 3 1
1 10 3 7

Sample Output 1

508

The sum of the following 24 values is 508.

• A_1 \cdot B_1 \cdot (1 \bmod 1) = 1 \cdot 1 \cdot 0 = 0
• A_1 \cdot B_2 \cdot (1 \bmod 2) = 1 \cdot 10 \cdot 1 = 10
• A_1 \cdot B_3 \cdot (1 \bmod 3) = 1 \cdot 3 \cdot 1 = 3
• A_1 \cdot B_4 \cdot (1 \bmod 4) = 1 \cdot 7 \cdot 1 = 7
• A_2 \cdot B_1 \cdot (2 \bmod 1) = 6 \cdot 1 \cdot 0 = 0
• A_2 \cdot B_2 \cdot (2 \bmod 2) = 6 \cdot 10 \cdot 0 = 0
• A_2 \cdot B_3 \cdot (2 \bmod 3) = 6 \cdot 3 \cdot 2 = 36
• A_2 \cdot B_4 \cdot (2 \bmod 4) = 6 \cdot 7 \cdot 2 = 84
• A_3 \cdot B_1 \cdot (3 \bmod 1) = 9 \cdot 1 \cdot 0 = 0
• A_3 \cdot B_2 \cdot (3 \bmod 2) = 9 \cdot 10 \cdot 1 = 90
• A_3 \cdot B_3 \cdot (3 \bmod 3) = 9 \cdot 3 \cdot 0 = 0
• A_3 \cdot B_4 \cdot (3 \bmod 4) = 9 \cdot 7 \cdot 3 = 189
• A_4 \cdot B_1 \cdot (4 \bmod 1) = 2 \cdot 1 \cdot 0 = 0
• A_4 \cdot B_2 \cdot (4 \bmod 2) = 2 \cdot 10 \cdot 0 = 0
• A_4 \cdot B_3 \cdot (4 \bmod 3) = 2 \cdot 3 \cdot 1 = 6
• A_4 \cdot B_4 \cdot (4 \bmod 4) = 2 \cdot 7 \cdot 0 = 0
• A_5 \cdot B_1 \cdot (5 \bmod 1) = 3 \cdot 1 \cdot 0 = 0
• A_5 \cdot B_2 \cdot (5 \bmod 2) = 3 \cdot 10 \cdot 1 = 30
• A_5 \cdot B_3 \cdot (5 \bmod 3) = 3 \cdot 3 \cdot 2 = 18
• A_5 \cdot B_4 \cdot (5 \bmod 4) = 3 \cdot 7 \cdot 1 = 21
• A_6 \cdot B_1 \cdot (6 \bmod 1) = 1 \cdot 1 \cdot 0 = 0
• A_6 \cdot B_2 \cdot (6 \bmod 2) = 1 \cdot 10 \cdot 0 = 0
• A_6 \cdot B_3 \cdot (6 \bmod 3) = 1 \cdot 3 \cdot 0 = 0
• A_6 \cdot B_4 \cdot (6 \bmod 4) = 1 \cdot 7 \cdot 2 = 14

Sample Input 2

20 20
36625 195265 98908 111868 111868 47382 147644 472464 472464 416653 111868 195265 327972 327972 262769 75439 381156 451275 36625 195265
327972 111868 416653 177330 340019 262769 47382 262769 47382 340019 47382 262769 327972 327972 359676 381156 327972 36625 451275 381156

Sample Output 2

58141644

Problem Statement

You are given a positive integer N and a permutation P=(P _ 1,P _ 2,\ldots,P _ N) of (1,2,\ldots,N).

You are given an integer K. Find the number of pairs of integers (l,r) satisfying the following two conditions.

• 1\le l\le r\le N
• The inversion number of the sequence (P _ l,P _ {l+1},\ldots,P _ r) equals K.

Constraints

• 1\le N\le5\times10 ^ 5
• 0\le K\le\dfrac{N(N-1)}2
• 1\le P _ i\le N\ (1\le i\le N)
• P _ i\ne P _ j\ (1\le i\lt j\le N)
• All input values are integers.

Sample Input 1

7 3
6 3 2 1 7 5 4

Sample Output 1

5

For example, the inversion number of the sequence (P _ 1,P _ 2,P _ 3)=(6,3,2) is 3, so (l,r)=(1,3) satisfies the conditions. The other pairs satisfying the conditions are (l,r)=(2,4),(2,5),(4,7),(5,7), so output 5.

Sample Input 2

4 1
1 2 3 4

Sample Output 2

0

The inversion number of every contiguous subsequence of P is 0, so there are no pairs (l,r) satisfying the conditions. Thus, output 0.

Sample Input 3

25 18
14 19 24 8 12 11 6 5 3 13 22 15 17 2 9 4 7 18 10 25 23 16 1 20 21

Sample Output 3

3

Problem Statement

For a sequence X = (X_1, \dots, X_n) of positive integers, we call X a 221 sequence if and only if the length and value are equal for every (length, value) pair in its run-length encoding. More formally, a sequence satisfying the following condition is called a 221 sequence.

• For any integer pair (l, r) satisfying 1 \leq l \leq r \leq n, if all three of the following conditions hold, then (r-l+1) = X_l.
  • l = 1 or (l \geq 2 and X_{l-1} \neq X_l)
  • r = n or (r \leq n-1 and X_{r+1} \neq X_r)
  • X_l = X_{l+1} = \dots = X_r

For example, (2,2,3,3,3,1,2,2) is a 221 sequence, but (1,1) and (4,4,1,4,4) are not 221 sequences.

You are given a sequence A = (A_1, \dots, A_N) of positive integers of length N. Find the number of distinct 221 sequences that appear as a non-empty contiguous subsequence of A.

Even if two subsequences are extracted from different positions, they are counted as one if they are equal as sequences.

Constraints

• 1 \leq N \leq 500\,000
• 1 \leq A_i \leq 9
• All input values are integers.

Sample Input 1

23
2 2 3 3 3 1 1 1 3 3 3 1 2 2 2 1 9 1 4 4 4 4 4

Sample Output 1

14

The 221 sequences that appear as a non-empty contiguous subsequence of A are the following 14:

• (1)
• (1,2,2)
• (1,3,3,3)
• (1,3,3,3,1)
• (1,3,3,3,1,2,2)
• (1,4,4,4,4)
• (2,2)
• (2,2,1)
• (2,2,3,3,3)
• (2,2,3,3,3,1)
• (3,3,3)
• (3,3,3,1)
• (3,3,3,1,2,2)
• (4,4,4,4)

Sample Input 2

2
6 7

Sample Output 2

0

No 221 sequences appear as a non-empty contiguous subsequence of A.