麦森数

Description

形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。
到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。 麦森数有许多重要应用，它与完全数密切相关。
任务：输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）。

Input

一个整数P（1000<P<3100000）。 Output 第一行：十进制高精度数2P-1的位数；
第2-11行：十进制高精度数2P-1的最后500位数字（每行输出50位，共输出10行，不足500位时高位补0）；
不必验证2P-1与P是否为素数。

Sample Input

1279

Sample Output

386
00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=1001;
int r[N],f[N],t[N],p;
void r1(){
	fill(t,t+N,0);
	for(int i=1;i<=500;i++)
		for(int j=1;j<=500;j++)
			t[i+j-1]+=r[i]*f[j];
	//进位		
	for(int i=1;i<=500;i++){
		t[i+1]+=t[i]/10;
		t[i]%=10;
	}	
	memcpy(r,t,sizeof(t));	
}
void r2(){
	fill(t,t+N,0);
	for(int i=1;i<=500;i++)
		for(int j=1;j<=500;j++)
			t[i+j-1]+=f[i]*f[j];
	//进位		
	for(int i=1;i<=500;i++){
		t[i+1]+=t[i]/10;
		t[i]%=10;
	}		
	memcpy(f,t,sizeof(t));
}
int main(){
	while(scanf("%d",&p)!=EOF){
		fill(r,r+N,0);
		fill(f,f+N,0);
		r[1]=1; f[1]=2;
		//求位数 
		printf("%d\n",(int)(log10(2)*p+1));
		//求快速幂 
		while(p){
			if(p%2==1) r1();
			p/=2;
			r2();
		}
		r[1]--;	
		for(int i=500;i>0;i--)
			if(i%50==1)
				printf("%d\n",r[i]);
			else
				printf("%d",r[i]);	
	}
	return 0;
}