The Return of the Tteokfire

A Tteokfire stays young by eating tteokguk, the Korean rice cake soup.

A Tteokfire ages one year for every bowl of tteokguk it eats. Digestion is instant, so it can eat as many bowls in one day as it likes. In exchange, a Tteokfire that goes a single day without tteokguk dies that day, no matter how much it ate before.

Didi knows only that one Tteokfire died on day $M$ at age $N$. Didi wants to count how many ways that Tteokfire could have aged, but the count grows out of hand as the age rises, so counting by hand is hopeless.

A Tteokfire starts at age 0. One way of aging is the list of bowl counts for day 1 through day $M$ in order, and two ways are different when the count differs on at least one day. The Tteokfire ate nothing on day $M$, which is why it died that day.

For $N$ equal to 3 and $M$ equal to 3 there are two ways: 1 bowl on day 1, 2 bowls on day 2 and 0 bowls on day 3, or 2 bowls on day 1, 1 bowl on day 2 and 0 bowls on day 3.

The first line has the number of test cases $T$ ($1 \le T \le 1000$).

Each of the next $T$ lines has two integers $N$ ($0 \le N \le 10^9$) and $M$ ($1 \le M \le 10^9$), separated by a space.

For each test case, print the number of ways of aging modulo 100007 on its own line. Note that 100007 is not a modulus you see often.