100
461842264 643562660 866500802 905566403 333504126 40811957 990042724 972993610 520493278 601489235 867289485 351147451
82434363 240972548 916307754 862233581 58082947 63336931 322404728 439972920 792923397 544029733 505700840 358360913
575595692 575595692 575595692 677516188 690694809 690694809 677516188 690694809 690694809 677516188 575595692 677516188
726650708 649211722 320467494 685384976 697374359 288632221 534269862 970358495 7701017 471970684 583529378 653044170
363219203 23369830 287615453 766762388 338750517 189114018 782064637 80662091 988061369 623917277 597246216 450812937
691914958 691914958 691914958 691914958 562956407 367790643 367790643 562956407 367790643 562956407 562956407 367790643
453332711 222531458 222531458 453332711 453332711 571814699 453332711 222531458 222531458 571814699 571814699 571814699
983291711 158246207 848828594 94625030 544061809 350617907 233054627 854699130 21159239 33064185 824246350 285551908
323805259 157857091 885620722 450543145 475383338 761073052 519832466 531318888 219861496 36801842 720539866 409382437
424879676 333795062 894569940 894569940 894569940 424879676 333795062 424879676 333795062 424879676 333795062 894569940
910142271 670882779 910142271 670882779 910142271 670882779 481654271 481654271 481654271 670882779 910142271 481654271
62258878 195107747 673023905 673023905 673023905 195107747 195107747 673023905 62258878 62258878 195107747 62258878
139967879 632753264 632753264 632753264 776958173 139967879 776958173 776958173 632753264 139967879 139967879 776958173
81989788 407626038 407626038 81989788 407626038 81989788 81989788 512950073 407626038 512950073 512950073 512950073
139465407 392254032 437660046 392254032 139465407 437660046 139465407 139465407 392254032 392254032 437660046 437660046
163184034 992779760 163184034 213773710 992779760 213773710 213773710 992779760 163184034 213773710 992779760 163184034
40024120 80558725 377260205 377260205 80558725 40024120 40024120 377260205 80558725 377260205 80558725 40024120
530434141 849103099 849103099 530434141 849103099 849103099 530434141 563573780 563573780 563573780 530434141 563573780
438072619 600582305 582463026 444665408 516062260 477793083 874394041 312831217 329221576 408694476 781373458 274150251
827182980 391061936 378773827 789802902 604872252 594538385 77052843 782077914 653047039 87296074 442558658 395324054
57467409 57467409 800052134 912964097 912964097 57467409 800052134 912964097 800052134 800052134 912964097 57467409
829775644 78296479 478328018 53949216 3188320 882270481 224761648 62778613 47324576 706788473 223669252 339727722
196606353 118431084 992426394 162243378 859517830 293902395 917628226 755895022 692388585 275913751 606516372 311913650
644997897 240029321 264550141 904889182 494500544 59507949 695836305 431627875 318719747 810762995 106720427 838708652
704361308 408588544 150863318 302537191 612121431 862278244 375000681 584116336 615507389 720032429 13153022 338798287
182402505 497111264 451961627 61242789 244525399 129449999 636243619 785034488 408328789 918482933 399336040 392936481
760057319 5798020 660251344 761030168 167995334 96305820 143674147 273178250 491527599 668910250 420464197 731477326
560189013 189104703 816404832 749801660 327900121 35023579 117270081 353518538 188577689 539219657 206731484 322729231
354670473 597452965 686598656 609813589 799104004 969697782 277040779 183108123 274209737 793482751 281179239 55124578
690007692 281474337 25102500 167229348 560225563 685800101 759777594 795411960 983761813 994566717 3537545 874455313
881089145 661927265 822353013 710650843 368249766 337765222 934164843 731114395 749155980 597688655 357724728 739652378
932452379 283311586 283311586 932452379 907862459 907862459 907862459 932452379 283311586 932452379 907862459 283311586
922025290 148093084 75261198 313391141 490207607 577229089 568565741 190107166 72195872 300832737 353985900 502152897
468447474 974919539 897008731 324329897 829402770 672556883 464742629 680604317 202132593 605399929 289145220 207769203
785777699 834035038 785777699 962544808 962544808 834035038 834035038 785777699 785777699 962544808 834035038 962544808
59430287 152749358 59430287 330847933 59430287 152749358 152749358 330847933 59430287 152749358 330847933 330847933
521321319 745716446 771559450 577427119 339112019 567266482 892845678 249261681 768596962 286502505 521339435 581722763
792281945 826903975 631696461 792281945 826903975 826903975 631696461 792281945 826903975 631696461 631696461 792281945
387782476 521155881 387782476 553736675 553736675 387782476 553736675 553736675 387782476 521155881 521155881 521155881
443714374 948671343 948671343 443714374 948671343 95349317 948671343 443714374 443714374 95349317 95349317 95349317
673433202 36928528 50058273 472468521 209082502 493858719 256317044 357694797 557358967 369638648 578563998 176820024
152338779 219321960 219321960 152338779 219321960 573713182 573713182 152338779 573713182 152338779 219321960 573713182
292220125 252160844 517899321 579072960 908399693 5739201 409591475 574014749 843516240 280616048 999664925 774835687
672560445 38849092 210093727 646466455 479473294 972546522 104086360 426457212 119064632 833646604 66018422 875308609
602021905 24871714 163966171 366267445 573774659 337410534 97866486 326526210 75614178 520344538 403583016 747456484
56983023 563146343 229563524 585566015 747156056 479778692 723320389 276156634 660606328 430192630 244855696 776006682
501368378 518321274 746315572 552980540 641002429 888840138 588831462 397180421 824934255 679676134 483725894 481793968
213998539 315822035 975393067 456914036 705639106 254934234 543750746 568475670 755315930 739138076 10519556 841620609
687795240 93299221 439846913 281457232 868699030 295640989 474722133 755316765 232800248 35307757 567334276 279666120
585823433 939200045 455987625 455987625 455987625 455987625 585823433 939200045 585823433 585823433 939200045 939200045
733112422 97469214 97469214 170965732 170965732 170965732 733112422 733112422 733112422 170965732 97469214 97469214
609044589 342562405 197659969 302500225 809311272 856656569 948541795 438456652 928416233 272715071 650502542 54836319
141926575 141926575 141926575 790872949 790872949 706139665 706139665 790872949 706139665 141926575 790872949 706139665
145174271 523602258 560083602 143322244 567391344 62306945 927956679 534972048 704195685 843815519 228946757 286834022
85315785 276131692 898502132 118672938 829961797 710963696 111539282 165166534 592758068 147415641 301563045 933156447
905246086 924794509 173364038 86440495 622245170 486552478 955580489 521800503 465417665 904402246 393515873 105279613
488332471 704536698 792151691 12177807 222661894 773588587 323403916 771108003 2499632 767756162 962218129 652242224
517441809 195454874 341143091 22092901 222821528 358048946 765466043 1170846 8840194 507744975 266244656 848268995
827819486 93245096 93245096 827819486 93245096 228067494 827819486 93245096 827819486 228067494 228067494 228067494
442110939 836165222 168130739 726011938 708731662 494858506 89013283 70298022 443541626 835753058 241359380 449987276
214825355 540499613 786579613 951959391 719010265 991696057 913905549 530811251 18391333 842998394 212854690 662382147
567088637 269207410 269207410 496460238 496460238 567088637 567088637 269207410 496460238 496460238 269207410 567088637
27856755 981352350 724303323 419508036 5263260 250789020 158771928 76168677 471508262 151893321 679080096 412695491
211994338 350545307 899823319 916046558 77878290 841978654 234051203 819214566 212834123 520483214 14157568 11959031
269974092 155020753 951131051 644168780 720064334 227657806 509236381 805958454 165077569 784952957 686629005 534546200
57520380 605109435 280801053 483756279 196965997 788724722 216631665 63520273 498849702 514583527 687639634 536107808
630447817 306093508 630447817 306093508 630447817 556685247 630447817 556685247 306093508 556685247 306093508 556685247
133437602 467274990 24324464 9249214 739478873 819089216 329812184 429993191 734163132 299932887 890745302 828694316
243117522 355760713 755408783 909164644 878508667 999772494 430967064 825340862 860626167 913673674 561942376 563562204
818152682 423198507 423198507 423198507 215113376 215113376 215113376 818152682 818152682 215113376 423198507 818152682
915149941 211956295 915149941 778993382 778993382 778993382 778993382 211956295 915149941 211956295 211956295 915149941
362316617 468004507 286068148 963218689 510235207 105172832 171792373 844507054 848920044 609178693 81296160 996261089
846087357 63967677 763558905 704412626 639922626 330529921 873708332 416655128 933083423 351143929 263248830 32862876
688028515 949596805 72166503 64228210 658087759 333941043 228887739 107690312 269822460 763374751 35322017 279217234
325288585 816485748 818405981 16825016 274521370 78226114 590118995 656868690 845660242 698275592 583543033 104448806
829813498 104574386 718808193 862596144 167355877 255332473 386398533 402121395 553695794 126251444 482921828 320075018
710177956 431991661 448110055 34231953 104729875 748755283 183579319 554978811 967303796 477631535 410942302 507767986
803229145 347029103 78160528 592776351 10006476 77463163 884211596 370997710 905719934 705333360 971288231 890984812
152815460 174685020 174685020 152815460 595343153 595343153 152815460 152815460 174685020 595343153 595343153 174685020
840420197 840420197 83982759 840420197 840420197 83982759 668077787 668077787 668077787 83982759 83982759 668077787
107792667 982470827 528388243 162171732 843866362 326071310 637475587 202188371 809465274 541691117 389884928 418769857
117135984 459477860 459477860 459477860 480017271 117135984 459477860 117135984 480017271 117135984 480017271 480017271
949647410 201935811 267654164 377473324 469153395 821499327 207891377 615590397 761912602 321904924 442329175 744826439
761632152 131604991 761632152 657050641 131604991 131604991 131604991 657050641 761632152 657050641 761632152 657050641
380173490 522793258 485661005 778515418 546849987 908672906 854459845 590372371 941956263 994761806 968463716 400573432
569097051 584699957 202371571 569097051 202371571 202371571 584699957 584699957 569097051 202371571 569097051 584699957
195934224 195934224 457771644 195934224 555268698 555268698 457771644 555268698 195934224 555268698 457771644 457771644
722242612 136885759 136885759 231954150 231954150 722242612 231954150 231954150 722242612 722242612 136885759 136885759
737403046 737403046 229657842 737403046 161474504 161474504 229657842 161474504 229657842 229657842 161474504 737403046
703191899 743851730 468014156 930887032 778573191 603363544 126925321 561213066 401434729 887342295 296704396 365980746
846479277 917039441 267501436 139697226 100009790 82430992 131906912 761530325 327530168 186371583 952673712 552080874
613787062 564237562 564237562 156865238 156865238 613787062 613787062 564237562 613787062 156865238 564237562 156865238
181778540 513632346 513632346 181778540 907279104 907279104 907279104 181778540 513632346 513632346 181778540 907279104
978507798 47524123 47524123 41579127 978507798 41579127 41579127 978507798 978507798 41579127 47524123 47524123
346892655 516584784 779507166 665322957 853390498 581990254 63319817 160872706 979754226 288744655 354417999 322748210
611350555 511293771 399568684 947602069 517509912 840766646 454551862 763810048 555470921 850014929 380033177 809987196
841954496 218616142 657399440 538432156 332724373 584744686 180639827 865266789 905690665 651514762 280422688 578765976
534791310 66556080 47354936 515417732 25675281 254717044 135130790 122081174 285910191 447544838 664517753 251913862
4582895 373871911 615783159 561544092 324854315 283800675 511784117 801460932 213777687 715638277 751046869 698853181
343465555 343465555 988204585 922132992 343465555 988204585 343465555 922132992 988204585 922132992 988204585 922132992