Problem D
Dice Tables
Rather than risking their lives in a showdown at high noon, Lester and Clemence decide to resolve their dispute by throwing dice. They have an elaborate system and don’t trust each other too much, so they’ve enlisted Old Man Joe to keep track of the dice rolls. Specifically, they would like to set up a table to record how often each result from rolling the dice appears. They don’t care about which die showed which face, but only which numbers appeared. For example, when rolling a four-sided die and a six-sided die, the table should only track the following eighteen distinct combinations:
|
1,1 |
1,2 |
1,3 |
1,4 |
1,5 |
1,6 |
|
2,2 |
2,3 |
2,4 |
2,5 |
2,6 |
3,3 |
|
3,4 |
3,5 |
3,6 |
4,4 |
4,5 |
4,6 |
Can you help to count how many entries the table should have, given the available dice?
Input
Input will consist of five space-separated integers on a single line: $0 \leq T, C, O, D, I \leq 10^9$. $T$ is the number of four-sided dice, $C$ is the number of six-sided dice, $O$ is the number of eight-sided dice, $D$ is the number of twelve-sided dice, and $I$ is the number of twenty-sided dice. There will be at least one die.
Output
Print the number of different distinct combinations. Since this number can be very large, output the number modulo $10^9 + 9$.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 0 0 0 |
18 |
| Sample Input 2 | Sample Output 2 |
|---|---|
0 0 0 1 0 |
12 |
| Sample Input 3 | Sample Output 3 |
|---|---|
1 1 1 1 1 |
7760 |
| Sample Input 4 | Sample Output 4 |
|---|---|
19 13 31 0 0 |
11575 |
