1000 1040
1 757 59516440
1 965 648284414
2 629 401122994
2 710 908626707
3 193 349561276
3 505 635259605
3 677 602521731
4 93 484729330
4 488 804945056
5 148 589243861
5 286 986973640
6 60 530183784
6 728 888702996
7 499 594560229
7 972 498756046
8 84 885645796
8 824 162946354
9 478 30313938
9 521 75172981
10 63 856331819
10 245 382039603
11 139 214199364
11 254 823843323
11 697 736416123
12 761 367737551
12 950 886040759
13 34 311773290
13 850 338189040
14 435 104638506
14 935 429225512
15 24 289233013
15 602 671907656
16 120 272263010
16 311 726861931
17 583 811039417
17 901 436003148
18 810 724578015
18 887 338475563
19 423 861833619
19 752 827335169
20 46 486463705
20 955 483034116
21 495 573825096
21 801 762449004
22 328 59497372
22 780 238585910
23 249 147140888
23 959 884588148
24 644 662860732
25 201 769630345
25 553 626155767
26 114 536056291
26 743 58869367
26 979 849921432
27 67 176634389
27 68 987526072
28 675 14743974
28 737 845452421
28 751 69598975
29 796 319799869
29 897 173671754
30 211 770232659
30 649 703422561
31 209 660412208
31 517 903363713
32 99 616054508
32 197 434401560
32 253 102732949
32 640 486793043
33 107 372185828
33 514 100678957
34 255 535249694
35 234 234766835
35 335 724242131
36 621 568377171
36 624 524204488
37 108 567865896
37 300 908969755
38 388 765660006
38 831 307511640
39 244 231196457
39 306 124631177
40 252 490501653
40 869 201059891
41 754 425811038
41 949 465702347
42 284 359352998
42 968 199224605
43 248 761927687
43 299 132570357
44 171 967010231
44 219 778490136
45 486 72654865
45 664 977285190
46 840 276242575
47 446 65403755
47 497 111101264
48 175 44908639
48 322 190089787
49 770 306782980
49 779 975201424
50 109 622387531
50 845 906361624
51 210 148564263
51 467 624579769
52 278 398115298
52 663 730127006
53 762 152333111
53 867 697909362
54 416 274259322
54 471 795895955
55 220 919883939
55 312 617398630
56 733 387629311
56 908 623767282
57 833 882801356
57 887 263608990
58 212 280479496
58 693 397521499
59 156 306331898
59 598 429274810
60 298 49803504
61 271 595336381
61 327 955968037
62 520 695549418
62 805 479163414
63 544 337155887
64 642 20086822
64 961 934355506
65 534 530520464
65 692 467296419
66 615 611505102
66 632 248445746
67 325 239198433
68 963 561795742
69 655 306878228
69 837 878452652
70 504 727556120
70 847 602396245
71 221 582389511
71 484 264568303
72 665 160589368
72 861 752008393
73 178 794831860
73 548 777437479
73 806 168057244
74 102 545684068
74 859 200518916
75 171 255151170
75 863 629335439
76 154 542896285
76 718 664804415
77 156 949924115
77 330 203779940
78 289 980874402
78 812 245522859
79 510 760337297
79 514 562475227
80 816 860836532
80 985 123889759
81 354 838329613
81 794 96854020
82 164 561894849
82 773 303655583
83 418 678359931
83 573 20121753
84 950 49954778
85 269 626005770
85 293 432789393
86 764 654698069
86 815 926247391
87 339 717040312
87 345 179308047
87 659 218635340
88 280 344449372
88 597 919129262
89 632 294000108
89 777 204732537
90 663 751599208
90 892 284869327
91 137 852492559
91 181 614929211
92 281 380136745
92 297 936455638
92 929 529763833
93 385 877335830
94 292 239766141
94 753 31385640
95 282 838230194
95 827 455654213
96 713 365981796
96 756 422635658
97 642 239036769
97 853 966717285
98 543 780001860
98 846 38446395
99 130 212689677
100 364 488331246
100 460 702164713
101 454 419145634
101 735 39089728
102 791 949555483
103 168 720217132
103 739 989004811
104 676 788895629
104 873 564644771
105 239 112621555
105 566 644479524
106 716 280479633
106 780 510158999
107 361 562252906
108 910 215924199
109 731 112766415
110 333 780532594
110 434 769061814
111 297 108545957
111 682 203194097
112 435 938290918
112 541 646854027
113 553 309457221
113 768 4428714
114 185 434671710
114 428 798339236
115 705 665347767
115 939 234333507
116 873 531230623
116 952 18713119
117 176 575059518
117 209 793617955
118 202 973524870
118 401 415602351
119 904 650641970
119 932 559794889
120 849 172664093
121 296 207462633
121 301 575152302
122 572 36143840
122 877 559131057
122 898 351367631
123 571 107313424
123 736 687335505
123 842 727249309
124 370 591903187
124 619 249730253
125 706 545532726
125 765 130338410
126 293 875601398
126 945 518685348
127 271 745652124
127 448 599613969
127 993 458813453
128 145 253916411
128 652 732095419
129 461 762232315
129 503 344749592
130 877 976612013
131 148 993315777
131 405 332923842
131 683 7015490
132 607 660919186
132 981 465068652
133 400 477290520
133 947 7042140
134 186 55829278
134 684 995465738
135 618 435520617
135 914 790230348
136 138 632864123
136 238 215720146
137 250 508316789
138 405 292595941
139 492 978857286
140 630 137588485
140 868 688156178
141 392 806772176
141 610 340759143
142 511 668753720
142 580 901327171
143 217 381782685
143 864 306174940
144 219 593757190
144 387 810190838
144 997 139391620
145 631 854136672
146 749 636889638
146 969 900095447
147 526 147702218
147 709 17864897
149 793 633054348
149 836 293184803
150 376 893040194
150 939 444362028
151 319 438444030
151 581 37325539
152 212 61645101
152 573 819595915
153 260 240492511
153 801 294049545
154 223 609426790
154 550 618969599
155 529 659841085
155 767 647969583
157 480 694896150
157 775 963840969
158 496 419534177
158 786 312684847
159 170 678788866
159 230 122595909
160 509 379710885
160 879 881228234
161 346 562298990
161 694 267029547
162 269 74910764
162 909 856404245
163 308 378039314
163 584 438337068
164 918 797904326
165 806 213255113
165 999 604252717
166 262 139243743
166 279 876522289
167 464 828492563
167 575 800944131
168 657 545779206
169 321 382985132
169 759 839982511
170 348 409946947
171 338 222332503
172 401 244324954
172 900 49035104
173 261 867881510
173 483 112311375
174 615 467190983
174 759 619772590
175 315 909004255
175 494 950019733
176 415 486853018
177 526 366890626
177 566 106662984
178 456 394648952
178 692 158470213
179 204 513404617
179 666 273782816
180 454 804012311
180 934 281824722
181 559 18085477
182 272 28080653
182 966 460979920
183 344 218150659
183 938 861866712
184 374 778620968
184 892 159010316
185 346 730493920
186 852 812215616
187 215 122609165
187 356 374409429
188 259 802833743
188 623 46256774
189 415 605304196
189 977 777916257
190 512 198295933
190 987 920881968
191 787 52748937
191 960 839673956
192 522 163204344
192 777 416318386
193 1000 635130992
194 349 292422139
194 503 948962310
195 764 749376844
195 982 98153142
196 491 961502542
196 812 194498265
197 353 543595311
197 414 84090480
198 284 18748657
198 520 318336576
199 685 875698339
199 745 242567620
200 336 394233345
200 702 539636919
201 761 602375310
202 540 360434670
203 524 425464726
203 655 966397578
204 973 352665115
205 294 768089073
205 917 853320070
206 485 903772501
206 883 255431059
207 390 136867645
207 445 17092401
208 278 373651735
208 875 294764988
210 707 452397093
211 387 738302895
213 324 985488145
213 798 319276583
214 441 173273261
214 591 697080799
215 277 136495105
216 250 38491412
216 785 803357909
216 967 419009883
217 326 789970189
218 235 227658678
218 638 153224962
219 511 705255453
220 587 396308505
221 510 715765639
222 576 20156457
222 807 9026710
223 783 327318194
223 848 900397277
224 358 17538178
224 536 899772909
225 536 334392737
225 723 838992753
226 452 352094565
226 574 947575971
227 416 785952905
227 967 407851504
228 384 199890422
228 758 319200348
229 530 174005589
229 795 564182563
230 487 258369167
231 474 315396100
231 601 996948225
232 449 264982317
232 711 66279203
233 353 963495083
233 660 379435332
234 548 663221031
235 688 168469506
236 262 7414394
236 828 815938553
237 547 632472885
237 883 728370268
238 310 853070163
239 771 925673738
240 685 671412900
240 989 513536579
241 343 992034134
241 384 261213800
242 247 93703942
242 725 816315318
243 378 46761525
243 498 204530108
244 701 835405785
245 577 411104556
246 359 879566410
246 906 668705452
246 985 181709259
247 905 681619766
248 579 8497005
249 304 517355208
250 610 683391961
251 602 596340634
251 942 226383778
252 742 974408341
253 914 516462407
254 285 315276637
255 373 338293552
256 440 372658994
256 669 182361195
257 360 938455151
257 994 75052035
258 512 722255382
258 781 217637877
259 604 329573904
260 734 436988811
261 402 643341220
263 545 713503336
263 858 8438621
264 270 284165779
264 611 173546620
264 630 944395867
265 532 566513553
265 682 74262883
266 670 954392970
266 860 862485159
267 286 403691417
267 830 503345561
268 360 46679448
268 399 340734182
270 653 29293950
270 817 150994647
271 925 321925296
272 349 640370996
273 381 413623781
273 940 612171527
274 389 323959012
274 525 738126950
275 342 71882799
275 733 917409859
276 502 346289856
276 729 495033641
277 646 414630269
279 612 429016650
280 629 6270616
281 758 127577960
282 613 506132901
283 560 586889467
283 800 398045592
285 717 643282375
287 674 280447464
287 741 16031326
288 698 39889885
288 721 158318732
289 365 182475209
290 406 797677010
290 593 757226166
291 811 400438956
291 876 468337389
292 422 873832457
294 750 879183386
295 694 898849204
295 855 629854599
296 754 487896621
297 836 22302054
298 980 166398082
299 432 30262833
300 921 712821081
301 843 282000805
302 458 826492775
302 461 119094162
303 715 9962559
303 899 930030583
304 469 682425252
305 330 770619538
305 689 575390003
306 734 837813098
307 527 140844921
307 888 195647246
308 548 91073673
309 813 635852622
309 814 971877076
310 338 965614998
311 603 342230061
311 672 411068388
312 699 423095290
313 439 804698311
314 618 119284007
314 799 790009596
315 369 267147178
315 519 344271696
316 542 347113336
316 874 382824651
317 476 742011993
317 919 160955028
318 687 460593736
318 918 373999628
319 427 670900645
320 555 493575941
320 736 701340177
321 438 347567209
322 557 569829514
323 369 587767584
323 457 579274328
323 676 349716391
324 447 66057
325 358 92612857
326 882 681457624
327 622 609061910
328 681 741814093
329 354 562246712
329 963 868124421
331 385 498777754
331 938 916899261
332 739 732947626
332 962 397520225
333 871 451294737
334 745 348895563
334 915 227535354
335 428 801680772
336 534 151996642
337 707 932436777
337 711 97120210
337 858 537528759
338 782 239411724
339 686 170723269
340 623 446050737
340 931 281256274
341 371 58684539
341 755 827763844
342 408 6545150
343 697 248649038
344 437 832370402
345 462 956165297
346 468 526471760
347 396 317453899
347 559 569560419
348 666 429500016
350 568 783920589
350 924 994292179
351 634 61390514
351 893 428842545
352 609 313740570
352 784 526593658
355 713 928427766
355 968 72421713
356 763 456292672
356 919 544422642
357 398 764552265
357 657 68889230
359 941 300920349
361 528 1910560
362 450 495259544
362 832 20965576
363 473 65242802
363 945 648419531
364 958 801894654
365 940 757650097
366 423 956900524
366 612 25234574
367 481 512991803
367 723 392098628
368 524 92207731
368 876 3505036
370 476 961529857
370 920 465806820
371 452 614998582
372 469 535778861
372 943 866386228
373 920 526854802
374 572 376712872
375 789 351711820
375 824 687908344
375 826 788860768
376 595 782083432
377 551 288429966
377 850 635856585
378 495 602031475
379 457 560175465
379 834 481593084
380 470 880085352
380 775 170675321
381 936 895984269
382 841 689750787
382 874 636634397
383 941 905750921
383 955 553873146
386 928 40258082
386 996 441941767
388 797 346119115
389 518 550532864
390 616 74156911
391 403 61932272
391 473 404789425
392 700 287513675
393 427 46741528
393 956 859786565
394 633 62955204
394 724 805400846
395 537 12888116
395 952 715314976
396 611 18175766
397 588 675837460
397 625 999296416
398 712 322946014
399 647 907816402
400 504 206888409
402 624 529811995
403 884 122375385
404 456 661163456
404 672 268795959
406 627 620754103
407 466 339650261
407 516 909527410
408 899 946206750
409 816 361479457
409 944 996925753
410 561 203767922
410 651 152066099
411 578 455693999
411 697 653680702
412 603 176572596
412 971 650302880
413 607 575960407
413 986 173026024
414 633 373733262
417 453 217658253
417 593 12344083
418 617 437630195
419 421 146893859
419 492 537630321
420 656 300091797
420 975 355766103
421 641 743194832
422 959 721307272
424 508 464530612
424 706 692222775
425 552 918180337
425 613 690580974
426 489 187532229
426 531 726853848
429 755 545781180
429 826 432770512
430 622 497933118
430 927 633398444
431 527 929854158
431 774 744566778
431 907 86675101
432 562 93845174
433 743 750619774
433 969 293382192
434 474 169337063
436 562 862000960
436 578 986310003
437 690 183727434
438 848 430406569
439 681 212553642
440 482 441581553
441 640 56831889
442 465 102399457
442 773 472331887
443 487 81988470
443 966 123510265
444 724 657060748
444 990 480273623
445 522 579502332
446 751 175920293
447 678 374229651
448 840 680704227
449 459 916184037
450 627 474851787
451 679 538528569
451 708 735773359
453 693 313409932
455 647 254799782
455 678 457456411
456 590 540539790
458 902 365990698
459 644 291303167
460 985 437063161
462 549 296276433
463 658 579988380
463 800 878863819
464 696 319191529
465 805 137761764
465 847 347861723
466 643 92003272
467 501 421417148
468 719 139381951
468 983 274878558
470 565 326353584
471 944 829441380
472 747 389419816
472 890 545864732
475 527 36968622
475 650 989926612
477 729 617271972
477 875 509937907
478 748 770664201
479 481 501851233
479 951 498147840
480 554 52675531
482 582 275691623
483 854 647294628
484 746 334347812
485 671 418851495
486 584 244619772
488 979 732711593
489 814 71076198
490 808 471283684
490 948 756288988
491 934 570904152
493 505 560399554
493 981 336055909
494 843 260821645
494 922 345266122
496 996 104913259
497 686 303684452
498 554 402496903
499 888 653350795
500 679 710125917
500 978 364657713
501 740 365722485
502 871 918622814
506 668 446091004
506 742 208375165
506 828 503747769
507 660 330487851
507 988 469659738
508 563 376293808
509 995 449797458
513 592 458689956
513 600 404868579
515 539 90937748
515 705 390313783
516 991 749870954
517 722 131420817
518 730 806360327
519 915 38392123
521 677 364395330
523 716 644560003
523 856 833797012
525 927 601626286
528 564 535150523
529 776 713267007
529 991 484959056
530 595 927050493
531 547 987439750
532 823 605926727
533 805 595967440
533 909 420703537
535 650 704525997
535 894 411411051
537 674 244525972
538 670 445078862
538 691 372534077
539 925 329134765
540 746 507027627
540 920 596623812
541 736 658270950
542 557 692421637
543 998 787300619
544 913 421750238
545 709 905415741
546 637 438875928
546 922 754303476
549 717 216230613
550 834 656824328
551 683 882849725
551 804 520913038
552 575 1488904
555 960 445629847
556 675 998304084
556 859 839314356
558 794 143799434
558 977 517051184
560 908 872291008
561 786 186069945
563 683 328279617
564 605 272215056
565 704 754311639
567 808 260395133
567 857 875222117
568 829 186848266
569 894 133058149
569 910 865353188
570 620 59973271
570 815 769595596
571 826 645451554
572 748 824089343
574 984 410028787
576 662 814008876
577 664 756643698
579 810 634188187
580 695 581967364
581 823 769193913
582 594 362411209
583 919 679872408
585 789 88440557
585 845 290082847
586 645 222929491
586 732 266222663
587 783 582797233
588 943 365163919
589 684 892592964
589 872 775555494
590 954 219912815
590 972 513251057
591 862 19741487
592 725 628032774
594 962 304757974
596 831 929027878
596 884 695933016
597 687 690340831
598 750 94752131
599 626 289383357
599 703 688429943
600 772 791882266
601 765 930109280
603 710 59562314
604 838 961613257
605 776 2254078
606 796 643201426
606 819 663232036
608 722 152918409
608 893 86899863
609 930 908149074
614 913 680722673
614 964 461130794
616 727 937874203
617 896 589934549
618 763 205083649
619 907 733955028
620 742 73698922
621 911 621025431
625 821 998546694
626 903 889560204
628 668 233614470
628 900 717892285
631 904 121986940
634 825 474921547
635 768 273407597
635 917 380518574
636 822 674545776
636 866 659311992
637 989 656243584
638 851 582609817
639 799 747256172
639 933 764859546
640 922 240407513
641 680 297046526
643 704 80802536
645 998 216945356
646 792 22796561
648 833 517941349
648 926 500472551
649 667 743421647
651 870 623068197
652 942 557279679
653 676 36375446
654 895 303583481
654 974 572525440
656 659 783110501
658 774 623258007
659 809 946850917
661 781 75469110
661 948 226201606
662 886 958451831
665 970 795739696
667 975 114844519
669 790 231861185
671 818 214908936
673 691 385789264
673 964 127355130
674 895 671969131
677 865 447183344
680 994 366570446
688 701 41585900
689 854 588181251
690 844 719192373
695 879 590797741
696 982 392434481
698 819 317198000
699 792 629629499
700 949 392322352
701 719 272599775
702 997 962741949
703 711 192569183
708 738 374739642
712 889 965448801
714 811 236981963
714 896 319297471
715 744 828101781
718 756 521315641
719 837 489556912
720 889 732838291
720 931 112334449
721 882 235294157
726 885 933419424
726 958 993958875
727 767 734151858
728 790 841978154
730 771 970576105
731 916 655279770
732 817 232876947
735 923 918226065
737 803 356408064
738 752 372509194
740 807 321003194
741 895 149109010
744 987 165731442
746 835 11713643
747 901 854904496
749 762 405752478
751 933 552505676
753 870 466616854
757 947 767402736
760 880 781751947
760 993 808027101
763 849 183000677
766 872 718567831
766 906 443230305
769 897 642306834
769 957 502725489
770 797 855723982
772 793 936564910
776 923 122405406
778 782 285752729
778 862 932056822
779 983 561129518
784 785 451558741
787 846 87621397
788 903 931368345
788 986 229504395
791 928 418199485
795 878 224257370
798 851 642841241
802 864 402201343
802 935 536916921
803 951 802370782
804 865 323411016
804 954 562648855
809 886 298119426
813 976 389757553
818 972 600703391
818 979 432821351
820 905 910223633
820 965 332245412
822 956 593594445
825 855 52601091
827 844 248178152
829 932 876466423
830 842 160591029
832 878 591701757
835 988 864255916
838 976 920850401
839 902 95594206
839 916 365494696
841 861 264316246
852 929 536936749
853 953 988516212
856 984 374070572
857 970 157966637
860 890 655781110
863 971 152949019
866 926 521785779
867 980 803713235
868 992 115924462
869 995 96542486
880 881 751970059
881 891 451663657
885 912 888686389
891 946 321371518
898 930 956731872
911 957 418461382
912 961 244582323
921 1000 775342241
922 934 422588331
924 978 810301786
936 953 93560589
937 946 873428025
937 992 965177877
973 999 695228765
974 990 107299984