Description

There are $k$ people, and X wants to persecute these $k$ people.

Each of these $k$ people has a number, from $1$ to $k$.

X has $n + m$ numbers: $n$ of them are $1$, and the other $m$ numbers have values that X can choose (once each number is fixed, it cannot be changed).

X can persecute a person if and only if he can choose some of the numbers in his hand whose sum equals that person's number. If so, the persecution succeeds. (The numbers are not consumed.)

Since X has great power and is very evil, he wants to carry out the persecutions starting from person $1$, one by one.

Since Little Z is also among those being persecuted, he is very nervous and wants you to tell him: starting from the first person, what is the maximum number of consecutive people X can persecute?

Because there are too many persecuted people, please output the answer modulo $1000000007$.

Input Format

The first line contains two integers $n, m$, meaning X has $n$ numbers equal to $1$, and $m$ numbers whose values can be chosen.

Output Format

Tell Little Z how many people X can persecute.

1 2

7

2 2

11

Hint

Sample 1 Explanation

X chooses two numbers as $2$ and $4$. It can be seen that he can persecute $7$ people consecutively.

Sample 2 Explanation

X chooses two numbers as $3$ and $6$. It can be seen that he can persecute $11$ people consecutively.

Constraints

This problem uses bundled testdata.

• Subtask 1 (50 points): $1 \le n \le 5$, $1 \le m \le 5$.
• Subtask 2 (30 points): It is guaranteed that the answer is within $10^{18}$ before taking modulo.
• Subtask 3 (20 points): No special restrictions.

For $100\%$ of the testdata, $1 \le n \le 10^6$, $1 \le m \le 10^9$.

Translated by ChatGPT 5