Problem Description
A sequence of integers is called a perfect sequence when all the partial sums a0, a0 + a1, a0 + a1 + a2, ..., a0 + a1 + ... + an are all positive.
Letⅴs consider a specific sequence , (ai = 1 or ai = (1-m), 1 ÷ i ÷ (m*n) ) , whose total sum is 1. Actually you can easily deduce that there are n occurrences of (1-m). So how many of these sequences are perfect sequences.
Input
Input contains several testcases.
For each test case, you will be given n, m (1 ÷ m, n ÷ 100000) in a single line.
Process to the end of the file.
Output
On each single line, output a number r mod 100000007, r is the number of perfect sequences (ai = 1 or ai = (1-m), 1 ÷ i ÷ (m*n) ) .
Sample Input
4 2
5 2
3 4
Sample Output
14
42
22
