Bar code 는 진하고 연한(진한 바를 1 , 연한 바를 0) bar 로 교대로 이루어진다. 시작은 진한 바로 시작한다.

그림 1 은 총 7 칸에 4 개의 bar 로 이루어져 있고, bar 중에서 가장 넓은 bar 는 3 번째 bar 로 3 칸을 차지하고 있다.

BC(n,k,m) 은 n 개의 유니트를 가지고 k 개의 bar 로 이루어져 있고, 각 바의 폭은 최대 m 이란 의미이다.

그러면 , BC(7,4,3) 으로 나올 수 있는 모든 종류는 다음과 같다.

1 , 0 은 각각 진하고 연한 색을 의미하고 , 사전식 순서로 차례를 정한다면 그림 1 은 BC(7,4,3)에서 4 번째에 나타난다.

입력

다음 s 줄에는 그림 2 와 같은 형태의 문자열이 주어진다.

출력

입출력 예

입력

7 4 3
5
1001110
1110110
1001100
1001110
1000100

출력

16
4
15
3
4
0

출처: ioi 기출