Problem L
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.

Input

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

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$.

100 100

2