I교 신자 2

현종이는 수 $I$를 신성시하는 I교에 입교했다. I교에서는 $I$는 물론이고 $I$와 사칙연산으로 만들 수 있는 다른 수도 모두 좋은 수로 여긴다. 좋은 수를 많이 만들려고 현종이는 다음 놀이를 한다.

준비물은 두 가지다.

• $I$가 그려진 카드 $A$장, $+$가 그려진 카드 $B$장, $\times$가 그려진 카드 $C$장. 같은 기호가 그려진 카드는 생김새가 같아서 서로 구별하지 못한다.
• $I$가 무한히 쌓여 있는 스택.

현종이는 카드 $A+B+C$장을 한 줄로 늘어놓고 왼쪽부터 차례로 뽑는다. 뽑은 카드에 따라 다음 작업을 한다.

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

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

카드를 늘어놓는 방법은 기호의 나열로만 구분하므로 모두 $\frac{(A+B+C)!}{A!B!C!}$가지다. 현종이는 가능한 모든 배열마다 작업을 끝낸 다음, 스택 맨 위에서 $i$번째에 있는 수를 모두 더한 값을 $i=1$부터 $i=K$까지 구하려고 한다. 현종이를 도와 이 $K$개의 합을 구하자.

첫 줄에 다섯 정수 $I$, $A$, $B$, $C$, $K$가 공백으로 구분되어 주어진다. ($1 \le I \le 10^9$, $0 \le A, B, C \le 40$, $1 \le K \le 40$)

$A$는 $I$가 그려진 카드의 개수, $B$는 $+$가 그려진 카드의 개수, $C$는 $\times$가 그려진 카드의 개수이고, $K$는 구하려는 합의 개수이다.

$K$개의 줄을 출력한다. $i$번째 줄에는 가능한 모든 배열에 대해 작업을 끝낸 스택에서 맨 위에서 $i$번째에 있는 수를 모두 더한 값을 $1\,000\,000\,007$로 나눈 나머지를 출력한다.