Digits and Last 500 Digits of a Mersenne‐Type Number

A number of the form \(2^P-1\) is called a Mersenne number when it is prime; in that case \(P\) must also be prime. However, if \(P\) is prime, \(2^P-1\) is not necessarily prime. Up to the end of 1998, 37 Mersenne primes had been found. The largest one discovered had \(P=3021377\) and contained 909526 digits. Mersenne numbers have many important applications and are closely related to perfect numbers.

Given an integer \(P\) with \(1000 < P < 3100000\), compute the number of digits of \(2^P-1\) and its last 500 digits in decimal representation. When \(2^P-1\) has fewer than 500 digits, output it with leading zeros so that exactly 500 digits are printed.

The number of digits of \(2^P-1\) can be computed by the formula:

\[ D = \lfloor P \cdot \log_{10}2 \rfloor + 1. \]

The last 500 digits can be computed using modular exponentiation by calculating \(2^P \bmod 10^{500}\) and then subtracting 1 (taking care of the case when the result is 0 modulo \(10^{500}\)).

inputFormat

The input consists of a single line containing an integer \(P\) (with \(1000 < P < 3100000\)).

outputFormat

Output two lines. The first line contains the number of digits of \(2^P-1\). The second line contains exactly 500 digits — the last 500 digits of \(2^P-1\) in decimal representation (with leading zeros if necessary).

sample

1001

302
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000021430172143725346418968500981200036211228096234110672148875007767407021022498722449863967576313917162551893458351062936503742905713846280871969155149397149607869135549648461970842149210124742283755908364306092949967163882534797535118331087892154125829142392955373084335320859663305248773674411336138751

</p>