ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1407. One-two, One-two

Time limit: 1.0 second
Memory limit: 64 MB
Having been awaken today’s morning Vito Maretti has understood that it’s boring for him to rob banks. Now he is planning to take from banks only sums of money with decimal notations containing only digits 1 and 2. Since Vito is very honest gangster he hesitates if he can divide the loot between his gang in equal parts. For quite some time now (after one of such Vito’s insight) Vito’s gang has exactly 2N members. Vito will reward you generously if given an integer N you determine the sum which decimal notation consists only of ones and twos that Vito will be able to divide in equal parts between the members of his gang.

Input

an integer N (1 ≤ N ≤ 100).

Output

If exists a number which decimal notation consists only of the digits 1 and 2 that is divided by 2N and has no more than 10000 digits then output it without the leading zeros. If there are several suitable numbers, then output any one of them. If there is no such number the output should contain the line “No solution”.

Sample

inputoutput
2
12
Problem Author: Sergey Pupyrev
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)