#include <stdio.h>
FILE *f=fopen("12perm.in","r"),*g=fopen("12perm.out","w");
int n,a[6],i,v[453]={12,6,2,254030,892114,243672,
1002988,49308,260756,
685320,423784,969170,
217366,831616,557064,
274516,542846,467722,
439414,505566,429934,
346818,192704,242242,
411278,252946,586136,
333740,865500,599380,
244168,792104,646802,
978390,984512,183112,
694676,563006,759370,
304566,755358,228398,
374146,8576,156802,
77006,981842,322392,
729452,575772,585748,
269960,578792,684882,
199318,514816,112264,
959188,91646,485770,
95990,194142,166126,
81986,496192,267970,
824078,981650,1025304,
617260,752988,744148,
238408,832424,34834,
1025878,995392,344520,
19476,701630,171210,
337974,394782,243118,
518914,606976,51458,
31054,252370,73432,
521452,872860,550292,
673800,504424,793810,
312342,853376,879880,
1021268,820094,339978,
506230,832990,459374,
636354,340928,31554,
319374,891154,88216,
966316,411100,528468,
3272,643368,864658,
155862,613056,669768,
818836,971326,467786,
76470,984478,814894,
434306,746624,732546,
116174,800850,545368,
378988,940572,154388,
848264,200680,247378,
556438,798720,762760,
460756,631038,30346,
621558,324958,261102,
961346,775488,581570,
994318,1030034,920600,
332332,888412,1000916,
587336,224936,1039122,
465494,886080,110280,
995604,323518,600522,
568630,427294,895150,
120322,427520,102914,
332366,530130,689624,
302060,778908,446612,
793352,716136,94162,
931606,350848,809480,
326228,573054,605450,
441974,767198,619886,
8386,751296,869442,
751758,349714,376728,
812460,87772,64340,
942024,625704,558226,
906198,765888,763208,
549780,855358,569418,
765878,820382,483886,
625538,698240,259714,
679630,488786,506200,
290668,387868,378388,
509064,1002216,334162,
389270,558336,1020040,
617684,646142,1016714,
1016054,62558,487150,
923202,268352,895170,
640270,947346,553752,
309548,106332,864468,
18760,797096,470546,
429398,252480,531400,
529940,469694,374474,
668214,66590,629678,
901378,510208,154370,
109390,676818,1043672,
344812,816028,998292,
1043976,10344,967378,
1026582,372608,345864,
286548,850302,215562,
246646,308190,911470,
560066,375232,658754,
659854,725778,403096,
920748,944092,255572,
963272,739112,776082,
83670,394432,463432,
936084,215102,15690,
275638,263070,283950,
947842,912000,835458,
718798,45650,204888,
464492,1014812,209172,
300936,886248,945234,
746390,842240,884104,
381396,136958,299146,
230902,455518,844270,
1016130,23360,160194,
810510,733586,973336,
548908,503900,334804,
629832,451752,426258,
917590,143168,559304,
719636,91582,541642,
636726,361246,495278,
764930,855040,205826,
410702,692434,87000,
649708,984220,108180,
377096,484200,267730,
597270,918656,537608,
902228,603262,218890,
968822,504542,285550,
194242,261312,448066,
43662,970770,167320,
242604,882908,53588,
67016,983592,469650,
834006,547264,819016,
929172,99134,903754,
702902,361118,215086,
352642,339328,362626,
233678,520018,690008,
900460,724252,695316,
223880,901352,1032018,
579222,601856,354952,
800468,152062,1023370,
363254,455262,283886,
191554,40512,473794,
456462,388754,82200,
1836,1032540,460500,
323400,237480,906258,
881494,558144,193992,
516116,237758,53450,
474166,262686,491950,
759554,413440,257282,
187726,576978,965336,
168172,234908,922004,
889864,40552,92370,
692246,940416,336136,
76116,880510,615434,
511350,307678,839278,
1008066,409536,237378,
1000334,36114,717976,
875180,952796,506964,
350408,310568,687506};
int main(void)
{
	fscanf(f,"%d",&n);
	a[1]=1;
	a[2]=2;
	a[3]=6;
	a[4]=12;
	if (n<=4)
		fprintf(g,"%d",a[n]);
	else
	{
		a[2]=n/100000;
		i=a[2];
		a[4]=v[i*3];
		a[3]=v[i*3+1];
		a[2]=v[i*3+2];
		
		for (i=(n/100000)*3+3;i<=n;i++)
		{
			a[5]=a[4]+a[2]+2*(i-2);
			a[5]=a[5]&((1<<20)-1);
			a[2]=a[3];
			a[3]=a[4];
			a[4]=a[5];
		}
		fprintf(g,"%d",a[4]);
	}	
	fclose(g);
	return 0;
}