979 90
597308583 662343083 104552491 169589500 836236921 923425222 314650686 113447888 895591083 215554 397206912 451138044 290064390 958940892 806496511 406563292 779570904 900942540 453057241 835251090 670787634 183056057 814105552 794818374 97491428 149615032 929255723 260782397 996962584 977190601 788782553 969327984 613057711 369781051 413317074 69842046 535148980 282526294 179246990 629288558 831196291 367256692 136189552 701300962 519907981 403142190 778908451 276920610 294878461 641464388 692024484 471794881 210417996 641166227 614458178 493578841 297801020 158466672 347873934 319448551 198572977 500697462 284410734 132169164 80194344 62254444 853926781 430713972 231285126 243512122 151838390 338280038 871371454 728240237 199744681 118040948 639783622 570016277 785303526 288775623 867333097 784791377 389142184 475447110 770549870 448221811 264024250 369320948 580125036 150255652 67534743 498370553 695164662 157010404 876859450 536751037 496457671 874834298 991599006 818041164 957113454 585236281 672331778 10666021 450880812 812309124 496679380 706937826 178835482 828102424 171263090 675858576 81253358 436446470 449761254 958990570 501192020 356548342 71939544 460175417 783747700 936667590 999494693 795769854 651326932 490451640 544745180 163771501 983195184 467296626 272709282 90740101 994313107 730741430 573662532 960998403 308214031 757669823 697759388 463627804 129516772 665741011 551708553 206456223 559127046 188314141 189465511 361612416 753820653 588636474 5013273 450320560 724159043 334435711 504353512 705589134 451603533 184873674 750818412 602577031 522813721 126277404 473957311 68491111 565539144 446326417 184566604 540193206 469639927 309332978 932924371 20305381 596938193 124270294 164786584 105836422 711775230 465303120 654934414 917206896 862776391 276617933 113480558 967322452 444172711 719917597 43096566 855199207 992370333 790551960 230375892 653236744 447357982 364459447 91905758 547926781 425448301 469948621 754242843 804538021 807676392 513702931 924184651 419816964 997431096 18485812 863533092 479758132 153586207 22306863 262373251 202332797 78159244 577400872 327756576 523392852 941690990 406976251 973749352 886829920 82344271 660847560 529033560 472028404 21229028 332267687 614166010 185110086 300515701 240611133 660506484 383402422 796548530 26041920 536661876 24760291 849617352 60820411 177168541 510421171 445493766 656331601 930455851 157501277 577423104 981761881 852751956 784979401 512946217 949735533 915191752 993121563 162127547 757360291 443916880 450744412 38551058 850125502 470599051 705562237 422554300 734296351 337248744 94039552 75466434 726526097 746446807 354783631 105652893 170443291 185250063 345264324 319789372 382885923 428298312 744951518 33368003 948037247 938612142 805663192 935736582 982789771 325391611 481833802 845451998 882970208 448669477 998721307 341902223 904466884 211176503 393794374 603408580 95022786 262415990 830025970 629844732 735419821 951457524 100932128 642327504 438839131 247472890 187306613 320931391 70771054 639341272 544256581 20662231 229429493 336379792 119088372 591638944 582564800 765250822 653914637 57260731 475231238 443217077 442569518 115293608 150802564 444641142 57600522 963297012 49777654 168626704 280769514 683395980 631043930 308311928 740454550 503861466 194645082 852943224 689790968 47350444 253720201 557818591 636469051 753689377 351184566 81774982 654881791 760577484 109657644 582892771 258156252 649516062 941521062 640890084 508501464 216738084 633354540 93191424 407663712 965898834 72213668 169370120 913445034 577839513 349774383 822101431 371488594 567100950 696004284 165000132 823724472 74319456 766345171 375949921 444036271 244947091 665222597 938842042 490271093 497768460 992698507 885799912 622117567 551254344 533045641 229032751 694034122 486422018 390944461 444087742 739904240 271334303 308378814 984145531 312943582 220421371 640032601 445239661 603780140 631632977 846705811 569562954 660281062 471328662 788451540 819591594 353227602 435229044 435873760 42941630 482974834 642998821 276934441 105414601 541643870 803250802 108670926 400243404 519774933 278147731 905283020 919952014 374677812 177964572 496893480 541994161 166667431 314916924 193771983 901664526 601666372 499190147 49535761 187771627 527050268 794394912 397646603 161337293 851044750 707742790 87399211 540999031 974449506 167113342 802307917 465782830 627417822 684637951 864297413 317816532 5119141 796690313 37241256 231619981 592089382 765412703 885468130 769334777 449437660 631799562 794178156 190868858 733094752 452432802 530876220 303691032 354839752 569332342 964319273 199150990 984242213 383402641 714787134 37245113 897825864 692859727 152122344 630248682 481733041 591758892 22563240 318299292 527576341 233239070 592436064 141511328 531556667 995271402 350429853 816480757 415243012 740860944 957872613 851812923 320229287 230549363 115377372 455141163 42000852 86293021 660476618 635846472 348331520 137255341 347235663 132631591 882393947 47304031 207677287 952612896 340426084 227880728 71167032 814670080 996072720 941565727 670991251 357765816 446748331 295785571 754459662 343127860 159111301 585863014 854314580 50393798 860405022 771220612 369729184 58862050 499745902 982322333 812972500 943229074 989794297 600063691 878835473 920644540 238291722 611373072 609783967 159144640 381679284 945297252 457247447 19976167 595236232 133455811 466444983 106215742 461205552 123969788 300846890 97337281 455616174 498824484 98184120 687816894 23664653 720739860 262664842 586070660 957171940 331425742 420965587 947700382 722072017 454461370 171171004 591065374 399187741 753338253 905122268 695966313 626362760 468007147 445797301 102667447 729070912 60393954 958750957 895644612 170335097 283475424 736408500 849905317 999650258 296495047 600626992 70351501 303625420 723928482 102627384 834794122 817162757 854687622 155940372 668619757 957749752 68636810 742487302 254192223 714297541 941615800 299941681 395015521 543090174 234919727 476168016 357090952 130651343 858431461 261810863 18257341 543191682 574792667 479497224 613644421 252683491 697055543 286071292 789962016 830964077 613326874 309190512 805684323 5177614 271079262 4487853 468162114 432772044 982975427 38629808 70976334 335610732 360678991 865003531 811707832 999132922 501602484 636091411 396673771 883681653 640944426 255117622 545044790 949347863 406594950 522261031 448849201 98015952 506973153 410794681 620734656 433342342 572577552 612345547 228880651 714410790 566787833 361202854 190550197 579895568 158973552 36188532 391445477 226302672 122446782 285617281 280096051 650566644 389703513 284668670 195309053 550443930 258396770 357902844 66744432 152860074 769139002 353221203 66385808 135052760 199846263 579718734 77005547 366492894 329068524 848573340 772819554 602618922 734662448 743980224 163830248 95433623 327569431 767053452 460750621 749063184 256205897 929196150 623162011 962974997 872563582 91391867 280942644 301769767 813725070 878212692 222944932 804885961 199684956 521240071 227824051 942640383 238662841 451438023 808495104 108433824 116295564 660696241 22621430 547551847 726408876 888946231 677224692 708438840 738894130 905218388 610519930 942977810 628150210 768894933 461905667 970944871 972235713 294142778 500939407 905705018 601603051 18964812 979905216 7969148 372962253 561745291 706727731 32370234 934062511 926919377 50999196 933221197 135550133 992171168 856689052 944808427 423963467 326262991 123904808 874441111 651915282 749221231 78844823 148453104 315591292 512132948 585199277 892966261 687163058 339345397 365227141 25674202 711262462 528187247 595259122 423792696 515454810 353588971 584762572 547298108 605255493 254861094 820024923 893914632 204969783 378836513 775216561 524759417 731127091 625549897 330413228 656430601 668013552 917866162 967348741 422079803 223578847 101063281 592274490 36546280 231626784 858580086 799938841 202472790 369316272 949355464 576526953 442663450 873142490 428542620 459358613 547323222 874910281 648001344 521698836 995844277 480969217 327436563 26215092 118588656 169262491 717611674 909933816 799771954 879019777 173969914 2095482 534096876 195940403 68202510 436145507 875989612 987884620 123154473 480138061 406539532 149635133 910106137 266330254 175702081 138753352 875562900 904760982 534242874 562169050 554239358 595756201 223598551 604601963 867937891 975022310 941898257 614834677 854330514 239847292 466796483 227516071 626933490 531338318 482559061 754928482 183746580 587342101 213120931 753216983 969264211 598867852 551970931 324928984 822768691 144816848 410194448 138422467 716711521 886932960 398591657 758851080 418374174 457202393 431457144 309678337 370477104 874227361 513336264 846509161 847527412 668265947 870112853 243505824 990120833 75942467 179377654 984945702 303393342 685274881 323336990 682605301 650208846 89598412 319612432 284734326 817416420 385952934 468730021 699469293 359940622 794688844 119298756 142341772 416460608 879829397 381122442 576097080 354057636 735250863 286680977 213208321 843675067 553057452 659020110 878926148 975960150 194383291 596403377 280352772 327309664 210219282 676621722 661455606 201583642 867031642 842875861 932016541 327196704 783390952 574081307 400043287 139511281 517123223 112281502 390301552 415124373 376259791 279618123 16033792 130590426 35301890 803886654 463939591 350342947 544491802 417223012 627450128 212162574 667183621 173960022 311653320 697973971 56190072 840738490 878535444 357602754 944361200 501388282 740504461 287746321 616970163 598748971 62204611 667294630 336359452 74748480 448234037 250251331 689357717 28090012 648779782 803564131 827357780 761320021 490505617 574638642 601584857