URI Online Judge | 1422


By Wanderley Guimarães, IME-USP Brazil
Timelimit: 1

Pietro Demazio is an Italian terrorist that escaped to Brazil and is now disguised as a game programmer. For his new plan to destroy the world, Pietro has developed a new kind of bacterium that is able to decimate the entire world population.

Demazio spent 4 days creating these microorganisms' colonies. In the end of the 4th day, however, he found out that their genetic code had an error. This error makes the bacteria die after living for 4 days. Since the first colony was created 3 days before, he quickly modified the genetic code (through radiation), in such a way that his bacteria reproduce every day. This is an asexual reproduction, and is done by bi-partitioning (i.e., one bacterium generates exactly one other bacterium in a day).

So, suppose that Pietro created 3 bacteria in the first day, 4 bacteria in the second day, 2 bacteria in the 3rd day and 5 bacteria in the 4th day. He will have 14 bacteria by the end of the 4th day, when he applies the mutation. Right after the mutation, they reproduce, and then he'll have 28 bacteria. Since the first colony (with 3 bacteria) dies in the end of the 4th day, the number of bacteria in the beginning of the 5th day is 25. By the end of the 5th day, these 25 bacteria reproduce, resulting in 50 bacteria. Since the second colony (with 4 bacteria) dies by the end of this day, he'll have 46 bacteria in the beginning of the 6th day.

Demazio carefully watches the growing of his bacteria population, and is already planning when to use them. To do so, he needs to know how many bacteria there will be after a given number of days. He is asking you to write a program that determines the number of bacteria that there will be after N days, given the number of bacteria of the colonies in the first 4 days.


The input consists of many test cases. Each test case consists of two lines. The first line contains the integer N (5 ≤ N ≤ 1,000,000,000), the number of days for which Pietro wants to know the number of bacteria he will have. The second line contains four integers a1, a2, a3, a4 (1 ≤ a1, a2, a3, a4 ≤ 1,000). The integer ak indicates the number of bacteria that were created in the k-th day.

The last test case if followed by a line with N=0.


For each test case, print a line containing the number of bacteria Pietri will have after N days, modulo 13371337.

Sample Input Sample Output

1 2 3 4
9 2 3 4