Given a series defined by:

F(n)=(F(n-1)+F(n-1)+F(n-1)......+pth time)%1000000007 (10^9+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 seperated 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