100 1 5653 390762096 5075 15 10322 317543261 10037 218718271 149178197 311573055 92016753 313060995 55711467 73621475 193170095 165148351 267981830 290795204 222329951 313230678 303232267 6 1819 480877386 1522 51521626 253358800 294776721 219047459 271844966 10 5895 77337157 1103 70149796 22716231 13543067 11844167 5859593 43796010 54189407 55361864 41100846 12 18483 378393368 3418 18996452 322187046 77715995 365492446 75727082 318820923 168177061 342937121 235621742 109058196 76489500 19 13256 283779938 282 86620826 14613712 187962211 261237258 94232712 184679449 128273592 13011814 208480995 14290197 156984765 100196605 120396484 233200497 201020540 17671445 178999143 229992198 22 1825 636567821 1596 38708425 471284673 474683020 280364263 94946114 90830826 307914747 173660206 630328330 241731288 627312998 110982174 366042520 161848892 385421929 581320970 153493826 196166869 334092607 622824450 307636038 12 3098 143090802 1213 81518189 116938194 119387686 61653015 38535324 111478800 102664081 88637754 106590321 60972722 77743699 3 12306 905397960 2557 77993437 673582577 12 4727 736404281 2018 475879760 215611586 88008431 565908789 400324219 662318940 292650257 80828477 650024026 271761034 423592991 4 20671 433386492 19812 378358365 75793143 29019352 5 22636 890877036 14923 673017423 165520873 106235139 801927349 16 4454 740301753 1408 126398507 613570759 82666640 441770178 324348438 122723021 441576134 229767149 100960986 393608323 170925624 400650026 423569916 315693183 147218269 2 18593 546854178 12675 221158988 11 16521 971624629 4594 460377769 967245218 842243243 99741206 314343847 167462501 299953750 270402816 242543721 848468045 16 2237 413163262 214 220709887 286651858 166165469 163699217 342586409 370160929 404539783 126915379 270276955 71006073 352224985 258666771 4399917 130893910 126162867 13 3637 134623670 2918 8579501 88578826 105846350 61295159 20446312 64098296 64675287 74444367 7958732 68350852 66217847 115455716 14 15701 416656477 332935931 388164604 238596529 263244266 16045185 33715502 390083734 55219872 216065199 103895740 243887020 193166551 241246026 24251816 23 28869 861762220 8395 384787514 765623376 461652266 670125787 110559039 645031035 442733540 639613089 567726006 687463910 566952213 160396486 274618725 664202147 780559770 696241174 170885406 374605941 247656283 610102708 36461117 406970596 9 14757 300531890 11464 226693864 222270980 265990064 31187877 142858926 115326008 134395723 116939980 12 23990 586392107 341752780 371154147 107529146 141437294 158687795 224637578 130374752 419937017 491297072 175512368 409424914 241057538 16 707 466833364 566 385681500 190857430 58273653 92948764 305001854 295719078 219717712 429457254 416507591 442515468 281674814 154638390 137876464 10938062 157710530 7 13544 318959360 11741 40966762 282246890 329040 51833707 244746292 252016282 28 1306 956660790 634707061 615324074 769917797 705785443 778084388 167701789 618691386 82063817 944498689 468940078 627678319 879880130 933908922 256256454 942056155 621771701 852350509 401382017 916883866 810497877 779378612 4388832 235823138 901811194 622759899 512512100 696226374 336716972 11 17574 818034534 8437 156469826 633423485 243620906 684030024 586011987 784510249 459762317 674330460 762285699 800039036 12 10125 310642638 561 305749317 294476977 113453120 92763100 105277365 149289032 175016564 285759124 177582038 236178141 110367878 3 6027 339059148 4370 143857658 135800767 3 28802 912327436 27938 792851013 684780631 6 18361 575383968 3326 262929885 350774486 520679516 371204613 294584999 20 6259 566292214 1316 104444429 178079065 179400984 241845517 397916468 159290157 506569320 227743494 474370530 144652927 346001973 264792966 119096294 312841161 423961899 520690473 451883551 299997710 337455409 14 16680 348890472 324 130763865 201073792 206755562 148685140 261074903 62436127 167219956 347330259 237094569 61780247 27877945 245135858 287441511 4 18682 451366760 1682 380907852 304149435 157467657 1 175 24164901 58 4 233 461700722 49 153730286 61895896 415080426 1 8739 99482623 272937 9 2559 289315884 540 109253355 109592380 74219292 184014047 122977916 120939628 236677211 55067064 18 8932 179252661 8697 13070310 178729285 65155740 141353399 177319667 69232936 74373675 117673963 31575047 114706127 93230283 74189466 81483997 23003381 169607636 25953882 82247084 6 420 166960336 419 9282641 61969581 163825269 51825844 106228906 20 22991 599225788 12734 472034154 138613856 370063364 137023872 396324967 174492700 498110042 340274385 579870207 8910257 158395738 136278878 76007450 109742890 400278025 463231211 579741078 235027367 329192192 13 1682 643013776 867 593207279 200310660 555768869 344878348 326773744 562094352 497434883 553749331 378898082 138486405 11356648 573629666 19 5113 200354167 2931 187473810 87828821 164826104 16245297 140574005 79808694 153454831 122877803 55297902 194204520 21552415 170265780 1893056 79469389 133295310 106691257 136035543 187657673 1 9990 661737103 8813 5 6268 242930893 4406 46969938 193483989 26857356 48662581 11 9835 666626687 167338577 519993855 118210788 546880114 32565165 86724232 428931477 202061097 565113804 118751124 436993226 40 11248 951206385 9637 488173430 855551329 847209240 898245927 106227510 707955777 239286625 630998644 729312831 250906248 474465381 550056619 56358572 701461241 473029248 260130063 672344905 513442069 418509259 498208656 568131499 236381918 846014401 532175807 295124645 391722703 550559592 393943468 902759401 335033948 138674978 703090823 456679680 322034979 914858257 908266553 385304316 491445356 342458183 17 17158 809439300 11324 479129935 542949629 549740132 284750012 140251454 769997917 207777329 288557257 704961558 596746916 128479010 449750345 661965043 742698614 202840653 120577041 10 1181 64659009 117 45994239 32620036 50225470 19892233 8400420 52445302 62407880 53916899 7753664 19 763 193572634 288 111640232 107758519 59447131 184393566 184827733 44023239 164711475 139644515 105086009 35752398 113709237 171225778 27562135 93916481 63808157 23805626 40708100 51509498 2 6564 181577850 5061 171229684 15 7195 240183062 2038 206710142 236960490 63956643 233009396 115204908 228753364 178280606 234583016 237040031 18217631 190364314 90662045 237962876 39927847 16 1492 42304602 1411 20209561 36095202 33627904 41095377 32466776 37687000 20749638 21290392 15107682 15048077 5107640 40791418 24820894 2794190 21148045 4 22106 956892369 15523 53925773 615654074 201616921 17 16585 547730896 16491 205827021 371118300 539573407 170693301 423500052 40184646 310135992 121754425 115116960 234528349 359844048 413788205 93136010 376723881 340477182 65489470 14 8609 145752741 5889 118136047 123226774 134546308 135863301 15662402 121104048 62749617 90941647 58844503 40789117 46494138 67848120 101513745 40 10329 726433738 4088 95312921 242197121 168053169 313425108 322781443 218091677 492219760 674295662 142275877 607255183 303601036 630468685 181919196 446808627 79954215 580614900 186658836 371049732 313764309 443447235 82269582 278151111 711740260 703689443 190768588 376927312 305945094 505779849 387402664 563045268 725421481 160995262 151366581 488989770 63520238 194553898 375638491 603201331 312207742 14 1854 919089597 1171 151199995 753768362 605127823 712871895 554474756 471596991 524169963 145705519 745100487 255824701 893483796 231931806 171984733 20 4325 790492270 3167 682162197 18989574 100495088 161462354 561362080 758015900 281817818 271883164 443732000 773206826 75623302 736648332 743628131 341456748 548795935 152746973 55356978 662861545 223079653 25 11699 679314574 1069 513044637 35796980 677129685 124702589 102091866 289268643 619717777 27101035 34191654 534320185 239137151 236002371 37640810 300789129 502367736 210996569 288666646 146809906 644937031 669663237 401263194 172030156 49257088 659028809 20 3812 978352082 638 297115641 472595601 335480706 744389884 722060698 91513560 392662047 70144269 96266287 735614059 405919245 740877204 553302518 509863413 893653796 203669061 950476589 8883187 871384206 16 25148 834340143 1741 137892659 623428800 451106868 477038244 368269283 822065740 605142729 601150644 66082851 532069352 586523726 535234969 142975768 607470952 222182711 4 5982 916708293 999 256008478 505017083 130889824 16 5623 131081281 2726 29346331 68426789 33981811 110932724 19547144 111872605 72524540 82573232 63061516 7663684 35314398 97201973 99909058 37772916 98940326 19 1971 426216537 213949510 347528963 207549584 29470622 242341107 260530866 237900738 6529738 171313257 130075503 327418890 259305095 101646902 30631863 109306331 367228768 414484349 261692439 102481730 15 2119 10305973 2007 3818957 8254531 8948613 2493135 3479713 3709608 10011251 4206709 6830825 6191651 2618263 4344458 2347999 4804392 14 20054 979313082 19150 643537734 628707339 62303378 642846736 150404430 223189480 741940732 233010888 10257902 567316186 467746957 275954020 229307141 40 391 90449565 74 37547796 89187277 20128318 80004511 11368955 28433441 25965086 36591796 34796464 31336344 35205520 66924217 77067049 25177131 87950799 75746918 13303566 21556553 70106123 49905014 68782613 64708419 34490503 77200770 69510747 47978756 76179991 11508756 51919002 17817970 83714445 55717031 89521319 37335400 54755701 79116949 74051817 39917274 67313669 15 2312 435011768 1 102114613 87034568 142936791 205372711 347082542 267229767 354521163 376190989 65774472 278371742 385554263 36357992 101901832 310583627 19 17097 929860278 5004 31394695 473117844 211872253 501668772 342430080 859998992 713862608 459309797 656753333 203981409 746757461 244506043 66243990 359830035 818585319 725841636 784199551 383612496 40 3604 677116111 1449 354631444 639398221 397248991 2287286 227603247 270475930 123889000 277167307 186298180 340660163 117058822 557272792 4905028 275859857 390654540 8812500 571718139 438116283 31910761 532890585 355270530 361808560 552217942 504680884 675417446 90406529 523389252 614347906 218095492 44724741 322394829 327610715 117476317 183626816 594685868 390181730 59602823 603030043 582597346 1 3962 47402035 998 17 18279 979119818 1675 545805746 456664713 508308673 424475182 906563673 543074156 262910394 712391788 846155416 370024447 539169212 167659757 206831083 131405860 379624148 799477310 20 16538 383097199 10870 152768160 246166160 45214901 273174321 286483091 50854048 284123462 201283876 44922914 215139295 181721126 198258354 68612784 221880706 53791482 328756360 127001123 251179346 268796619 8 6669 666498633 4042 211807044 666229200 349045448 659002980 382289188 418390952 102900471 11 3682 167095924 228 14992673 85756759 147845444 148229101 129689376 81873349 68215933 26215140 113409819 89990846 23 14403 320656341 7303 96787042 41712548 250553012 287424383 100096819 145772050 178505695 10576054 250400122 52806159 306831016 99788064 99844108 157503475 238083364 78549358 231278465 297581371 55876613 67867299 268129509 58240133 14 13661 479317409 13011 252737821 65681321 183928408 223729328 381671203 264959091 202331076 54771069 322095344 260051307 27522186 417914550 170594105 18 11481 218058893 6760 15975100 116969224 49050602 13609769 52300181 38304874 36667670 202091692 20724374 103329357 149591408 130270664 214746942 21958549 167304240 169786380 40888583 17 3721 934647239 1906 655420946 881709286 312636544 127936773 366481729 242223326 886959868 259601500 726476389 361590858 895538005 543256508 531761905 900265523 982479 296986905 15 9418 596409855 67682083 530217934 330257480 348718929 501666044 140006108 407287085 5588391 488974363 134162880 39015562 466120474 232760106 449552709 228257245 4 5119 625822757 4212 567548910 373836820 452082426 19 9453 547036761 7827 191237470 122203289 18646419 274340349 536728268 485100916 70529285 292394331 73219120 70636264 223252072 36929486 375848763 307805399 293764990 37431145 268222768 540240704 18 3041 16234552 2693 8413903 6878243 3826993 9440486 14553774 9108423 4894187 15197983 12909739 12954191 13036271 9900297 8038276 9136656 2408064 1149969 4177586 10 947 592426062 428 106603466 61411683 405785037 360221653 479647300 23437960 488946155 587619860 198364550 1 16927 775042410 1819 15 7161 160567542 6236 155520924 147039065 100139327 43612595 138462946 37479037 98554185 28295153 141403882 106188818 11271907 30117298 49475031 62605714 19 18293 783155710 9569 419087812 53581623 227652210 448609143 248476732 344718432 329006577 297172715 708770897 526335458 252805789 559274209 526107352 272761856 266299176 720393158 557200731 768045286 1 945 326109887 544 9 3687 384723834 1232 329284426 372715350 239652283 88127261 89510282 325921168 252172801 6246185 12 18737 477657703 981 69955081 321543760 384977280 277239952 68866833 458654657 414639539 427114910 179195068 261653919 36340864 20 1413 901776741 1197 576182498 175419031 833340674 367716926 25912536 424037730 20041989 191931038 148518989 549235473 321458874 46899545 451167211 624365171 871248456 864448937 875408979 651872725 280647626 20 11712 586525627 1303 433888343 357912877 216117909 121224277 434195553 518419346 138342706 34017993 272562704 525497743 448286837 455340942 44817878 116509711 252360061 347328418 338325651 153589279 92996342 5 11565 790460489 7589 115113770 349360036 629041982 311117033 8 12737 758953551 7800 404219296 73667898 397326082 25014855 544830530 717561686 261754347 14 9544 448235891 7769 164052455 284464925 444227405 28217612 213546175 332613398 148955025 155983171 258731894 166912606 299560293 270745342 104122305 18 24631 856615825 9299 601387197 738281700 251808364 524878265 571683121 591829891 347987423 747722563 585551901 172993057 629623086 119744866 735514284 697869862 262832527 35502005 430186166 40 21492 764348098 3603 161231816 53916035 305386870 248657005 635892758 748912812 275096002 654676132 622636120 619684308 178358734 113999640 223121535 525695424 635466760 394172216 91947567 633123025 36266730 666258951 244187083 720880232 540989783 263916462 166222189 217768247 227665724 442359600 21696161 752855213 623716397 292282994 383100263 223652312 637857781 376866325 127159850 553043687 441833933 10 21078 494303214 6435 140982612 18609405 272687373 64533786 339844024 450795359 466524526 245707698 3694632 3 6373 819863479 4672 358211347 372100458 6 12664 662879743 10363 294732539 399938663 268696751 531752341 415095843 1 5832 1000000000 4330