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.
an integer N (1 ≤ N ≤ 100).
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”.
Problem Author: Sergey Pupyrev
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)