#include <stdio.h>
#include <stdlib.h>
#define lint long long int
lint max=1000000007;
lint arr[3000006]={0};
void set()
{
lint i=0;
for(i=1;i<=2000001;i++)
}
lint FormArray(lint arr[],lint n)
{
lint i,j,carry,sum;
j=1;
carry=0;
for(i=2000001;j<=n;j++,i--)
{
sum=carry+j;
carry=sum/10;
arr[i]=sum%10;
}
j=j-2;
for(;j>0;i--,j--)
{
sum=j+carry;
carry=sum/10;
arr[i]=sum%10;
//if(i<0)
// printf("Ooopsss\n");
}
return i+1;
}
lint MulArray(lint arr[],lint p,lint d)
{
lint carry=0,sum,i;
for(i=2000001;i>=p||carry!=0;i--)
{
sum=arr[i]*d+carry;
arr[i]=sum%10;
carry=sum/10;
}
return i+1;
}
lint Mulpow
(lint arr
[],lint
pow[],lint p
){
lint sum=0,i,j;
for(i=p,j=0;i<=2000001;i++,j++)
{
sum
=sum
+(arr
[i
]*pow[j
])%max
; sum=sum%max;
}
return sum;
}
int main()
{
int test;
lint n,p,d,sum,i;
set();
while(test--)
{
p=FormArray(arr,n);
p=MulArray(arr,p,d*d);
for(i=p;i<=2000001;i++)
arr[i]=0;
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2RlZmluZSBsaW50IGxvbmcgbG9uZyBpbnQKbGludCAgbWF4PTEwMDAwMDAwMDc7CmxpbnQgYXJyWzMwMDAwMDZdPXswfTsKbGludCBwb3dbMzAwMDAwNl09ezB9Owp2b2lkIHNldCgpCnsKICAgIHBvd1swXT0xOwogICAgbGludCBpPTA7CiAgICBmb3IoaT0xO2k8PTIwMDAwMDE7aSsrKQogICAgICAgIHBvd1tpXT0ocG93W2ktMV0qMjMpJW1heDsKCn0KbGludCAgRm9ybUFycmF5KGxpbnQgYXJyW10sbGludCBuKQp7CiAgICBsaW50IGksaixjYXJyeSxzdW07CiAgICBqPTE7CiAgICBjYXJyeT0wOwogICAgZm9yKGk9MjAwMDAwMTtqPD1uO2orKyxpLS0pCiAgICB7CiAgICAgICAgc3VtPWNhcnJ5K2o7CiAgICAgICAgY2Fycnk9c3VtLzEwOwogICAgICAgIGFycltpXT1zdW0lMTA7CiAgICB9CiAgICBqPWotMjsKICAgIGZvcig7aj4wO2ktLSxqLS0pCiAgICB7CiAgICAgICAgc3VtPWorY2Fycnk7CiAgICAgICAgY2Fycnk9c3VtLzEwOwogICAgICAgIGFycltpXT1zdW0lMTA7CiAgICAgICAgLy9pZihpPDApCiAgICAgICAgICAgLy8gcHJpbnRmKCJPb29wc3NzXG4iKTsKICAgIH0KICAgIHJldHVybiBpKzE7Cn0KbGludCBNdWxBcnJheShsaW50IGFycltdLGxpbnQgcCxsaW50IGQpCnsKICAgIGxpbnQgY2Fycnk9MCxzdW0saTsKICAgIGZvcihpPTIwMDAwMDE7aT49cHx8Y2FycnkhPTA7aS0tKQogICAgewogICAgICAgIHN1bT1hcnJbaV0qZCtjYXJyeTsKICAgICAgICBhcnJbaV09c3VtJTEwOwogICAgICAgIGNhcnJ5PXN1bS8xMDsKICAgIH0KICAgIHJldHVybiBpKzE7Cn0KbGludCBNdWxwb3cobGludCBhcnJbXSxsaW50IHBvd1tdLGxpbnQgcCkKewogICAgbGludCBzdW09MCxpLGo7CiAgICBmb3IoaT1wLGo9MDtpPD0yMDAwMDAxO2krKyxqKyspCiAgICB7CiAgICAgICAgc3VtPXN1bSsoYXJyW2ldKnBvd1tqXSklbWF4OwogICAgICAgIHN1bT1zdW0lbWF4OwogICAgfQogICAgcmV0dXJuIHN1bTsKfQppbnQgbWFpbigpCnsKICAgIGludCB0ZXN0OwogICAgbGludCBuLHAsZCxzdW0saTsKICAgIHNjYW5mKCIlZCIsJnRlc3QpOwogICAgc2V0KCk7CiAgICB3aGlsZSh0ZXN0LS0pCiAgICB7CiAgICAgICAgc2NhbmYoIiVsbGQlbGxkIiwmbiwmZCk7CiAgICAgICAgcD1Gb3JtQXJyYXkoYXJyLG4pOwogICAgICAgIHA9TXVsQXJyYXkoYXJyLHAsZCpkKTsKICAgICAgICBzdW09TXVscG93KGFycixwb3cscCk7CiAgICAgICAgcHJpbnRmKCIlbGxkXG4iLHN1bSk7CiAgICAgICAgZm9yKGk9cDtpPD0yMDAwMDAxO2krKykKICAgICAgICAgICAgYXJyW2ldPTA7CiAgICB9CiAgICByZXR1cm4gMDsKfQo=