Yayoi and Iori like traveling together.
One day, they arrived to a strange planet.
The currency system on the planet is really simple:
the denominations are precisely all nonnegative powers of an integer M.
I.e., the coins have the following values: 1, M, M^2, M^3, ...
Yayoi and Iori now want to buy souvenirs for their friends.
The total price of those souvenirs is X.
Yayoi and Iori would like to pay this amount exactly.
They have a sufficient supply of coins with each of the available values.
You are given the int M and the long X.
Let W be the number of different ways in which they can pay the required amount.
Here, two ways are considered different if and only if there is some value such that in each way we use a different number of coins with this value.
As W can be huge, return the value (W modulo 1,000,000,007).