DWITE Contest

Test Case for Question #3 in DWITE 2010-2011 High School Round 3

Contest: DWITE 2010-2011 High School Round 3
Question: #3
Input File: DATA3.txt
Output File: OUT3.txt


Input

18
5
0
28
30




Output

110771
0
1
80198051
299303201