1 2 3 4 5 6 7 8 9 10 886 1819 3317 4391 5078 6022 6255 7309 8046 12270 12572 14517 16082 18880 20671 22166 22272 25751 26189 26947 29001 29030 32276 33376 33420 33832 36380 38201 40802 41171 42515 43842 49130 49793 50173 50600 51165 51176 58152 59463 60153 61848 63197 64103 64501 64530 65478 65541 66379 66773 67389 68226 68597 68982 71050 73205 73528 74507 77326 78241 78513 78837 79116 79711 82155 82282 82503 83183 83621 83646 83808 84964 87277 87856 88485 90803 91096 92290 92651 93570 94792 95189 96787 96920 97114 97409 98312 100696 102904 103142 103963 104555 104886 105165 105863 106378 106986 107024 107956 109199 110236 110539 110716 110801 110901 111156 115260 115879 116294 116794 117083 117657 117661 119291 122438 122577 122619 122897 123316 124060 124957 128462 130089 130824 131315 132179 133022 133412 133971 136255 138240 139719 140222 141221 142707 144113 144542 145044 145287 145648 146600 146740 148157 149418 149898 150332 150557 151200 154094 154605 154843 155521 155567 156314 156823 157002 157792 158921 159141 159418 160909 161740 161761 162021 162441 162990 164389 165453 167202 167287 168000 169817 170140 172297 172420 173424 174618 175344 176027 181423 181808 183127 185831 186150 186508 187303 187963 188214 188387 188594 189242 190408 191399 191780 192565 192836 194308 194375 195067 196745 199679 200803 201653 201922 204006 206910 208235 208530 209361 214697 214883 215154 216151 216545 216591 218305 219333 220708 221031 221348 221352 221757 222709 223265 224088 224405 224511 224983 225172 225610 226485 227461 228294 228653 230020 230082 230443 232379 232747 233994 237071 238782 238797 239927 242769 243079 243348 244036 248074 252170 253901 254586 259698 261311 262264 262611 263222 263807 266054 267759 267967 268705 270140 271126 271314 271441 272011 272982 273082 273395 274129 274600 275780 277258 277477 277664 279884 280681 282444 282521 282879 285131 286403 288514 288786 289281 289290 290609 291092 291336 291645 291735 293530 293896 294173 294942 296398 296979 297131 299103 301573 303999 304844 305487 306308 307942 307949 308345 308604 309255 313274 313474 313987 314034 314697 315237 315515 316705 318014 319152 319885 323520 324025 324807 325355 325548 325789 326649 328883 329444 330833 331098 331565 331871 333011 333403 334583 336616 336658 337227 337289 337317 338948 342402 344021 345938 346527 349602 351487 352278 352320 352370 353010 353085 353343 356384 356428 358961 361277 361878 365206 365334 365736 366591 368143 368795 370629 371893 372524 372740 373107 374431 377176 381319 381869 383480 386089 386299 386930 388482 389331 390894 391461 392997 395343 397826 401759 402395 403143 403446 404760 405391 407181 408099 413167 413387 416506 416909 417829 418021 418838 420683 420888 422909 426330 428176 428250 428385 428665 428761 429481 429563 429725 431553 432215 433657 435379 435941 438664 438952 440606 440823 441010 444529 446752 447073 447765 448010 450097 450454 450541 450732 452978 453083 455720 456709 456732 457049 457300 457653 459564 460671 460779 463839 464054 465333 465834 467091 467694 467963 469565 469927 470403 472604 473298 473508 477048 477459 478756 480634 480716 480893 481029 481715 484122 484734 484858 485725 487225 488218 490412 490859 491290 491356 492989 493781 494606 494850 495452 495582 495673 495725 496629 497054 497066 497644 498781 500249 500640 500692 502900 503448 504323 505224 505542 506084 506208 507008 509519 509905 510125 511006 511994 512113 513906 514171 514224 515505 516372 516573 517655 519412 521163 523349 523812 524396 525490 525646 526282 526686 527530 527691 528333 532264 532468 533153 533237 533841 534924 534952 535955 536343 537196 538755 544561 545501 545849 546744 547351 549540 550398 552227 552356 553297 553381 554026 556830 556859 557102 557421 559144 559513 562725 562999 563308 563451 564925 565789 566054 568470 569287 570808 572994 573675 574262 574940 575788 578272 578356 580030 580742 581501 582148 584408 584736 585712 588893 589802 594379 595820 596692 597120 598592 598851 601577 601995 602092 603661 604367 607058 607392 607413 608090 609493 610254 614043 615124 616596 616936 618582 619023 621979 622150 622265 622964 622983 624071 624145 629301 629646 630083 631137 631412 631880 632016 632070 633923 634101 634336 634386 634500 634766 635324 637991 638344 639504 640328 640499 640978 642384 642477 644259 644945 645155 645377 646356 646709 647412 648011 648388 648716 650281 650793 650906 651800 655179 655488 655888 656641 657138 658281 658691 661611 662377 665780 665979 666335 667065 667268 668473 669576 669603 671474 673296 675163 678496 678857 680556 681436 681695 682486 684724 685373 687062 687067 687602 688373 688661 690062 690271 691159 692715 693014 693619 693760 694505 698483 699110 699339 700785 700901 701591 703274 703500 703657 704137 704302 706282 706319 706886 711539 713023 713548 713795 714970 716860 717057 717720 717740 717970 718217 718558 719971 720582 720951 721815 722146 723191 723567 724406 724779 725128 725513 726021 728479 728537 729729 731128 732251 732875 734424 736213 736593 737015 737058 739314 740005 740378 741336 741801 742478 742660 744448 744615 745112 745217 747481 748200 748265 748662 750747 750932 750997 753433 756539 757252 757790 760100 760423 760916 761262 762239 762475 762698 763624 763927 765254 765742 766596 768866 770952 772354 774314 776655 777414 778387 778846 779486 780204 780533 782030 782733 783691 784433 785815 789249 789288 790662 791753 791768 793540 793871 795979 798314 800479 801662 802902 804319 804589 806381 806716 807188 807805 808374 808410 811765 811957 813362 813505 815424 817935 818068 818995 820744 823227 824620 825459 825613 827064 827461 827914 828529 830549 832139 832152 833304 834009 835487 838349 838619 840762 841945 841953 843093 844841 845130 845729 846276 846514 846699 847430 847449 849554 849584 849758 854973 855325 855802 857196 859205 860399 860654 860974 861210 861398 861475 862514 863950 865695 866496 866916 867308 868068 868435 868464 869051 869647 871609 872413 873201 873508 873527 874087 878545 880193 880393 881925 883491 884637 884648 886072 888541 889138 889279 889474 892232 893068 897690 899440 900262 900377 901140 901945 902367 902402 903244 904189 904348 904726 905128 907209 908006 908865 908992 910501 910887 911256 911940 912080 913447 913626 915072 916568 916649 917199 917378 917445 919509 919772 920243 921368 922113 925724 926415 927173 927919 929228 929711 930330 930819 931514 931999 932155 933562 934048 934809 934850 936114 939603 940959 941099 942008 944497 945239 948021 948342 948985 950315 950565 951966 952252 954176 956914 957043 958178 959137 960218 960871 963254 964228 965853 966248 966334 968124 968958 969186 972623 973622 974650 975477 979541 983794 984782 985176 986301 988698 988839 992101 994533 999990 999991 999992 999993 999994 999995 999996 999997 999998 999999 1000000 |
1 1 3 4 20 36 252 576 5184 14400 511700553 951541904 779554757 285760074 147499443 183442028 67487245 349664647 658530214 465968110 44438184 401790921 386936098 244487533 710896332 850808827 882612643 758991684 889550623 586539592 145804386 108753828 606909776 750897186 632568905 449312001 666571661 270035348 426254547 406818807 637282911 595699026 965827960 853027950 380084732 611115266 465688214 631429396 433953120 275437486 795751997 869781533 441866669 270732198 239616855 899445139 543049683 168722299 394763988 697682036 561209659 798305928 381613463 86496464 516359874 18618095 239009437 323612346 798391003 855046879 948728986 838210034 726890057 966420663 989708156 550751737 753979178 922215397 995210052 73296744 615686629 479390622 14170832 612675499 344914442 757173825 874906559 227007557 800204794 456046778 24228070 16304823 756247235 621172767 280361542 670768388 163106853 437430806 90763542 888860191 905618233 525279627 205145440 21685522 886913741 383916499 541066794 814537680 169813216 693882689 523427684 88657179 642759776 560668889 892008126 761955500 661026600 444075494 723397146 737516089 531677315 742527378 235412296 455771066 501419677 892143411 767530530 960233664 273295256 821885469 972296811 283953461 33889574 420020565 364740991 909567117 642256716 852068956 83986294 125472446 778992549 708443771 724992062 685137801 960011556 24231968 810098542 84667179 446047164 660820080 433651754 255216534 829042331 547234441 588623631 469322470 869298666 619278994 389961669 609344873 577954832 334957494 581779423 803554997 395873562 219047083 758421 139716329 199667985 43199005 872878245 701948144 397187376 510226004 959858574 493290522 389803465 966757615 86344062 716818914 852969272 59640600 417724071 14898303 362078162 967971692 266293181 638440922 719981033 10473693 848457998 948646320 35728750 951166141 520164864 900558345 363837495 406220395 172297138 642012665 845672906 610407928 85357752 399419016 285168773 146467875 686568518 213274710 158559035 684719105 862858278 766255358 983852403 158087414 835456110 932121203 800877813 78888688 905112199 510548257 387489806 498943414 927895767 143090209 47699944 623029003 451744988 685251695 208112710 627251470 337508029 249828899 295617501 165958182 778743207 115461183 626392859 213670869 936493116 60773597 12898442 896581944 411131038 155180176 712501086 487224273 144721742 181516824 582813667 464405178 809046713 990247788 689562151 342573810 319243581 982164737 272052893 34760653 319536872 760708992 945056661 419345566 71362749 281450654 234661476 522071704 189112598 326205813 133022698 840802376 121018746 493699485 338731804 320876547 393545274 511648138 387727458 789674580 924776939 627618552 239930564 246226673 818714894 466284523 681580076 870423896 431370575 215604114 973639912 871578373 763686134 331572916 467415466 222792263 511070840 291521690 703800025 293490075 685273646 67355193 730731187 186206559 999627104 247524600 590393684 783588857 659734994 181072569 606837418 321165838 459948164 7884970 496716316 148119256 897923790 135587384 603430372 802069368 316164033 571545701 990795260 220509002 456395109 877317858 78790985 893943721 626396223 447695735 774741533 313164109 745038703 483774432 879932856 860871406 169993765 354199329 14660031 461012135 558037599 687295205 749593708 148836836 727980480 269242639 112003218 746954275 481350238 772410711 630105195 951056486 862489904 349559076 38878874 2583840 23640187 158618967 361242493 821854145 612826425 109838772 616611954 478796303 531832040 671484221 948121054 998794605 900939723 423574217 961423466 924663260 19935956 563673777 229800965 601749654 529018649 761557363 981026248 905842290 460492322 775782985 91192727 545384543 445573226 810109482 893876421 523138036 938826545 692316369 570539879 363345892 693364441 140658163 327891394 805646712 581527002 919758788 768782305 587447146 578621819 531064379 146398739 727366342 455351195 608485443 715028116 351754043 469956565 718509872 781415691 45640952 275927275 631609061 950126195 504371105 705612706 621072189 900429923 677606520 510776694 460405409 665469320 763254367 273765156 386069019 208350852 440926036 681190502 142792375 874977918 592925917 267049833 896834733 322837828 305013525 231257346 156008568 995896007 628319775 216394564 98724476 40592893 586803807 200622813 937965042 293668614 757451380 92342151 579561803 598889294 500618284 17623036 343745391 40346077 673695439 761186854 809611656 350464647 505115162 447154185 556064734 495326492 346561864 427528428 37798904 417017856 380864540 480767651 751988884 604676803 879726211 936177879 615154062 306044524 547189979 90120026 473226675 298048597 605345814 573586975 31624815 166874708 592034864 99844945 692486849 956493794 980138750 643733367 729414469 350616199 4883810 22363116 518983121 201481553 538927771 519641960 953865841 519020197 873000326 108760712 4135959 422193373 878708221 850411076 185528158 599840562 320189825 587665047 63429133 231491374 140359256 44851373 291573924 846592012 75134838 155792996 483401657 910083323 599345462 709290492 124371844 851124724 100048008 865860749 326609068 666328320 825367757 227811721 656597284 712196704 808096630 4361231 556892358 305275537 127848799 357251477 64508760 338157928 969202662 805428515 870376032 425632191 455508365 647827791 79958737 257716901 801066455 494522519 482403650 344220740 289194789 327948948 783208537 422465224 628996839 574646768 381735301 295018596 187587759 285707378 484528324 764376603 962950500 137881316 435205667 137477626 782012588 945556170 791464646 665076069 151434808 795185264 52318995 395153209 527766036 112465942 382370937 774038649 833385262 628296723 920961253 348933356 688517183 166031824 487529102 841741430 592345507 485178655 234322285 222785518 270522011 108382385 426446063 894670819 702705005 746905390 587391043 537543629 226205035 101607003 807275984 697981741 711823762 49040724 122620803 511989603 938560574 902344119 158973522 691257874 623946109 691068855 714339422 922429140 309344597 138888453 867803422 122544481 989114266 226291466 58734209 350212317 654525851 240787783 254890618 243089585 570732727 289152919 850183360 723656677 727620877 230110092 544482273 651641046 787143850 844685306 946992025 406624242 299098152 651973679 888956607 136187267 965566106 180134747 122574806 54134862 129243209 401251194 434878256 128198195 480408209 263479392 509493713 447922390 834374762 446450099 53847689 738827177 877461302 982962356 925684345 824898493 360640179 520546054 527321147 214785488 844428908 704905577 844171699 837308693 168406753 114315280 134603417 202745359 100441403 354405419 753377936 102629268 418424004 792167807 309255668 756933764 380945448 964881603 991374284 834039912 960787464 402805480 240192018 80862795 312285595 436146325 105120918 265319986 345872334 561915087 800167949 602914382 776116723 533333603 436317408 701491958 673701133 382705322 560427192 181753806 467937081 252944007 953369618 136336545 404400197 401935704 400332443 803442061 507465821 157471437 433046895 653359402 429000843 352487514 98319558 570671741 159717129 585992290 16070903 618600694 661104167 956844763 125880047 248895057 955240662 35236509 690069258 831023951 153030862 884343077 377425771 494011691 96964922 385216813 265533858 5895553 586529616 170642392 75716806 669566504 799536801 255573432 767568920 748322826 607018800 959714965 326892777 764752727 830845449 922757396 175494261 323746564 303439697 687556916 578561518 365598136 205960364 143798436 372689181 53583000 288562881 191678713 928701661 13737267 735473418 405410738 366706239 23585877 968921885 623556385 414922300 708803566 434831686 6145167 41855459 177296025 350731675 276160671 33762285 951151730 638850967 871301671 792144395 750961023 331835304 478459951 191485732 455726192 583638784 577855144 512854397 460274598 730072578 589371879 495838055 674766995 716957033 6139782 879036602 71923398 541041371 368978740 549312272 866745655 56439623 510961563 778611477 535893222 465094992 247836839 925744185 538089464 54807498 678809323 895342739 315705269 26649583 644339623 611211370 174249912 889961712 493355819 130043274 105019867 16793115 864779625 974132156 321897477 167319585 876298857 979320722 931086465 694714191 18692868 853882772 484159266 123245431 346766898 571538433 147692475 463509585 823109245 427888499 840833373 851310161 18535045 396864630 507305850 792602380 147267007 986924678 460537683 7866365 970646945 956016987 384831520 143305331 498058845 590419541 291474265 692301287 468437918 521787006 871655100 2294754 139064497 352019289 221339546 109375660 850878095 611669124 257767671 50310091 873472088 705236101 912812713 141295990 526776250 850804417 494370762 273129434 674612951 53925731 770293050 807786741 173495232 196261365 868848242 182370267 134004042 433722044 709486211 349327595 878801772 220933171 444407501 562883848 772734325 848073800 249507540 609864278 563409 636233720 376829057 522604437 356393983 738978333 977763687 209931071 91235343 127329076 393575997 348591691 312009822 538924597 550085469 611236792 235249186 364474863 859508109 199481648 160923981 796347554 567386378 386535806 860390594 605574700 757203250 151948311 411525115 39058004 807210567 261206295 791868295 462792858 745020084 649961713 919966746 703762549 220903754 949179080 663126121 210941685 85338935 804927978 399039053 308560995 547250570 784516286 262315881 664422638 562293162 459478403 364371690 155999174 277373591 651264611 261214504 772675529 98359003 194724392 787226244 375810144 112435161 640921185 118337367 968930772 748611570 969074377 914622408 354741077 882105442 332785998 418651775 313737347 649107384 228662477 345764318 939203958 594640686 439315485 853982686 512311327 576447024 159755982 543077884 59602319 901366560 276614998 612988719 38089483 368464928 898761332 426947348 167680011 |