I교 신자 3

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

준비물은 두 가지다.

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

현종이는 카드를 섞은 다음 섞인 순서대로 한 장씩 뽑고, 뽑은 카드에 따라 다음 작업을 한다.

• 'I' 카드: 스택에 $I$를 넣는다.
• '+' 카드: 스택의 가장 위에 있는 두 수를 꺼낸 뒤, 두 수의 합을 스택에 넣는다.
• '×' 카드: 스택의 가장 위에 있는 두 수를 꺼낸 뒤, 두 수의 곱을 스택에 넣는다.

스택에는 언제나 수가 무한히 많으므로 어떤 순서로 뽑아도 작업은 끝까지 진행된다.

카드를 모두 뽑고 나면 스택의 가장 위에 있는 수뿐 아니라 그 밑에 있는 수도 모두 좋은 수다. 그래서 현종이는 가능한 모든 카드 배열에 대해, 작업을 끝낸 스택에서 가장 위에 있는 수의 합, 위에서 두 번째에 있는 수의 합, ..., 위에서 $K$번째에 있는 수의 합을 모두 구하려고 한다.

같은 기호가 그려진 카드는 서로 구분하지 않는다. 즉 카드 배열은 길이 $A+B+C$인 서로 다른 기호 나열이고, 배열 하나를 정확히 한 번씩 센다.

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

• $1 \le I \le 10^9$
• $0 \le A, B, C \le 40$
• $1 \le K \le 40$

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