1 315570551
2 782252257
3 773753161
4 123884603
5 447839221
6 213398077
7 122895607
8 581820269
9 552348757
10 146799281
11 751532081
12 913558771
13 258833999
14 987122813
15 263792951
16 295182227
17 784294843
18 135287693
19 876938669
20 938669857
21 996014807
22 971293369
23 362559719
24 586619147
25 769326461
26 646102351
27 116312389
28 238999001
29 340676449
30 316211719
31 829345199
32 418486319
33 134625041
34 825427157
35 455062877
36 800131109
37 650138483
38 501384833
39 384833453
40 271193729
41 598707331
42 310977059
43 762630857
44 382787227
45 674505649
46 498738587
47 389439671
48 600667829
49 597160933
50 971609339
51 958333531
52 531282737
53 527676157
54 615716807
55 716807321
56 447755069
57 696614543
58 614543737
59 379855757
60 921419903
61 894917809
62 455183273
63 341979349
64 720061079
65 892843001
66 567941071
67 970654369
68 102212059
69 117173723
70 762078857
71 792086369
72 920863693
73 934994119
74 411953743
75 433668031
76 658792549
77 249819431
78 591190807
79 946871881
80 342471079
81 710795731
82 428404687
83 105038911
84 580712207
85 697073687
86 695426891
87 689191771
88 147218233
89 868007711
90 404274461
91 821724437
92 888042269
93 157379891
94 379891739
95 672437837
96 978149113
97 202174733
98 267641441
99 207010093
100 939381007
101 563788307
102 343607333
103 395490241
104 332872219
105 473924509
106 239835301
107 353017129
108 792813067
109 355819559
110 194069903
111 699033017
112 606869479
113 303085961
114 547126927
115 692751601
116 921660479
117 404708309
118 673853051
119 578600203
120 103703947
121 226690333
122 838802267
123 413580863
124 580863233
125 421695809
126 809648659
127 787859647
128 945274277
129 277326991
130 308728529
131 529081711
132 772319159
133 660855749
134 755170309
135 663209047
136 560809063
137 701490481
138 275794921
139 949211147
140 911389937
141 361206551
142 932640323
143 253493641
144 239849989
145 956589199
146 349867487
147 338344871
148 711943399
149 816566483
150 316868549
151 133080121
152 455630129
153 113955173
154 563031059
155 161965289
156 764404559
157 440455919
158 190653901
159 539014423
160 157047391
161 456181021
162 978146951
163 669351161
164 856373389
165 625461097
166 307483763
167 835262359
168 259953997
169 306037513
170 751314323
171 323774441
172 607723283
173 723283741
174 837414223
175 852028337
176 202833779
177 779002837
178 937940221
179 794022157
180 947689751
181 476897513
182 321902101
183 590951429
184 514290113
185 424803251
186 517959947
187 473126617
188 707022709
189 387235109
190 949564309
191 733756853
192 656205311
193 852782803
194 371353811
195 811939853
196 248536669
197 366697063
198 970630897
199 706308973
200 221317741
201 350024159
202 441637967
203 675718243
204 243111721
205 216703027
206 332343181
207 936372089
208 363720893
209 861238019
210 312490369
211 750759791
212 400058119
213 370743383
214 700348279
215 279471937
216 658653043
217 865304353
218 386337607
219 553460113
220 305212931
221 411629761
222 525994571
223 716326307
224 732193811
225 466666367
226 235977961
227 302238553
228 875446889
229 261789721
230 201303419
231 493009597
232 597456553
233 854445871
234 360594589
235 493513747
236 473284457
237 281144393
238 526804519
239 212077897
240 993888479
241 986165723
242 150464767
243 504647677
244 647677201
245 731494781
246 232024459
247 682081303
248 302458063
249 806394923
250 459961577
251 720344123
252 481554287
253 926581619
254 955130503
255 400834223
256 432802613
257 725962843
258 975813613
259 136130837
260 769731761
261 973176121
262 942509063
263 120860521
264 208605217
265 907433951
266 943531079
267 801039761
268 947439457
269 105256339
270 336075661
271 661593523
272 709708057
273 323527427
274 742720799
275 720799367
276 592873711
277 986135261
278 352614121
279 141210803
280 252772747
281 478774579
282 787745797
283 579773203
284 781573679
285 266417989
286 537783881
287 111710479
288 905274911
289 274911541
290 491154119
291 154904257
292 726311801
293 222005213
294 147472109
295 218925359
296 658871729
297 258307681
298 420999233
299 844845601
300 208701509
301 299930237
302 807923849
303 105511277
304 127711219
305 674311747
306 117479627
307 544126897
308 469495231
309 432780193
310 260422087
311 648956047
312 560478883
313 478883473
314 783985327
315 230428769
316 288338423
317 299945147
318 278950351
319 124176601
320 458906311
321 453869653
322 230705851
323 246880099
324 490633933
325 720177559
326 177559777
327 728405861
328 925975439
329 632385931
330 600101767
331 723947033
332 239470333
333 820598777
334 674572891
335 829078031
336 268650563
337 199855259
338 808051987
339 987261659
340 882049723
341 331527541
342 145284283
343 242521819
344 585243601
345 608630833
346 338965223
347 857308297
348 768624929
349 160677211
350 513776089
351 197844461
352 217244189
353 441899027
354 189902729
355 316391561
356 299283469
357 630556373
358 771096031
359 920007457
360 576718453
361 967461907
362 835355041
363 230879969
364 173765489
365 802127587
366 427878889
367 244052843
368 491888801
369 342743053
370 430532243
371 228037427
372 624184973
373 387098171
374 981716759
375 195282203
376 193748771
377 863009387
378 339553517
379 814464769
380 464769007
381 601445263
382 422581633
383 378195953
384 496053797
385 449274913
386 183953069
387 530692367
388 692367719
389 670627703
390 829302371
391 200201213
392 229457341
393 386615077
394 488194153
395 488367259
396 836725961
397 151150249
398 186366353
399 395544629
400 850242853
401 242853001
402 300133219
403 760045397
404 272156107
405 107875219
406 403671421
407 854646043
408 942834803
409 636197251
410 394882399
411 399631241
412 412256297
413 629766253
414 943668511
415 807281603
416 346418263
417 731063909
418 826761259
419 703468873
420 610599053
421 990532937
422 265320533
423 519613327
424 897446521
425 650543237
426 175595249
427 752856457
428 493051513
429 151320251
430 655230593
431 812393069
432 418050197
433 561257167
434 186570047
435 440609381
436 767300993
437 752255807
438 112276223
439 379889773
440 743896091
441 361709437
442 418446103
443 900264041
444 640418357
445 404183579
446 835790869
447 692456381
448 498712213
449 812748317
450 127483177
451 177637987
452 246950219
453 725959477
454 119629057
455 198120361
456 796813027
457 479002313
458 698959117
459 988018219
460 842748331
461 814510133
462 470141993
463 681529049
464 499544651
465 954465131
466 308360527
467 527917087
468 590746813
469 681339881
470 354439619
471 593497981
472 217712401
473 124014629
474 874163753
475 691594103
476 660550327
477 242238179
478 432924157
479 172729177
480 774488783
481 239164463
482 392664971
483 266497129
484 294046933
485 653754809
486 375480901
487 809016851
488 901685167
489 751289629
490 518225957
491 311094643
492 394636019
493 194184821
494 881143427
495 384722609
496 423873349
497 240554243
498 243843557
499 854748203
500 241847273
501 116600447
502 166004471
503 108638533
504 685499237
505 502716391
506 536412329
507 487629221
508 726294011
509 294011503
510 162056509
511 794935949
512 493594921
513 640577797
514 549647627
515 866643317
516 664331791
517 761639689
518 470283799
519 283799773
520 445394539
521 312551257
522 576881639
523 472524461
524 920953081
525 209530819
526 110205629
527 629523691
528 497532877
529 141564827
530 156482723
531 427399613
532 996134917
533 299195213
534 775353487
535 424767869
536 515508233
537 507332201
538 885972427
539 242732597
540 353578861
541 867641969
542 778733509
543 332946491
544 836962213
545 317729593
546 798383099
547 309929173
548 904572287
549 287493587
550 749358773
551 587733077
552 574955593
553 295168663
554 146200819
555 926186249
556 747326621
557 622286209
558 761967607
559 684189271
560 790456517
561 456517559
562 664805783
563 879360623
564 637615763
565 650822869
566 405262747
567 749292631
568 292631981
569 142136009
570 426072551
571 515671757
572 156717571
573 630820013
574 611040853
575 252970651
576 970651139
577 655138609
578 970095853
579 472158143
580 344444621
581 444446213
582 604091623
583 162348773
584 853470403
585 512205737
586 275484697
587 846978361
588 978361157
589 314447561
590 460506509
591 688867603
592 867603119
593 311906069
594 307287581
595 620822317
596 973488479
597 488110541
598 861623489
599 292951489
600 351370991
601 268452589
602 823591721
603 118424707
604 565349999
605 349999813
606 143918861
607 335235827
608 230964913
609 913130171
610 178779143
611 320189839
612 334516219
613 219969229
614 298439587
615 806400313
616 117806629
617 267540149
618 631822117
619 472668233
620 682334299
621 334299463
622 892288361
623 964744111
624 646750849
625 467508493
626 849305507
627 182653561
628 826535617
629 439319449
630 344877461
631 290403541
632 403541863
633 163986203
634 862034869
635 992525981
636 118598131
637 256880653
638 880653569
639 535699391
640 250386781
641 812631097
642 459339427
643 225587851
644 540919697
645 663615397
646 615397997
647 971122751
648 428878897
649 333498119
650 861395789
651 139578941
652 626275691
653 579420923
654 963858683
655 586830071
656 540298147
657 297067937
658 499488001
659 403911199
660 429762583
661 762583873
662 732215083
663 322150837
664 126935593
665 210785437
666 588024259
667 285350713
668 130394357
669 303943571
670 495890209
671 958902097
672 727522793
673 589880311
674 213403403
675 340340353
676 848960353
677 903936361
678 377752561
679 525616001
680 154604959
681 264331729
682 483972631
683 149203091
684 912688897
685 756840559
686 624965171
687 171718711
688 884292719
689 429271939
690 212108887
691 669225881
692 922588103
693 588103603
694 103603043
695 437191757
696 185478037
697 603435011
698 689310059
699 597926603
700 681968629
701 629286157
702 275386403
703 629896853
704 896853791
705 835583443
706 151552997
707 552997453
708 982818509
709 411929267
710 109859669
711 114364043
712 690480389
713 803898713
714 389871343
715 242504929
716 691597807
717 266866877
718 534987067
719 663592673
720 378780683
721 780683327
722 288342433
723 584677673
724 554227957
725 214490299
726 749299091
727 684043277
728 592651349
729 317243141
730 855966997
731 394730033
732 524240573
733 142189447
734 421894471
735 214498769
736 757659193
737 742770467
738 625469069
739 576095893
740 394967401
741 166505057
742 781048337
743 810483371
744 923182837
745 778396309
746 968560493
747 575845279
748 452798321
749 214047563
750 308314493
751 209761309
752 301012609
753 425949859
754 463101283
755 310128307
756 242991787
757 553814399
758 930339559
759 639021059
760 390210599
761 109606829
762 524775919
763 775919519
764 669879653
765 653245763
766 116984261
767 840108481
768 830427329
769 222633529
770 769616131
771 613135423
772 354231769
773 349839881
774 384911959
775 849119597
776 107602307
777 222748247
778 668015839
779 583984129
780 129594403
781 871078567
782 875879773
783 286027199
784 271992913
785 900470491
786 915514393
787 520855187
788 551873141
789 514468021
790 320934773
791 477380017
792 499126711
793 175214453
794 160457351
795 348724031
796 487240319
797 872403193
798 725912323
799 408138433
800 138433657
801 589051373
802 793781701
803 418147423
804 453849419
805 799645193
806 312648121
807 362266979
808 760491341
809 591277081
810 888975533
811 181166933
812 792089503
813 608547077
814 303878749
815 896648041
816 555831557
817 711770729
818 574465763
819 633481501
820 282462937
821 293718479
822 412167257
823 250938607
824 404869693
825 327269171
826 326566909
827 901985663
828 299459089
829 617438593
830 961660363
831 355516793
832 938892737
833 737387213
834 356502161
835 104072791
836 324321923
837 938866303
838 106051741
839 208704347
840 347228377
841 301171841
842 450317591
843 591177773
844 777731033
845 731033437
846 855292181
847 193665539
848 920022007
849 220076921
850 572013721
851 279255947
852 475231877
853 752318779
854 486338857
855 417278819
856 509850631
857 799393019
858 968948213
859 718263743
860 826374323
861 743235457
862 883558579
863 689339887
864 605473021
865 255845309
866 449596039
867 748730161
868 719504677
869 841005679
870 990924197
871 425491331
872 746500543
873 766501093
874 633935881
875 986068637
876 280540423
877 805404239
878 423964633
879 689407813
880 407813083
881 691725917
882 458094253
883 942530657
884 603541733
885 541733807
886 338076703
887 568155083
888 978781667
889 857848493
890 484936093
891 477004679
892 882525929
893 810524063
894 587468359
895 468359663
896 831022769
897 616403467
898 390666751
899 191741729
900 694913579
901 357934853
902 836545531
903 362628017
904 449703043
905 916157401
906 795788417
907 259546741
908 954674153
909 540188581
910 901194523
911 934280731
912 982664909
913 909791843
914 184360229
915 898424389
916 253748119
917 537481199
918 748119973
919 589859329
920 593295421
921 295421233
922 142479521
923 382541363
924 885476089
925 854760899
926 972696211
927 180537913
928 752066459
929 645910781
930 179902531
931 170995663
932 520806071
933 710299519
934 932998193
935 749070523
936 362092727
937 865713833
938 393616303
939 342404017
940 404017063
941 170635631
942 945416867
943 674424563
944 245636701
945 403995307
946 447456721
947 579019843
948 525612553
949 347526167
950 616768727
951 626345459
952 896705857
953 319161841
954 618410953
955 184109537
956 944053549
957 802558909
958 725167349
959 167349953
960 349953319
961 227983871
962 887108357
963 262902011
964 792333673
965 158837573
966 762067459
967 590241013
968 622255273
969 960594307
970 376061443
971 867587947
972 533260549
973 956694667
974 901219421
975 942194983
976 576559957
977 521823119
978 771976811
979 112829027
980 595458091
981 469464467
982 457344941
983 449416391
984 442404247
985 424042471
986 221917291
987 826330573
988 903513719
989 371990789
990 474214297
991 238086007
992 269584069
993 695840693
994 449816111
995 111934981
996 152160913
997 662820793
998 439240273
999 240273403
1000 340321879