Description

A prime of the form $2^{P}-1$ is called a "Mersenne number"; in that case $P$ must also be a prime. The converse is not necessarily true, i.e., even if $P$ is prime, $2^{P}-1$ may not be prime. By the end of 1998, 37 Mersenne numbers had been found. The largest one had $P=3021377$, and it has 909526 digits. Mersenne numbers have many important applications and are closely related to perfect numbers.

Task: Given $P$ ($1000<P<3100000$), compute the number of digits of $2^{P}-1$ and the last $500$ digits (in decimal big integer representation).

Input Format

The file contains a single integer $P$ ($1000<P<3100000$).

Output Format

• Line 1: The number of digits of the decimal big integer $2^{P}-1$.
• Lines 2–11: The last $500$ digits of the decimal big integer $2^{P}-1$ (50 digits per line, 10 lines in total; if there are fewer than 500 digits, pad with leading zeros on the most significant side).

You do not need to verify whether $2^{P}-1$ or $P$ is prime.

1279

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

Hint

[Problem Source]

NOIP 2003 Junior Problem 4

Translated by ChatGPT 5