Uzbek Trek

Traveler Todd plans on making the trek from Kazakhstan to Turkmenistan. In order to do so, he must navigate through the great nation of Uzbekistan.

Unfortunately, Uzbekistan imposes a tax on all foreign travelers who pass through it. Uzbekistan has imposed a particularly peculiar tax on Todd. While trekking through Uzbekistan, Todd must wear special shoes with the blue, white and green flag of Uzbekistan stiched onto them. Each shoe only lasts for a certain amount of footsteps. Specifically, the $k$th type of shoe lasts for exactly $p^ k$ footsteps, where $k \ge 0$ and $p$ is some predetermined value.

Being the prepared traveler he is, Todd calculates that it
will take him $n$
footsteps to travel through Uzbekistan. He then goes to the
Uzbek Shoe Depot where he plans to purchases all the shoes he
needs to complete his journey. The Uzbek Shoe Depot is a luxury
store, so Todd can order as many shoes as he likes. For each
shoe that Todd orders, he specifies the type $k$ of shoe that he wants. Todd would
hate to waste the durability of his purchased shoes; help him
determine how many ways he can order sets of shoes so that he
can wear all the shoes in sequence to travel **exactly** $n$
footsteps! The answer may be large, so output its remainder
modulo $10^9 + 7$.

Note that two sets of shoes are considered the same if they have the same number of shoes of each type. It does NOT matter what order Todd wears the shoes in.

The first line contains space-separated integers $n$ and $p$ such that $1 \leq n \leq 10^9$ and $10^2 \leq p \leq 10^9$.

Output a single integer, the number of unique sets of shoes Todd can order to travel exactly $n$ steps. Since the answer can be large, output it modulo $10^9 + 7$.

Sample Input 1 | Sample Output 1 |
---|---|

100 100 |
2 |