맥주 통

마침내 좋아하는 양조장의 지하 저장고에 들어왔다. 그곳에는 거대한 맥주 통 더미가 잔뜩 쌓여 있을 것이라 기대했다. 통들을 살펴보고, 어쩌면 통 안의 내용물까지 확인하고 싶었다. 내용물이 아주아주 많을 테니까.... 안타깝게도 통은 다섯 개뿐이고, 모두 절망적일 만큼 비어 있고 말라 있었다. 처음 네 통에는 숫자가 하나씩 칠해져 있다. 다섯 번째 통에는 쪽지가 붙어 있다. 어둠 속 통 뒤쪽 벽에는 낮고 겨우 알아볼 수 있는 문이 있는데, 보아하니 더 아래에 있는 저장고로 통하는 문인 듯하다. 그곳에는 가득 찬 통이 잔뜩 숨겨져 있으리라 기대한다. 문은 무겁고 복잡해 보이는 자물쇠로 잠겨 있다. 달리 할 만한 일이 떠오르지 않아, 다섯 번째 통에 붙은 쪽지를 살펴보기로 한다.

쪽지의 핵심은 이렇다.

첫 번째, 두 번째, 세 번째, 네 번째 통에 칠해진 숫자를 각각 A, B, K, C라고 하자. A, B, C는 한 자리 숫자다.

이제 아주 먼 미래에, (양자 효모로 구동되는) 엄청나게 강력한 컴퓨터가 정확히 K자리이고 각 자리가 A 또는 B인 모든 수의 목록을 출력한다고 상상하자. 그다음 똑같이 강력한 다른 컴퓨터가 그 목록과 값 C를 입력으로 받아, 목록 전체에서 숫자 C가 몇 번 나타나는지 계산한다.

그 결과를 1 000 000 007로 나눈 나머지를 문 잠금장치에 입력하면 문이 열리고 아래 저장고에 들어갈 수 있다.

가지고 온 공책에 그 수를 계산하기로 한다.

입력은 한 줄로 이루어지며, 처음 네 통에 칠해진 숫자를 나타내는 네 정수 A, B, K, C (1 ≤ A, B, C ≤ 9, 0 ≤ K ≤ 1000)가 주어진다.

문 잠금장치를 여는 정수 하나를 출력한다.