1 643647241
2 738336289
3 879351029
4 633086627
5 276831733
6 214005479
7 968115587
8 155879489
9 327776191
10 564558769
11 145250683
12 276587939
13 929588063
14 320447219
15 782638903
16 515912081
17 487745879
18 894087011
19 710693161
20 693161461
21 448359091
22 183448757
23 446296303
24 986190871
25 380440721
26 721421339
27 365528113
28 113716703
29 670326911
30 269114987
31 306725273
32 794748127
33 359728199
34 560780537
35 607805377
36 288594727
37 278625931
38 216065819
39 497776259
40 382230067
41 230067977
42 665797003
43 375857939
44 857939503
45 949159663
46 215693657
47 876355309
48 355309477
49 500525803
50 315412739
51 274272289
52 752126527
53 701952217
54 195221743
55 749751511
56 993664733
57 482075233
58 793907659
59 907659619
60 261475157
61 558812843
62 284361151
63 220677781
64 743137721
65 670011149
66 292364207
67 165049051
68 510728611
69 381118079
70 964943359
71 943359533
72 561832757
73 829283309
74 462458207
75 379967603
76 521312093
77 360589349
78 589349041
79 893490413
80 413075491
81 888380567
82 514281281
83 286748353
84 897618019
85 367749469
86 842894977
87 774027053
88 402705311
89 705311753
90 466484719
91 922984441
92 547711817
93 711817391
94 206150249
95 228249239
96 243518579
97 903005617
98 665557889
99 557889377
100 829141597
101 821921917
102 366267557
103 952543177
104 543177253
105 438763517
106 850821109
107 946182877
108 828776777
109 103130509
110 305095871
111 747471161
112 852464489
113 893289079
114 694744469
115 969804089
116 713571409
117 135714091
118 924355813
119 813782743
120 737219677
121 686576663
122 583927297
123 754878763
124 787639621
125 396211177
126 621117709
127 937842133
128 352824431
129 265497563
130 400441369
131 921507827
132 122012041
133 527295761
134 272957611
135 785636167
136 636167923
137 885090391
138 128357291
139 352815919
140 281591987
141 159198703
142 854068751
143 687510589
144 926787703
145 304296919
146 924484991
147 192751849
148 865761341
149 961600243
150 152515403
151 566169761
152 173553343
153 345153811
154 786517357
155 280038907
156 907684709
157 847099469
158 997450411
159 118667183
160 160059883
161 800449249
162 776140643
163 832411967
164 967449751
165 674497513
166 621368669
167 127563533
168 482805727
169 572780041
170 727800419
171 707240659
172 362534803
173 348986903
174 986903851
175 800958827
176 958827127
177 893599871
178 681967207
179 207525691
180 752569133
181 994565947
182 599888521
183 406352861
184 821790569
185 665929337
186 375152951
187 544229291
188 706321787
189 552558751
190 856118983
191 612605341
192 600692761
193 692761723
194 127270439
195 727043929
196 819813503
197 405510241
198 180517457
199 174572887
200 280889009
201 890094529
202 453499363
203 760362047
204 244267213
205 764544377
206 980686979
207 809524019
208 893776673
209 766736699
210 667366993
211 508709759
212 895543879
213 312926099
214 609907247
215 291555599
216 584602831
217 424669307
218 443226521
219 322652117
220 122604793
221 793944197
222 375218359
223 315773729
224 157737299
225 198334519
226 217873093
227 932496739
228 254966099
229 320323501
230 205375559
231 969735911
232 735911507
233 761037377
234 103737737
235 377376581
236 848808253
237 385875319
238 432425261
239 252614983
240 632923471
241 424702693
242 259904977
243 154485559
244 555972283
245 831554953
246 527905129
247 955119167
248 360362711
249 271179127
250 972665087
251 408188069
252 383061971
253 300192181
254 921819683
255 253362379
256 533623799
257 379920511
258 596576723
259 210403189
260 805440653
261 440653709
262 653670883
263 378738509
264 404081011
265 819432869
266 337969493
267 523667957
268 186139861
269 811328809
270 248681029
271 135820109
272 563519939
273 582437971
274 125506877
275 131962949
276 674462069
277 445812047
278 403550681
279 154401959
280 440195969
281 697853789
282 899092511
283 432487733
284 248773367
285 135192371
286 395845291
287 954220559
288 422055989
289 220559893
290 425840629
291 406290277
292 792613643
293 305227031
294 682790609
295 939975877
296 184759769
297 415250393
298 598982563
299 634794371
300 510439649
301 862656397
302 563973187
303 898809409
304 508351513
305 132668597
306 597897691
307 363478013
308 347801353
309 264429359
310 602453261
311 470609609
312 706096099
313 609609907
314 943041689
315 168910801
316 959628539
317 804448027
318 301381463
319 152801177
320 528011773
321 737606393
322 606393331
323 393331747
324 838328761
325 994417727
326 486845263
327 205588433
328 116324297
329 242972927
330 836613391
331 579033011
332 903301183
333 183426283
334 342628339
335 710765663
336 671568923
337 682439833
338 673226159
339 449187301
340 187301239
341 186209981
342 448831303
343 466148141
344 661481417
345 481417309
346 982264697
347 622253561
348 256561453
349 942100591
350 630232609
351 302326093
352 324138329
353 291555581
354 162155471
355 662259659
356 157110169
357 834040411
358 467111867
359 603622133
360 302939341
361 968942657
362 530873951
363 335704163
364 361151347
365 907126091
366 179731883
367 692825723
368 327777661
369 766135529
370 805986157
371 497518051
372 862351549
373 105300619
374 632346971
375 244494149
376 204450679
377 276176767
378 617676791
379 912580657
380 237969161
381 724349713
382 463931539
383 278431897
384 756988009
385 285259433
386 533285021
387 478646933
388 169228337
389 283370771
390 880551887
391 188715749
392 875686211
393 175424461
394 461922781
395 922781903
396 902574091
397 126881539
398 831372263
399 635759543
400 789471929
401 115322983
402 322983803
403 621073591
404 425586241
405 952475431
406 316910639
407 145127261
408 930118043
409 301180433
410 180433039
411 927933481
412 107719169
413 191690251
414 586193789
415 963500921
416 568830553
417 280043143
418 434291857
419 860376247
420 702590477
421 772449023
422 902353163
423 531630637
424 699193877
425 659716703
426 469959143
427 699591439
428 404473259
429 595762133
430 576213397
431 762133973
432 754476271
433 476271449
434 122620781
435 226207819
436 542384527
437 238452701
438 527016059
439 270160591
440 434962433
441 327892603
442 803102189
443 218989543
444 181067273
445 772005413
446 180962941
447 294149951
448 733952227
449 806448109
450 644810983
451 219599143
452 438044609
453 806888539
454 427276961
455 748979159
456 257959501
457 434998841
458 841020239
459 202394581
460 945817007
461 817007291
462 291921407
463 407776153
464 306796799
465 366894529
466 283671613
467 575022491
468 293989937
469 937409471
470 192589009
471 258900907
472 628718749
473 443825539
474 806268011
475 688985629
476 507974333
477 508944497
478 729179537
479 626072983
480 805279129
481 384710687
482 166902521
483 669025211
484 130222511
485 769440719
486 956569751
487 975169969
488 996998539
489 478399087
490 798820697
491 780965443
492 443256091
493 779086793
494 267302531
495 319008629
496 651198323
497 262645783
498 208888079
499 761884261
500 842614313
501 292488919
502 919931627
503 817651291
504 356915749
505 889540669
506 728026727
507 802672789
508 578606947
509 415944337
510 443374639
511 408062327
512 327017983
513 452182573
514 884285527
515 855276101
516 610186921
517 802934551
518 121807853
519 160045031
520 600450311
521 162839827
522 739928551
523 303778303
524 328285577
525 290022283
526 790769963
527 723461161
528 554622269
529 622269829
530 985583633
531 946938353
532 745308769
533 336858167
534 748995439
535 489954397
536 138571229
537 775411601
538 601640773
539 341910631
540 676486301
541 486301583
542 321807677
543 102580043
544 812086021
545 120860219
546 969573659
547 389629651
548 602993389
549 909074227
550 422785673
551 278567327
552 956629517
553 295178827
554 973272541
555 381503399
556 925124279
557 973391539
558 916985513
559 826828543
560 543682333
561 955662023
562 236214191
563 466866311
564 668663119
565 139261091
566 926109109
567 926773459
568 345902917
569 459029177
570 291770021
571 359168273
572 368065871
573 252649367
574 663230713
575 866852699
576 483159527
577 831595277
578 952772173
579 559427021
580 903698959
581 569755751
582 655169969
583 969218287
584 889520369
585 895505467
586 312063547
587 779376469
588 697025267
589 526791413
590 914139119
591 863785823
592 785823457
593 850212373
594 152113891
595 113891933
596 244141589
597 414158911
598 581349539
599 945853339
600 832393399
601 901208599
602 468670019
603 670019093
604 503178719
605 221080703
606 870111673
607 657695681
608 953319481
609 519473443
610 108167659
611 856770989
612 677098957
613 895728881
614 810140921
615 273561697
616 803602003
617 483175943
618 790348133
619 192416291
620 547618153
621 815380301
622 505390357
623 595243651
624 632397203
625 893825117
626 179481637
627 426657769
628 441404573
629 369027983
630 622885357
631 535766089
632 755282741
633 552827413
634 274133759
635 598665329
636 329082421
637 125113811
638 200957597
639 326925581
640 109204859
641 688681843
642 712085467
643 358502861
644 471727901
645 551613509
646 399888199
647 987941137
648 665645881
649 645881659
650 491633503
651 682677953
652 715869907
653 565723657
654 505368601
655 852069473
656 346702903
657 316606981
658 989186587
659 218023811
660 113878109
661 109842611
662 129509671
663 967169417
664 753156241
665 318210593
666 630207233
667 957591967
668 783119591
669 184066937
670 473089163
671 751004173
672 872403437
673 374439893
674 698962477
675 896247761
676 486803431
677 937627753
678 640762769
679 828306029
680 669376073
681 376073933
682 336680639
683 955589093
684 142244183
685 422441837
686 356775593
687 798803717
688 803717077
689 772527227
690 658646309
691 309562303
692 219674563
693 563766829
694 299317099
695 732944237
696 864888551
697 217052497
698 880447907
699 478759339
700 835912939
701 359129399
702 879906061
703 158530663
704 850448251
705 897476497
706 970076449
707 288402251
708 840225181
709 811643933
710 393358187
711 983065547
712 816997897
713 789729643
714 972964373
715 443784683
716 410586793
717 555841441
718 333012341
719 227078777
720 655873783
721 691248559
722 945110821
723 120336127
724 780547279
725 805472797
726 474782933
727 384040843
728 726546707
729 242244749
730 244749587
731 906112217
732 176338577
733 633857747
734 936093157
735 931577833
736 783352831
737 831215167
738 753918721
739 214427201
740 792033427
741 400806667
742 692087563
743 669498419
744 273097523
745 246880279
746 165979819
747 597981911
748 981911477
749 911477137
750 952968803
751 588505699
752 699325687
753 302782153
754 207584777
755 847773379
756 777337919
757 773379197
758 125481827
759 925373923
760 790698911
761 620958953
762 561958597
763 461387623
764 487013479
765 610559407
766 296169583
767 695839951
768 951984347
769 411778091
770 948019691
771 685645427
772 564542761
773 611839309
774 118393097
775 553373071
776 307183477
777 834876257
778 201522109
779 529203517
780 351739247
781 173924717
782 327757987
783 967741387
784 601680557
785 491559847
786 446329229
787 463292299
788 911409529
789 981507011
790 745197221
791 120056309
792 231716299
793 413533283
794 332832559
795 583099591
796 575001029
797 500102903
798 838352111
799 110602069
800 535668557
801 574509239
802 925877377
803 877377169
804 442595567
805 234321181
806 823786547
807 865472191
808 961750523
809 785615921
810 547005037
811 625882627
812 627196621
813 719662171
814 501429317
815 498702133
816 637058423
817 295250621
818 967153853
819 853014119
820 356711893
821 478020061
822 179859413
823 594131383
824 201842699
825 768647329
826 297128257
827 282574147
828 741477701
829 272035873
830 720358733
831 842584397
832 787406671
833 687941167
834 286493663
835 936808567
836 808567057
837 856196179
838 617958829
839 756612869
840 828182363
841 450799903
842 903212467
843 268175077
844 921252071
845 566162287
846 661622879
847 637558217
848 482446891
849 824468917
850 110944373
851 613856483
852 382918363
853 918363653
854 626714323
855 360691699
856 446792063
857 620250599
858 563455261
859 190423507
860 725212289
861 253648739
862 648739489
863 227238967
864 704126993
865 695017369
866 262918613
867 825273203
868 252732031
869 605149273
870 113945693
871 925665577
872 167324957
873 732495761
874 761999417
875 994179337
876 757425269
877 742526929
878 882601751
879 515085073
880 850733599
881 316874897
882 684706691
883 207047261
884 821731109
885 955696177
886 569617771
887 843017653
888 301765393
889 537579527
890 703038659
891 959251739
892 402881711
893 460991891
894 700370009
895 813315449
896 544902863
897 807975601
898 405460787
899 528538139
900 853813907
901 536281003
902 296752817
903 919352921
904 935292107
905 884262367
906 323582807
907 685648241
908 482416607
909 795544283
910 404016043
911 401829601
912 176674621
913 667462111
914 325052327
915 523102483
916 159164933
917 997779061
918 894638089
919 988096621
920 966218507
921 524209687
922 687537421
923 999973703
924 717860401
925 637902253
926 225346349
927 630200609
928 254253089
929 667389377
930 492707021
931 718576699
932 505711397
933 113974087
934 528958601
935 627482677
936 888310373
937 975877501
938 775018421
939 750184219
940 120656813
941 681387229
942 882346253
943 346253951
944 539510089
945 904219597
946 389539991
947 539991253
948 274292639
949 681696577
950 257501663
951 400996907
952 690705889
953 348556193
954 386916253
955 353478233
956 347823373
957 319744889
958 974488951
959 459160943
960 482888717
961 111347287
962 429113791
963 461344813
964 320828003
965 903980237
966 398023783
967 980237837
968 802378373
969 932179607
970 802865293
971 652934141
972 735698429
973 984293021
974 312390679
975 239067947
976 734905687
977 687110839
978 485906791
979 563104907
980 193115899
981 438085559
982 380855591
983 572470777
984 303571813
985 181365637
986 826324903
987 228312289
988 514196359
989 977958043
990 765788981
991 205405427
992 540542771
993 956096639
994 157153301
995 830628217
996 918529223
997 852922319
998 992417249
999 341327893
1000 900583417