1 398874989
2 752126633
3 250171169
4 222104321
5 626296313
6 381497587
7 587012203
8 408058879
9 410443207
10 104432077
11 850987433
12 433944221
13 798731761
14 523689427
15 287856997
16 165339247
17 115881863
18 993432359
19 509040947
20 116456299
21 602017279
22 471753427
23 827505131
24 248093947
25 358057727
26 304592647
27 575605231
28 727775203
29 936210767
30 362107673
31 248235521
32 565734797
33 976639723
34 639723949
35 873039623
36 396230903
37 399385621
38 471780341
39 302315417
40 344170093
41 954409627
42 544096279
43 795589867
44 678723209
45 309704509
46 956844017
47 475926007
48 223188913
49 923007803
50 424936271
51 271359251
52 251876077
53 615023891
54 312231053
55 223105339
56 533923213
57 213624319
58 979864247
59 508615487
60 482647181
61 773224499
62 322449943
63 435308899
64 194320481
65 767586331
66 113978153
67 139781539
68 414914453
69 775486163
70 548616307
71 595044977
72 247856459
73 644361709
74 170933417
75 341727091
76 172709191
77 336501371
78 510055901
79 505078081
80 881990633
81 129827981
82 141174533
83 972792221
84 570832373
85 708323731
86 323731097
87 759151177
88 841611763
89 711163307
90 832587103
91 121101989
92 841491751
93 313401527
94 340152733
95 384383723
96 345009347
97 792945991
98 991582201
99 125810459
100 810459823
101 528721241
102 704361491
103 496118087
104 475604431
105 443178479
106 798584539
107 985845397
108 783257039
109 782308271
110 893902111
111 829659773
112 310343603
113 953679593
114 742631251
115 201231127
116 127955189
117 141589117
118 589117799
119 911779919
120 550656329
121 355234667
122 747593269
123 759326951
124 136301819
125 625547281
126 137824669
127 782466917
128 708157007
129 102101191
130 836067509
131 895774681
132 553396303
133 807291691
134 723657203
135 731250161
136 484818109
137 602442523
138 123710239
139 317406931
140 343564531
141 850581353
142 505813531
143 353108549
144 905836367
145 836367541
146 363675413
147 908624063
148 212524261
149 574405837
150 440583727
151 138247831
152 865650649
153 650649343
154 934341803
155 343418039
156 390041017
157 339505877
158 557552293
159 177298337
160 266786743
161 674357923
162 435792397
163 272027477
164 983536727
165 727761407
166 805220461
167 123248239
168 261043271
169 104327191
170 975753689
171 689041763
172 636502547
173 729886321
174 839590363
175 582764491
176 912459809
177 555961379
178 613483049
179 494968681
180 108953569
181 608420339
182 944194571
183 621053603
184 541993687
185 199368731
186 368731609
187 207788227
188 815325617
189 411769097
190 113718529
191 991921631
192 205928537
193 842987807
194 807706201
195 411719101
196 989038447
197 684416947
198 844169479
199 954530459
200 218704567
201 870456799
202 553520347
203 414994127
204 135567763
205 390710387
206 680335003
207 288166441
208 664415309
209 548241451
210 888251899
211 794215589
212 421558957
213 356674589
214 410703599
215 783204463
216 489497663
217 321243743
218 149005907
219 580437181
220 718151261
221 725244061
222 351068063
223 365166743
224 270376231
225 426183841
226 841359707
227 379771463
228 555975379
229 703552271
230 440128309
231 731538959
232 300736727
233 647961143
234 145613987
235 873026039
236 525432673
237 267385759
238 852993913
239 736228391
240 120181273
241 201812731
242 129165899
243 922031837
244 372356827
245 279385637
246 938563733
247 331265479
248 246327503
249 355318729
250 195535961
251 830314883
252 839117693
253 834109429
254 807541711
255 682987849
256 829878493
257 878493271
258 271299751
259 498357751
260 877178041
261 519016339
262 847390793
263 392943781
264 929437813
265 420726629
266 629001809
267 322872269
268 722698069
269 459945119
270 126125257
271 828066433
272 331261657
273 261657469
274 923641183
275 646851431
276 373190429
277 319042951
278 909518713
279 765996041
280 308585533
281 553323877
282 253802327
283 327276329
284 276329773
285 329773721
286 143547409
287 354740999
288 766112383
289 669404473
290 865837529
291 862362509
292 721725649
293 470005163
294 112153687
295 368730091
296 659131637
297 686072713
298 533043799
299 794340563
300 626888569
301 601169189
302 194012197
303 907223651
304 514771391
305 713912687
306 543288883
307 417429209
308 742920901
309 920901563
310 563133283
311 756220897
312 971376563
313 586542479
314 481453351
315 832336459
316 598369637
317 722575691
318 474742381
319 238151107
320 927349483
321 936983249
322 832491799
323 179029751
324 515875049
325 722772601
326 171740453
327 106195819
328 799516873
329 405542927
330 927345883
331 345883711
332 945720823
333 910153357
334 357910727
335 850295419
336 132004009
337 589394713
338 495647203
339 548701523
340 614031739
341 140317391
342 403173913
343 391390361
344 198455051
345 491211697
346 792001201
347 394100701
348 276323273
349 905542513
350 513797233
351 685981679
352 598167953
353 739424531
354 759834323
355 584314063
356 106261553
357 529750223
358 217783441
359 408982577
360 775447411
361 447411533
362 411533207
363 755380471
364 553804711
365 804711629
366 270549623
367 702740699
368 429216299
369 921629981
370 917508611
371 317209561
372 565647869
373 547448927
374 698374211
375 374211379
376 353330447
377 675862289
378 643468489
379 751484087
380 763365439
381 673898117
382 389811781
383 781050341
384 430036657
385 723617137
386 229255841
387 306730639
388 314601527
389 228613907
390 613907831
391 900381487
392 488278897
393 558886079
394 569419909
395 480298249
396 298249319
397 740783807
398 431877827
399 160879157
400 829297577
401 763442861
402 354442789
403 444278983
404 820212023
405 450336581
406 218549203
407 203679989
408 367998997
409 935353919
410 968121331
411 319516537
412 444518303
413 775960541
414 389959313
415 959313067
416 663118919
417 122410609
418 255478789
419 218853307
420 762305563
421 163164019
422 770477933
423 873879907
424 740304907
425 870615433
426 433072963
427 703812751
428 710426459
429 405569509
430 408889037
431 132797711
432 750901651
433 916073833
434 738339377
435 302457019
436 628464911
437 888575213
438 752134637
439 254180833
440 726789379
441 950537591
442 500301757
443 823060123
444 680101987
445 670259543
446 976529341
447 991552711
448 915527113
449 526677859
450 159890231
451 332102651
452 761904953
453 158296883
454 105654589
455 589130629
456 629827717
457 827717249
458 465110419
459 495628603
460 598674859
461 266074933
462 496519997
463 322601723
464 235710733
465 464759989
466 759989999
467 725277541
468 515947781
469 947781221
470 662736209
471 620916607
472 103929673
473 127389259
474 436424383
475 204086321
476 863214991
477 832242737
478 997965541
479 655413859
480 521030207
481 207686047
482 371971063
483 519778169
484 927510901
485 870525059
486 125505841
487 232071883
488 713618377
489 394655539
490 143387567
491 433875677
492 773034979
493 730349791
494 540104233
495 744274711
496 485126401
497 866073683
498 519164029
499 640292179
500 687726191
501 464786897
502 841384513
503 845131621
504 119297201
505 670728601
506 613028149
507 967734457
508 344579773
509 978570871
510 122831543
511 104569123
512 245217449
513 452174497
514 449739613
515 160514293
516 293848447
517 452382127
518 581361967
519 255636503
520 912306617
521 471431509
522 932419249
523 419249141
524 238592573
525 227227333
526 384362621
527 225055489
528 805730837
529 883194839
530 319483999
531 963405763
532 635284717
533 847175627
534 176190197
535 216595597
536 565249171
537 584030641
538 153550759
539 284662813
540 174505909
541 758046571
542 430823693
543 308236939
544 756119017
545 561190171
546 190171561
547 481331171
548 434445103
549 796852921
550 947323933
551 239335237
552 222343481
553 167574937
554 757493731
555 731446409
556 446409283
557 103558619
558 861936181
559 686489239
560 728949941
561 867891461
562 891461971
563 728155451
564 542499691
565 424996919
566 249969197
567 996919741
568 919741027
569 769462069
570 462069859
571 409212091
572 120913799
573 434645227
574 933029239
575 592268987
576 426058951
577 951056203
578 907202893
579 479960059
580 964048607
581 607619891
582 900803279
583 429924881
584 819864613
585 461361713
586 485773469
587 175403413
588 973846169
589 846169481
590 481293479
591 234609743
592 152656781
593 819764507
594 345234781
595 601409183
596 657272851
597 272851511
598 284311039
599 296250193
600 501936989
601 639880957
602 414477803
603 477803021
604 647286239
605 836350877
606 403225343
607 225343799
608 401555377
609 660367303
610 147158279
611 691240399
612 939085517
613 408912061
614 206108401
615 924685591
616 646883477
617 668673739
618 917118931
619 898996081
620 492068677
621 339041821
622 210877463
623 877463803
624 726995963
625 204748319
626 225472727
627 524440391
628 275729369
629 893029961
630 315238589
631 238589753
632 644876417
633 613552343
634 432698657
635 986572897
636 630691801
637 180174277
638 852057257
639 948516733
640 781329313
641 602893229
642 938904061
643 485084597
644 122543273
645 445880837
646 458808377
647 986850659
648 984085457
649 165416917
650 670521119
651 327524389
652 243899977
653 740427029
654 404270297
655 220363477
656 746055199
657 401107711
658 725644261
659 984336253
660 535847069
661 576261677
662 156268699
663 907999117
664 215031007
665 632404219
666 439926953
667 654967769
668 677690471
669 561375091
670 394177429
671 451666687
672 564878549
673 785493601
674 287733133
675 133883917
676 665998607
677 126748841
678 335548537
679 992240369
680 342731419
681 419415743
682 343820759
683 317664421
684 442190267
685 219026777
686 579945031
687 585536363
688 363372517
689 487268843
690 840965779
691 572782307
692 656445563
693 737982803
694 484465127
695 276264649
696 463674019
697 401955997
698 822335539
699 649783331
700 565124093
701 753752801
702 238706927
703 692730719
704 464945497
705 434374621
706 746215439
707 462154391
708 697436653
709 305885621
710 128373577
711 779434153
712 270987037
713 379769213
714 773627669
715 276699187
716 106452061
717 645206137
718 452061373
719 658221931
720 992291761
721 291761471
722 566217241
723 535857983
724 579837541
725 610041547
726 927671189
727 895277333
728 823356043
729 335604337
730 428351993
731 706491847
732 132569317
733 256931743
734 473432879
735 440896091
736 619767553
737 767553023
738 755302363
739 827708891
740 933077293
741 705984247
742 826379413
743 935208959
744 382371427
745 823714271
746 371427193
747 681544729
748 509206409
749 769257469
750 125995901
751 259959017
752 279478247
753 947824753
754 174814799
755 642466277
756 371528221
757 715282219
758 608506001
759 824516947
760 451694783
761 165827491
762 578264633
763 463340399
764 334039921
765 860013859
766 859653877
767 901449743
768 337623761
769 556468421
770 211226987
771 750624997
772 776009393
773 600939343
774 434355833
775 951651329
776 101860849
777 803380909
778 620547959
779 669883573
780 735604043
781 347128399
782 128399801
783 137687609
784 702128507
785 641753173
786 753173483
787 531734839
788 762771979
789 732857689
790 141780313
791 417803137
792 853917469
793 499025467
794 765966599
795 659665991
796 599164547
797 645473651
798 850652843
799 697485377
800 340788127
801 788127721
802 812772157
803 457423327
804 230364863
805 745531327
806 197652607
807 607107643
808 431531123
809 239152607
810 391526077
811 674331613
812 743316137
813 696621047
814 629047949
815 708371201
816 368180173
817 585816629
818 340934791
819 991036859
820 669577523
821 684581369
822 136914079
823 664234787
824 787466143
825 746614399
826 168674281
827 686742817
828 987891461
829 366293093
830 816174059
831 332408113
832 222141683
833 141683089
834 618696271
835 945385499
836 842751733
837 275173369
838 832014583
839 544847423
840 438780847
841 780850561
842 643459051
843 677275747
844 833496091
845 574474357
846 474357503
847 743575039
848 602016397
849 766611427
850 142765369
851 939148429
852 307037167
853 303480803
854 942341203
855 947825303
856 593730437
857 468675253
858 867525349
859 301302767
860 302767823
861 413111779
862 897315151
863 259375271
864 154798183
865 479818307
866 954564631
867 410671981
868 883233223
869 585068971
870 689710187
871 478190653
872 256575841
873 657584189
874 529144717
875 914471783
876 173226029
877 786292943
878 563669321
879 816245957
880 326988923
881 490988831
882 831468529
883 685299409
884 708424429
885 363023293
886 163300961
887 330096121
888 872083651
889 218017669
890 801766963
891 200532887
892 873494893
893 759421699
894 464124347
895 149157793
896 753348053
897 348053033
898 377287321
899 169921993
900 259760393
901 603937207
902 937207949
903 307738163
904 773816321
905 632162767
906 823154551
907 551171213
908 983186861
909 318686111
910 542705557
911 535264469
912 911577431
913 359565299
914 595652999
915 994635319
916 319487323
917 372140627
918 847758871
919 557582117
920 351435523
921 663933161
922 331618523
923 967991251
924 618008071
925 270606851
926 186496931
927 931519049
928 719216273
929 192162731
930 536314201
931 363142019
932 137017541
933 795152923
934 669561923
935 192313829
936 992370193
937 985317269
938 768627781
939 862778123
940 781233457
941 838050307
942 675028309
943 836562949
944 105357359
945 357359291
946 964616231
947 646162313
948 377078029
949 373375243
950 297676081
951 819735349
952 735349213
953 466408387
954 282860167
955 984522491
956 224918783
957 249187837
958 657019507
959 701950783
960 950783443
961 761705423
962 704765473
963 291393359
964 335961869
965 596186911
966 791867789
967 642657401
968 108940859
969 408594913
970 202158871
971 647405833
972 375040007
973 542799937
974 780598067
975 598067761
976 806776121
977 416259521
978 625952137
979 137023199
980 370845053
981 233906957
982 415269293
983 777251263
984 689347553
985 282342701
986 239800177
987 185956843
988 609274381
989 263033087
990 308720453
991 305726483
992 342759013
993 858476503
994 476503981
995 650398193
996 158031959
997 803195927
998 592708789
999 926161399
1000 507261529