시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB117787.500%

문제

방학 동안 어떤 일을 겪었는지 몰라도 현종이는 수 \(I\)를 신성시하는 \(I\)교에 입교하였다.

\(I\)교에서는 \(I\)는 물론, \(I\)와 사칙연산을 이용해 만들 수 있는 다른 많은 수를 좋은 수라고 생각한다. \(I\)교에서 좋은 수들을 만드는 활동을 왕성히 펼치던 현종이는 아래와 같은 놀이를 통해 좋은 수들을 많이 만들어 좀 더 많은 사람에게 \(I\)교를 포교하고자 하였다.

이 놀이를 하기 위해서는 몇 개의 준비물이 필요하다.

  • 앞/뒷면에 '\(I\)'가 그려진 카드 \(A\)개, '\(+\)'가 그려진 카드 \(B\)개, '\(\times\)'가 그려진 카드 \(C\)개.
  • 무한히 많은 개수의 \(I\)가 들어있는 스택. 이 스택은 수 \(I\)에 대한 무한한 믿음, 감사, 사랑을 의미하며, 또한 \(I\)에 내재한 절대적인 진리와 불멸성을 상징한다.

준비물이 마련되었으면, 놀이를 시작하자! 우선 현종이는 현재 가지고 있는 카드를 섞는다. 이는 \(I\)가 세상에 내려와 다른 만물과 어우러져 조화를 이루고 사랑으로 감싸줌을 의미한다. 그다음 현종이는 카드를 섞인 순서대로 뽑는데, 카드를 뽑을 때마다 뽑힌 카드가 어떤 카드인지에 따라 다음과 같은 작업을 수행할 것이다.

  • '\(I\)'가 그려진 카드가 뽑히면 : 스택에 \(I\)를 넣는다.
  • '\(+\)'가 그려진 카드가 뽑히면 : 스택의 가장 위에 있는 두 수를 뽑은 후, 이 두 수를 더한 수를 스택에 넣는다.
  • '\(\times\)'가 그려진 카드가 뽑히면 : 스택의 가장 위에 있는 두 수를 뽑은 후, 이 두 수를 곱한 수를 스택에 넣는다.

모든 과정이 끝나면 스택에는 좋은 수들이 많이 쌓여 있을 것이다. 현종이는 스택에 있는 수많은 수 중에서 스택의 가장 위에 있는 수는 가장 좋은 수일 것으로 생각했다. 그렇게 생각했었다. 하지만 곧 현종이는 깨달았다. 다른 수들도 모두 좋은 수들일진대 감히 우열을 따질 수 있겠는가! 스택의 가장 위에 있는 수만이 아니라 그 밑에 있는 수들도 모두 좋은 수들일 것이며, 수들은 카드의 배열에 따라 모습을 바꾸어 현종이에게 자애로운 웃음을 지어줄 것이다!

그래서 현종이는 가능한 모든 카드 배열에 대해, 작업을 끝냈을 때 스택의 가장 위에 있는 수들의 합을 구하기로 하였다. 또한, 가장 위에 있는 수뿐만 아니라 두 번째로 위에 있는 수들의 합, 세 번째로 위에 있는 수들의 합, ...,  \(K\)번째로 위에 있는 수들의 합을 모두 구하기로 하였다. 그러나 현종이는 가능한 카드 배열의 개수가 너무 많다는 것을 알고 당신에게 \(I\)교의 아름다움을 알리는 겸 이 일을 맡겼다. 현종이를 도와주자!

입력

첫 줄에 \(I (1 \leq I \leq 10^9)\), \(A\), \(B\), \(C\) \((0 \leq A,B,C \leq 40)\), \(K (1 \leq K \leq 40)\)를 나타내는 다섯 정수가 공백으로 구분되어 주어진다. \(I\)는 \(I \)이며, \(A\)는 '\(I\)'가 그려진 카드의 개수, \(B\)는 '\(+\)'가 그려진 카드의 개수, \(C\)는 '\(\times\)'가 그려진 카드의 개수, \(K\)는 구하고자 하는 합의 개수이다.

이 문제는 세 개의 부분 문제로 이루어져 있다.

1번 문제의 입력은 \(0 \leq A+B+C \leq 15\)을 만족하며 해결하면 10점을 얻을 수 있다.

2번 문제의 입력은 \(K=1\)을 만족하며 해결하면 20점을 얻을 수 있다.

3번 문제의 입력은 다른 제한이 없으며 해결하면 70점을 얻을 수 있다.

출력

\(i\)번째 줄에 모든 카드 배열에 대해 작업을 끝낸 후의 모든 스택에 대해 맨 위에서 \(i\)번째에 있는 수들의 합을 출력한다. 숫자가 너무 커질 수 있으므로 \(1,000,000,007\)로 나눈 나머지를 출력한다.

예제 입력 1

1 1 1 1 1

예제 출력 1

10

출처

Contest > Coder's High > Coder's High 2015 Side Contest I2번