1000 999
1 2 25944966
2 3 592924608
3 4 348609800
4 5 634803973
5 6 448121172
6 7 96651151
7 8 827434217
8 9 164766756
9 10 202641123
10 11 99515987
11 12 997936033
12 13 725603374
13 14 150187260
14 15 246469044
15 16 824429728
16 17 983495443
17 18 492755544
18 19 95516316
19 20 317761780
20 21 643986255
21 22 583319080
22 23 530081401
23 24 289793160
24 25 64707733
25 26 536913531
26 27 87149940
27 28 308798173
28 29 24684712
29 30 343857853
30 31 540678841
31 32 650477894
32 33 986587943
33 34 593001661
34 35 574982972
35 36 522635737
36 37 66331184
37 38 135138977
38 39 410591180
39 40 614502620
40 41 843199852
41 42 448079259
42 43 787271737
43 44 890295639
44 45 205051977
45 46 380190058
46 47 448427995
47 48 334607182
48 49 810824948
49 50 130024222
50 51 949369510
51 52 581762620
52 53 408863846
53 54 382558465
54 55 555618360
55 56 958966456
56 57 551349798
57 58 567873946
58 59 368218343
59 60 340415826
60 61 2451737
61 62 677909800
62 63 296747906
63 64 426283836
64 65 392460196
65 66 908007583
66 67 848910391
67 68 303301393
68 69 662808207
69 70 802503381
70 71 786818514
71 72 217077923
72 73 154329982
73 74 4557294
74 75 347375786
75 76 478332487
76 77 866340733
77 78 878160151
78 79 974909194
79 80 250987685
80 81 537160540
81 82 788026399
82 83 180898516
83 84 576195781
84 85 977173691
85 86 150748089
86 87 283093685
87 88 536340559
88 89 743518182
89 90 582223584
90 91 421003041
91 92 211367114
92 93 904853613
93 94 124741669
94 95 67386384
95 96 348850244
96 97 208678440
97 98 832096330
98 99 561533
99 100 599992800
100 101 413103099
101 102 593043
102 103 227646462
103 104 400084321
104 105 733287422
105 106 449091471
106 107 619979449
107 108 980436720
108 109 488134312
109 110 450544252
110 111 94088768
111 112 658973733
112 113 783751724
113 114 884689170
114 115 535339929
115 116 654259643
116 117 3531882
117 118 521878223
118 119 464163917
119 120 110802161
120 121 870942631
121 122 153391270
122 123 232329407
123 124 383616624
124 125 167969122
125 126 191202755
126 127 444796017
127 128 990495477
128 129 325997330
129 130 40758173
130 131 162304839
131 132 467022096
132 133 31089751
133 134 238868664
134 135 121571368
135 136 142098999
136 137 421386894
137 138 675900799
138 139 519783011
139 140 850140207
140 141 81277901
141 142 63216374
142 143 62090821
143 144 854908311
144 145 141676528
145 146 376725224
146 147 164498674
147 148 573182381
148 149 711962031
149 150 943393361
150 151 282394183
151 152 531219847
152 153 836101948
153 154 523958187
154 155 133295013
155 156 840859326
156 157 953087945
157 158 652337384
158 159 777957023
159 160 668462656
160 161 656072042
161 162 69426675
162 163 642779562
163 164 402642551
164 165 331460265
165 166 314165525
166 167 884360593
167 168 684067421
168 169 467300126
169 170 541763154
170 171 582348366
171 172 314032747
172 173 449465496
173 174 577390108
174 175 631929783
175 176 80190936
176 177 330914500
177 178 481878942
178 179 363852208
179 180 461776250
180 181 845760269
181 182 565872774
182 183 19570417
183 184 544677255
184 185 87416872
185 186 493641542
186 187 439395861
187 188 741058677
188 189 35693421
189 190 938471404
190 191 830473063
191 192 229691369
192 193 634147283
193 194 864920720
194 195 462458993
195 196 729751285
196 197 957859919
197 198 279794152
198 199 948271972
199 200 317418564
200 201 739755868
201 202 440794996
202 203 174411144
203 204 698592901
204 205 214118896
205 206 236975619
206 207 478167790
207 208 514847087
208 209 682358164
209 210 435129508
210 211 47186918
211 212 863449554
212 213 450462357
213 214 459855524
214 215 524804285
215 216 422908146
216 217 366903450
217 218 336096773
218 219 582486262
219 220 440399736
220 221 865000405
221 222 335660264
222 223 361855539
223 224 271217183
224 225 686663695
225 226 488761751
226 227 740211517
227 228 691118919
228 229 643088625
229 230 461933138
230 231 682638205
231 232 74960137
232 233 938132643
233 234 916363679
234 235 790540899
235 236 355886984
236 237 820045923
237 238 585252183
238 239 503597146
239 240 618591821
240 241 952687045
241 242 230682992
242 243 591157596
243 244 20735752
244 245 904416894
245 246 471500468
246 247 982957573
247 248 854733369
248 249 401388132
249 250 451225575
250 251 70988931
251 252 101964920
252 253 454313547
253 254 143057985
254 255 353565995
255 256 167146318
256 257 185440441
257 258 730356771
258 259 452809135
259 260 771857577
260 261 803532909
261 262 842338935
262 263 40761966
263 264 655686735
264 265 922463504
265 266 302709579
266 267 475137303
267 268 694706194
268 269 805544972
269 270 558135647
270 271 251789843
271 272 612145719
272 273 338584991
273 274 140515068
274 275 290294694
275 276 611106548
276 277 410759695
277 278 28760534
278 279 671840945
279 280 842221
280 281 722033990
281 282 401896245
282 283 95145613
283 284 68948961
284 285 101098052
285 286 837548556
286 287 811556441
287 288 736679773
288 289 802513376
289 290 503435345
290 291 99801686
291 292 244697984
292 293 781184501
293 294 78336706
294 295 795851583
295 296 561265568
296 297 188145896
297 298 520204731
298 299 384662087
299 300 639771180
300 301 827630492
301 302 575657439
302 303 442984982
303 304 679918532
304 305 183539386
305 306 808859829
306 307 528043611
307 308 655207135
308 309 31113112
309 310 730508602
310 311 215053975
311 312 290932961
312 313 874063845
313 314 274455001
314 315 209987794
315 316 932309720
316 317 580929147
317 318 285578818
318 319 517197503
319 320 524713079
320 321 29027097
321 322 995863420
322 323 794009711
323 324 400268669
324 325 458177364
325 326 573430327
326 327 614436718
327 328 765958463
328 329 743629257
329 330 440422145
330 331 593015372
331 332 323649144
332 333 854185784
333 334 56999146
334 335 265583329
335 336 918125592
336 337 997362726
337 338 198854140
338 339 747442546
339 340 771593076
340 341 517262986
341 342 527348891
342 343 930526761
343 344 687616858
344 345 839338966
345 346 172723265
346 347 396856787
347 348 199234274
348 349 82426550
349 350 642261558
350 351 675463741
351 352 620483315
352 353 526827216
353 354 985233537
354 355 658838965
355 356 44059761
356 357 828075235
357 358 602085769
358 359 690656271
359 360 454294964
360 361 109669125
361 362 664085949
362 363 855445227
363 364 177961887
364 365 768871687
365 366 339278331
366 367 351649454
367 368 784023134
368 369 165055116
369 370 853359970
370 371 210385189
371 372 647234722
372 373 521271602
373 374 429548467
374 375 88261688
375 376 310907592
376 377 834240183
377 378 723039315
378 379 529967910
379 380 225811150
380 381 861733033
381 382 232719747
382 383 776993579
383 384 81973390
384 385 895469301
385 386 96225811
386 387 308356720
387 388 827854998
388 389 226529232
389 390 175292303
390 391 2556380
391 392 281955979
392 393 763686411
393 394 438649716
394 395 511710852
395 396 115146504
396 397 774708699
397 398 566335229
398 399 237366693
399 400 867358167
400 401 437701384
401 402 130591157
402 403 965968831
403 404 987146294
404 405 127581120
405 406 40324238
406 407 74336282
407 408 544235351
408 409 39049215
409 410 228619638
410 411 35221685
411 412 859870664
412 413 744566681
413 414 928142019
414 415 684638592
415 416 761148386
416 417 427348718
417 418 806669979
418 419 694478446
419 420 407397496
420 421 712323575
421 422 14252029
422 423 57633627
423 424 164642112
424 425 552075878
425 426 148284720
426 427 636712107
427 428 226217387
428 429 777916598
429 430 793492200
430 431 914747596
431 432 499879906
432 433 46754922
433 434 77533899
434 435 446566479
435 436 140547448
436 437 870374532
437 438 928946219
438 439 940504263
439 440 691901669
440 441 445143604
441 442 871446576
442 443 557538338
443 444 756314340
444 445 138459090
445 446 749669107
446 447 765375651
447 448 969234175
448 449 422606509
449 450 419512162
450 451 948911664
451 452 221570340
452 453 687829789
453 454 534010712
454 455 999128400
455 456 68149402
456 457 162818453
457 458 907579752
458 459 109599126
459 460 31285849
460 461 459303181
461 462 505530754
462 463 686726998
463 464 614298293
464 465 440330505
465 466 36897387
466 467 78260045
467 468 619249853
468 469 341148553
469 470 689974580
470 471 98732261
471 472 990102020
472 473 793543519
473 474 898090821
474 475 460135958
475 476 210255390
476 477 517660403
477 478 228585935
478 479 768276868
479 480 843815695
480 481 634103418
481 482 125272034
482 483 569248223
483 484 848293581
484 485 866154512
485 486 89223304
486 487 277757560
487 488 23005784
488 489 422456376
489 490 439266509
490 491 282405127
491 492 909498189
492 493 457037764
493 494 327437984
494 495 193094274
495 496 1309342
496 497 49352711
497 498 93821638
498 499 407206560
499 500 998537588
500 501 707971806
501 502 124190155
502 503 264817391
503 504 175264984
504 505 129053712
505 506 942519751
506 507 876547542
507 508 706165796
508 509 380628266
509 510 268302808
510 511 177371719
511 512 342441266
512 513 799339339
513 514 820418408
514 515 71372121
515 516 351473797
516 517 388854284
517 518 463208904
518 519 349804288
519 520 353139010
520 521 347187796
521 522 745837003
522 523 474791694
523 524 785490904
524 525 147029485
525 526 509202754
526 527 748984099
527 528 92538567
528 529 59184555
529 530 140578309
530 531 581276517
531 532 51896898
532 533 142449773
533 534 587346797
534 535 592708910
535 536 79560330
536 537 862418453
537 538 974507090
538 539 826900472
539 540 446458747
540 541 255518395
541 542 739623053
542 543 226162142
543 544 581008021
544 545 20032208
545 546 922168090
546 547 429496001
547 548 769136904
548 549 436855588
549 550 433035285
550 551 365420674
551 552 283494202
552 553 371414766
553 554 233733906
554 555 717143670
555 556 689309853
556 557 802448117
557 558 736421886
558 559 415077666
559 560 671746078
560 561 375385116
561 562 485486247
562 563 734486581
563 564 553463519
564 565 531265837
565 566 762169254
566 567 152475006
567 568 748560280
568 569 960608545
569 570 185543300
570 571 253131699
571 572 143902863
572 573 134194531
573 574 265444904
574 575 758656701
575 576 667758541
576 577 211031616
577 578 879759107
578 579 174804991
579 580 750910572
580 581 932851376
581 582 410960444
582 583 554189888
583 584 4907398
584 585 251638589
585 586 559514452
586 587 127316811
587 588 820160265
588 589 679991282
589 590 371214666
590 591 892537337
591 592 903657916
592 593 255488744
593 594 799170073
594 595 557551575
595 596 768958010
596 597 586972677
597 598 318677778
598 599 259190208
599 600 993726553
600 601 499654835
601 602 121582474
602 603 237197537
603 604 443591798
604 605 262597394
605 606 526172709
606 607 611788040
607 608 889311847
608 609 922071085
609 610 807931381
610 611 547940396
611 612 817947675
612 613 78228332
613 614 647080991
614 615 993272128
615 616 972992393
616 617 635100481
617 618 602140994
618 619 177578098
619 620 475773831
620 621 259738728
621 622 647934080
622 623 559600744
623 624 884390683
624 625 246016739
625 626 754964673
626 627 282863185
627 628 686072088
628 629 67144940
629 630 74146685
630 631 219737737
631 632 688723302
632 633 350617408
633 634 648719668
634 635 552331956
635 636 974629687
636 637 230776104
637 638 409715276
638 639 429796507
639 640 421811600
640 641 285658633
641 642 824399741
642 643 46374487
643 644 128433286
644 645 718664631
645 646 979263035
646 647 796356396
647 648 454157554
648 649 955982874
649 650 12302388
650 651 888214808
651 652 116336465
652 653 335566798
653 654 402443679
654 655 521629862
655 656 681749648
656 657 956375573
657 658 670988535
658 659 903642747
659 660 182365982
660 661 405940501
661 662 536854217
662 663 83747600
663 664 124155026
664 665 669639963
665 666 953939481
666 667 399570856
667 668 882480314
668 669 350176132
669 670 984467999
670 671 68554484
671 672 166596121
672 673 824624931
673 674 475309642
674 675 270651075
675 676 770316824
676 677 278852344
677 678 181051984
678 679 239681258
679 680 269010625
680 681 947850760
681 682 53199540
682 683 394376941
683 684 762751826
684 685 709580363
685 686 311089911
686 687 823746318
687 688 97561071
688 689 739625690
689 690 42983274
690 691 554616222
691 692 796315927
692 693 506388368
693 694 703822396
694 695 863463551
695 696 171130881
696 697 822397516
697 698 971712500
698 699 550781933
699 700 140976990
700 701 294070892
701 702 371564591
702 703 204346088
703 704 870523130
704 705 607800919
705 706 271153980
706 707 182216
707 708 685733510
708 709 140242155
709 710 441598419
710 711 784097019
711 712 561115765
712 713 637336756
713 714 478495630
714 715 649973334
715 716 156823435
716 717 813780160
717 718 523867979
718 719 700622004
719 720 707407761
720 721 735475604
721 722 762038303
722 723 31845754
723 724 603535715
724 725 401645159
725 726 431577783
726 727 425179440
727 728 14940137
728 729 180013152
729 730 539057950
730 731 557457223
731 732 179997656
732 733 801812166
733 734 497322652
734 735 337577422
735 736 368844225
736 737 364288739
737 738 512326695
738 739 261071188
739 740 495715357
740 741 634053353
741 742 277191896
742 743 560324459
743 744 439895042
744 745 517785393
745 746 716459625
746 747 762798378
747 748 757422761
748 749 571575806
749 750 995815567
750 751 868969239
751 752 108354458
752 753 361126907
753 754 120686114
754 755 961475003
755 756 609689035
756 757 393401287
757 758 192070680
758 759 668479296
759 760 90200982
760 761 160309836
761 762 958198710
762 763 549842753
763 764 89933347
764 765 244012813
765 766 611370257
766 767 694385316
767 768 602721480
768 769 600961591
769 770 652630284
770 771 491915950
771 772 651624379
772 773 187517392
773 774 558024287
774 775 173503828
775 776 985479131
776 777 665831056
777 778 820151831
778 779 162270552
779 780 355223589
780 781 799565272
781 782 419582259
782 783 23946173
783 784 158576553
784 785 5021858
785 786 149591800
786 787 476199787
787 788 604844945
788 789 606963559
789 790 555343269
790 791 194036474
791 792 423892991
792 793 215442240
793 794 689673972
794 795 159293866
795 796 805344141
796 797 623626187
797 798 756740335
798 799 862901484
799 800 619859494
800 801 744239502
801 802 535219089
802 803 490406940
803 804 154216037
804 805 108866084
805 806 370491812
806 807 790138361
807 808 57826494
808 809 566249818
809 810 877534670
810 811 342069271
811 812 119106672
812 813 878255018
813 814 681392014
814 815 580260393
815 816 978456036
816 817 435068919
817 818 968247084
818 819 508930683
819 820 186626999
820 821 682350137
821 822 420345212
822 823 65260847
823 824 595464519
824 825 805163931
825 826 628357465
826 827 589898601
827 828 645643715
828 829 399658251
829 830 190747956
830 831 983621688
831 832 175986890
832 833 754602888
833 834 811841698
834 835 959542506
835 836 783187648
836 837 927602577
837 838 49606770
838 839 249825407
839 840 433658341
840 841 361292623
841 842 70766452
842 843 997049767
843 844 544757026
844 845 936615791
845 846 50364608
846 847 412901292
847 848 81320892
848 849 279228817
849 850 146184073
850 851 167469756
851 852 468931836
852 853 59556810
853 854 518682574
854 855 649734939
855 856 239901850
856 857 431415345
857 858 841499784
858 859 725036957
859 860 521576446
860 861 132948921
861 862 959511986
862 863 617445215
863 864 477008092
864 865 517307317
865 866 278035215
866 867 588414051
867 868 326081237
868 869 292107826
869 870 274793958
870 871 640987460
871 872 929890984
872 873 345771621
873 874 582786764
874 875 293770155
875 876 673342373
876 877 80420036
877 878 127201965
878 879 84776610
879 880 999367222
880 881 473887490
881 882 655684495
882 883 206873028
883 884 664168321
884 885 592353000
885 886 361319722
886 887 824241213
887 888 938735102
888 889 225123122
889 890 629640362
890 891 756262258
891 892 62696003
892 893 895367614
893 894 148893236
894 895 723125933
895 896 373577962
896 897 914321959
897 898 965150084
898 899 628494791
899 900 58552148
900 901 482147271
901 902 963964330
902 903 298338242
903 904 629511549
904 905 896732629
905 906 31589024
906 907 952164016
907 908 157908730
908 909 539190266
909 910 781946893
910 911 987789683
911 912 237386577
912 913 402356347
913 914 890863408
914 915 276806936
915 916 11411325
916 917 518349368
917 918 822527814
918 919 991699700
919 920 883243817
920 921 375820680
921 922 984358598
922 923 523233382
923 924 433839259
924 925 114421578
925 926 782023167
926 927 641085953
927 928 841364904
928 929 668967217
929 930 291666824
930 931 897565897
931 932 293607883
932 933 72642278
933 934 239722311
934 935 478253693
935 936 665873415
936 937 92582831
937 938 861952884
938 939 531416471
939 940 438697999
940 941 29768352
941 942 502513526
942 943 876148957
943 944 663879745
944 945 744296066
945 946 738689120
946 947 991792277
947 948 561608581
948 949 821999937
949 950 243012085
950 951 797569211
951 952 895097312
952 953 930565614
953 954 815613502
954 955 9048940
955 956 997565264
956 957 232555513
957 958 292268107
958 959 834593091
959 960 565398884
960 961 140916920
961 962 513788894
962 963 406089848
963 964 732538621
964 965 293523744
965 966 453678852
966 967 860255759
967 968 573485405
968 969 317290714
969 970 398290727
970 971 237204723
971 972 183159161
972 973 972852308
973 974 974250272
974 975 903537545
975 976 663152724
976 977 965963324
977 978 14418967
978 979 473579873
979 980 459196081
980 981 379231372
981 982 988960353
982 983 2463668
983 984 92360502
984 985 490855860
985 986 836348368
986 987 244200833
987 988 549078344
988 989 161284061
989 990 75640059
990 991 348387386
991 992 76684529
992 993 351994003
993 994 686725757
994 995 776435678
995 996 912221277
996 997 862133408
997 998 225417192
998 999 584566219
999 1000 605089624