1000 999
1 2 1719140
1 3 923865634
1 4 259413763
1 5 347315639
1 6 305035308
1 7 140052796
1 8 413509389
1 9 275927001
1 10 213387877
1 11 84753098
1 12 74037414
1 13 60554017
1 14 454371813
1 15 593228087
1 16 742236430
1 17 534752069
1 18 240618642
1 19 43156498
1 20 632581219
1 21 160362318
1 22 282762648
1 23 579774969
1 24 257386521
1 25 900200250
1 26 425020265
1 27 353694564
1 28 909128810
1 29 157394001
1 30 373761368
1 31 322531499
1 32 336632625
1 33 91878271
1 34 477961322
1 35 863307067
1 36 787306338
1 37 447892796
1 38 526532423
1 39 617601933
1 40 307115430
1 41 509913149
1 42 915990742
1 43 481042769
1 44 234833979
1 45 165656158
1 46 888472824
1 47 405738791
1 48 643394935
1 49 626650209
1 50 348377070
1 51 130051909
1 52 988955255
1 53 98530459
1 54 139075184
1 55 596041018
1 56 718751651
1 57 66449808
1 58 738358911
1 59 831419484
1 60 662285779
1 61 938615504
1 62 740879128
1 63 474511598
1 64 469773224
1 65 407268397
1 66 234705728
1 67 653413104
1 68 972890282
1 69 141522221
1 70 316289281
1 71 658001760
1 72 368282825
1 73 925395153
1 74 936377905
1 75 677101744
1 76 100490788
1 77 278897212
1 78 537984478
1 79 167444663
1 80 548023957
1 81 332933860
1 82 344921862
1 83 994475829
1 84 527893667
1 85 295266157
1 86 624137937
1 87 952570993
1 88 632975080
1 89 41133825
1 90 157149014
1 91 320750679
1 92 702392920
1 93 647589432
1 94 738696090
1 95 766268275
1 96 549220665
1 97 310319574
1 98 274805309
1 99 69932704
1 100 308256462
1 101 509950220
1 102 953824472
1 103 62742739
1 104 10311341
1 105 599988785
1 106 181896732
1 107 399677769
1 108 989101968
1 109 574993766
1 110 548196389
1 111 248385382
1 112 852734659
1 113 133113375
1 114 179882312
1 115 952981729
1 116 978749663
1 117 198679178
1 118 701082160
1 119 243059705
1 120 315762649
1 121 819493325
1 122 137153710
1 123 267524224
1 124 579222528
1 125 598851926
1 126 780532309
1 127 923926380
1 128 868690736
1 129 259594268
1 130 22071486
1 131 222112707
1 132 589792663
1 133 282421514
1 134 636405889
1 135 918892727
1 136 562451633
1 137 72905186
1 138 885390758
1 139 967266035
1 140 425510009
1 141 322917226
1 142 18620342
1 143 976369365
1 144 869657269
1 145 487863012
1 146 855863517
1 147 480950339
1 148 862883936
1 149 686794879
1 150 300537785
1 151 36703306
1 152 379196380
1 153 422726577
1 154 510957358
1 155 123012730
1 156 979363472
1 157 686487426
1 158 907733474
1 159 596447255
1 160 403662495
1 161 102146708
1 162 21320563
1 163 757311314
1 164 511949947
1 165 704297995
1 166 393808632
1 167 561651326
1 168 494164526
1 169 22187233
1 170 681696899
1 171 383995546
1 172 113933928
1 173 704365664
1 174 984378754
1 175 609317028
1 176 189602276
1 177 840210400
1 178 741392844
1 179 898010196
1 180 147261726
1 181 998609505
1 182 376573848
1 183 687971660
1 184 163508127
1 185 586983722
1 186 499576349
1 187 281969067
1 188 645475045
1 189 889428061
1 190 816670308
1 191 190422012
1 192 595167964
1 193 217931987
1 194 6095637
1 195 920405494
1 196 432163636
1 197 672926776
1 198 770809328
1 199 937482175
1 200 204992283
1 201 989161264
1 202 536072724
1 203 578016241
1 204 593557803
1 205 56450543
1 206 247336828
1 207 101502244
1 208 372468806
1 209 240215248
1 210 940023119
1 211 347639586
1 212 921990876
1 213 143522887
1 214 873722676
1 215 786881571
1 216 24141137
1 217 927391948
1 218 829950145
1 219 578733788
1 220 18371179
1 221 542122584
1 222 185588915
1 223 139082202
1 224 820794203
1 225 306519168
1 226 421191913
1 227 772889598
1 228 25695069
1 229 646995248
1 230 400513336
1 231 162321549
1 232 666083499
1 233 783586083
1 234 511854227
1 235 852911131
1 236 699409385
1 237 77562748
1 238 891157242
1 239 533316548
1 240 701577059
1 241 672774011
1 242 24305153
1 243 578362622
1 244 706155215
1 245 109291375
1 246 877905832
1 247 128369900
1 248 366736951
1 249 2443105
1 250 455786759
1 251 744904481
1 252 415219553
1 253 685321009
1 254 227435047
1 255 310231962
1 256 679484108
1 257 981280183
1 258 755504507
1 259 835394532
1 260 667711197
1 261 735019574
1 262 823450906
1 263 337551827
1 264 997429250
1 265 795845094
1 266 724641711
1 267 124462420
1 268 322796726
1 269 691004301
1 270 974753868
1 271 620622061
1 272 873508098
1 273 965612866
1 274 113835047
1 275 165541305
1 276 99228017
1 277 959703449
1 278 560776554
1 279 692636649
1 280 210882863
1 281 91862204
1 282 91508075
1 283 387099740
1 284 482020994
1 285 923638737
1 286 672702493
1 287 557120522
1 288 702444699
1 289 728164477
1 290 395327951
1 291 52707262
1 292 638543901
1 293 274782064
1 294 731763297
1 295 222048464
1 296 530714515
1 297 787383946
1 298 217523870
1 299 313718412
1 300 461370740
1 301 776903339
1 302 556167764
1 303 736811656
1 304 485124856
1 305 896448023
1 306 730050780
1 307 238120733
1 308 485897632
1 309 425698144
1 310 732722942
1 311 69519622
1 312 350578115
1 313 77647395
1 314 793066735
1 315 265325841
1 316 237767448
1 317 853432969
1 318 112061189
1 319 292449595
1 320 925478062
1 321 727153683
1 322 666361393
1 323 949094645
1 324 386412842
1 325 828164276
1 326 666609134
1 327 952886585
1 328 749984090
1 329 629808277
1 330 742856907
1 331 138115945
1 332 935578555
1 333 271547563
1 334 122212582
1 335 531327206
1 336 380839781
1 337 711395038
1 338 220531236
1 339 931362353
1 340 839367948
1 341 374651206
1 342 646472876
1 343 795311547
1 344 416398131
1 345 414682555
1 346 584489045
1 347 770407276
1 348 485514687
1 349 947272516
1 350 534940314
1 351 855982139
1 352 746152092
1 353 534615713
1 354 348198528
1 355 640464173
1 356 884808712
1 357 307794403
1 358 250211686
1 359 440158558
1 360 558778510
1 361 691297868
1 362 637674733
1 363 470404064
1 364 433454618
1 365 825482767
1 366 549193264
1 367 706192051
1 368 868272153
1 369 520107124
1 370 597381426
1 371 800485504
1 372 750644298
1 373 701655259
1 374 580695784
1 375 966988148
1 376 568184888
1 377 899982899
1 378 626224038
1 379 938111409
1 380 968020479
1 381 949497636
1 382 225048297
1 383 764461090
1 384 51187494
1 385 410371069
1 386 69784009
1 387 107255813
1 388 534417206
1 389 302220423
1 390 869628566
1 391 419435496
1 392 550419769
1 393 395262363
1 394 152326521
1 395 693029176
1 396 467359927
1 397 463341928
1 398 544462530
1 399 654152796
1 400 123167743
1 401 187835858
1 402 625671590
1 403 345649449
1 404 103444171
1 405 39226444
1 406 380284456
1 407 656538214
1 408 571491376
1 409 517719136
1 410 449376818
1 411 135062865
1 412 392607777
1 413 956217015
1 414 980382568
1 415 356237662
1 416 336193179
1 417 557452013
1 418 461872137
1 419 674456488
1 420 129397879
1 421 650414916
1 422 134228736
1 423 296106607
1 424 191691273
1 425 141272831
1 426 933018018
1 427 209187398
1 428 127965186
1 429 900936316
1 430 153745642
1 431 66279947
1 432 822114690
1 433 251459227
1 434 950697976
1 435 972058212
1 436 656924167
1 437 902716702
1 438 360804771
1 439 853528132
1 440 570563546
1 441 74895956
1 442 16617369
1 443 869062500
1 444 887616202
1 445 70327346
1 446 656251791
1 447 987948499
1 448 394099298
1 449 563472988
1 450 732741200
1 451 600010195
1 452 789039383
1 453 849884622
1 454 745254509
1 455 465555260
1 456 431388544
1 457 872738502
1 458 598960705
1 459 666272663
1 460 250818251
1 461 892289540
1 462 206593152
1 463 275505532
1 464 244385104
1 465 738185618
1 466 910286071
1 467 100076929
1 468 866932253
1 469 252292670
1 470 889909135
1 471 483743948
1 472 602906885
1 473 441907265
1 474 709948130
1 475 538293553
1 476 481338580
1 477 586145623
1 478 942407205
1 479 551040911
1 480 183193583
1 481 33616076
1 482 753278615
1 483 904407532
1 484 90677988
1 485 126370242
1 486 156658325
1 487 379156971
1 488 648947956
1 489 367898427
1 490 786051337
1 491 578896369
1 492 256377153
1 493 391388170
1 494 506528916
1 495 171391506
1 496 558650776
1 497 689928606
1 498 560764874
1 499 773209472
1 500 59167771
1 501 120489410
1 502 675077972
1 503 888141025
1 504 108434632
1 505 201311155
1 506 659867327
1 507 259701108
1 508 760651473
1 509 907073233
1 510 464682125
1 511 427033243
1 512 858467654
1 513 681994655
1 514 331108686
1 515 418032225
1 516 847452018
1 517 76302301
1 518 103552170
1 519 136936679
1 520 748572477
1 521 318151100
1 522 110055255
1 523 403119692
1 524 780303914
1 525 338053291
1 526 612679823
1 527 343994937
1 528 587305090
1 529 949471640
1 530 435043735
1 531 714734660
1 532 481886781
1 533 831129022
1 534 148110145
1 535 866983734
1 536 145746478
1 537 196388042
1 538 764831140
1 539 438059538
1 540 933609540
1 541 373690080
1 542 203709551
1 543 497628314
1 544 562276960
1 545 292952307
1 546 966343544
1 547 603344337
1 548 596889600
1 549 385669432
1 550 870445158
1 551 119468140
1 552 893990064
1 553 636997081
1 554 446839355
1 555 550536346
1 556 478586077
1 557 223549645
1 558 679802895
1 559 42161883
1 560 107354691
1 561 989855001
1 562 852187077
1 563 191052857
1 564 972162362
1 565 422512451
1 566 270972984
1 567 446210338
1 568 756813840
1 569 870159739
1 570 615679512
1 571 354053499
1 572 550080723
1 573 474377743
1 574 665395914
1 575 709098907
1 576 802670928
1 577 896212357
1 578 7908663
1 579 606730172
1 580 84738708
1 581 341212515
1 582 744347686
1 583 251716924
1 584 263594490
1 585 272689158
1 586 145786297
1 587 582317665
1 588 341568155
1 589 495323309
1 590 488063535
1 591 636892018
1 592 620821920
1 593 174177231
1 594 597869076
1 595 271560720
1 596 246201357
1 597 784346046
1 598 483280488
1 599 657748490
1 600 976708981
1 601 618272832
1 602 812653835
1 603 315068452
1 604 594171364
1 605 231123902
1 606 708569326
1 607 757688152
1 608 982569702
1 609 293002369
1 610 10062590
1 611 415217994
1 612 593689240
1 613 124352748
1 614 132215043
1 615 127908019
1 616 870802247
1 617 521164238
1 618 17051565
1 619 77292509
1 620 664963989
1 621 10848822
1 622 712099424
1 623 6241185
1 624 673060120
1 625 151583315
1 626 858403850
1 627 512812441
1 628 5330806
1 629 121924289
1 630 897486987
1 631 199581063
1 632 556906994
1 633 211708012
1 634 76524234
1 635 145022535
1 636 634205996
1 637 981462362
1 638 212767177
1 639 108572002
1 640 117390053
1 641 616127391
1 642 657943125
1 643 937949038
1 644 280370365
1 645 397177620
1 646 151547761
1 647 482916585
1 648 217082234
1 649 708284953
1 650 655484415
1 651 298019393
1 652 160524360
1 653 743653829
1 654 627776451
1 655 934568740
1 656 743047730
1 657 214131103
1 658 534236401
1 659 581699092
1 660 707463330
1 661 816759436
1 662 919772709
1 663 150024484
1 664 409814081
1 665 471822054
1 666 70130114
1 667 921765077
1 668 729643699
1 669 783534130
1 670 527125370
1 671 145023257
1 672 189313332
1 673 690822758
1 674 610875484
1 675 490220892
1 676 865786256
1 677 440075695
1 678 480083963
1 679 744155577
1 680 503182134
1 681 704286272
1 682 372846936
1 683 815881068
1 684 828179540
1 685 529904207
1 686 526727863
1 687 213629645
1 688 607807784
1 689 667273635
1 690 679499108
1 691 823133109
1 692 142679052
1 693 777142256
1 694 477193541
1 695 454859363
1 696 171655081
1 697 490002729
1 698 299475538
1 699 515990628
1 700 815560914
1 701 110970769
1 702 240314474
1 703 584845004
1 704 444559015
1 705 862589630
1 706 233624055
1 707 832071492
1 708 282197439
1 709 391955334
1 710 460181744
1 711 879580152
1 712 812336064
1 713 545844635
1 714 577719373
1 715 920827526
1 716 71695857
1 717 378624692
1 718 356411241
1 719 850483656
1 720 907686193
1 721 122924548
1 722 768845007
1 723 946488882
1 724 544778516
1 725 202192665
1 726 330403728
1 727 616973144
1 728 494886412
1 729 45537403
1 730 318753914
1 731 172721644
1 732 698739340
1 733 433664105
1 734 812486006
1 735 686407621
1 736 9368008
1 737 493481615
1 738 879584971
1 739 86888880
1 740 715550128
1 741 456590591
1 742 988326609
1 743 707004964
1 744 719531547
1 745 516267277
1 746 244505914
1 747 436477840
1 748 860451490
1 749 443551503
1 750 24508285
1 751 506898444
1 752 126949522
1 753 562493370
1 754 211135570
1 755 728199609
1 756 371761863
1 757 557947255
1 758 135725959
1 759 605377707
1 760 261860258
1 761 472028092
1 762 364985236
1 763 19862817
1 764 623559735
1 765 452997553
1 766 866205680
1 767 815241592
1 768 666951997
1 769 634782198
1 770 923696700
1 771 268299650
1 772 794314989
1 773 164113461
1 774 444716875
1 775 254208543
1 776 54639887
1 777 109513523
1 778 740391909
1 779 741696056
1 780 995419566
1 781 707595462
1 782 894263220
1 783 178091471
1 784 545767868
1 785 348851432
1 786 914181427
1 787 884589217
1 788 633694918
1 789 658678602
1 790 980162108
1 791 979933648
1 792 600132674
1 793 847621894
1 794 719210134
1 795 579712024
1 796 101815067
1 797 359739252
1 798 30870236
1 799 313341023
1 800 142007171
1 801 636313023
1 802 151208282
1 803 96307823
1 804 786575112
1 805 944869311
1 806 169395563
1 807 218832394
1 808 167380502
1 809 632794947
1 810 304425485
1 811 353533178
1 812 830191154
1 813 842994992
1 814 214412098
1 815 963413177
1 816 576495077
1 817 374383189
1 818 993105993
1 819 379112010
1 820 253556961
1 821 920380043
1 822 7463241
1 823 495386761
1 824 582071626
1 825 549830622
1 826 434446636
1 827 431154746
1 828 624279548
1 829 642996441
1 830 179634359
1 831 867643332
1 832 619287736
1 833 69041292
1 834 216953149
1 835 355713567
1 836 217422470
1 837 956542200
1 838 413723735
1 839 997238902
1 840 860068664
1 841 655161248
1 842 244906578
1 843 534140064
1 844 896801539
1 845 548683459
1 846 986783390
1 847 188955174
1 848 468904160
1 849 859376100
1 850 31527485
1 851 934729141
1 852 469446668
1 853 20882191
1 854 843761641
1 855 880641981
1 856 267837607
1 857 941549336
1 858 725939979
1 859 105290527
1 860 208810152
1 861 856758519
1 862 580979348
1 863 501410071
1 864 295815367
1 865 91742797
1 866 572917185
1 867 363550864
1 868 660683923
1 869 700722490
1 870 424357026
1 871 404053404
1 872 206224477
1 873 567734458
1 874 804848633
1 875 558845283
1 876 898475138
1 877 737289092
1 878 865763388
1 879 775542868
1 880 460048293
1 881 390636523
1 882 730107895
1 883 978831911
1 884 543158453
1 885 838737477
1 886 195497314
1 887 461157226
1 888 774182047
1 889 96949532
1 890 940675614
1 891 258170235
1 892 672000836
1 893 798255224
1 894 994749074
1 895 5355543
1 896 88231785
1 897 162814812
1 898 272088166
1 899 624127167
1 900 174841537
1 901 123794487
1 902 285977417
1 903 776147921
1 904 712171221
1 905 179790813
1 906 676148994
1 907 952137226
1 908 533851777
1 909 324971959
1 910 36959921
1 911 887180272
1 912 824338201
1 913 804499815
1 914 28818738
1 915 96226374
1 916 416536720
1 917 292736952
1 918 118152049
1 919 635159322
1 920 665695581
1 921 855324193
1 922 337410752
1 923 828569069
1 924 863044984
1 925 844206454
1 926 313203192
1 927 291329753
1 928 999646936
1 929 31477340
1 930 508939701
1 931 255746962
1 932 887759802
1 933 679701529
1 934 389400030
1 935 830136167
1 936 658220753
1 937 319947711
1 938 414109594
1 939 374382793
1 940 462789117
1 941 163106698
1 942 841423924
1 943 506504571
1 944 66646453
1 945 96547346
1 946 279624299
1 947 848923371
1 948 80227610
1 949 19692982
1 950 639333961
1 951 103692966
1 952 454664260
1 953 314407102
1 954 424786606
1 955 181163277
1 956 439387706
1 957 908772615
1 958 501497325
1 959 648364866
1 960 173385127
1 961 62613472
1 962 178382288
1 963 916340427
1 964 252172449
1 965 434117480
1 966 72949716
1 967 587967437
1 968 246176997
1 969 760367584
1 970 647837746
1 971 63283439
1 972 33232924
1 973 355676359
1 974 577989539
1 975 120973262
1 976 333057648
1 977 649593545
1 978 519326839
1 979 142367502
1 980 646194003
1 981 523208001
1 982 96795303
1 983 40403786
1 984 883448738
1 985 534236886
1 986 354259661
1 987 858640981
1 988 590434911
1 989 860304155
1 990 313301749
1 991 477820161
1 992 449101949
1 993 537719214
1 994 931406160
1 995 534003475
1 996 428620728
1 997 396957983
1 998 327784700
1 999 990186276
1 1000 321134425