A sequence <a0, a1, a2, ..., an> 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 <a0, a1, a2, ..., amn>, (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 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.
On each single line, output a number r mod 100000007, r is the number of perfect sequences <a0, a1, a2, ..., amn> (ai = 1 or ai = (1-m), 1 ÷ i ÷ (m*n) ) .