Given a series defined by:

F(n) = (F(n - 1) + F(n - 1) + F(n - 1) ... + pth time) % 1000000007 (10⁹+7).

where p is any prime number between (1-100). Now you are provided n and nth term of the sequence. Find the first term of the given series.

Input

Input contains only three integers n, nth term and p separated by spaces.

Here n will be between 1 to 1000000000 inclusive.

and each term ranges between 0 to 1000000006 inclusive.

Output

Output a single integer that is first term of the sequence.

Example

Input: 
5 32 2

Output: 
2