와플

모든 사람이 슈퍼히어로 영화를 좋아한다. 하지만 슈퍼히어로의 진짜 취미를 아는 사람은 많지 않다. 아이언맨은 장미를 키우고, 헐크는 랩을 듣는 것을 좋아하며, 토르는 그림에 관심이 많다. 그리고 블랙 팬서는 와플에 푹 빠져 있다.

블랙 팬서에게는 자신만의 와플 레시피가 있고, 그는 이 와플을 친구들에게 대접한다. 블랙 팬서가 슈퍼히어로의 작은 약점을 사람들이 알기를 원하지 않기 때문에, 아무도 이 레시피를 모른다.

블랙 팬서의 특제 와플은 $m \cdot (a + b)$개의 칸으로 이루어진다. 처음 $a$칸에는 초콜릿이 묻어 있고, 다음 $b$칸에는 초콜릿이 없다. 그 뒤의 $a$칸에는 다시 초콜릿이 묻어 있으며, 이런 식으로 이어진다. 따라서 이 와플에는 초콜릿이 묻은 칸이 $m \cdot a$개, 묻지 않은 칸이 $m \cdot b$개 있다.

블랙 팬서는 굽는 일 말고도 할 일이 많아서, 와플을 직접 만들지 않고 가게에서 사 와서 레시피에 맞게 고치는 경우가 많다. 오늘은 $n$칸짜리 와플을 가게에서 샀다. 칸마다 초콜릿이 묻어 있기도 하고 없기도 하다. 블랙 팬서는 왼쪽 끝에서 칸을 몇 개(0개일 수도 있음) 떼어 내고, 오른쪽 끝에서도 몇 개(0개일 수도 있음) 떼어 내어, 정확히 $m \cdot (a + b)$칸으로 이루어진 연속된 부분만 남긴다. 그다음 일부 칸의 초콜릿을 벗겨 내서 특제 와플로 만들 수 있다. 특수 장비가 없어서, 원래 초콜릿이 없던 칸에는 초콜릿을 새로 묻히지 않는다. 이 작업을 마친 뒤에는 와플을 뒤집을 수 없다.

블랙 팬서가 가게에서 산 와플로 특제 와플을 만드는 방법의 수를 구하라. 남기는 원래 칸의 집합이 다르면 서로 다른 방법으로 본다.

첫째 줄에 가게에서 산 와플의 칸 수 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에는 길이 $n$의 문자열이 주어진다. 왼쪽에서 $i$번째 문자가 1이면 그 칸에 초콜릿이 묻어 있고, 0이면 묻어 있지 않다. 셋째 줄에는 특제 와플의 매개변수 $m$, $a$, $b$ ($1 \leq m, a, b$, $m \cdot (a + b) \leq n$)가 공백으로 구분되어 주어진다.

방법의 수를 나타내는 정수 하나를 출력한다.

첫 번째 예제에서 블랙 팬서가 특제 와플을 만드는 방법은 두 가지다.

1. 1번과 2번 칸을 남기고, 2번 칸의 초콜릿을 벗겨 낸다.
2. 2번과 3번 칸을 남긴다. 블랙 팬서는 3번과 4번 칸을 남길 수 없다. 3번 칸에는 초콜릿이 없는데, 특제 와플의 첫 칸에는 초콜릿이 묻어 있어야 하기 때문이다. 두 번째 예제에서 블랙 팬서는 초콜릿을 뒤집을 수 없어서 특제 와플을 만들 수 없다. 세 번째 예제에서 블랙 팬서는 산 와플을 건드리지 않고 그대로 둘 수 있다.