MEMO = {
0 => 1,
1000000 => 641102369,
2000000 => 578095319,
3000000 => 5832229,
4000000 => 259081142,
5000000 => 974067448,
6000000 => 316220877,
7000000 => 690120224,
8000000 => 251368199,
9000000 => 980250487,
10000000 => 682498929,
11000000 => 134623568,
12000000 => 95936601,
13000000 => 933097914,
14000000 => 167332441,
15000000 => 598816162,
16000000 => 336060741,
17000000 => 248744620,
18000000 => 626497524,
19000000 => 288843364,
20000000 => 491101308,
21000000 => 245341950,
22000000 => 565768255,
23000000 => 246899319,
24000000 => 968999,
25000000 => 586350670,
26000000 => 638587686,
27000000 => 881746146,
28000000 => 19426633,
29000000 => 850500036,
30000000 => 76479948,
31000000 => 268124147,
32000000 => 842267748,
33000000 => 886294336,
34000000 => 485348706,
35000000 => 463847391,
36000000 => 544075857,
37000000 => 898187927,
38000000 => 798967520,
39000000 => 82926604,
40000000 => 723816384,
41000000 => 156530778,
42000000 => 721996174,
43000000 => 299085602,
44000000 => 323604647,
45000000 => 172827403,
46000000 => 398699886,
47000000 => 530389102,
48000000 => 294587621,
49000000 => 813805606,
50000000 => 67347853,
51000000 => 497478507,
52000000 => 196447201,
53000000 => 722054885,
54000000 => 228338256,
55000000 => 407719831,
56000000 => 762479457,
57000000 => 746536789,
58000000 => 811667359,
59000000 => 778773518,
60000000 => 27368307,
61000000 => 438371670,
62000000 => 59469516,
63000000 => 5974669,
64000000 => 766196482,
65000000 => 606322308,
66000000 => 86609485,
67000000 => 889750731,
68000000 => 340941507,
69000000 => 371263376,
70000000 => 625544428,
71000000 => 788878910,
72000000 => 808412394,
73000000 => 996952918,
74000000 => 585237443,
75000000 => 1669644,
76000000 => 361786913,
77000000 => 480748381,
78000000 => 595143852,
79000000 => 837229828,
80000000 => 199888908,
81000000 => 526807168,
82000000 => 579691190,
83000000 => 145404005,
84000000 => 459188207,
85000000 => 534491822,
86000000 => 439729802,
87000000 => 840398449,
88000000 => 899297830,
89000000 => 235861787,
90000000 => 888050723,
91000000 => 656116726,
92000000 => 736550105,
93000000 => 440902696,
94000000 => 85990869,
95000000 => 884343068,
96000000 => 56305184,
97000000 => 973478770,
98000000 => 168891766,
99000000 => 804805577,
100000000 => 927880474,
101000000 => 876297919,
102000000 => 934814019,
103000000 => 676405347,
104000000 => 567277637,
105000000 => 112249297,
106000000 => 44930135,
107000000 => 39417871,
108000000 => 47401357,
109000000 => 108819476,
110000000 => 281863274,
111000000 => 60168088,
112000000 => 692636218,
113000000 => 432775082,
114000000 => 14235602,
115000000 => 770511792,
116000000 => 400295761,
117000000 => 697066277,
118000000 => 421835306,
119000000 => 220108638,
120000000 => 661224977,
121000000 => 261799937,
122000000 => 168203998,
123000000 => 802214249,
124000000 => 544064410,
125000000 => 935080803,
126000000 => 583967898,
127000000 => 211768084,
128000000 => 751231582,
129000000 => 972424306,
130000000 => 623534362,
131000000 => 335160196,
132000000 => 243276029,
133000000 => 554749550,
134000000 => 60050552,
135000000 => 797848181,
136000000 => 395891998,
137000000 => 172428290,
138000000 => 159554990,
139000000 => 887420150,
140000000 => 970055531,
141000000 => 250388809,
142000000 => 487998999,
143000000 => 856259313,
144000000 => 82104855,
145000000 => 232253360,
146000000 => 513365505,
147000000 => 244109365,
148000000 => 1559745,
149000000 => 695345956,
150000000 => 261384175,
151000000 => 849009131,
152000000 => 323214113,
153000000 => 747664143,
154000000 => 444090941,
155000000 => 659224434,
156000000 => 80729842,
157000000 => 570033864,
158000000 => 664989237,
159000000 => 827348878,
160000000 => 195888993,
161000000 => 576798521,
162000000 => 457882808,
163000000 => 731551699,
164000000 => 212938473,
165000000 => 509096183,
166000000 => 827544702,
167000000 => 678320208,
168000000 => 677711203,
169000000 => 289752035,
170000000 => 66404266,
171000000 => 555972231,
172000000 => 195290384,
173000000 => 97136305,
174000000 => 349551356,
175000000 => 785113347,
176000000 => 83489485,
177000000 => 66247239,
178000000 => 52167191,
179000000 => 307390891,
180000000 => 547665832,
181000000 => 143066173,
182000000 => 350016754,
183000000 => 917404120,
184000000 => 296269301,
185000000 => 996122673,
186000000 => 23015220,
187000000 => 602139210,
188000000 => 748566338,
189000000 => 187348575,
190000000 => 109838563,
191000000 => 574053420,
192000000 => 105574531,
193000000 => 304173654,
194000000 => 542432219,
195000000 => 34538816,
196000000 => 325636655,
197000000 => 437843114,
198000000 => 630621321,
199000000 => 26853683,
200000000 => 933245637,
201000000 => 616368450,
202000000 => 238971581,
203000000 => 511371690,
204000000 => 557301633,
205000000 => 911398531,
206000000 => 848952161,
207000000 => 958992544,
208000000 => 925152039,
209000000 => 914456118,
210000000 => 724691727,
211000000 => 636817583,
212000000 => 238087006,
213000000 => 946237212,
214000000 => 910291942,
215000000 => 114985663,
216000000 => 492237273,
217000000 => 450387329,
218000000 => 834860913,
219000000 => 763017204,
220000000 => 368925948,
221000000 => 475812562,
222000000 => 740594930,
223000000 => 45060610,
224000000 => 806047532,
225000000 => 464456846,
226000000 => 172115341,
227000000 => 75307702,
228000000 => 116261993,
229000000 => 562519302,
230000000 => 268838846,
231000000 => 173784895,
232000000 => 243624360,
233000000 => 61570384,
234000000 => 481661251,
235000000 => 938269070,
236000000 => 95182730,
237000000 => 91068149,
238000000 => 115435332,
239000000 => 495022305,
240000000 => 136026497,
241000000 => 506496856,
242000000 => 710729672,
243000000 => 113570024,
244000000 => 366384665,
245000000 => 564758715,
246000000 => 270239666,
247000000 => 277118392,
248000000 => 79874094,
249000000 => 702807165,
250000000 => 112390913,
251000000 => 730341625,
252000000 => 103056890,
253000000 => 677948390,
254000000 => 339464594,
255000000 => 167240465,
256000000 => 108312174,
257000000 => 839079953,
258000000 => 479334442,
259000000 => 271788964,
260000000 => 135498044,
261000000 => 277717575,
262000000 => 591048681,
263000000 => 811637561,
264000000 => 353339603,
265000000 => 889410460,
266000000 => 839849206,
267000000 => 192345193,
268000000 => 736265527,
269000000 => 316439118,
270000000 => 217544623,
271000000 => 788132977,
272000000 => 618898635,
273000000 => 183011467,
274000000 => 380858207,
275000000 => 996097969,
276000000 => 898554793,
277000000 => 335353644,
278000000 => 54062950,
279000000 => 611251733,
280000000 => 419363534,
281000000 => 965429853,
282000000 => 160398980,
283000000 => 151319402,
284000000 => 990918946,
285000000 => 607730875,
286000000 => 450718279,
287000000 => 173539388,
288000000 => 648991369,
289000000 => 970937898,
290000000 => 500780548,
291000000 => 780122909,
292000000 => 39052406,
293000000 => 276894233,
294000000 => 460373282,
295000000 => 651081062,
296000000 => 461415770,
297000000 => 358700839,
298000000 => 643638805,
299000000 => 560006119,
300000000 => 668123525,
301000000 => 686692315,
302000000 => 673464765,
303000000 => 957633609,
304000000 => 199866123,
305000000 => 563432246,
306000000 => 841799766,
307000000 => 385330357,
308000000 => 504962686,
309000000 => 954061253,
310000000 => 128487469,
311000000 => 685707545,
312000000 => 299172297,
313000000 => 717975101,
314000000 => 577786541,
315000000 => 318951960,
316000000 => 773206631,
317000000 => 306832604,
318000000 => 204355779,
319000000 => 573592106,
320000000 => 30977140,
321000000 => 450398100,
322000000 => 363172638,
323000000 => 258379324,
324000000 => 472935553,
325000000 => 93940075,
326000000 => 587220627,
327000000 => 776264326,
328000000 => 793270300,
329000000 => 291733496,
330000000 => 522049725,
331000000 => 579995261,
332000000 => 335416359,
333000000 => 142946099,
334000000 => 472012302,
335000000 => 559947225,
336000000 => 332139472,
337000000 => 499377092,
338000000 => 464599136,
339000000 => 164752359,
340000000 => 309058615,
341000000 => 86117128,
342000000 => 580204973,
343000000 => 563781682,
344000000 => 954840109,
345000000 => 624577416,
346000000 => 895609896,
347000000 => 888287558,
348000000 => 836813268,
349000000 => 926036911,
350000000 => 386027524,
351000000 => 184419613,
352000000 => 724205533,
353000000 => 403351886,
354000000 => 715247054,
355000000 => 716986954,
356000000 => 830567832,
357000000 => 383388563,
358000000 => 68409439,
359000000 => 6734065,
360000000 => 189239124,
361000000 => 68322490,
362000000 => 943653305,
363000000 => 405755338,
364000000 => 811056092,
365000000 => 179518046,
366000000 => 825132993,
367000000 => 343807435,
368000000 => 985084650,
369000000 => 868553027,
370000000 => 148528617,
371000000 => 160684257,
372000000 => 882148737,
373000000 => 591915968,
374000000 => 701445829,
375000000 => 529726489,
376000000 => 302177126,
377000000 => 974886682,
378000000 => 241107368,
379000000 => 798830099,
380000000 => 940567523,
381000000 => 11633075,
382000000 => 325334066,
383000000 => 346091869,
384000000 => 115312728,
385000000 => 473718967,
386000000 => 218129285,
387000000 => 878471898,
388000000 => 180002392,
389000000 => 699739374,
390000000 => 917084264,
391000000 => 856859395,
392000000 => 435327356,
393000000 => 808651347,
394000000 => 421623838,
395000000 => 105419548,
396000000 => 59883031,
397000000 => 322487421,
398000000 => 79716267,
399000000 => 715317963,
400000000 => 429277690,
401000000 => 398078032,
402000000 => 316486674,
403000000 => 384843585,
404000000 => 940338439,
405000000 => 937409008,
406000000 => 940524812,
407000000 => 947549662,
408000000 => 833550543,
409000000 => 593524514,
410000000 => 996164327,
411000000 => 987314628,
412000000 => 697611981,
413000000 => 636177449,
414000000 => 274192146,
415000000 => 418537348,
416000000 => 925347821,
417000000 => 952831975,
418000000 => 893732627,
419000000 => 1277567,
420000000 => 358655417,
421000000 => 141866945,
422000000 => 581830879,
423000000 => 987597705,
424000000 => 347046911,
425000000 => 775305697,
426000000 => 125354499,
427000000 => 951540811,
428000000 => 247662371,
429000000 => 343043237,
430000000 => 568392357,
431000000 => 997474832,
432000000 => 209244402,
433000000 => 380480118,
434000000 => 149586983,
435000000 => 392838702,
436000000 => 309134554,
437000000 => 990779998,
438000000 => 263053337,
439000000 => 325362513,
440000000 => 780072518,
441000000 => 551028176,
442000000 => 990826116,
443000000 => 989944961,
444000000 => 155569943,
445000000 => 596737944,
446000000 => 711553356,
447000000 => 268844715,
448000000 => 451373308,
449000000 => 379404150,
450000000 => 462639908,
451000000 => 961812918,
452000000 => 654611901,
453000000 => 382776490,
454000000 => 41815820,
455000000 => 843321396,
456000000 => 675258797,
457000000 => 845583555,
458000000 => 934281721,
459000000 => 741114145,
460000000 => 275105629,
461000000 => 666247477,
462000000 => 325912072,
463000000 => 526131620,
464000000 => 252551589,
465000000 => 432030917,
466000000 => 554917439,
467000000 => 818036959,
468000000 => 754363835,
469000000 => 795190182,
470000000 => 909210595,
471000000 => 278704903,
472000000 => 719566487,
473000000 => 628514947,
474000000 => 424989675,
475000000 => 321685608,
476000000 => 50590510,
477000000 => 832069712,
478000000 => 198768464,
479000000 => 702004730,
480000000 => 99199382,
481000000 => 707469729,
482000000 => 747407118,
483000000 => 302020341,
484000000 => 497196934,
485000000 => 5003231,
486000000 => 726997875,
487000000 => 382617671,
488000000 => 296229203,
489000000 => 183888367,
490000000 => 703397904,
491000000 => 552133875,
492000000 => 732868367,
493000000 => 350095207,
494000000 => 26031303,
495000000 => 863250534,
496000000 => 216665960,
497000000 => 561745549,
498000000 => 352946234,
499000000 => 784139777,
500000000 => 733333339,
501000000 => 503105966,
502000000 => 459878625,
503000000 => 803187381,
504000000 => 16634739,
505000000 => 180898306,
506000000 => 68718097,
507000000 => 985594252,
508000000 => 404206040,
509000000 => 749724532,
510000000 => 97830135,
511000000 => 611751357,
512000000 => 31131935,
513000000 => 662741752,
514000000 => 864326453,
515000000 => 864869025,
516000000 => 167831173,
517000000 => 559214642,
518000000 => 718498895,
519000000 => 91352335,
520000000 => 608823837,
521000000 => 473379392,
522000000 => 385388084,
523000000 => 152267158,
524000000 => 681756977,
525000000 => 46819124,
526000000 => 313132653,
527000000 => 56547945,
528000000 => 442795120,
529000000 => 796616594,
530000000 => 256141983,
531000000 => 152028387,
532000000 => 636578562,
533000000 => 385377759,
534000000 => 553033642,
535000000 => 491415383,
536000000 => 919273670,
537000000 => 996049638,
538000000 => 326686486,
539000000 => 160150665,
540000000 => 141827977,
541000000 => 540818053,
542000000 => 693305776,
543000000 => 593938674,
544000000 => 186576440,
545000000 => 688809790,
546000000 => 565456578,
547000000 => 749296077,
548000000 => 519397500,
549000000 => 551096742,
550000000 => 696628828,
551000000 => 775025061,
552000000 => 370732451,
553000000 => 164246193,
554000000 => 915265013,
555000000 => 457469634,
556000000 => 923043932,
557000000 => 912368644,
558000000 => 777901604,
559000000 => 464118005,
560000000 => 637939935,
561000000 => 956856710,
562000000 => 490676632,
563000000 => 453019482,
564000000 => 462528877,
565000000 => 502297454,
566000000 => 798895521,
567000000 => 100498586,
568000000 => 699767918,
569000000 => 849974789,
570000000 => 811575797,
571000000 => 438952959,
572000000 => 606870929,
573000000 => 907720182,
574000000 => 179111720,
575000000 => 48053248,
576000000 => 508038818,
577000000 => 811944661,
578000000 => 752550134,
579000000 => 401382061,
580000000 => 848924691,
581000000 => 764368449,
582000000 => 34629406,
583000000 => 529840945,
584000000 => 435904287,
585000000 => 26011548,
586000000 => 208184231,
587000000 => 446477394,
588000000 => 206330671,
589000000 => 366033520,
590000000 => 131772368,
591000000 => 185646898,
592000000 => 648711554,
593000000 => 472759660,
594000000 => 523696723,
595000000 => 271198437,
596000000 => 25058942,
597000000 => 859369491,
598000000 => 817928963,
599000000 => 330711333,
600000000 => 724464507,
601000000 => 437605233,
602000000 => 701453022,
603000000 => 626663115,
604000000 => 281230685,
605000000 => 510650790,
606000000 => 596949867,
607000000 => 295726547,
608000000 => 303076380,
609000000 => 465070856,
610000000 => 272814771,
611000000 => 538771609,
612000000 => 48824684,
613000000 => 951279549,
614000000 => 939889684,
615000000 => 564188856,
616000000 => 48527183,
617000000 => 201307702,
618000000 => 484458461,
619000000 => 861754542,
620000000 => 326159309,
621000000 => 181594759,
622000000 => 668422905,
623000000 => 286273596,
624000000 => 965656187,
625000000 => 44135644,
626000000 => 359960756,
627000000 => 936229527,
628000000 => 407934361,
629000000 => 267193060,
630000000 => 456152084,
631000000 => 459116722,
632000000 => 124804049,
633000000 => 262322489,
634000000 => 920251227,
635000000 => 816929577,
636000000 => 483924582,
637000000 => 151834896,
638000000 => 167087470,
639000000 => 490222511,
640000000 => 903466878,
641000000 => 361583925,
642000000 => 368114731,
643000000 => 339383292,
644000000 => 388728584,
645000000 => 218107212,
646000000 => 249153339,
647000000 => 909458706,
648000000 => 322908524,
649000000 => 202649964,
650000000 => 92255682,
651000000 => 573074791,
652000000 => 15570863,
653000000 => 94331513,
654000000 => 744158074,
655000000 => 196345098,
656000000 => 334326205,
657000000 => 9416035,
658000000 => 98349682,
659000000 => 882121662,
660000000 => 769795511,
661000000 => 231988936,
662000000 => 888146074,
663000000 => 137603545,
664000000 => 582627184,
665000000 => 407518072,
666000000 => 919419361,
667000000 => 909433461,
668000000 => 986708498,
669000000 => 310317874,
670000000 => 373745190,
671000000 => 263645931,
672000000 => 256853930,
673000000 => 876379959,
674000000 => 702823274,
675000000 => 147050765,
676000000 => 308186532,
677000000 => 175504139,
678000000 => 180350107,
679000000 => 797736554,
680000000 => 606241871,
681000000 => 384547635,
682000000 => 273712630,
683000000 => 586444655,
684000000 => 682189174,
685000000 => 666493603,
686000000 => 946867127,
687000000 => 819114541,
688000000 => 502371023,
689000000 => 261970285,
690000000 => 825871994,
691000000 => 126925175,
692000000 => 701506133,
693000000 => 314738056,
694000000 => 341779962,
695000000 => 561011609,
696000000 => 815463367,
697000000 => 46765164,
698000000 => 49187570,
699000000 => 188054995,
700000000 => 957939114,
701000000 => 64814326,
702000000 => 933376898,
703000000 => 329837066,
704000000 => 338121343,
705000000 => 765215899,
706000000 => 869630152,
707000000 => 978119194,
708000000 => 632627667,
709000000 => 975266085,
710000000 => 435887178,
711000000 => 282092463,
712000000 => 129621197,
713000000 => 758245605,
714000000 => 827722926,
715000000 => 201339230,
716000000 => 918513230,
717000000 => 322096036,
718000000 => 547838438,
719000000 => 985546115,
720000000 => 852304035,
721000000 => 593090119,
722000000 => 689189630,
723000000 => 555842733,
724000000 => 567033437,
725000000 => 469928208,
726000000 => 212842957,
727000000 => 117842065,
728000000 => 404149413,
729000000 => 155133422,
730000000 => 663307737,
731000000 => 208761293,
732000000 => 206282795,
733000000 => 717946122,
734000000 => 488906585,
735000000 => 414236650,
736000000 => 280700600,
737000000 => 962670136,
738000000 => 534279149,
739000000 => 214569244,
740000000 => 375297772,
741000000 => 811053196,
742000000 => 922377372,
743000000 => 289594327,
744000000 => 219932130,
745000000 => 211487466,
746000000 => 701050258,
747000000 => 398782410,
748000000 => 863002719,
749000000 => 27236531,
750000000 => 217598709,
751000000 => 375472836,
752000000 => 810551911,
753000000 => 178598958,
754000000 => 247844667,
755000000 => 676526196,
756000000 => 812283640,
757000000 => 863066876,
758000000 => 857241854,
759000000 => 113917835,
760000000 => 624148346,
761000000 => 726089763,
762000000 => 564827277,
763000000 => 826300950,
764000000 => 478982047,
765000000 => 439411911,
766000000 => 454039189,
767000000 => 633292726,
768000000 => 48562889,
769000000 => 802100365,
770000000 => 671734977,
771000000 => 945204804,
772000000 => 508831870,
773000000 => 398781902,
774000000 => 897162044,
775000000 => 644050694,
776000000 => 892168027,
777000000 => 828883117,
778000000 => 277714559,
779000000 => 713448377,
780000000 => 624500515,
781000000 => 590098114,
782000000 => 808691930,
783000000 => 514359662,
784000000 => 895205045,
785000000 => 715264908,
786000000 => 628829100,
787000000 => 484492064,
788000000 => 919717789,
789000000 => 513196123,
790000000 => 748510389,
791000000 => 403652653,
792000000 => 574455974,
793000000 => 77123823,
794000000 => 172096141,
795000000 => 819801784,
796000000 => 581418893,
797000000 => 15655126,
798000000 => 15391652,
799000000 => 875641535,
800000000 => 203191898,
801000000 => 264582598,
802000000 => 880691101,
803000000 => 907800444,
804000000 => 986598821,
805000000 => 340030191,
806000000 => 264688936,
807000000 => 369832433,
808000000 => 785804644,
809000000 => 842065079,
810000000 => 423951674,
811000000 => 663560047,
812000000 => 696623384,
813000000 => 496709826,
814000000 => 161960209,
815000000 => 331910086,
816000000 => 541120825,
817000000 => 951524114,
818000000 => 841656666,
819000000 => 162683802,
820000000 => 629786193,
821000000 => 190395535,
822000000 => 269571439,
823000000 => 832671304,
824000000 => 76770272,
825000000 => 341080135,
826000000 => 421943723,
827000000 => 494210290,
828000000 => 751040886,
829000000 => 317076664,
830000000 => 672850561,
831000000 => 72482816,
832000000 => 493689107,
833000000 => 135625240,
834000000 => 100228913,
835000000 => 684748812,
836000000 => 639655136,
837000000 => 906233141,
838000000 => 929893103,
839000000 => 277813439,
840000000 => 814362881,
841000000 => 562608724,
842000000 => 406024012,
843000000 => 885537778,
844000000 => 10065330,
845000000 => 60625018,
846000000 => 983737173,
847000000 => 60517502,
848000000 => 551060742,
849000000 => 804930491,
850000000 => 823845496,
851000000 => 727416538,
852000000 => 946421040,
853000000 => 678171399,
854000000 => 842203531,
855000000 => 175638827,
856000000 => 894247956,
857000000 => 538609927,
858000000 => 885362182,
859000000 => 946464959,
860000000 => 116667533,
861000000 => 749816133,
862000000 => 241427979,
863000000 => 871117927,
864000000 => 281804989,
865000000 => 163928347,
866000000 => 563796647,
867000000 => 640266394,
868000000 => 774625892,
869000000 => 59342705,
870000000 => 256473217,
871000000 => 674115061,
872000000 => 918860977,
873000000 => 322633051,
874000000 => 753513874,
875000000 => 393556719,
876000000 => 304644842,
877000000 => 767372800,
878000000 => 161362528,
879000000 => 754787150,
880000000 => 627655552,
881000000 => 677395736,
882000000 => 799289297,
883000000 => 846650652,
884000000 => 816701166,
885000000 => 687265514,
886000000 => 787113234,
887000000 => 358757251,
888000000 => 701220427,
889000000 => 607715125,
890000000 => 245795606,
891000000 => 600624983,
892000000 => 10475577,
893000000 => 728620948,
894000000 => 759404319,
895000000 => 36292292,
896000000 => 491466901,
897000000 => 22556579,
898000000 => 114495791,
899000000 => 647630109,
900000000 => 586445753,
901000000 => 482254337,
902000000 => 718623833,
903000000 => 763514207,
904000000 => 66547751,
905000000 => 953634340,
906000000 => 351472920,
907000000 => 308474522,
908000000 => 494166907,
909000000 => 634359666,
910000000 => 172114298,
911000000 => 865440961,
912000000 => 364380585,
913000000 => 921648059,
914000000 => 965683742,
915000000 => 260466949,
916000000 => 117483873,
917000000 => 962540888,
918000000 => 237120480,
919000000 => 620531822,
920000000 => 193781724,
921000000 => 213092254,
922000000 => 107141741,
923000000 => 602742426,
924000000 => 793307102,
925000000 => 756154604,
926000000 => 236455213,
927000000 => 362928234,
928000000 => 14162538,
929000000 => 753042874,
930000000 => 778983779,
931000000 => 25977209,
932000000 => 49389215,
933000000 => 698308420,
934000000 => 859637374,
935000000 => 49031023,
936000000 => 713258160,
937000000 => 737331920,
938000000 => 923333660,
939000000 => 804861409,
940000000 => 83868974,
941000000 => 682873215,
942000000 => 217298111,
943000000 => 883278906,
944000000 => 176966527,
945000000 => 954913,
946000000 => 105359006,
947000000 => 390019735,
948000000 => 10430738,
949000000 => 706334445,
950000000 => 315103615,
951000000 => 567473423,
952000000 => 708233401,
953000000 => 48160594,
954000000 => 946149627,
955000000 => 346966053,
956000000 => 281329488,
957000000 => 462880311,
958000000 => 31503476,
959000000 => 185438078,
960000000 => 965785236,
961000000 => 992656683,
962000000 => 916291845,
963000000 => 881482632,
964000000 => 899946391,
965000000 => 321900901,
966000000 => 512634493,
967000000 => 303338827,
968000000 => 121000338,
969000000 => 967284733,
970000000 => 492741665,
971000000 => 152233223,
972000000 => 165393390,
973000000 => 680128316,
974000000 => 917041303,
975000000 => 532702135,
976000000 => 741626808,
977000000 => 496442755,
978000000 => 536841269,
979000000 => 131384366,
980000000 => 377329025,
981000000 => 301196854,
982000000 => 859917803,
983000000 => 676511002,
984000000 => 373451745,
985000000 => 847645126,
986000000 => 823495900,
987000000 => 576368335,
988000000 => 73146164,
989000000 => 954958912,
990000000 => 847549272,
991000000 => 241289571,
992000000 => 646654592,
993000000 => 216046746,
994000000 => 205951465,
995000000 => 3258987,
996000000 => 780882948,
997000000 => 822439091,
998000000 => 598245292,
999000000 => 869544707,
1000000000 => 698611116,
}

MOD = 10**9+7
M = 10**6

def fact(n)
    m = n/M*M
    ret = MEMO[m]
    ((m+1)..n).each do |i|
        ret = ret * i % MOD
    end
    ret
end

def extgcd(a, b)
    if b == 0
        {x: 1, y: 0, gcd: a}
    else
        prev = extgcd(b, a % b)
        {
            x: prev[:y],
            y: prev[:x] - (a / b) * prev[:y],
            gcd: prev[:gcd]
        }
    end
end

def inv_mod(num)
    hash = extgcd(num, MOD)
    hash[:x] % MOD
end


K = gets.to_i

if K % 2 == 1
    puts 0
else
    inv = inv_mod(fact(K/2))
    puts fact(K) * (inv**2) % MOD
end