I교 신자 1

현종이는 수 $I$를 신성하게 여기는 모임에 들어갔다. 이 모임에서는 $I$뿐 아니라 $I$와 덧셈, 곱셈으로 만들 수 있는 수도 모두 좋은 수라고 부른다. 좋은 수를 많이 만들려고 현종이는 다음 놀이를 한다.

놀이에 필요한 준비물은 두 가지다.

• 양면에 $I$가 그려진 카드 $A$장, $+$가 그려진 카드 $B$장, $\times$가 그려진 카드 $C$장.
• $I$가 무한히 들어 있는 스택.

현종이는 카드를 모두 한 줄로 늘어놓은 다음, 왼쪽부터 한 장씩 보면서 카드에 그려진 그림에 따라 다음 작업을 한다.

• $I$ 카드: 스택에 $I$를 넣는다.
• $+$ 카드: 스택의 맨 위에 있는 두 수를 꺼내고, 두 수의 합을 스택에 넣는다.
• $\times$ 카드: 스택의 맨 위에 있는 두 수를 꺼내고, 두 수의 곱을 스택에 넣는다.

스택 바닥에는 $I$가 무한히 쌓여 있으므로 꺼낼 수가 모자라는 일은 없다.

같은 그림이 그려진 카드는 서로 구별하지 않는다. 따라서 카드를 늘어놓는 서로 다른 방법은 $\frac{(A+B+C)!}{A!\,B!\,C!}$가지다.

현종이는 서로 다른 모든 배열에 대해 작업을 끝낸 뒤, 스택의 맨 위에서 $i$번째에 있는 수를 모두 더한 값을 $i = 1, 2, \dots, K$에 대해 구하려고 한다. 현종이를 도와주자.

첫 줄에 다섯 정수 $I$, $A$, $B$, $C$, $K$가 공백으로 구분되어 주어진다. $A$는 $I$ 카드의 장수, $B$는 $+$ 카드의 장수, $C$는 $\times$ 카드의 장수, $K$는 구하려는 합의 개수다.

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

$K$개의 줄을 출력한다. $i$번째 줄에는 서로 다른 모든 카드 배열에 대해 작업을 끝낸 뒤 스택의 맨 위에서 $i$번째에 있는 수들의 합을 $10^9 + 7$로 나눈 나머지를 출력한다.