結果
| 問題 | No.2131 Concon Substrings (COuNt Version) |
| ユーザー |
👑  p-adic
|
| 提出日時 | 2022-10-25 12:53:21 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 2,000 ms |
| コード長 | 54,492 bytes |
| コンパイル時間 | 2,553 ms |
| コンパイル使用メモリ | 201,800 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-07-03 12:25:31 |
| 合計ジャッジ時間 | 2,845 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,940 KB |
| testcase_04 | AC | 2 ms
6,940 KB |
| testcase_05 | AC | 2 ms
6,940 KB |
| testcase_06 | AC | 2 ms
6,940 KB |
| testcase_07 | AC | 2 ms
6,944 KB |
| testcase_08 | AC | 3 ms
6,940 KB |
| testcase_09 | AC | 2 ms
6,944 KB |
| testcase_10 | AC | 2 ms
6,944 KB |
| testcase_11 | AC | 2 ms
6,944 KB |
| testcase_12 | AC | 2 ms
6,940 KB |
| testcase_13 | AC | 2 ms
6,940 KB |
| testcase_14 | AC | 2 ms
6,944 KB |
| testcase_15 | AC | 2 ms
6,944 KB |
| testcase_16 | AC | 2 ms
6,940 KB |
| testcase_17 | AC | 2 ms
6,944 KB |
| testcase_18 | AC | 2 ms
6,940 KB |
| testcase_19 | AC | 2 ms
6,940 KB |
ソースコード
// 念の為（？）埋め込み解チェック
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define CIN( LL , A ) LL A; cin >> A
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX )
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX )
#define QUIT return 0
#define RETURN( ANSWER ) cout << ( ANSWER ) << "\n"; QUIT
#define CHECK_REDUNDANT_INPUT string VARIABLE_FOR_CHECK_REDUNDANT_INPUT = ""; cin >> VARIABLE_FOR_CHECK_REDUNDANT_INPUT; assert( VARIABLE_FOR_CHECK_REDUNDANT_INPUT == "" ); assert( ! cin );
int main()
{
constexpr const int bound_N = 3000;
CIN_ASSERT( N , 3 , bound_N );
CHECK_REDUNDANT_INPUT;
constexpr const ll answer[bound_N + 1] =
{
0 ,
0 ,
0 ,
1 ,
101 ,
6376 ,
322027 ,
14232227 ,
575129152 ,
827039040 ,
701907442 ,
277845895 ,
576446680 ,
98704771 ,
581398102 ,
562145665 ,
170298373 ,
244198299 ,
981746362 ,
75584221 ,
195415695 ,
814025243 ,
474295314 ,
8941106 ,
49934313 ,
160598438 ,
815795654 ,
449512192 ,
648524733 ,
189771026 ,
813114736 ,
765233312 ,
549305412 ,
535783047 ,
720427119 ,
481010691 ,
316063442 ,
32778069 ,
235322726 ,
100657435 ,
494730726 ,
777877236 ,
228339370 ,
664126646 ,
235399238 ,
821639977 ,
193572569 ,
740240062 ,
837446059 ,
984065258 ,
2236013 ,
103445890 ,
881459499 ,
762365986 ,
729469583 ,
764254482 ,
913288619 ,
176062298 ,
302439046 ,
908745084 ,
379776527 ,
730375363 ,
131169827 ,
518619205 ,
751390461 ,
997398477 ,
261251134 ,
152648201 ,
48307836 ,
126650735 ,
137061342 ,
537724526 ,
997565245 ,
845232978 ,
886233616 ,
378301408 ,
275992813 ,
72165864 ,
443884010 ,
859853137 ,
613001374 ,
209391279 ,
835530 ,
648384886 ,
125484676 ,
875428169 ,
532728632 ,
397043582 ,
505319151 ,
42384407 ,
564084411 ,
326173063 ,
809849412 ,
443193314 ,
350803219 ,
505498251 ,
111171517 ,
858743509 ,
505273258 ,
14000708 ,
291304103 ,
27640647 ,
61476128 ,
127248709 ,
825527500 ,
8511348 ,
631909785 ,
925426414 ,
340002670 ,
749112657 ,
723209948 ,
495286762 ,
791076844 ,
721359243 ,
849135481 ,
766623858 ,
19449058 ,
177283782 ,
287132408 ,
350678023 ,
577128191 ,
812946358 ,
633987998 ,
68659831 ,
244837819 ,
606488479 ,
916302093 ,
309278064 ,
566408094 ,
776307274 ,
48740289 ,
305867367 ,
905333170 ,
111994546 ,
652378334 ,
979752057 ,
804517856 ,
905331918 ,
546679726 ,
245067293 ,
67185856 ,
196966406 ,
216634829 ,
891091540 ,
275182861 ,
570597849 ,
779121760 ,
961212915 ,
461901067 ,
660133188 ,
602859276 ,
628813186 ,
742001027 ,
599771290 ,
192412692 ,
362065655 ,
749039373 ,
756161215 ,
579039793 ,
852613062 ,
855858942 ,
981257090 ,
500793964 ,
990381460 ,
316844353 ,
652347767 ,
467544732 ,
853197813 ,
566856094 ,
361963989 ,
366777195 ,
836893140 ,
995307637 ,
215306650 ,
776014186 ,
547421712 ,
85640292 ,
874540197 ,
705646477 ,
816801141 ,
423942730 ,
145487415 ,
719790860 ,
762752377 ,
822706657 ,
330887601 ,
331649002 ,
399126393 ,
456997965 ,
558437808 ,
754797401 ,
366192922 ,
246460873 ,
180122584 ,
952338726 ,
191946463 ,
41707762 ,
128863051 ,
857066999 ,
255524362 ,
419167070 ,
850070504 ,
287013122 ,
561650059 ,
425015953 ,
517456909 ,
560169400 ,
613124231 ,
541110363 ,
248376414 ,
4511471 ,
773081729 ,
737488127 ,
470666686 ,
79469546 ,
663406913 ,
857484355 ,
806799054 ,
225313216 ,
527101921 ,
819079602 ,
857936040 ,
360073350 ,
367706621 ,
483564528 ,
977253699 ,
656844459 ,
473778707 ,
231372137 ,
402692820 ,
331816509 ,
124017725 ,
194073776 ,
855359665 ,
533531299 ,
103049496 ,
367880512 ,
96180518 ,
507263531 ,
942777399 ,
413240290 ,
812921862 ,
350037642 ,
589367204 ,
193398852 ,
426324733 ,
906723654 ,
448752138 ,
932408588 ,
613774820 ,
98237551 ,
552421201 ,
864244771 ,
436880637 ,
111608034 ,
556969256 ,
353447283 ,
837608279 ,
532685151 ,
734195360 ,
186854981 ,
479624226 ,
422675839 ,
547297053 ,
179717144 ,
605847379 ,
366267217 ,
714826078 ,
336877225 ,
205915990 ,
298985168 ,
739435876 ,
704265010 ,
400742549 ,
504541128 ,
612138870 ,
54368855 ,
990897615 ,
825098060 ,
112853771 ,
472190359 ,
333027737 ,
143633263 ,
232463299 ,
848941736 ,
817926083 ,
840062880 ,
154691553 ,
924783629 ,
659156465 ,
471954935 ,
620242380 ,
656565689 ,
395103494 ,
950930616 ,
915848880 ,
852654924 ,
378801002 ,
806906777 ,
406719496 ,
403981484 ,
802033734 ,
804606504 ,
699497705 ,
631009376 ,
868401868 ,
838330308 ,
699800171 ,
268571525 ,
658880309 ,
639617550 ,
988236238 ,
755776523 ,
205486849 ,
158667401 ,
330209991 ,
236986843 ,
836750293 ,
445666123 ,
648394813 ,
903222087 ,
127767748 ,
609142161 ,
597815548 ,
223617620 ,
796952666 ,
358033445 ,
177705773 ,
694141654 ,
419266355 ,
542589655 ,
469838372 ,
560124732 ,
126470002 ,
208513433 ,
735465029 ,
933706279 ,
143968907 ,
431283769 ,
672240860 ,
281125893 ,
770719642 ,
659167361 ,
429453828 ,
233349562 ,
650982723 ,
823089 ,
583582488 ,
197222301 ,
101240488 ,
330849325 ,
712703310 ,
695052652 ,
732829351 ,
31833251 ,
122982253 ,
211411192 ,
449178323 ,
573640945 ,
41177280 ,
935373421 ,
191199686 ,
306318149 ,
106861182 ,
276620110 ,
281107380 ,
316409515 ,
411992037 ,
917941007 ,
194544559 ,
751240321 ,
8662263 ,
56796515 ,
662998379 ,
376099716 ,
926297891 ,
213442226 ,
588409487 ,
885319613 ,
201134633 ,
150843079 ,
50409897 ,
425716649 ,
775990419 ,
472023344 ,
158343285 ,
726606994 ,
451508611 ,
924430738 ,
573654266 ,
145812825 ,
752900511 ,
419746533 ,
60177625 ,
261724565 ,
642647139 ,
107670976 ,
134696786 ,
454755185 ,
205848381 ,
751072537 ,
726388607 ,
535351161 ,
581855658 ,
374256937 ,
447091044 ,
747877788 ,
331460128 ,
395072367 ,
141177197 ,
899501674 ,
830666735 ,
94384262 ,
40364058 ,
813271978 ,
890626760 ,
420093867 ,
351070190 ,
664789696 ,
922377170 ,
47649282 ,
49169108 ,
667266156 ,
199644559 ,
487674462 ,
470170023 ,
848045155 ,
539602668 ,
127448338 ,
307359130 ,
955720186 ,
846877284 ,
708597804 ,
85290056 ,
863553690 ,
447092952 ,
25828122 ,
133705655 ,
62025000 ,
987409557 ,
13196396 ,
857922291 ,
920662566 ,
510091385 ,
812055968 ,
192217741 ,
319111779 ,
252812176 ,
710471802 ,
644644987 ,
76923046 ,
289305908 ,
877746215 ,
567220171 ,
266558076 ,
938838144 ,
798021246 ,
253336966 ,
158890606 ,
889008278 ,
533553505 ,
530384731 ,
708842909 ,
925614849 ,
431204510 ,
87383269 ,
409964491 ,
213109408 ,
814484600 ,
956100305 ,
445806646 ,
554710544 ,
556670220 ,
773268868 ,
993948282 ,
897641236 ,
279656564 ,
619586906 ,
762987207 ,
458302067 ,
912311851 ,
661683430 ,
191032321 ,
614763226 ,
379058058 ,
381014265 ,
357656796 ,
589511449 ,
473582870 ,
877031849 ,
299269143 ,
144294609 ,
237323539 ,
89250527 ,
409582503 ,
725993827 ,
308966077 ,
985288864 ,
389976449 ,
465714501 ,
79058297 ,
545559775 ,
111150345 ,
823819485 ,
200145396 ,
933281162 ,
861363201 ,
561231444 ,
567625430 ,
988370840 ,
725037055 ,
27694663 ,
745872163 ,
846374124 ,
445423867 ,
240410824 ,
679413977 ,
335363327 ,
212033731 ,
380187766 ,
274339277 ,
172127116 ,
512933087 ,
457445920 ,
717682278 ,
353204342 ,
194265569 ,
883434411 ,
990108654 ,
308804855 ,
166767112 ,
510707750 ,
402208540 ,
829188501 ,
250519624 ,
19274390 ,
678461466 ,
735943330 ,
656031722 ,
397706533 ,
522271420 ,
944665598 ,
461502755 ,
76128232 ,
573768685 ,
348155143 ,
897564116 ,
203049694 ,
154547307 ,
967251933 ,
100607986 ,
265713006 ,
413482225 ,
446693306 ,
969460304 ,
947865674 ,
746530118 ,
361870177 ,
66999121 ,
979901070 ,
456822385 ,
491127877 ,
319954804 ,
165880719 ,
870866191 ,
741266415 ,
20338179 ,
326162793 ,
468225370 ,
786647649 ,
17177237 ,
837809503 ,
948672877 ,
328159835 ,
854097618 ,
634574936 ,
428265485 ,
954909744 ,
217802930 ,
598731759 ,
403551322 ,
369668674 ,
117456101 ,
965897566 ,
743634908 ,
185143269 ,
784831794 ,
259922566 ,
414779634 ,
645904013 ,
122914828 ,
299611571 ,
798907922 ,
664389141 ,
568543153 ,
641205375 ,
350508042 ,
353792900 ,
897717219 ,
663706889 ,
717469405 ,
170865928 ,
671124852 ,
812648041 ,
409610711 ,
101239759 ,
304368130 ,
288689721 ,
145116267 ,
341718989 ,
954652170 ,
666207838 ,
681982655 ,
654651349 ,
892813049 ,
134588050 ,
72859819 ,
582869826 ,
813890551 ,
559280182 ,
543303170 ,
626612092 ,
403672939 ,
294760212 ,
536843540 ,
240024316 ,
39220159 ,
265957667 ,
370572623 ,
69804636 ,
298173241 ,
382690243 ,
298340872 ,
953055831 ,
974890249 ,
251475323 ,
846068845 ,
230649367 ,
776928535 ,
66948455 ,
183948966 ,
489389530 ,
568131973 ,
612113318 ,
865678670 ,
617949229 ,
853513164 ,
161020178 ,
902258493 ,
215798402 ,
913290213 ,
781437402 ,
590918356 ,
180787 ,
598706714 ,
123092853 ,
854872216 ,
385621040 ,
576369855 ,
137861754 ,
957287159 ,
137629167 ,
384389589 ,
806723033 ,
533194735 ,
21818868 ,
166732164 ,
940553599 ,
163621833 ,
962972802 ,
632151486 ,
544672783 ,
703812004 ,
315723823 ,
980584555 ,
67378323 ,
445371847 ,
412394573 ,
726519743 ,
666545066 ,
492806919 ,
845941618 ,
602760256 ,
770177668 ,
676096830 ,
604164024 ,
947857726 ,
847620360 ,
884990104 ,
259137969 ,
433830669 ,
807330291 ,
374941462 ,
167791072 ,
428915007 ,
364504291 ,
483977728 ,
302966094 ,
432794724 ,
456053354 ,
484576167 ,
817425926 ,
111740002 ,
693405133 ,
248218800 ,
587229434 ,
340723446 ,
482880642 ,
563395006 ,
904306622 ,
99133262 ,
29195826 ,
697044160 ,
447910179 ,
950823113 ,
341482425 ,
260088986 ,
486148825 ,
527445893 ,
397569005 ,
798905696 ,
60943197 ,
407430055 ,
688592433 ,
633489611 ,
138832153 ,
301225937 ,
160762987 ,
952029084 ,
776824387 ,
56875981 ,
773891743 ,
342626076 ,
41373064 ,
25701173 ,
146364712 ,
875204561 ,
723502507 ,
468451952 ,
339842410 ,
546354765 ,
525685123 ,
367562046 ,
256306419 ,
341802056 ,
407779458 ,
294005808 ,
508634335 ,
91011451 ,
87067102 ,
928124720 ,
186821826 ,
671000594 ,
592347302 ,
860196614 ,
908647170 ,
23128763 ,
317066683 ,
526244467 ,
92027453 ,
81380167 ,
566232429 ,
725443431 ,
590922329 ,
17214591 ,
531552561 ,
331583843 ,
146899459 ,
557807703 ,
282588840 ,
171448992 ,
437621476 ,
810644924 ,
801199926 ,
643568856 ,
196800309 ,
879870320 ,
407241454 ,
846824580 ,
529142703 ,
530205771 ,
754175443 ,
115899709 ,
417925828 ,
645188390 ,
916596371 ,
179460459 ,
849949983 ,
371163645 ,
995955987 ,
473889930 ,
173717029 ,
95027161 ,
113556924 ,
531505430 ,
697605777 ,
40943969 ,
883947830 ,
923086371 ,
845831882 ,
861267826 ,
865530744 ,
54570539 ,
965145078 ,
103881137 ,
730357303 ,
611452571 ,
639345259 ,
301319521 ,
282180322 ,
445635588 ,
243988786 ,
528178922 ,
512855652 ,
233254721 ,
197998550 ,
105216097 ,
987950393 ,
108103323 ,
149938339 ,
142999437 ,
987069070 ,
311605789 ,
784674896 ,
300468906 ,
189034627 ,
277209559 ,
469800819 ,
37763776 ,
396561648 ,
843903298 ,
738151242 ,
528487179 ,
905055379 ,
697558924 ,
810312322 ,
167457164 ,
108200290 ,
828304113 ,
949351621 ,
489046934 ,
17055881 ,
844239725 ,
198804295 ,
665862151 ,
385401096 ,
749975311 ,
593057883 ,
927100908 ,
91789477 ,
877649692 ,
157575999 ,
169019140 ,
807590643 ,
911791875 ,
757547771 ,
609362602 ,
937751478 ,
971617758 ,
646014853 ,
439594743 ,
23465482 ,
732010960 ,
342922167 ,
201870335 ,
27602849 ,
533158240 ,
561540483 ,
668484745 ,
825338094 ,
6926252 ,
629524396 ,
601587985 ,
579379523 ,
117497746 ,
334748854 ,
768257174 ,
421326962 ,
99284122 ,
326862292 ,
292511580 ,
818397881 ,
375090152 ,
58950207 ,
118881842 ,
229382328 ,
197716375 ,
494317040 ,
321457148 ,
574463624 ,
813259509 ,
261236780 ,
936743153 ,
5244246 ,
222302460 ,
336495635 ,
845395181 ,
927836529 ,
895794017 ,
755228729 ,
593056469 ,
548089490 ,
451630806 ,
372203836 ,
627791030 ,
419711811 ,
613737051 ,
191901652 ,
624473596 ,
557776572 ,
41200486 ,
579832622 ,
531496700 ,
218394327 ,
291763933 ,
112960840 ,
423912828 ,
260205211 ,
605857370 ,
79122699 ,
448431043 ,
406112616 ,
171816454 ,
50141064 ,
415987425 ,
280887775 ,
356771190 ,
577330164 ,
652212708 ,
48556069 ,
885902591 ,
357885122 ,
618079499 ,
523777741 ,
447726792 ,
933783546 ,
424548426 ,
919832607 ,
719166769 ,
949427969 ,
507145284 ,
703984787 ,
787526954 ,
411786732 ,
176111350 ,
819142959 ,
858330246 ,
93974903 ,
858102127 ,
353833976 ,
870350758 ,
704907363 ,
409803042 ,
612883666 ,
164840618 ,
530448207 ,
476183401 ,
239715854 ,
269054086 ,
993203843 ,
500241343 ,
930805151 ,
862724583 ,
310526340 ,
101201346 ,
937828647 ,
974422146 ,
201544777 ,
519714769 ,
662501472 ,
502469427 ,
497189066 ,
191535129 ,
320888101 ,
591252807 ,
972996480 ,
764143808 ,
70780524 ,
659724296 ,
220933802 ,
754815991 ,
913207762 ,
453090305 ,
208439401 ,
65893050 ,
510973313 ,
843705498 ,
980854518 ,
812933356 ,
492297950 ,
264121993 ,
307752880 ,
824996369 ,
661912109 ,
401910675 ,
261631499 ,
942494346 ,
802293480 ,
364391250 ,
879606489 ,
753300838 ,
262249046 ,
437752127 ,
693759670 ,
772797449 ,
306193954 ,
878734053 ,
144258360 ,
490405599 ,
691975032 ,
580621268 ,
373777219 ,
529476736 ,
883991336 ,
871066591 ,
670438917 ,
37546404 ,
160991710 ,
648042110 ,
736775701 ,
622498231 ,
487321729 ,
149997127 ,
582685639 ,
318448432 ,
394945644 ,
283730659 ,
335708215 ,
27625669 ,
882591512 ,
313210322 ,
332359573 ,
742294120 ,
891500226 ,
903989037 ,
247110125 ,
637447018 ,
33908430 ,
866664275 ,
737902911 ,
664481583 ,
879906891 ,
543110687 ,
787236189 ,
394597757 ,
460694226 ,
960067620 ,
508440145 ,
984366337 ,
215824005 ,
489856980 ,
275996678 ,
468488173 ,
24665297 ,
34480153 ,
379535419 ,
675912440 ,
166596274 ,
789820233 ,
304408540 ,
123952625 ,
914027728 ,
238919588 ,
82892476 ,
302419934 ,
83567434 ,
324900151 ,
37821922 ,
46841649 ,
218675138 ,
460856859 ,
341616353 ,
766359724 ,
146370825 ,
521331637 ,
213587221 ,
198138786 ,
369505623 ,
204787882 ,
713148385 ,
981309872 ,
17407767 ,
303382990 ,
261426768 ,
755118032 ,
819697618 ,
731529924 ,
909052995 ,
722407859 ,
472675672 ,
120316459 ,
565914687 ,
563974355 ,
222081823 ,
210791559 ,
716242398 ,
432207429 ,
866812044 ,
345558540 ,
420517750 ,
162195348 ,
606328829 ,
665317182 ,
137199184 ,
269606528 ,
261670295 ,
490409908 ,
913664395 ,
932914907 ,
297024854 ,
690913139 ,
982070428 ,
339532918 ,
472747005 ,
683100667 ,
523533902 ,
915856884 ,
698409091 ,
138909227 ,
495771853 ,
675124474 ,
903879745 ,
758389098 ,
112127988 ,
634987256 ,
26206768 ,
417175329 ,
594170829 ,
866324315 ,
356767682 ,
781653716 ,
726165728 ,
263542820 ,
365155001 ,
320899670 ,
388084879 ,
792999491 ,
139696491 ,
739114253 ,
549651094 ,
161254252 ,
953364707 ,
643427487 ,
436243596 ,
491512558 ,
890024705 ,
821450629 ,
29089697 ,
409778061 ,
79117491 ,
190470911 ,
150894541 ,
867443163 ,
828489182 ,
232592124 ,
72261265 ,
547946350 ,
984761847 ,
334792272 ,
516083146 ,
929162320 ,
265041316 ,
34600417 ,
932698390 ,
828559632 ,
33680842 ,
542188255 ,
551534170 ,
410798253 ,
747850486 ,
121113289 ,
567874790 ,
677291883 ,
20139706 ,
679341299 ,
925387920 ,
986671632 ,
515207449 ,
538982906 ,
959601788 ,
169054607 ,
205707797 ,
73388666 ,
566013569 ,
372961145 ,
576918024 ,
566405441 ,
524223009 ,
67251600 ,
994994795 ,
62847779 ,
12270439 ,
99872716 ,
630405739 ,
956331770 ,
975967316 ,
467619241 ,
594385114 ,
743517868 ,
648038386 ,
437643691 ,
945810445 ,
520539873 ,
391852510 ,
818158423 ,
620978859 ,
331894517 ,
295612422 ,
889412520 ,
384452994 ,
799191926 ,
803092015 ,
567947152 ,
768449159 ,
760983639 ,
129594852 ,
802745797 ,
356911453 ,
542733004 ,
896386216 ,
91857618 ,
432000499 ,
788361978 ,
579034824 ,
990189047 ,
217633545 ,
528179477 ,
355658658 ,
594908584 ,
494090114 ,
565862544 ,
517622883 ,
465454438 ,
738674698 ,
640301049 ,
564667280 ,
677713603 ,
824368940 ,
82168556 ,
541134884 ,
792420709 ,
326342290 ,
220652737 ,
688807926 ,
44934871 ,
721938165 ,
975447353 ,
932487925 ,
859622219 ,
775480441 ,
205488772 ,
969949428 ,
783924614 ,
347136117 ,
633832773 ,
451722900 ,
670878294 ,
267005907 ,
711513190 ,
369629561 ,
961312535 ,
996747030 ,
351213876 ,
835139828 ,
80632679 ,
35507352 ,
423597246 ,
738735386 ,
737673812 ,
303162076 ,
508223284 ,
487049301 ,
333883187 ,
369647396 ,
415133788 ,
26661775 ,
992969673 ,
968039512 ,
31000278 ,
622166092 ,
22816927 ,
604842141 ,
953128243 ,
581416376 ,
223393187 ,
245721251 ,
796709987 ,
563887506 ,
736144952 ,
800199580 ,
499192061 ,
897126077 ,
222498946 ,
822376518 ,
169448577 ,
984694895 ,
803078105 ,
321092006 ,
549743220 ,
665538621 ,
658594331 ,
576967859 ,
602738418 ,
516993341 ,
328833342 ,
966366648 ,
442506389 ,
728230157 ,
291297490 ,
908036412 ,
783577804 ,
700737506 ,
681289415 ,
994068448 ,
330074062 ,
688852048 ,
300029157 ,
634719621 ,
102863779 ,
718959928 ,
143811011 ,
420305515 ,
61930688 ,
146284441 ,
952659289 ,
361862355 ,
846320616 ,
941588195 ,
307999066 ,
257491796 ,
693848831 ,
701929243 ,
121437303 ,
731265225 ,
636890557 ,
270935997 ,
911893831 ,
661976414 ,
872080271 ,
657541335 ,
142226669 ,
514271278 ,
972078671 ,
793439347 ,
583148201 ,
811725335 ,
133090969 ,
625809087 ,
87016401 ,
281072973 ,
190697958 ,
545253982 ,
789141649 ,
502004477 ,
755651895 ,
831024972 ,
326668708 ,
122912519 ,
715347194 ,
723687211 ,
665870626 ,
349983945 ,
464309845 ,
568484971 ,
559944205 ,
202190037 ,
344926690 ,
525466543 ,
587581991 ,
627263344 ,
41764996 ,
519514095 ,
946515064 ,
279527317 ,
594384223 ,
765362219 ,
747613813 ,
385646517 ,
228046369 ,
235975149 ,
363233584 ,
609181059 ,
962213217 ,
137863458 ,
990473246 ,
414876675 ,
789726216 ,
932060014 ,
128272488 ,
527083447 ,
553934121 ,
996089366 ,
768634186 ,
831662815 ,
33261795 ,
338418782 ,
240314522 ,
720696823 ,
226075118 ,
814847558 ,
626182273 ,
705777784 ,
499627069 ,
967144333 ,
221140800 ,
225444559 ,
355603317 ,
747193392 ,
555451554 ,
936126499 ,
112265224 ,
378470229 ,
666570407 ,
521633396 ,
28418606 ,
922943866 ,
374900472 ,
302480780 ,
913100649 ,
984184065 ,
630970470 ,
50628526 ,
359506843 ,
576075386 ,
739599029 ,
451664833 ,
527060438 ,
606321348 ,
504333875 ,
175187473 ,
836859877 ,
450675294 ,
570133936 ,
617140543 ,
494279644 ,
210963565 ,
198389486 ,
68757536 ,
522121430 ,
176360807 ,
693180233 ,
904040909 ,
283219906 ,
91398487 ,
127601442 ,
236605816 ,
401629989 ,
624624577 ,
207002126 ,
30957453 ,
904125848 ,
972086982 ,
505683288 ,
371832109 ,
451840839 ,
878745917 ,
430395554 ,
147209310 ,
430921068 ,
139123648 ,
401791787 ,
535878343 ,
841915183 ,
74848259 ,
506298598 ,
469129630 ,
863700610 ,
79397490 ,
635505843 ,
130591989 ,
438942754 ,
267490768 ,
69691648 ,
471690321 ,
410635580 ,
308126149 ,
830660661 ,
461972237 ,
896727579 ,
808935514 ,
35976364 ,
954171964 ,
674465926 ,
106752667 ,
197710163 ,
782100549 ,
708853678 ,
772417668 ,
906149358 ,
889444901 ,
751350342 ,
97671943 ,
311309373 ,
588824019 ,
35439701 ,
913836043 ,
498266377 ,
520222570 ,
364584081 ,
728646506 ,
784840994 ,
515589311 ,
444843105 ,
963775228 ,
94134335 ,
217363487 ,
475572809 ,
496260552 ,
762623630 ,
63808862 ,
115817078 ,
875770434 ,
215649929 ,
455175950 ,
40164148 ,
773496910 ,
823931576 ,
386326553 ,
789903764 ,
408176771 ,
150369135 ,
220225716 ,
755890368 ,
740253267 ,
900346430 ,
644456944 ,
455191729 ,
240165678 ,
182137293 ,
263797558 ,
163217383 ,
447920255 ,
858633761 ,
219315337 ,
237599314 ,
2229724 ,
473175469 ,
658809115 ,
698246562 ,
509765398 ,
236562092 ,
955549104 ,
870797088 ,
714964996 ,
765342821 ,
471293570 ,
463962405 ,
451371066 ,
962822196 ,
437633278 ,
268480259 ,
175136775 ,
88058776 ,
314752390 ,
937752299 ,
665731661 ,
194013201 ,
399048534 ,
177793852 ,
220644580 ,
858244099 ,
196791273 ,
135981026 ,
943957027 ,
158440897 ,
170106922 ,
171026547 ,
657177864 ,
281993448 ,
865672277 ,
766122576 ,
862274195 ,
536081222 ,
466441563 ,
830980422 ,
825302509 ,
881487628 ,
831099453 ,
419386581 ,
29026258 ,
797760778 ,
798779111 ,
529163236 ,
393563603 ,
768191632 ,
484015010 ,
652723489 ,
845418721 ,
508101421 ,
97060452 ,
28585816 ,
631666856 ,
262426399 ,
966951225 ,
832594061 ,
390212644 ,
78288289 ,
81123627 ,
836645268 ,
704200536 ,
459225422 ,
211568180 ,
419740294 ,
933980151 ,
634796072 ,
946607770 ,
735175410 ,
664913717 ,
288456995 ,
905204867 ,
633036556 ,
329963957 ,
451134177 ,
535688281 ,
808970440 ,
322835045 ,
689466886 ,
556451599 ,
521374559 ,
954346824 ,
427971656 ,
11145049 ,
829149306 ,
622558523 ,
238352069 ,
902751757 ,
434255614 ,
552351345 ,
657058377 ,
407623705 ,
357679118 ,
699911940 ,
83192055 ,
4582461 ,
454465220 ,
879582280 ,
746651184 ,
313989824 ,
338433341 ,
410705545 ,
765202871 ,
126467224 ,
660839922 ,
342112470 ,
903601517 ,
630088437 ,
370948936 ,
225591056 ,
99652342 ,
857363335 ,
391329565 ,
488570275 ,
97426319 ,
567326769 ,
177761782 ,
614397702 ,
898695657 ,
817454036 ,
816656442 ,
500449466 ,
778387039 ,
652843855 ,
641622699 ,
775952326 ,
221821442 ,
684483611 ,
491400588 ,
804993651 ,
121919862 ,
510621672 ,
525235004 ,
301374538 ,
298644367 ,
240801312 ,
774040124 ,
388849054 ,
91243053 ,
657194819 ,
444829676 ,
125460616 ,
150403917 ,
136577152 ,
901145309 ,
996138220 ,
626741929 ,
32981986 ,
400932945 ,
461187290 ,
347207670 ,
481936504 ,
52326122 ,
934946352 ,
570386447 ,
127593297 ,
69278677 ,
570071461 ,
729107402 ,
873599126 ,
345898274 ,
483671011 ,
465343172 ,
922555136 ,
516896776 ,
414490831 ,
924571150 ,
394185911 ,
274740726 ,
412913651 ,
84093283 ,
217223006 ,
360210148 ,
269328755 ,
394672513 ,
901020293 ,
566471615 ,
718502872 ,
251564137 ,
928711921 ,
145698427 ,
479032127 ,
874976095 ,
26977960 ,
586964353 ,
1559708 ,
870494824 ,
197070777 ,
90568169 ,
786732592 ,
356088321 ,
213445545 ,
545854372 ,
504526427 ,
841962504 ,
386480582 ,
885844439 ,
764780337 ,
128458182 ,
47044441 ,
330959333 ,
36160941 ,
108148636 ,
50556046 ,
394361429 ,
443409440 ,
625737641 ,
514785689 ,
189937756 ,
586949099 ,
428197867 ,
331169894 ,
789648414 ,
362135606 ,
332849973 ,
869895785 ,
38647341 ,
179027658 ,
140713539 ,
240322452 ,
390895016 ,
643331282 ,
416449482 ,
616624768 ,
30161542 ,
75536091 ,
724890179 ,
560130724 ,
891343551 ,
44455542 ,
66776123 ,
563195075 ,
631237469 ,
212305143 ,
511339785 ,
189607911 ,
588500131 ,
736983942 ,
808297535 ,
150064232 ,
545139450 ,
141869885 ,
609122258 ,
917759007 ,
349427944 ,
870208137 ,
702951930 ,
830821814 ,
718854797 ,
597970400 ,
316466389 ,
532499711 ,
811586206 ,
100228149 ,
31133045 ,
323600885 ,
181195071 ,
220344960 ,
916520400 ,
62092293 ,
621528430 ,
337018189 ,
728701834 ,
274600792 ,
450098737 ,
544827938 ,
512041529 ,
768057909 ,
310930715 ,
816242049 ,
584302676 ,
882595137 ,
366108342 ,
615609220 ,
672870843 ,
409624240 ,
715905613 ,
656415317 ,
544302753 ,
872887894 ,
601933722 ,
75110969 ,
944943037 ,
929034136 ,
754506028 ,
719016691 ,
504287232 ,
354659064 ,
607690717 ,
631854863 ,
980656472 ,
743247653 ,
51345576 ,
97248015 ,
658603593 ,
485915836 ,
858415528 ,
765069802 ,
100580183 ,
41293703 ,
544068582 ,
991695145 ,
430798036 ,
94243843 ,
718779338 ,
901210833 ,
6279663 ,
607574126 ,
409236164 ,
41661092 ,
351508494 ,
334816412 ,
437878636 ,
216727366 ,
516074959 ,
117182204 ,
516835815 ,
566795249 ,
339580406 ,
842932217 ,
6938534 ,
790219724 ,
396744039 ,
264237449 ,
255789035 ,
162134539 ,
689062059 ,
956233967 ,
665157772 ,
123899508 ,
880400852 ,
662031489 ,
792900015 ,
935926005 ,
600871287 ,
536730587 ,
269457934 ,
355712720 ,
911770019 ,
121510405 ,
447536943 ,
314033271 ,
279642369 ,
726634586 ,
467491559 ,
383938693 ,
845868175 ,
203890161 ,
760517448 ,
661005450 ,
162533613 ,
463630584 ,
449350427 ,
663563984 ,
881344323 ,
575962848 ,
557341329 ,
406814927 ,
180704352 ,
560448963 ,
827290213 ,
873535831 ,
387569994 ,
940149534 ,
419879420 ,
359672969 ,
718705202 ,
285397093 ,
74366368 ,
205272664 ,
639947878 ,
113830818 ,
876324274 ,
204441254 ,
981202694 ,
316126947 ,
857302577 ,
768314904 ,
360267640 ,
577436966 ,
972156435 ,
267019155 ,
917888714 ,
956266080 ,
46271477 ,
190217281 ,
782828758 ,
114958526 ,
954452342 ,
462610825 ,
297638496 ,
370977121 ,
409608048 ,
208595611 ,
573460344 ,
866288104 ,
874931037 ,
714366183 ,
94764989 ,
894558350 ,
664744450 ,
600288526 ,
532720710 ,
828887975 ,
66239171 ,
625111511 ,
490224973 ,
496994566 ,
114711703 ,
18694494 ,
216776299 ,
884771286 ,
906182646 ,
734405960 ,
369341820 ,
800627276 ,
298793733 ,
738514641 ,
30129693 ,
515052918 ,
675003233 ,
326396278 ,
456302906 ,
276923884 ,
705800430 ,
737053670 ,
780326747 ,
882126448 ,
176183132 ,
555394626 ,
156722503 ,
535906441 ,
802285065 ,
283419910 ,
151725583 ,
253959530 ,
427066528 ,
549665861 ,
986121848 ,
665956796 ,
319002632 ,
937614499 ,
313301866 ,
136475258 ,
297625656 ,
545722115 ,
84365042 ,
984554017 ,
719471437 ,
153810303 ,
91360030 ,
872074786 ,
211205785 ,
216379371 ,
364979145 ,
136330388 ,
674087069 ,
685712639 ,
244761027 ,
472166209 ,
932359055 ,
18011095 ,
486104513 ,
101171614 ,
828919338 ,
361339214 ,
909399008 ,
928753471 ,
561274350 ,
851153773 ,
268482522 ,
51528897 ,
358212146 ,
499377072 ,
168292979 ,
598553907 ,
193396365 ,
414338861 ,
504600993 ,
627686739 ,
913588343 ,
640512312 ,
385528058 ,
777297048 ,
739562637 ,
393735005 ,
46110289 ,
258730867 ,
168051372 ,
813069125 ,
237828932 ,
92578502 ,
946313122 ,
975338506 ,
859159232 ,
118094908 ,
223509158 ,
78363315 ,
677199600 ,
671360871 ,
559648123 ,
98971669 ,
308103899 ,
692815461 ,
644833982 ,
410264590 ,
440164190 ,
20641372 ,
816259787 ,
535979692 ,
32563454 ,
679819830 ,
914397066 ,
962658484 ,
711509317 ,
862412590 ,
94096110 ,
782140980 ,
344218357 ,
302044541 ,
45373421 ,
637521435 ,
648008419 ,
582936917 ,
695028940 ,
35990066 ,
335798714 ,
139589808 ,
207402100 ,
893970719 ,
880755473 ,
130180059 ,
140085191 ,
972787992 ,
727120812 ,
43429650 ,
257849559 ,
629064974 ,
96352902 ,
403373480 ,
194577429 ,
304507265 ,
762764069 ,
344882151 ,
454570588 ,
982738971 ,
67621870 ,
386317431 ,
122607639 ,
566497857 ,
366336731 ,
732961729 ,
313294463 ,
693927998 ,
300045345 ,
46877128 ,
46400169 ,
638655285 ,
279287986 ,
866842295 ,
500730254 ,
568974366 ,
323008531 ,
622728274 ,
565537186 ,
482594674 ,
689453705 ,
126786276 ,
902081967 ,
328425455 ,
913829073 ,
769793743 ,
423614205 ,
294026871 ,
192523176 ,
632203277 ,
860164053 ,
115638466 ,
970997027 ,
708144528 ,
860417304 ,
717530056 ,
804395564 ,
529600657 ,
616140323 ,
956448919 ,
44697388 ,
626019686 ,
437610005 ,
384642313 ,
222404010 ,
699839624 ,
769524322 ,
145610965 ,
909136286 ,
963923766 ,
189620689 ,
897088559 ,
22184613 ,
489468181 ,
234112597 ,
296693560 ,
456269746 ,
138882168 ,
675425005 ,
189425064 ,
57345041 ,
879874364 ,
584796494 ,
658135623 ,
330388084 ,
166147017 ,
868988663 ,
793578168 ,
433741201 ,
247992978 ,
192369023 ,
53241795 ,
592002176 ,
822229131 ,
949602488 ,
372476707 ,
702620635 ,
512318413 ,
95341929 ,
545026393 ,
887836192 ,
219698210 ,
346637529 ,
529735219 ,
618248806 ,
44716559 ,
581556042 ,
662654199 ,
7432524 ,
520586859 ,
441440981 ,
249596751 ,
45874893 ,
516087764 ,
435986629 ,
525348048 ,
22040837 ,
842464691 ,
639036449 ,
275878300 ,
777116565 ,
345640652 ,
663595205 ,
524755411 ,
389221685 ,
923975288 ,
195971721 ,
525078168 ,
121162284 ,
172075775 ,
395434579 ,
479314844 ,
427947331 ,
750193013 ,
635232754 ,
122680958 ,
224279429 ,
822431707 ,
715874433 ,
712498092 ,
428088784 ,
480171739 ,
592478217 ,
192709643 ,
102093487 ,
25655925 ,
71354708 ,
840822494 ,
108507187 ,
66922248 ,
297081887 ,
379562863 ,
431640962 ,
148780868 ,
320276757 ,
14788421 ,
260194517 ,
653287893 ,
189506463 ,
945392806 ,
836108001 ,
244818018 ,
340575928 ,
414379548 ,
15088579 ,
596942825 ,
417148328 ,
381500072 ,
668082433 ,
282993340 ,
943709524 ,
326509076 ,
791826369 ,
502022017 ,
205219068 ,
314335536 ,
632650622 ,
770785923 ,
876211935 ,
768749190 ,
943658959 ,
491042512 ,
911813070 ,
901486038 ,
78442904 ,
148769344 ,
325283809 ,
307155700 ,
177960206 ,
652411236 ,
914086990 ,
675387719 ,
174942266 ,
359591686 ,
527991652 ,
47101881 ,
586273838 ,
194383595 ,
185953230 ,
311964351 ,
785819295 ,
839714141 ,
48875979 ,
724949157 ,
565764177 ,
703119265 ,
630086582 ,
835798506 ,
193867935 ,
970439366 ,
58578167 ,
780166490 ,
942308769 ,
980476376 ,
101311819 ,
714489570 ,
500324768 ,
809781733 ,
746685885 ,
748129317 ,
345983955 ,
70747338 ,
631807546 ,
526354965 ,
587041677 ,
824736731 ,
592544236 ,
158776765 ,
819856686 ,
236608610 ,
966775931 ,
474061551 ,
338456016 ,
930032839 ,
436247059 ,
706988820 ,
649343509 ,
383148354 ,
393460830 ,
589288567 ,
266427785 ,
193016521 ,
577173410 ,
662139508 ,
321178537 ,
923206021 ,
486003317 ,
740782529 ,
929807292 ,
463966530 ,
912889721 ,
641677254 ,
54563572 ,
349430474 ,
74555972 ,
815151500 ,
437825180 ,
22029886 ,
511378917 ,
388993968 ,
878826622 ,
869936148 ,
134373634 ,
219025224 ,
665914848 ,
6238570 ,
994619158 ,
864158445 ,
605654946 ,
234016900 ,
296627419 ,
232971784 ,
713856667 ,
150164413 ,
506136191 ,
569222992 ,
297768856 ,
852885215 ,
432576458 ,
256349517 ,
218986058 ,
206083741 ,
14046348 ,
178107233 ,
126066504 ,
3487225 ,
565333527 ,
808680993 ,
630417318 ,
788631886 ,
18684362 ,
681008435 ,
684227460 ,
19297414 ,
523174333 ,
300936163 ,
163848454 ,
711313279 ,
284472837 ,
513033055 ,
154246033 ,
464567025 ,
325027629 ,
401298932 ,
75387265 ,
356714801 ,
514911025 ,
63807742 ,
812250038 ,
351063020 ,
198529440 ,
133595725 ,
510947415 ,
476864271 ,
318147338 ,
380206104 ,
259025797 ,
191788518 ,
129248370 ,
282536562 ,
586002868 ,
701821155 ,
304724368 ,
805152423 ,
122814207 ,
173203288 ,
652049943 ,
84688278 ,
615589924 ,
874166919 ,
1521790 ,
171477965 ,
590154597 ,
133321349 ,
303348101 ,
541725244 ,
918330165 ,
326364410 ,
862314036 ,
58645636 ,
85565215 ,
677103593 ,
8495861 ,
198437272 ,
173717138 ,
358290416 ,
942607525 ,
291109102 ,
277596339 ,
851818386 ,
571752224 ,
235730885 ,
73983346 ,
66207727 ,
573062782 ,
180944888 ,
649573101 ,
843326135 ,
206882364 ,
142599216 ,
54134739 ,
6189068 ,
145321075 ,
563799638 ,
15136116 ,
954117169 ,
234917248 ,
852075805 ,
88467965 ,
5204263 ,
149822964 ,
661407760 ,
832235842 ,
748624089 ,
984568296 ,
636559261 ,
882886712 ,
332110586 ,
855794403 ,
113477948 ,
330584578 ,
280546504 ,
559421287 ,
313996919 ,
650709465 ,
557529671 ,
317284529 ,
772182105 ,
441666784 ,
30250053 ,
336151501 ,
42036790 ,
813990073 ,
945465060 ,
113531018 ,
730995857 ,
990734747 ,
462056405 ,
826564589 ,
473787016 ,
761159125 ,
512727020 ,
515193742 ,
224582535 ,
448838768 ,
273202563 ,
990137448 ,
637819846 ,
87830318 ,
270000097 ,
713042257 ,
47609409 ,
620448874 ,
404731181 ,
404589287 ,
799961277 ,
642468792 ,
658071166 ,
685746569 ,
478209600 ,
570498859 ,
879276380 ,
968939164 ,
134778219 ,
140001214 ,
700195245 ,
74222694 ,
661494842 ,
403546374 ,
889154841 ,
35818204 ,
877254517 ,
860541553 ,
952463495 ,
796080576 ,
336192161 ,
15486778 ,
361032685 ,
699522915 ,
101027155 ,
584056535 ,
786523502 ,
591596146 ,
367213294 ,
126199525 ,
662165722 ,
701978075 ,
959605874 ,
840061280 ,
885417912 ,
502606268 ,
563728178 ,
110177608 ,
74365443 ,
750677904 ,
240435517 ,
459150171 ,
772610425 ,
531514073 ,
601554008 ,
517670600 ,
186004761 ,
799385750 ,
547303792 ,
614997878 ,
691170900 ,
190014244 ,
119003428 ,
715561026 ,
267983660 ,
718159169 ,
524664643 ,
787795834 ,
48062595 ,
475038608 ,
696379347 ,
313048411 ,
185863363 ,
34529876 ,
761853938 ,
217252471 ,
938861457 ,
572434474 ,
558792798 ,
867735267 ,
781805547 ,
875818854 ,
140312086 ,
289505768 ,
73507645 ,
764828089 ,
32963816 ,
66784132 ,
699086618 ,
852044084 ,
393529856 ,
57388758 ,
930060555 ,
760720643 ,
260088817 ,
638994765 ,
503048028 ,
269182970 ,
280263756 ,
276177825 ,
663071936 ,
919376416 ,
106922166 ,
250424811 ,
508371568 ,
705773316 ,
857435568 ,
380911562 ,
435906365 ,
847406059 ,
994446495 ,
448594687 ,
731579487 ,
961917801 ,
324848789 ,
260934308 ,
73244590 ,
388788933 ,
750853152 ,
928544276 ,
722748357 ,
716159842 ,
57559659 ,
443271379 ,
147700143 ,
151350186 ,
355373454 ,
834590299 ,
642380507 ,
735221242 ,
407052534 ,
285397452 ,
221745842 ,
286385431 ,
836674748 ,
456851864 ,
627742648 ,
324561251 ,
818296957 ,
413343155 ,
717079755 ,
709610338 ,
206519238 ,
25743681 ,
824516955 ,
355157036 ,
424624924 ,
118613667 ,
160335569 ,
904922835 ,
174795954 ,
543512236 ,
928830791 ,
813888671 ,
701992779 ,
665060993 ,
152545431 ,
85782985 ,
17333297 ,
65381899 ,
729184567 ,
199351520 ,
73401833 ,
295816927 ,
482866381 ,
809956952 ,
887673269 ,
266175130 ,
56266040 ,
328263324 ,
426908436 ,
173149597 ,
421758578 ,
137683935 ,
457081673 ,
313920963 ,
729940099 ,
775561729 ,
142959500 ,
131340902 ,
168862476 ,
887277364 ,
645997879 ,
860125203 ,
134084398 ,
214254571 ,
685187512 ,
544213561 ,
639310834 ,
32656974 ,
716610196 ,
262511836 ,
271632647 ,
162721287 ,
260034849 ,
351419270 ,
26623892 ,
571524107 ,
841751645 ,
878936531 ,
38095141 ,
16455959 ,
675620114 ,
182430520 ,
535280080 ,
927633129 ,
619978977 ,
590581472 ,
575186915 ,
308873396 ,
855410730 ,
317666643 ,
814913368 ,
461640564 ,
187977754 ,
948567959 ,
508597453 ,
5255850 ,
965436151 ,
416029891 ,
402138477 ,
716573127 ,
685912381 ,
56471381 ,
173913790 ,
688734881 ,
244624926 ,
952084784 ,
702086521 ,
1645671 ,
138953557 ,
272607559 ,
709974560 ,
508896367 ,
526083145 ,
285740326 ,
508811799 ,
289744226 ,
997818772 ,
5102940 ,
939970152 ,
947229248 ,
420570856 ,
122061806 ,
959170271 ,
289825815 ,
358874419 ,
918594025 ,
254106139 ,
76967389 ,
43752475 ,
543902753 ,
157253582 ,
387338709 ,
657435622 ,
231374821 ,
747100577 ,
347608261 ,
592011741 ,
529678652 ,
288310344 ,
689886912 ,
463767408 ,
177238234 ,
590186979 ,
142329142 ,
974883194 ,
683747877 ,
875044932 ,
442775276 ,
3511830 ,
813221895 ,
53575925 ,
505546724 ,
624979859 ,
574048968 ,
747157637 ,
729147166 ,
952741368 ,
620768453 ,
210807913 ,
268425256 ,
556830656 ,
760317141 ,
14783988 ,
204794360 ,
526327257 ,
66695189 ,
90918196 ,
708837005 ,
254839595 ,
646064618 ,
391646633 ,
538814099 ,
732818422 ,
359185015 ,
609894494 ,
60614711 ,
584875983 ,
636364843 ,
11731777 ,
392510691 ,
444803544 ,
117427394 ,
500590073 ,
596645590 ,
212439913 ,
136794389 ,
616584583 ,
203871029 ,
772277876 ,
995234490 ,
932143354 ,
863104046 ,
719455449 ,
796039332 ,
171787016 ,
121612427 ,
462794901 ,
777216776 ,
334188291 ,
904160150 ,
921874788 ,
450718498 ,
342226352 ,
959755721 ,
960493260 ,
407112336 ,
854215617 ,
453569713 ,
463651969 ,
787456035 ,
772726971 ,
839845966 ,
558055195 ,
810169582 ,
106339091 ,
597454740 ,
10778396 ,
182773266 ,
578839159 ,
894765683 ,
775480512 ,
859136982 ,
179549398 ,
160098077 ,
62128987 ,
217102995 ,
598785675 ,
951048332 ,
733614217 ,
424819039 ,
237404454 ,
770556425 ,
501450677 ,
873647662 ,
189177819 ,
554175621 ,
370626248 ,
651726864 ,
573081446 ,
909008397 ,
63038911 ,
218298116 ,
59230778 ,
53315061 ,
73370891 ,
614035897 ,
868817194 ,
991627998 ,
697204780 ,
440045073 ,
967209064 ,
712507201 ,
427336905 ,
483068167 ,
538946759 ,
482325054 ,
318273749 ,
150047783 ,
181651416 ,
930991663 ,
218683827 ,
350455207 ,
41471086 ,
304234648 ,
211508168 ,
142446578 ,
485859105 ,
716082409 ,
218605449 ,
550937368 ,
645719626 ,
224887177 ,
704262100 ,
211773258 ,
909683215 ,
942570603 ,
793534722 ,
663803200 ,
740101551 ,
492727631 ,
18139551 ,
790735012 ,
794477254 ,
826026322 ,
613122958 ,
481677870 ,
487702216 ,
614816428 ,
254992227 ,
193592624 ,
373813108 ,
810953537 ,
914243147 ,
697934953 ,
849336804 ,
53984079 ,
11498219 ,
460939778 ,
930826420 ,
484656516 ,
343546316 ,
830939137 ,
277447928 ,
559397059 ,
12938375 ,
889973871 ,
868038464 ,
766912779 ,
432013588 ,
293846612 ,
542707108 ,
947863406 ,
894449310 ,
512796064 ,
913734040 ,
461042330 ,
884160388 ,
720631929 ,
207706561 ,
700113830 ,
45711462 ,
441247066 ,
680607908 ,
319983632 ,
18371608 ,
263674548 ,
802144502 ,
291791953 ,
19416844 ,
525493623 ,
984586909 ,
683813057 ,
719279590 ,
901409573 ,
140374923 ,
586512686 ,
680123483 ,
962935909 ,
859710923 ,
797639714 ,
692390522 ,
6176686 ,
530017476 ,
870607037 ,
146310274 ,
434989004 ,
64631542 ,
393989816 ,
417288305 ,
190155901 ,
973278981 ,
320699930 ,
723546452 ,
722184628 ,
993054754 ,
371337710 ,
24517899 ,
635822831 ,
780820303 ,
908495616 ,
194604448 ,
202414613 ,
511425473 ,
920939652 ,
926795115 ,
579467130 ,
756689403 ,
774452811 ,
475897673 ,
332014073 ,
516931492 ,
422367604 ,
474607993 ,
546099270 ,
618286293 ,
536087526 ,
691178280 ,
358717235 ,
86852624 ,
281597428 ,
74785830 ,
101759639 ,
538905638 ,
2936575 ,
631696729 ,
56156755 ,
77440857 ,
128994831 ,
236472803 ,
484819576 ,
34083393 ,
23930777 ,
267145265 ,
366694484 ,
132190138 ,
690449938 ,
588431527 ,
575231640 ,
933480728 ,
219282449 ,
522014522 ,
198630191 ,
415316758 ,
352448584 ,
816255684 ,
945198654 ,
109909679 ,
831614524 ,
784897492 ,
979132763
};
RETURN( answer[N] );
}