Interval#4902

Interval

1 second

64 megabytes

Hard

Determine the number of integers within the closed interval $[X, Y]$ [X, Y] that can be represented as the sum of distinct powers of $b$ ; that is, the number of integers $Z$ such that each power of $b$ is used at most once in the representation:

Z = a_{n} b^{n} + a_{n - 1} b^{n - 1} + \dots + a_{1} b^{1} + a_{0} b^{0},

Z = a_n b^n + a_{n-1} b^{n-1} + \dots + a_1 b^1 + a_0 b^0,

where $a_{i} \in {0, 1}$ a_i \in \{0, 1\}.

Input

The first line contains the integers $X$ , $Y$ , and $b$ ( $1 \leq X \leq Y \leq 1 0^{100}$ 1 \le X \le Y \le 10^{100}, $2 \leq b \leq 10$ 2 \le b \le 10), separated by spaces.

Output

Print a single integer — the number of integers in $[X, Y]$ [X, Y] that can be expressed as the sum of distinct powers of $b$ .

Examples

Example 1

Note

For $X = 4$ X = 4, $Y = 10$ Y = 10, $b = 3$ b = 3, the numbers are:

4910 = 3^{1} + 3^{0}, = 3^{2}, = 3^{2} + 3^{0} .

\begin{align*} 4 &= 3^1 + 3^0,\\ 9 &= 3^2,\\ 10 &= 3^2 + 3^0. \end{align*}

For $X = 1$ X = 1, $Y = 12$ Y = 12, $b = 2$ b = 2, the numbers are:

123456789101112 = 2^{0}, = 2^{1}, = 2^{1} + 2^{0}, = 2^{2}, = 2^{2} + 2^{0}, = 2^{2} + 2^{1}, = 2^{2} + 2^{1} + 2^{0}, = 2^{3}, = 2^{3} + 2^{0}, = 2^{3} + 2^{1}, = 2^{3} + 2^{1} + 2^{0}, = 2^{3} + 2^{2} .

\begin{align*} 1 &= 2^0,\\ 2 &= 2^1,\\ 3 &= 2^1 + 2^0,\\ 4 &= 2^2,\\ 5 &= 2^2 + 2^0,\\ 6 &= 2^2 + 2^1,\\ 7 &= 2^2 + 2^1 + 2^0,\\ 8 &= 2^3,\\ 9 &= 2^3 + 2^0,\\ 10 &= 2^3 + 2^1,\\ 11 &= 2^3 + 2^1 + 2^0,\\ 12 &= 2^3 + 2^2. \end{align*}

[X, Y]

Z = a_{n} b^{n} + a_{n - 1} b^{n - 1} + \dots + a_{1} b^{1} + a_{0} b^{0},

a_{i} \in {0, 1}

1 \leq X \leq Y \leq 1 0^{100}

2 \leq b \leq 10

[X, Y]

X = 4

Y = 10

b = 3

4910 = 3^{1} + 3^{0}, = 3^{2}, = 3^{2} + 3^{0} .

X = 1

Y = 12

b = 2

123456789101112 = 2^{0}, = 2^{1}, = 2^{1} + 2^{0}, = 2^{2}, = 2^{2} + 2^{0}, = 2^{2} + 2^{1}, = 2^{2} + 2^{1} + 2^{0}, = 2^{3}, = 2^{3} + 2^{0}, = 2^{3} + 2^{1}, = 2^{3} + 2^{1} + 2^{0}, = 2^{3} + 2^{2} .