풋볼 스코어의 경우의 수

풋볼은 종목마다 득점 방식이 다르다. 축구는 한 번에 1점씩만 올린다. 어떤 종목은 서로 다른 플레이가 같은 점수를 준다. 럭비 유니언의 드롭골과 페널티골은 둘 다 3점이지만 서로 다른 득점 방식이다. 한 번 득점한 뒤에 값이 다른 보너스 득점을 시도하는 종목도 많다. 미식축구는 터치다운이 6점이고, 그 뒤에 1점짜리 킥 컨버전이나 2점짜리 패스 또는 런 컨버전 중 하나를 시도한다. 터치다운 뒤 컨버전을 실패하면 6점, 성공하면 선택한 방식에 따라 7점이나 8점이 된다.

경기의 진행 기록은 득점 플레이를 일어난 순서대로 나열하고 각 플레이를 득점한 팀에 붙인 것이다. 플레이의 순서가 다르거나, 같은 플레이를 다른 팀이 했거나, 점수가 같더라도 득점 방식이 다르면 서로 다른 기록이다.

축구의 득점 방식은 1점짜리 골 하나뿐이다. 1-1 무승부의 기록은 두 가지다. 0-0에서 0-1을 거쳐 1-1이 되는 기록과, 0-0에서 1-0을 거쳐 1-1이 되는 기록이다.

경기의 최종 점수와 그 종목이 허용하는 득점 방식이 주어진다. 그 점수로 끝나는 기록의 수를 구하라. 럭비 리그에서 득점 방식이 1 2 3 6:1:2일 때 26 대 17로 끝나는 기록은 4507705365837803005가지다. 이처럼 수가 크므로 1000000009로 나눈 나머지를 출력한다.

첫째 줄에 두 팀의 최종 점수를 나타내는 정수 $a$와 $b$가 주어진다 ($0 \le a, b \le 200$). 두 점수 모두 주어진 득점 방식으로 만들 수 있다.

둘째 줄에 득점 옵션이 공백 하나로 구분되어 주어진다. 각 옵션은 기본 점수 $s$ ($0 < s \le 20$)이고, 그 뒤에 보너스 점수를 콜론으로 이어 붙일 수 있다. 미식축구의 6:1:2가 그런 예다. 보너스 점수 $b_j$는 $0 < b_j < s$를 만족하고, 한 옵션 안에서 오름차순으로 나열된다. $s:b_1:\dots:b_k$로 쓴 옵션은 각각 $s$점, $s+b_1$점, ..., $s+b_k$점짜리인 서로 다른 득점 방식 $k+1$개를 뜻한다. 기본 점수는 옵션 사이에서 내림차순이 아닌 순서로 나열되고, 개수는 1개 이상 20개 이하다. 기본 점수가 같은 옵션이 둘 이상 있을 수 있고, 이들은 서로 다른 득점 방식이다.

한 줄을 출력한다.

a vs b can be achieved N ways

$a$와 $b$는 입력으로 주어진 두 점수이고, $N$은 기록의 수를 1000000009로 나눈 나머지다. 출력하는 $N$이 정확히 1이면 ways 대신 way를 쓴다.