Problem Statement

Today is August 24, one of the five Product Days in a year.

A date m-d (m is the month, d is the date) is called a Product Day when d is a two-digit number, and all of the following conditions are satisfied (here d_{10} is the tens digit of the day and d_1 is the ones digit of the day):

• d_1 \geq 2
• d_{10} \geq 2
• d_1 \times d_{10} = m

Takahashi wants more Product Days, and he made a new calendar called Takahashi Calendar where a year consists of M month from Month 1 to Month M, and each month consists of D days from Day 1 to Day D.

In Takahashi Calendar, how many Product Days does a year have?

Constraints

• All values in input are integers.
• 1 \leq M \leq 100
• 1 \leq D \leq 99

Sample Input 1

15 40

Sample Output 1

10

There are 10 Product Days in a year, as follows (m-d denotes Month m, Day d):

• 4-22
• 6-23
• 6-32
• 8-24
• 9-33
• 10-25
• 12-26
• 12-34
• 14-27
• 15-35

Sample Input 2

12 31

Sample Output 2

5

Sample Input 3

1 1

Sample Output 3

0

Problem Statement

We have a sequence of N integers A~=~A_0,~A_1,~...,~A_{N - 1}.

Let B be a sequence of K \times N integers obtained by concatenating K copies of A. For example, if A~=~1,~3,~2 and K~=~2, B~=~1,~3,~2,~1,~3,~2.

Find the inversion number of B, modulo 10^9 + 7.

Here the inversion number of B is defined as the number of ordered pairs of integers (i,~j)~(0 \leq i < j \leq K \times N - 1) such that B_i > B_j.

Constraints

• All values in input are integers.
• 1 \leq N \leq 2000
• 1 \leq K \leq 10^9
• 1 \leq A_i \leq 2000

Sample Input 1

2 2
2 1

Sample Output 1

3

In this case, B~=~2,~1,~2,~1. We have:

• B_0 > B_1
• B_0 > B_3
• B_2 > B_3

Thus, the inversion number of B is 3.

Sample Input 2

3 5
1 1 1

Sample Output 2

0

A may contain multiple occurrences of the same number.

Sample Input 3

10 998244353
10 9 8 7 5 6 3 4 2 1

Sample Output 3

185297239

Be sure to print the output modulo 10^9 + 7.

Problem Statement

There are 2N squares arranged from left to right. You are given a string of length 2N representing the color of each of the squares.

The color of the i-th square from the left is black if the i-th character of S is B, and white if that character is W.

You will perform the following operation exactly N times: choose two distinct squares, then invert the colors of these squares and the squares between them. Here, to invert the color of a square is to make it white if it is black, and vice versa.

Throughout this process, you cannot choose the same square twice or more. That is, each square has to be chosen exactly once.

Find the number of ways to make all the squares white at the end of the process, modulo 10^9+7.

Two ways to make the squares white are considered different if and only if there exists i (1 \leq i \leq N) such that the pair of the squares chosen in the i-th operation is different.

Constraints

• 1 \leq N \leq 10^5
• |S| = 2N
• Each character of S is B or W.

Sample Input 1

2
BWWB

Sample Output 1

4

There are four ways to make all the squares white, as follows:

• Choose Squares 1, 3 in the first operation, and choose Squares 2, 4 in the second operation.
• Choose Squares 2, 4 in the first operation, and choose Squares 1, 3 in the second operation.
• Choose Squares 1, 4 in the first operation, and choose Squares 2, 3 in the second operation.
• Choose Squares 2, 3 in the first operation, and choose Squares 1, 4 in the second operation.

Sample Input 2

4
BWBBWWWB

Sample Output 2

288

Sample Input 3

5
WWWWWWWWWW

Sample Output 3

0

Problem Statement

AtCoder's head office consists of N rooms numbered 1 to N. For any two rooms, there is a direct passage connecting these rooms.

For security reasons, Takahashi the president asked you to set a level for every passage, which is a positive integer and must satisfy the following condition:

• For each room i\ (1 \leq i \leq N), if we leave Room i, pass through some passages whose levels are all equal and get back to Room i, the number of times we pass through a passage is always even.

Your task is to set levels to the passages so that the highest level of a passage is minimized.

Constraints

• N is an integer between 2 and 500 (inclusive).

Sample Input 1

3

Sample Output 1

1 2
1

The following image describes this output:

For example, if we leave Room 2, traverse the path 2 \to 3 \to 2 \to 3 \to 2 \to 1 \to 2 while only passing passages of level 1 and get back to Room 2, we pass through a passage six times.

Problem Statement

There are N cards placed on a grid with H rows and W columns of squares.

The i-th card has an integer A_i written on it, and it is placed on the square at the R_i-th row from the top and the C_i-th column from the left.

Multiple cards may be placed on the same square.

You will first pick up at most one card from each row.

Then, you will pick up at most one card from each column.

Find the maximum possible sum of the integers written on the picked cards.

Constraints

• All values are integers.
• 1 \leq N \leq 10^5
• 1 \leq H, W \leq 10^5
• 1 \leq A_i \leq 10^5
• 1 \leq R_i \leq H
• 1 \leq C_i \leq W

Sample Input 1

6 2 2
2 2 2
1 1 8
1 1 5
1 2 9
1 2 7
2 1 4

Sample Output 1

28

The sum of the integers written on the picked cards will be 28, the maximum value possible, if you pick up cards as follows:

• Pick up the fourth card from the first row.
• Pick up the sixth card from the second row.
• Pick up the second card from the first column.
• Pick up the fifth card from the second column.

Sample Input 2

13 5 6
1 3 35902
4 6 19698
4 6 73389
3 6 3031
3 1 4771
1 4 4784
2 1 36357
2 1 24830
5 6 50219
4 6 22645
1 2 30739
1 4 68417
1 5 78537

Sample Output 2

430590

Sample Input 3

1 100000 100000
1 1 1

Sample Output 3

1

Problem Statement

Find the number of sequences of N non-negative integers A_1, A_2, ..., A_N that satisfy the following conditions:

• L \leq A_1 + A_2 + ... + A_N \leq R
• When the N elements are sorted in non-increasing order, the M-th and (M+1)-th elements are equal.

Since the answer can be enormous, print it modulo 10^9+7.

Constraints

• All values in input are integers.
• 1 \leq M < N \leq 3 \times 10^5
• 1 \leq L \leq R \leq 3 \times 10^5

Sample Input 1

4 2 3 7

Sample Output 1

105

The sequences of non-negative integers that satisfy the conditions are:

\begin{aligned} &(1, 1, 1, 0), (1, 1, 1, 1), (2, 1, 1, 0), (2, 1, 1, 1), (2, 2, 2, 0), (2, 2, 2, 1), \\ &(3, 0, 0, 0), (3, 1, 1, 0), (3, 1, 1, 1), (3, 2, 2, 0), (4, 0, 0, 0), (4, 1, 1, 0), \\ &(4, 1, 1, 1), (5, 0, 0, 0), (5, 1, 1, 0), (6, 0, 0, 0), (7, 0, 0, 0)\end{aligned}

and their permutations, for a total of 105 sequences.

Sample Input 2

2 1 4 8

Sample Output 2

3

The three sequences that satisfy the conditions are (2, 2), (3, 3), and (4, 4).

Sample Input 3

141592 6535 89793 238462

Sample Output 3

933832916