P6195 [EER1] Persecution

"In Germany they first came for the Communists,　 and I didn't speak up because I wasn't a Communist.　　 Then they came for the Jews,　　 and I didn't speak up because I wasn't a Jew.　　 Then they came for the trade unionists,　　 and I didn't speak up because I wasn't a trade unionist. Then they came for the Catholics,　　 and I didn't speak up because I was a Protestant.　　 Then they came for me , and by that time no one was left to speak up." -- Pastor Martin Niemöller "At first they persecuted the Communists, and I said nothing, because I was not a follower of Marx. Later they persecuted the Jews, and I said nothing, because I was a Germanic person. After that they persecuted the Catholics, and I said nothing, because I was a Protestant pastor. In the end they came for me. I looked around, but there was no one left to speak for me."

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$.

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

Tell Little Z how many people X can persecute.

**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