빌런 호석

치르보기 빌딩에는 $1$층부터 $N$층까지 운행하는 엘리베이터가 있다. 엘리베이터의 층수를 보여주는 디스플레이에는 $K$ 자리의 수가 나타난다. 수는 $0$으로 시작할 수도 있다. $0$부터 $9$까지의 각 숫자가 디스플레이에 표시되는 방식은 아래와 같다. 각 숫자는 7개의 표시등 가운데 일부에 불이 들어오면서 표현된다.

예를 들어 $K=4$인 경우에 $1680$층과 $501$층은 아래와 같이 보인다.

빌런 호석은 치르보기 빌딩 엘리베이터 디스플레이의 LED 가운데 최소 $1$개, 최대 $P$개를 반전시킬 계획을 세우고 있다. 반전이란 켜진 부분은 끄고, 꺼진 부분은 켜는 것을 말한다. 예를 들어 숫자 $1$을 $2$로 바꾸려면 총 5개의 LED를 반전시켜야 한다. 또한 반전한 뒤 디스플레이에 올바른 수가 보이면서 $1$ 이상 $N$ 이하가 되도록 바꿔 사람들을 헷갈리게 할 예정이다. 치르보기를 사랑하는 모임의 회원인 당신은 호석 빌런의 행동을 미리 파악해서 혼쭐을 내주려 한다. 현재 엘리베이터가 실제로는 $X$층에 멈춰 있을 때, 호석이가 반전시킬 LED를 고를 수 있는 경우의 수를 구해보자.

첫째 줄에 $N, K, P, X$ 가 공백으로 구분되어 주어진다.

호석 빌런이 엘리베이터 LED를 올바르게 반전시킬 수 있는 경우의 수를 구해보자.

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