No Division Allowed

In order to stop the division among the fighters, the government of Eniarku decided to test the mathematical skills of the soldiers, while also boosting their morale in the fight against the invaders.

Given three integers $a, b$ and $x$, find the number of integers in the range $[a, b]$ such that they are not multiple of any of the integers in the range $[2, x]$. Since the answer can be really big, you need to print the remainder of the answer modulo $10^9 + 7$.

Since this is an easy challenge for the leader of Eniarku, he wants to see if you are up to the challenge.

Input

The first line of the input contains three integers, $a$, $b$ and $x$ ($1 ≤ a ≤ b ≤ 10^{100 \ 000}$), ($2 ≤ x ≤ 20$).

For tests worth $10$ points, $(1 ≤ b ≤ 10^6)$.

For tests worth $10$ more points, $(1 ≤ b ≤ 10^{18})$.

For tests worth $20$ more points, $(2 ≤ x ≤ 5)$.

For tests worth $30$ more points, $(2 ≤ x ≤ 10)$.

Output

The output will contain the answer, modulo $10^9 + 7$.

Examples

stdin

1 14 5

stdout

4

stdin

392692 6382655 20

stdout

1024429

Explanation

For the first sample, the numbers which are not divisible by either $2, 3, 4$ or $5$ are $1, 7, 11$ and $13$.