100
929319402 239457147 290958385 506122468 199728306 328782409 896125273 466309214 260683450 746576690 858363907 701313211
663367574 303447474 191517200 475414350 102288345 580570266 28230847 891238094 299806054 313910233 487755986 646943767
807087860 774397440 492082400 774397440 492082400 774397440 807087860 492082400 807087860 774397440 807087860 492082400
518990940 707831385 747955558 446849775 537905242 433534347 466437114 509723442 350986337 491898450 404352199 929283516
103833978 114665242 290114679 375864277 672397045 324985407 492989985 999833793 894968140 673506409 411835744 335073827
651537904 651537904 933148298 651537904 712072579 933148298 712072579 933148298 651537904 712072579 712072579 933148298
840226088 701419732 889529752 889529752 840226088 889529752 840226088 701419732 701419732 840226088 701419732 889529752
825954988 255698559 860516100 667155543 885418930 26099350 493446177 996847468 684831191 68908768 477079603 268074409
188497406 188497406 416092555 188497406 416092555 724170609 724170609 188497406 416092555 416092555 724170609 724170609
591291079 306525014 591291079 306525014 306525014 591291079 306525014 143406118 591291079 143406118 143406118 143406118
856099685 210640008 210640008 856099685 210640008 856099685 992320108 856099685 992320108 210640008 992320108 992320108
515383815 782213715 634081156 546932699 674369491 633658480 508032996 374419711 437671369 989829734 118404430 84125315
921647171 795514880 298196232 891417980 235809610 995219636 257882288 983165086 880731549 629944293 483707804 467785840
614270147 641389527 974083672 281993398 845362812 819016255 220489571 25644532 204365480 688917137 620279505 279058560
387324349 818984 956569158 306580547 816352929 485668740 690492354 565299163 281524356 938348243 527037139 266925506
999494280 589747504 827440189 612573289 962297992 937190996 887807844 764454379 972732982 456796408 141134091 11854831
249940190 972392005 249940190 249940190 972392005 418336212 418336212 418336212 249940190 972392005 418336212 972392005
268571797 484181937 15307953 881983872 690724824 220206081 565945464 220366493 872753010 928106749 41438911 797371822
457125682 437989783 572819019 163725932 564790446 742768429 596875218 910610370 424287832 392925568 339726575 673943313
898040243 898040243 98895118 98895118 98895118 898040243 412490477 412490477 98895118 898040243 412490477 412490477
940253102 193381340 305262078 193381340 940253102 305262078 193381340 305262078 193381340 940253102 940253102 305262078
380053624 872062700 562859763 752840322 640204380 107952838 85531049 500513338 746147987 709707219 782251798 370705474
263935226 263935226 902750243 686178750 902750243 902750243 686178750 686178750 263935226 686178750 902750243 263935226
751369102 139081663 526678480 526678480 139081663 526678480 139081663 751369102 751369102 139081663 751369102 526678480
529260355 912094568 279711297 309492711 373087596 207559126 129521208 363365471 418685770 567408246 603779425 636086877
104892386 608942913 608942913 104892386 762177113 762177113 762177113 608942913 104892386 104892386 762177113 608942913
769367102 64061142 18825099 951135148 815457997 922090505 449367884 62357584 42328893 162838991 325457884 246067888
510993035 510993035 510993035 982986399 982986399 982986399 775295671 775295671 775295671 510993035 775295671 982986399
208830871 208830871 641457147 183318916 641457147 183318916 208830871 641457147 183318916 208830871 641457147 183318916
247864770 742562533 427656912 920132639 95561436 472009224 631854808 952345041 117666191 433043458 155233329 110567263
983008673 983008673 304637628 304637628 304637628 228361085 983008673 228361085 228361085 228361085 304637628 983008673
739869606 61373588 61373588 739869606 61373588 921531680 61373588 921531680 739869606 739869606 921531680 921531680
288954042 288954042 177240952 288954042 633921718 177240952 633921718 633921718 288954042 177240952 177240952 633921718
896635647 684566672 684566672 642770317 684566672 896635647 642770317 684566672 896635647 896635647 642770317 642770317
571982555 286191857 358657409 177665283 633546999 447809330 646540277 738325940 886062358 544428312 966332424 839726798
906022013 965673304 878262275 631680690 341889612 698430356 709416727 147799171 463896844 91901607 211331663 245256122
760943221 984549368 314063475 241308393 136402429 766124888 656209722 949788817 924099044 396158353 123463370 896967135
876001509 637374090 876001509 923666418 923666418 876001509 637374090 923666418 923666418 637374090 637374090 876001509
896026350 896026350 446547648 446547648 265954076 896026350 265954076 265954076 265954076 446547648 446547648 896026350
39891301 485471579 485471579 39891301 384732595 485471579 384732595 39891301 384732595 39891301 384732595 485471579
78798199 359378692 154479401 704461113 173854459 609283813 901184855 182288796 612719586 311027732 165120526 308193445
177778737 346650377 153610688 346650377 153610688 177778737 153610688 177778737 346650377 346650377 177778737 153610688
796758990 397965547 452391309 694355311 457861107 320390182 722454292 362761823 752862834 649735340 479058798 66206184
425092113 425092113 834616722 691671085 834616722 425092113 834616722 425092113 691671085 691671085 834616722 691671085
26441346 15528550 586068498 26441346 586068498 586068498 586068498 15528550 15528550 26441346 15528550 26441346
708522490 504647109 504647109 708522490 708522490 708522490 504647109 700254555 700254555 504647109 700254555 700254555
325413625 325413625 776268785 776268785 217899500 776268785 217899500 325413625 776268785 217899500 217899500 325413625
52115911 771881972 271267279 65546261 155027147 784219405 332000680 301534903 166848514 234349347 827877042 920881210
881799547 796439111 240206635 796439111 796439111 881799547 240206635 240206635 796439111 240206635 881799547 881799547
252408406 808029674 899737862 252408406 808029674 899737862 899737862 252408406 808029674 899737862 252408406 808029674
891823921 923117294 381159300 971521316 692368562 928077564 319230676 913019468 837851778 552339711 43464620 68716339
227659122 206405551 755617769 106842782 286172904 356979353 333063214 814244192 332778775 508679076 508321360 471341905
195348863 140155565 140155565 140155565 195348863 140155565 195348863 951096931 951096931 951096931 195348863 951096931
371208236 922368611 922368611 61119752 61119752 922368611 922368611 371208236 61119752 371208236 371208236 61119752
431654671 139677712 139677712 472026822 139677712 472026822 431654671 139677712 472026822 472026822 431654671 431654671
382807645 682829255 333656279 531722625 952856977 599942556 523194339 65556477 397347114 756188919 371077202 626532916
916365364 134089276 134089276 958699514 134089276 958699514 916365364 916365364 958699514 958699514 916365364 134089276
487867366 627370481 627370481 487867366 579308874 627370481 487867366 579308874 487867366 579308874 627370481 579308874
281420225 281420225 932172464 281420225 795973881 795973881 795973881 932172464 281420225 932172464 932172464 795973881
713094522 436794295 713094522 436794295 962423581 436794295 962423581 962423581 436794295 962423581 713094522 713094522
282091574 606520737 157995813 157995813 606520737 157995813 606520737 282091574 282091574 157995813 606520737 282091574
82429088 96225244 159796785 82429088 82429088 96225244 159796785 96225244 82429088 159796785 159796785 96225244
324422023 377906724 519562214 124215518 501588885 823145711 900753761 409371584 461696978 435135665 815815399 261369304
81031809 168122352 760106300 573975042 331977007 119325754 124173857 96033936 906092468 678592560 625480287 510737110
478623609 309067538 293705973 273072759 603983704 467947780 851148018 2468898 627510111 641265916 157409216 405301419
578058446 749747983 859676368 749747983 749747983 749747983 578058446 859676368 578058446 859676368 859676368 578058446
99262504 99262504 99262504 99262504 46809556 506241180 46809556 46809556 506241180 506241180 506241180 46809556
801460944 136642566 701676391 595925535 166767601 529082993 796421959 748840775 759076718 229681134 747527813 118139885
806548774 196702040 806548774 626828801 806548774 626828801 806548774 626828801 196702040 196702040 626828801 196702040
223942694 688762534 421187714 14205747 696223241 292926622 966182498 700603675 106129577 261810709 907961043 699914668
151573097 62032411 187596688 277806404 602008506 904321688 277528596 115099003 736521090 440401898 92681483 586331339
402783331 808921224 402783331 175064785 175064785 402783331 808921224 175064785 175064785 808921224 808921224 402783331
467724320 76374461 559249136 315127365 50760211 136101800 302003497 792664354 187760328 953590508 350130896 264225
634024354 736832668 396447034 320888627 127001146 610631111 538331714 431810023 965513295 229283933 905779163 629266283
780094972 780094972 780094972 792806626 792806626 792806626 780094972 809277441 792806626 809277441 809277441 809277441
822432370 327496592 19897594 761769933 533563761 988542715 867438269 362223404 95281652 134579069 818122500 919812910
321844967 488651589 860528538 902736508 357077291 62203546 41489055 542336749 894033682 224982770 594158445 635404804
877453584 877453584 443830459 584541279 443830459 584541279 584541279 584541279 443830459 877453584 877453584 443830459
971070676 684654866 684654866 440693408 684654866 440693408 971070676 971070676 440693408 440693408 684654866 971070676
497362175 497362175 497362175 931823175 931823175 111410880 111410880 111410880 931823175 931823175 111410880 497362175
302086527 737332906 934469861 219653639 557790288 916934229 891931786 999477682 786439143 190479004 381892228 838252774
911083346 924479295 924479295 911083346 766920848 766920848 911083346 924479295 766920848 911083346 924479295 766920848
148943028 635458624 245248056 896836986 358916584 86968008 299616387 419933170 978572827 476972554 215331542 663504846
657498069 593933099 47347171 959447253 101485040 638062812 819092763 360148397 152276677 994200870 719872451 261021669
493808279 493808279 493808279 226770172 321801172 226770172 493808279 321801172 226770172 321801172 226770172 321801172
625806011 996267156 857329768 625806011 996267156 625806011 857329768 996267156 996267156 857329768 857329768 625806011
823729273 823729273 401212874 885589484 401212874 885589484 823729273 885589484 401212874 401212874 823729273 885589484
43041437 49164358 945864487 56249057 222232099 950643940 518723240 501602604 63093999 790131460 696485203 535380998
511264741 421202980 223935523 206143907 909959895 196890443 786517532 596372388 558213944 654192893 400953341 641972417
436650744 538853617 510103285 153433747 223011913 750149835 134380961 923559767 117459468 360393426 955862772 984867527
909215007 578911866 989404545 711319050 284414651 463330311 840828905 111993944 627163170 703007571 91710890 121198789
928903632 174643077 359568862 967168017 588618333 153961204 252763175 629256337 609555906 207360405 375170650 387862026
260136541 678924379 31080334 260136541 31080334 31080334 260136541 678924379 678924379 678924379 31080334 260136541
446531661 693674957 446531661 46061527 46061527 693674957 446531661 693674957 46061527 446531661 46061527 693674957
411359668 651405236 411359668 557320311 557320311 651405236 651405236 557320311 411359668 411359668 557320311 651405236
237776693 237776693 853696534 237776693 853696534 466561826 853696534 466561826 466561826 853696534 466561826 237776693
526625483 908758132 908758132 908758132 526625483 526625483 788922857 788922857 788922857 788922857 526625483 908758132
207943594 171096789 341762732 207943594 171096789 207943594 171096789 207943594 341762732 171096789 341762732 341762732
592011177 389972517 325745058 861351476 177192307 366585782 716211501 66591515 390072592 54895649 426944629 85086232
191508603 737357084 818703850 527446109 177323696 881174937 642967149 244691304 545738948 932137833 377640968 993414932