22251번 - 빌런 호석

문제

치르보기 빌딩은 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 $

힌트