482 2
35588215 433396562 975495480 267060791 623261346 311442182 171502782 629844426 1234234 605941486 759754069 491219385 306825614 433725940 300010125 823382516 202217130 968824936 740264079 72961267 795299770 173279136 416398781 985161288 490993693 561236981 699064751 533063847 327158093 170760109 674764967 630822397 260941066 460874588 756707081 508972879 703071140 271600693 963957850 215841774 638301668 485603119 810460140 566938602 940671608 866512664 604947743 133466348 217308188 842599367 102366669 354192403 153687961 917726802 667756997 420461170 209022038 187881809 986749750 920407890 686849846 799392910 737622706 430635071 31985520 13085857 698341609 980734542 955227798 420901872 321817865 978769442 386704294 462720820 337733566 564463642 678663734 299984367 536903425 537405230 221482892 821126190 693537012 669717910 795158430 923502677 264243118 461676931 535425427 26409134 500297751 934784820 894654410 85375756 218887045 840063962 71694151 563709470 415716113 575558097 905735273 36111819 522947607 575653013 987718266 829294200 364752 80274656 75927809 46741031 732624569 218427659 433772468 881500451 323277282 201185263 289327547 812006755 433653031 43219143 420645329 151337390 243955244 73786122 827688977 121458003 131103440 499005161 175430067 863031677 276890902 642950241 652906422 901368985 247373309 560083979 673341044 525762697 985757818 149561202 998753705 458407199 150862345 884258492 507810590 397748939 769183531 210765582 377815920 458717695 654037199 331845441 715873487 515736431 864442280 486398270 431084998 231424528 527814485 776244513 855965168 165453317 759012685 886563218 965365971 835606827 455624447 990296406 136392781 836250388 80798004 823486632 263368372 875125718 981542400 926707105 967094165 415512354 645486600 666959332 998669082 918917953 94687445 902212663 876981192 669222364 405964031 108913501 259770089 679397381 571743192 339383586 686394318 999642710 388917369 509702108 106812558 224266380 543007420 35678927 365415579 965411303 582033850 143389516 149499431 429027265 46719454 986186606 214570135 637016560 620413778 382177900 168155788 974977170 597084547 169235237 655820227 531068402 681711754 17383263 641067792 873974796 186046735 275051799 975492216 229793208 699885326 891134498 289655156 325110021 48992236 947930507 652399440 44471866 991239596 433766283 249158437 102505123 454148740 177193020 582071561 520759938 297515781 500272419 810464444 161695832 738410321 403265236 119364825 706976832 452359807 682401474 685640045 134193931 616176271 440448071 991491535 126066827 903617728 512649 342957359 790876351 965010606 92383348 30234207 101530479 613520816 173137984 237211004 313607414 997773725 188827600 239036186 432361366 98960732 339632531 467220998 563181179 150013312 418589303 960239186 438993021 942600792 969350253 103719137 588530943 120474871 52764090 199317112 677322531 383974931 420906840 829547229 752589218 187064198 906724223 560984153 705440292 49467218 230871226 146193477 110297619 199974520 878256571 657285477 292714620 72474403 699425387 904032697 331365868 68081874 553290540 543582174 967960343 378920533 663647741 782464216 777695232 181513751 67329472 899553498 663311777 426952255 206514843 939134289 809064884 314525106 182439604 426372329 181837741 429757471 952935195 977287124 460479979 972261942 99371896 981902303 309877068 989084784 793076236 567099227 564429471 613613619 696136894 515509955 725127438 860994734 901338723 913399701 589136849 683735929 646193271 649430464 315142297 781510758 986662241 214905331 140460178 218069280 325837017 380927425 785854262 28349950 275049707 388433193 453354200 984875587 260764266 492338213 907500160 290572605 138133474 475457200 776290173 856050885 525024190 8980839 781073524 626382761 353701890 967786759 734975951 899682447 892402223 70558161 935100522 231935869 271185594 674646921 709022742 195219781 343577026 705618938 245199578 438772462 885791035 583767174 835300813 602536319 881389792 630343216 474375268 453047664 927469757 258305379 182581385 897119999 186538475 129271713 966722909 904266743 335922298 667108127 604391361 29811755 718447249 758505710 388526899 277999564 650420075 132922020 719017198 247973813 166717260 294655338 37443033 834816304 805303842 205798129 377455365 931248688 523540718 817751784 705240062 701178502 593782044 71347304 659515754 670336684 522620285 853302198 353963673 813355318 998497271 31851566 320153936 668609864 653362344 466292457 206564202 716358079 975730442 383547031 395680531 647634287 385206613 723725466 448946674 309778098 505500319 748329188 622708650 82339526 581045749 269498264 315132735 699064172 494392668 748515865 841134319 977404442 306530355 726781551 618150377 592517328 869379733 668642862 469444595 729269518 565411235 965694384 768825076
917314246 27716893 456988167 85739477 382707611 876363440 454488855 712868767 669449916 760178826 138241117 351020565 60188810 317385070 807439671 507031749 974856538 708847058 114070041 271052463 826411298 926176906 705180481 682660589 103542276 325997022 950093695 467831999 617010384 476990943 426492890 911526917 68949823 759596550 453751932 596675617 258191368 69458937 544236513 241371572 901694029 937010901 784154641 66501736 775385554 286973797 426777935 323526728 983168386 946285143 799857304 900397745 689259651 249150500 199348667 829655636 616753043 820930997 212092446 61935117 904603539 471101069 574094035 545154357 76829574 448010593 385506333 877032290 139585413 152995903 950848203 568078680 228598810 917030266 186720884 530373053 511449919 184566070 436339835 509130551 179906665 472920368 503281469 834472157 481121545 663865621 544235625 661178804 260221000 954368179 565959665 702108326 317558665 544635239 323164084 193201554 315433049 710084226 402929737 210143818 752948143 186279764 840605794 13997124 696393489 59259584 536452307 670221775 34810918 162219668 865920016 564063336 66274797 837378511 597823370 260925777 503531035 755694418 179319304 254488484 457450810 710246175 715593174 407511513 642227947 751739130 987181194 367580362 185223440 482088047 557960537 500787317 613541226 229546938 319775352 792294307 153708803 842555147 290567986 325613995 796886152 903475463 351886474 57833249 858790635 144483532 451996193 414542903 931164638 687089762 995633874 354776320 24246393 348659493 231085234 569384953 324013315 118819264 605177257 627126157 203922554 41972825 767272445 993592918 473218919 658389954 196269546 824234444 530586049 628488288 817469924 768502762 178349597 896013657 368224784 660281224 118278145 829568344 829142228 225193928 46874586 64048152 138451581 940504825 676785469 88349683 37772498 641609082 785901258 499008336 159359689 420309028 670440339 399084964 264301142 312144066 641386110 601130617 130437975 943302551 621103780 156603933 129176286 884441615 794497887 22740454 521956672 927345326 303273277 809709290 802914029 863668815 104895586 155593962 14976762 400281181 234494762 570743162 575993004 821038639 265296192 569006529 583970226 173550089 967951754 335295969 874766168 515080261 436556871 3950943 734254903 165674125 986069807 5808288 708681629 622117409 507563840 853525028 966360985 959948455 330190520 290174867 362072784 925519221 192380233 311367042 504042685 181683400 927435946 442339455 193442263 190168283 865495144 909304742 831516470 472536291 909783444 475518384 615260172 240238708 486073843 317240909 442282140 667611947 226755414 518527532 520566637 51816481 158832172 219749352 947033314 539749991 442599927 803472444 125746829 67964461 30519230 481464734 196654931 854565285 744399993 91626802 710789593 353492399 855453713 456286536 257825419 955858334 804764398 242479722 592963798 726599518 955870168 351080157 647048575 558965305 890399005 39539171 335523015 911292667 682473708 516328480 261901566 861206550 679856886 918865705 672553716 660782110 440322571 394272870 709726424 199631733 182327320 199704081 171243993 34093463 392013577 929276251 163323104 812810234 413454996 360968671 186698716 794136023 867977546 225685355 708491628 566672398 489989293 905741878 236024911 189223160 497390681 516442714 371368916 549983683 127044633 573644251 781904822 890634394 628000805 377100101 135670759 738940841 515362677 130008190 7791966 801724733 464670679 389444077 534472406 660665673 75467970 424527801 952367055 210704088 563418845 354139425 423044824 95021033 106652405 88136257 469277938 37513205 419299984 296394070 685350745 581238610 68920296 642537637 642685745 362064106 945996821 881833900 262941001 4503994 658019948 231187289 127655525 259948963 935754928 511094060 846899562 571031544 673997663 933125354 367117651 925281541 704673270 833571686 88432597 713940201 664045005 831039259 742531122 304491605 339076114 258350864 917016265 475544788 897542559 757663365 439081278 725424405 574729489 954215858 54667578 367087969 217957133 412734409 112871070 807040031 934485693 979987227 839612527 432963637 909448957 943784550 494461202 644507998 368656300 477135908 714702638 118267112 379332851 405068935 321052715 821336571 241440920 800670681 500384959 883895315 808638733 878716148 656003424 167666084 907485895 575513196 336921751 737060008 271717581 228637631 282327827 180995670 667592687 649967098 677792749 334010353 785668009 903124206 894724308 525874678 542498670 509461740 74570280 370888350 240605510 11720694 200905131 354384683 883451628 863602082 330989001 239228609 845811887 155887093 854460715 841578686 234551837 300135040 412906591 641449589 592808697 806344885 663181327 916875276 68591197 376165936 10429192 119267449 579831542 707913475