Follower of I 1

Hyeonjong has joined a group whose members treat the number $I$ as sacred. They call $I$ a good number, and every number that can be built from $I$ with addition and multiplication is a good number too. To make many good numbers, Hyeonjong plays the following game.

He needs two things.

• $A$ cards with $I$ drawn on both sides, $B$ cards with $+$ on them, and $C$ cards with $\times$ on them.
• A stack that already holds infinitely many copies of $I$.

Hyeonjong lays every card out in a single row, then reads the cards one at a time from the left and does the following.

• $I$ card: push $I$ onto the stack.
• $+$ card: pop the top two numbers off the stack and push their sum.
• $\times$ card: pop the top two numbers off the stack and push their product.

The bottom of the stack holds infinitely many copies of $I$, so the stack never runs out of numbers to pop.

Cards that show the same symbol are not told apart, so the number of different rows is $\frac{(A+B+C)!}{A!\,B!\,C!}$.

For every different row, Hyeonjong finishes the whole procedure and reads the number that sits $i$-th from the top of the stack. He wants the sum of those numbers over all rows, for $i = 1, 2, \dots, K$. Help him.

The first line contains five integers $I$, $A$, $B$, $C$, and $K$, separated by spaces. $A$ is the number of $I$ cards, $B$ is the number of $+$ cards, $C$ is the number of $\times$ cards, and $K$ is how many sums to compute.

$1 \le I \le 10^9$, $0 \le A$, $0 \le B$, $0 \le C$, $A + B + C \le 15$, and $1 \le K \le 40$.

Print $K$ lines. On line $i$, print the sum, over every different row of cards, of the number that sits $i$-th from the top of the stack once the procedure ends. Print each sum modulo $10^9 + 7$.