Villain Hoseok

Time limit1sMemory limit512 MB

Summary

Count how many K-digit displays (with leading zeros, value 1 to N) can be reached from the current display by flipping 1 to P of the seven-segment LEDs.

Level: Medium5 of 10
Topics: Brute force, Implementation, Math, Simulation
Solved: No attempts yet

Problem

The Chirbogi Building has an elevator that serves floors $1$ through $N$ . The display showing the elevator's floor shows a $K$ -digit number. The number may start with $0$ . Each digit from $0$ to $9$ is shown on the display as below. Each digit is drawn by lighting some of the 7 segments.

For example, when $K=4$ , floors $1680$ and $501$ look like this.

Villain Hoseok plans to flip at least $1$ and at most $P$ of the LEDs on the Chirbogi Building's elevator display. Flipping means turning a lit segment off and an unlit segment on. For example, to change the digit $1$ into $2$ , 5 LEDs must be flipped. After flipping, he will change the display to show a valid number between $1$ and $N$ inclusive, confusing people. As a member of the Association of People Who Love Chirbogi, you want to figure out Hoseok's action in advance and teach him a lesson. Given that the elevator is actually stopped at floor $X$ , count the number of ways Hoseok can choose which LEDs to flip.

Input

The first line gives $N, K, P, X$ separated by spaces.

Output

Count the number of ways Villain Hoseok can correctly flip the elevator LEDs.

Constraints

$1 ≤ X ≤ N < 10^K$
$1 ≤ K ≤ 6$
$1 ≤ P ≤ 42$

Examples2

Example 1
Input
```
9 1 2 5
```
Expected output
```
4
```
Example 2
Input
```
48 2 5 35
```
Expected output
```
30
```