Football scorelines

Each code of football scores points in its own way. In soccer a team can only score one point at a time. In some codes two different plays are worth the same number of points: in rugby union a drop goal and a penalty goal are both worth 3 points, but they are different modes of scoring. Many codes let a team score points for a play and then attempt a bonus of a different value. In American football a touchdown is worth 6 points, and the team then attempts either a 1 point kick conversion or a 2 point pass or run conversion. A touchdown followed by a failed conversion is 6 points, and a touchdown followed by a successful conversion is 7 or 8 points depending on the option taken.

A history of a game lists the scoring plays in the order they happened and attributes each play to the team that made it. Two histories differ if the order of the plays differs, if a play belongs to the other team, or if a play uses a different mode of scoring even when the two modes are worth the same number of points.

The only mode of scoring in soccer is a 1 point goal. A 1-1 draw has two histories: 0-0 to 0-1 to 1-1, and 0-0 to 1-0 to 1-1.

You are given the final score of a game and the modes of scoring its code allows. Count the histories that end at that score. A rugby league game ending 26 to 17 with the modes 1 2 3 6:1:2 has 4507705365837803005 histories. The count gets large, so report it modulo 1000000009.

The first line contains two integers $a$ and $b$, the final scores of the two teams ($0 \le a, b \le 200$). Both scores are attainable with the given modes of scoring.

The second line contains the scoring options, separated by single spaces. Each option is a base score value $s$ ($0 < s \le 20$), optionally followed by bonus score values joined by colons, as in 6:1:2 for American football. Every bonus score value $b_j$ satisfies $0 < b_j < s$, and the bonus score values inside one option are listed in ascending order. An option written $s:b_1:\dots:b_k$ stands for $k+1$ different modes of scoring, worth $s$, $s+b_1$, ..., $s+b_k$ points. The base score values are listed in non-descending order across the options, and there are at least 1 and at most 20 of them. Two options may share the same base score value, and they are still different modes of scoring.

Print one line.

a vs b can be achieved N ways

Here $a$ and $b$ are the two scores given in the input and $N$ is the number of histories modulo 1000000009. Write way instead of ways when the printed $N$ is exactly 1.