FLT - Unique Sequence

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

Added by:ps_19
Date:2020-11-14
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:None

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.