Golden Dust X95360


Statement
 

pdf   zip

html

Zynoulus the Wizard has invented a new magical way of multiplying magical dust. In a single day he is able to transform a single piece of golden dust into two pieces of golden dust and three pieces of silver dust. He is also able to transform a single piece of silver dust into three pieces of golden dust and five pieces of silver dust.

He has bought a single piece of golden dust. Using his process, he will have two pieces of golden dust and three pieces of silver dust next day. After the next day, he will have 2 · 2 + 3 · 3 = 13 pieces of golden dust and 3 · 5 + 2 · 3 = 21 pieces of silver dust.

Whenever he collects 1000000000 (109) pieces of dust of the same type, he immediately sells them for a big profit.

Given an integer D, calculate the number of pieces of dust Zynoulus the Wizard will possess after D days.

Input

Input may consist of several test cases.

A description of each test case has two lines. The first line contains a number d, 1 ≤ d ≤ 1000000. The second line contains D written as a d-digit number, 0 ≤ D < 10d.

After the last test case input contains a single digit 0.

Output

For each number D in the input, output the number of pieces of dust Zynoulus the Wizard will possess after D days.

Public test cases

  • Input

    1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
10
2
11
2
12
2
13
2
14
0

    Output

    1
5
34
233
1597
10946
75025
514229
3524578
24157817
165580141
1134903170
1778742049
1316291173
1435296162
    • Information
    Author
    Eryk Kopczynski
    Language
    English
    Official solutions
    Unknown.
    User solutions
    C++