The Answer to the Ultimate Question of Life, the Universe, and Everything

Time limit0.42sMemory limit420 MB

Summary

Given n, k, and the leading digit x of 2^n, count the powers of 2 up to 2^n whose leading digit is 4.

Level: Hard9 of 10
Topics: Math, Number theory
Solved: No attempts yet

Problem

$2^n$ has $k$ digits in decimal notation, and its leading digit is $x$ .

Given positive integers $n$ , $k$ , and $x$ , count the powers of 2 among the integers from $1$ to $2^n$ that start with the digit 4.

Input

The first line contains the positive integers $n$ , $k$ , and $x$ . ( $1 \le n, k \le 10^{18}$ ; $1 \le x \le 9$ ; $x \times 10^{k-1} \le 2^n < (x + 1) \times 10^{k-1}$ )

Only cases where $|2^n/10^{k-1} - x - 0.5| < 0.5 - 10^{-6}$ are given.

Output

Print the number of powers of 2 among the integers from $1$ to $2^n$ that start with the digit 4.

Examples4

Example 1
Input
```
4 2 1
```
Expected output
```
1
```
Example 2
Input
```
13 4 8
```
Expected output
```
2
```
Example 3
Input
```
255 77 5
```
Expected output
```
25
```

Example 4

Input

999999999999999992 301029995663981193 6

Expected output

96910013008056414