Multiply or Add Possibilities

Just as Jill is about to calculate the probability from the Double or Add Possibilities problem, Jack speaks up again. He says that an even better game would be to use the rules from the Multiply or Add game, starting at 0 and choosing some integer m, such that each turn he can either multiply by m or add some number between 1 and m-1 at each turn. After i turns some number n is produced, after which Jill must guess n being told only the values of i and m.

Formally, the rules are as follows:

• Jack always starts at the number 0.
• Each turn, Jack can perform one of two actions, either
  • Multiply the current number by m, or
  • Add some value between 1 and m - 1 to the current number.
• However he added the previous turn, then Jack must multiply on the next turn. That is, he cannot perform two "add" actions consecutively.
• After performing i turns yielding the final number n, Jack tell Jill the values of both i and m.
• Without having witnessed the actions made by Jack, Jill must guess the value of n.

The first move cannot be 0 -> 0.
Note that any move from 1 -> m should be regarded as multiplication rather than addition.

Jill ponders for a moment, reflecting on the insight she gained from the previous problem and devising a new method to calculate the probability of this new question.

Problem Statement

Given a number of moves i and integer m, calculate u being the total quantity of unique integers which could be yielded after applying the above rules to the starting number 0 for a total of i turns.

The probability to guess n will be equal to 1 / u.

Input Data
First line is Q, the quantity of testcases.
Q lines will then follow, each with a testcase in the format i m.

Answer
Should consist of Q space-separated values of u corresponding to each testcase.
Report all values modulo 1000000007

Example

input data:
5
1 2
3 4
56 78
987654321 123456789
123456789 987654321

answer:
1 12 88187685 472512096 600147221