1797
356720723 498930181 716567728 560535720 84407474 242229959 24368740 280834941 925638150 948187508 936208951 520770952 149086827 827289634 670192416 882018221 919435389 673796877 775228922 312566231 537261162 119059485 933697692 58910782 569436052 536767209 495514951 340018628 720015711 278671501 194873481 980190822 193783056 34221959 767505118 842722234 960713519 535749713 568589393 357870064 563855592 176177550 72300563 831170515 867880704 943002802 994225672 680948439 808151500 348227380 190728969 575112791 968905247 688852481 463476137 848494300 875490891 499402314 60482285 400962496 161389398 419827701 846430425 389093073 484651379 64773840 484358877 7983796 270943940 558235792 405185693 866455395 554647916 847426126 446748423 960363458 39376260 668173026 144089062 80687974 382001544 179873010 95667610 990675318 987408428 421761451 207924517 552842628 741222234 974685264 992919076 31753881 173266231 425506912 815037703 260548749 996236085 345929581 50663354 700697151 808313925 35076719 866508835 850499115 837232483 319077806 372506864 220114223 547906602 762503963 932765253 175087529 433860324 624525745 817496504 238320314 90486048 437526437 432518720 121449406 287817017 779320549 149680203 636426702 413106415 396535854 115795664 168406686 970074920 627651755 253574429 877953802 588836651 29485282 290237637 209027863 802806175 461916187 553241320 787810291 552888309 929554727 124005968 472459385 459738839 459179785 709646688 475925520 23460677 992260471 338828735 756011626 261717917 381095641 482548818 837353096 450334180 268346638 693223712 700446364 353283713 217128470 304617691 854008597 637381147 379335600 215399127 643565881 975190646 38732158 535066795 94168681 559343562 731963539 922842928 47108081 951894340 32308486 35843616 788808888 284126383 825065206 275735386 245222085 266846126 734719609 156284912 488835720 133882611 569697557 982716383 533255575 685382349 569481393 673744256 497398698 566735618 606400624 177561520 501066389 881110632 649935786 666511179 855830816 267863653 283431443 371625701 936498733 104624350 64949589 669654756 595631000 533532247 360976180 103455897 303670951 43422235 7993236 33755332 367148983 829786760 850729315 924960983 672274805 792848932 610346828 899347041 415125706 377202871 827012089 951379912 828399861 815528301 193277955 542266852 636735186 392948310 764581055 186823284 916423841 371202785 946599684 228563257 18283950 261069569 200734524 272742914 860425830 634753677 980756826 11591372 766402608 736960385 586881941 612174560 639150615 268440879 234197558 67965711 279746281 848985620 851395400 457229234 490100483 898861778 781149588 119006498 395535229 484232224 512579560 83387662 337212710 968302133 160358292 526664279 621614656 196496381 629110473 825070281 263807206 372850422 695050588 426133553 141597838 792070140 307628766 551096845 9036326 84537548 247075951 657275241 985453768 304086431 322421713 326075848 941788357 411125273 925759958 573275966 97658079 443318038 90467539 307671069 927651597 279899875 792418770 916495698 746682160 67825753 966794753 951195512 144017570 584987672 648565846 239195936 345228121 757163653 662141399 65580931 675414405 236009653 782604512 318849385 612375028 244840421 980912971 234970700 527400634 323029702 983686704 392627104 767758042 209074067 610957586 868072415 863179312 97760390 527418608 452289255 683868870 131128156 980720597 839414733 476874352 263313633 82537395 844442956 498921774 296742105 410165032 305431054 237322938 246775661 988183601 541311082 657186838 815360983 283470706 695295445 878639196 40562016 805520800 193269066 489527075 729038188 504160301 658471200 175280639 974771358 955803114 772179282 730102506 378574346 529453943 124534137 492230680 548728336 810681925 812308089 355798243 632818178 250640885 578017270 892497066 802425680 496675859 706390176 351777110 823368405 193379943 920190521 32645912 814514746 791161273 268637573 117048448 732171388 731870239 616025395 4790851 776255105 436404448 743697443 68230978 50498208 286050269 393498525 162939448 115153414 862988438 93118785 606277080 886368109 720741810 359780104 307081300 947537479 39324424 56735519 793814091 480900200 393279980 351237498 25150910 25786077 941460907 923532888 20962421 239861960 162349499 164411659 173108881 71979855 255232183 89745230 525086440 837546903 676349258 164440487 700559097 556550713 290222366 286089165 244122359 344520339 270187308 466463400 194148480 895701493 875987121 265086139 830557797 612566999 119841111 63068978 175424894 512066395 32192629 527581190 440566321 194282203 37706012 160494295 83299305 533993275 926107025 374384968 983687415 781736482 807462490 21238174 597683768 787392818 307578412 768912471 401580848 88045298 611782248 453118062 320241776 705399045 225813538 619676031 52174334 983075408 665051429 318438820 154408877 197420006 862906295 526891826 314063290 977156955 828485524 595309552 107931643 613070751 241578305 222931666 318143064 523559548 206783241 361267596 488469426 474029831 987547310 692487114 941419701 698197628 52107372 619489458 670169489 114314202 800427473 658113001 149688388 694212935 22643980 758121653 412074830 369935296 616762975 846610526 887185102 291584878 411054812 11732037 832843770 699987883 958179715 266473555 153204914 59566225 1985783 740506829 352797946 595298467 865718282 220408078 865464568 68695925 524570674 354479729 414401712 270180743 375241073 140821002 16606008 652362258 657800883 440259239 177585258 602183114 181410895 274550367 158818719 738118492 395068207 85064199 975515142 656724424 372855055 682260951 807177666 470693496 247606047 238562208 850242620 127651130 148592477 756419847 675693998 610515489 247009331 875150639 143628795 236609665 712661046 462221506 678688086 999037128 744643671 827285023 644901864 725464497 209531940 366019192 169278910 335845436 822948023 331669925 95767869 522786786 81473745 995785844 415499883 70505066 555777999 107207547 109230632 236992932 688057482 66002884 76749269 714983370 183424732 582817942 617813834 786704481 427472012 715253324 632423971 939176466 965557081 415605751 993070285 315831505 362955496 269027306 3646605 115399196 290238173 678103053 469144821 631938145 585691131 784878110 190498943 418710847 638634353 673896158 557545087 470056473 947631361 871472885 486825398 363291498 254578036 814116591 901932756 948944431 964314216 36147427 175198511 233803610 929509352 265671097 207244189 393114243 557679445 501421063 919250929 528007521 8850664 426936591 32069862 671735414 496050591 417394652 135450647 22771812 530672743 993389719 182618565 693724898 391504289 918595476 274259514 328631177 821479249 984563727 134192045 614063139 58021122 669731239 263276278 511478096 489383295 992156876 602769201 24321542 233159374 937866726 846330017 557374478 520580866 68351772 196852695 664235234 807929820 591381468 369101199 5519555 108343979 585248804 234095537 420710775 690899716 827612996 333480695 314254050 393396993 189334654 18698242 925463151 622026223 279093011 346314717 986373365 836311038 844980226 593916824 114062055 929079046 950039327 967360508 79049065 869231410 812151921 259220840 920916018 462095247 784228342 578359852 857229001 711608507 291476245 739424503 483099902 740912549 94697954 39914524 654415618 976613858 426951403 260523085 358053588 313251310 565577896 15204762 544242574 22726687 71080583 257342857 397425162 272861189 393104302 56642091 834653575 891509439 958270064 120321285 107739665 619483177 575288830 440130299 95471736 268489369 391880167 366971374 817490545 346545495 252263775 52958154 639820483 584503516 770575966 315363453 371193426 122524526 501819035 182528811 439824951 582711212 97668242 283745452 997788881 844939342 383980482 138714491 8480379 525889611 121724854 260663553 577009489 682988698 291709734 286492886 311562460 20220703 579790698 189269049 786971129 346420669 292641713 980420060 270550015 360877605 565768418 960149141 724580976 799401007 418536519 670967502 46814502 934678043 186905615 630431742 922745113 862900462 161114918 338701077 570972245 305463166 96163574 310981678 988590063 976911644 971881640 376765849 472237718 930601198 698218481 225569409 589958178 938951604 974150425 260405074 398539353 208561813 549969325 995863462 834519055 60582587 813506704 303434494 502849671 126763432 505981052 734078325 667740782 220966330 86567715 559261829 840149812 167869649 9888351 145124597 199890035 741469215 652172293 864216423 744790408 937466078 59484846 187957623 331234957 879298047 182191095 147628050 169185170 429166 62936722 359638653 126749176 145982664 845948813 180881851 332260719 928987446 393310552 946878109 902946395 695727782 740903823 124661142 237641729 578024496 815293347 63869736 834139687 458613381 687680907 31405271 614946363 63845066 277468102 92410985 843689316 31643450 22645374 747461627 644481338 387962777 284076518 171488227 210288821 626618359 519822140 141654051 538565403 915635455 968010245 171145046 269508915 355187155 405379682 108718502 592885898 946240371 89821840 599599183 518149558 747626529 67929020 294892166 932398133 782044439 911160679 835309768 156956269 204775004 423374673 416375502 243420655 755881356 709240661 742835675 348681302 220791288 319364543 199387577 407134408 935111773 296389244 25663290 535776972 486222967 356843077 586445779 425958648 684099436 655129173 598860407 121960603 690600929 744227114 765956761 103944695 430896557 543809415 818302932 98003452 445311233 826677983 981916998 23894943 690135557 418091233 13459279 208673924 677986251 259544192 677843371 399467502 336391938 364906115 250855345 26891005 14328973 408502646 321738221 202206981 675168260 685111219 526872083 477139860 263142294 22070806 501575951 562009363 415872929 261715887 284873302 890847603 630114220 990126941 46515760 86536599 299931966 802774553 705150248 64062873 279777945 742359699 878249302 993951858 395391438 220101822 49049689 445258345 919453987 773371627 155816385 977644726 472691979 201787587 316082912 294475196 646168335 859582641 37912172 433967744 859714540 570898167 196288636 641337300 581856611 477089026 363708852 873641990 294437642 32958601 930614856 874098833 586621059 948851123 749193868 206133016 81150953 260963554 82477106 720422999 214750723 522156761 308879562 580589532 833278353 704109857 182819492 915414264 129567112 612379684 354551965 291574201 271940085 289890957 350748278 777323442 889445639 775068867 682262931 561089226 217877960 463450931 699493111 234882472 408297638 183696982 155296906 146224178 874617414 316059376 586902999 80655515 319194350 804777838 955778876 742464244 281163251 465836914 726317150 34556017 824690139 377142509 566199935 996200120 208107759 409808620 883997938 117840490 670151266 249352529 448556974 675928826 423292778 634078725 571043722 923362851 253881746 143396476 416288868 885212983 157818829 605818927 527858625 909221752 664943457 980022639 83997745 246213442 576676506 203355219 845997089 142414807 335224862 751517925 697731844 356431157 154360364 158928905 125593570 975121974 529449919 127878952 240835407 464960076 56971447 642222543 453048033 861248702 96405849 679660677 795858303 70921423 41427711 521464782 591778069 547664999 175270636 707818214 831855364 414507691 436801341 218630182 924441323 833677355 459956516 329638417 348220361 209342088 835752532 846579616 127316319 688132340 716307343 132470658 415937115 168342506 744472044 666138744 335729655 547520418 132221058 299545210 306968942 608501363 436417734 777239638 214125970 202775281 420629722 163484161 83117623 108095013 123211818 266691041 480447143 494940747 745438324 982377285 688768381 265983932 242873986 987341476 768713319 200984608 379282700 739927375 648707893 267224389 547035898 308308136 559259736 107314681 549180815 486915095 446805645 43787015 736523881 96847850 724326830 473309133 316146025 43835188 881886956 136330677 674570446 252412629 140957509 686227877 628769222 613591231 432923894 326888245 930187778 249840619 481784113 437276499 854253970 146238345 262558505 358123375 283497120 737700123 431055384 770153066 492932181 256452175 752249140 503009164 111444713 777207193 873646987 524269445 49420795 158492902 75930303 172558120 452246552 129185648 328925619 851968958 251405412 125565342 103668501 666217377 630071571 624896817 803805924 180031527 133977735 678406839 385235558 230072058 669879822 536857894 799190043 638306110 269032440 704138935 791965833 983650999 537238579 812234695 3610955 769691813 340440933 23023741 50516869 491549055 790945495 622241299 263284581 79137394 733701956 672769654 225264610 119196204 48075318 743864279 491242968 889406729 717670394 313932047 970725713 469808493 748650348 765320573 650106565 701714237 813012426 425431130 371667150 896016141 67180972 325106873 634300512 135458205 148674971 138157035 121635957 212934660 754731336 397647485 91353506 698899271 273509329 342096154 237696575 472158022 30521769 855496949 550983395 168312270 664559568 333811585 51799100 283198996 798415668 903550289 832893038 175701267 307890260 775730227 94445406 253399252 786780998 755751198 886117529 53794503 20628289 725044577 324695776 282295773 71017765 26614006 929436732 824645099 170986582 278537041 960525312 770224582 962272253 288048632 182551583 999464185 274219964 634336480 128735970 972087389 898887178 455543634 279377892 777385851 510115374 646786303 510157027 534215569 766667548 5265801 668187501 749640632 228522777 500653408 380112523 189751 563998325 595524812 398812447 133304484 467348814 670282881 470871713 333176633 122719680 795105644 460426581 973690654 713498338 626425215 58436673 57730708 528956565 361169576 301119422 956992077 723636328 770480109 604563508 529290265 13247100 129101192 595790232 263708760 991132644 764575056 94471145 805388231 646795313 785507567 276504412 294622874 699006626 176166060 545780250 912457729 147344686 272279415 311753840 104522694 253046516 602605197 836151416 534236992 327774587 35354024 383603316 432746427 547171689 903016518 215710029 628923573 968649192 567140173 169431854 265647637 205519531 268336157 367312967 894397334 541084028 763946391 71156316 696809187 952875680 838544658 794876083 603782326 783034216 869867549 99468863 776741067 679072322 103222587 44597517 228155346 786170783 512861474 158943748 149517255 502138380 245737688 70929229 468844066 818608422 562595829 286442587 350836680 677528076 287509089 329401675 965281349 597224633 950110740 877346134 881706304 973380034 764002372 99676384 384172405 574048529 269722273 773528926 231525863 369210518 171242976 688299599 588210312 357500809 312594068 366927533 927973152 402899063 462301740 398929306 830318550 132424296 331009913 725545607 783532493 258481701 994224293 56167929 61108821 858669015 183880455 17444065 151635166 384011263 904379706 447583613 12563959 943754128 932173971 995506741 283689323 369932889 964787447 477344318 92962953 129775894 908965570 98306392 981690531 413462105 748235065 796299520 646638325 811358720 887483930 779853238 361744715 676293430 524391601 822521787 33017787 257733461 715066780 350240092 840408512 806763409 282829326 535883082 429047200 667231271 616286394 90648487 565974328 467336724 495263483 121161452 60811396 885849358 899188703 297000044 378501313 683854055 231826256 994497729 304565923 100333038 382235196 394710511 808909590 988372658 45973008 251560840 751250120 521459783 529210181 277437415 582598487 271033679 99014514 948492030 635075414 562105750 740695091 881047525 222049872 476911555 223474446 199376281 59198580 854328501 601186633 50386305 971754795 107316318 990380193 918929137 14491707 682079604 685160318 494266883 198963807 632552770 216701409 493322666 774030840 443982683 579913665 203383536 858402454 16114203 829447146 561181453 807111978 722023139 468462385 554132701 703675547 382228468 671360093 371861043 616854251 350950127 33866486 465125354 587753282 890797675 960289223 351439214 674075272 785548684 793880573 19486873 495415885 24443615 707549844 810646333 607207184 205907996 164086278 935913241 80496104 376967520 719508282 812309650 691339143 755283115 890796230 93889843 373050871 685006198 476762265 249730146 12146071 505293284 372054334 175958759 370047136 637596888 633526433 589618024 531018391 620710243 141065694 424299428 118928059 841741917 482836087 269200254 153522132 536819264 367218819 411172491 17656518 50460269 953958019 710155622 389807324 906523963 586921118 267242850 602444927 667307718 345001651 559125243 271410928 232025538 662263010 62334289 785397020 511920395 732732251 284160903 138146707 784980115 454340251 78802483 360931663 879657689 546862948 192748519 862360466 454641489 132372652 834358097 441535201 977034590 281212824 580292867 844687546 923567952 289009979 533114166 127685349 328993016 439809932 515374351 292167746 770675462 202216412 552234038 867558036 464571012 734934677 644289472 246959240 349087279 814482635 200905515 49421538 192454728 422991668 250788103 841339482 969026951 207429612 337545122 530488580 864111977 70476940 371923124 95709259 156826537 628355851 161182557 337542858 777072267 180568623 95248923 851532412 116657049 491094988 786167494 904194280 55982261 787221370 478411236 598713342 609814125 742655214 123221859 447071368 442784103 46696720 835515403 526315648 697323843 42359620 407001347 284967753 381339288 67222254 504032567 795019014 804142479 737256261 333865626 197447945 779376778 99447263 448226269 898317084 895817090 945273425 823840367 828806880 142229485 424663947 421091760 512799253 98645791 956033082 14377934 501557521 74203986 461552323 196762146 645276925 522594419 945282849 490724243 543425960 327420415 590154964 477162380 483221031 213087193 439763639 979893718 941624122 867163512 193459248 502137875 37248884 24227028 192194424 22595235 853285743 272479187 270733355 808192514 432634887 
288316606 437434243 805089868 723922462 971507779 506074661 157627458 719735045 249035684 697136409 624145508 630933558 966815253 748790661 124019659 377710402 447001436 67421583 511761648 406855564 169640879 75541087 401901018 373527964 19099792 127446811 202994309 248049140 490373621 619900421 552091014 344920945 548087993 99711042 246523573 517220491 911546427 418698222 853872929 398257418 267459351 723615590 259586493 68019260 243157641 796388829 431246916 189558988 228195984 334054939 771054679 527501442 143872344 903356979 210454646 292830198 646045676 866301596 202284026 614773997 150522079 134250646 333498635 753074001 843478436 426771071 84897587 503580288 647145326 588125497 146590603 663283505 884649345 245199509 922555659 728440235 611379828 831364365 816307301 326498439 655276768 132225982 488123278 898989352 192885502 35760539 784972211 606490907 112419267 992297509 431279449 973577351 286058382 551598324 735054976 183553110 729134542 272941472 817339613 496212739 58905585 878675853 745826614 60043613 840973673 772740029 928503947 697122233 849825572 570890612 265482363 2422115 740406148 320842511 626955840 489428739 784120802 502671122 826533075 922400062 805019091 818679522 5667623 783307291 30528786 439293795 245148618 210875374 950991244 170440671 6277644 281769427 687378745 436354373 271349895 877553602 359803090 697954330 376695611 330120030 829381942 795331304 844569741 831916291 760016392 214229456 881688865 604254864 908350128 428775605 256236918 933408227 68014923 430674776 140275732 156550985 735910763 696885885 866716629 745004130 103953200 327147427 364783443 566431618 804023683 724679127 720823499 391625162 128412558 731370084 665434164 990926880 131706063 432566873 891101014 621047307 500116313 460425497 577119128 529281183 374914334 509777906 6638007 51550582 86482399 921215716 60425064 355607588 752114923 902820370 737660190 403119748 590772268 564084718 37372006 680138895 751128704 482054581 815639277 535877629 464689532 876428348 185688993 101645180 753308040 968321322 168709142 295747432 270469738 199541809 511903571 690942008 917954235 227065483 811365347 72037600 810652246 364076524 391578471 883056705 926695499 106495236 803991856 707193018 559707219 352129851 279171121 576864125 361765105 448865741 606665905 768595931 488118778 636285747 449901966 177052334 785550373 792746609 667225044 801805213 490019013 178543707 33419178 898828046 57325311 150851864 106351674 356435713 375408783 646872393 292030289 354556303 347926364 499374083 478544574 635432588 706832297 439416274 616775421 179162063 458305981 91831276 806168340 337884245 699696704 154475300 733442468 82296056 155698225 25924420 13014383 177422436 594470130 49032482 846939675 580229976 542890431 255900997 339314677 828514166 130365894 667747117 562962363 63131188 148051121 577738521 297709558 142975932 263120315 651711831 390688776 957599049 644826441 957057364 982433143 239007675 939821578 577692819 91200156 835009823 59364875 980899111 919684146 673382813 222431419 397124053 725876312 939341757 428201937 91924092 691075232 334223648 350353458 987954603 773895279 281206993 727798717 489851793 616566742 639861320 646266878 231837090 556717869 913618463 593348680 98604832 516827446 499597296 595582848 858693424 382036115 198117809 287009333 954518184 859237093 33277679 380076447 979829226 149012537 883043940 861994842 609213890 775753794 70037649 483970917 41609731 389821969 73157321 831369302 156660102 884554678 99156828 171320375 672983920 119997509 915352148 333838039 985109209 893082708 346175057 646149552 712917134 456078548 772672808 583875573 273154954 364849854 616669316 991657758 255343128 566392719 749716493 24391491 212024207 697384204 234528623 454037715 658872824 973870661 290132466 41802319 796626391 610613649 121163754 478593754 54419905 90221748 180664547 284924718 880926987 326973742 293277484 884847725 481748732 479907303 394036419 830198441 184232478 175072342 206600 825317862 630072781 161386141 203947464 514351207 113678386 417312413 349050605 103820396 194719492 566583399 948514764 898312890 745643644 542603519 147657910 237327407 133343389 648706613 183436133 827197847 983298688 135809232 921045747 481080160 343377293 689554861 671249785 547457196 949690115 970794111 281713323 445202905 283314130 366721744 364832081 102256125 549465875 482323266 262798954 142167026 592242195 246863294 657683812 238813125 571868714 749292724 784310236 934953442 183496375 223654340 359104884 845495493 223711158 189828676 111720398 109871889 213498017 815583133 429211425 525194147 565159233 907255271 128316686 991560236 347199920 814004819 791093261 26439161 869915499 743828626 970322251 396779568 17546645 728483963 129201987 120370205 904731517 537605451 326334968 970891718 481258148 66096925 167248626 155176744 666023647 552500333 256973095 400283333 660872657 628524242 267197777 759523982 432509724 441476658 808862458 629805040 771238880 862035966 469312752 792270076 60757184 411954335 609525088 152968819 400088023 898485825 260413661 557867719 286005032 312116411 72250322 182000285 43008678 246962875 515039871 288352361 532627826 238100491 592909106 998647155 672202672 104694192 21805075 596310091 838106288 409352669 580059256 247747752 320282916 65415965 989548151 738147356 30596949 726609554 873857109 1260850 399230159 584737337 759253313 978319265 525988456 653770330 684016460 746884677 75182715 965657394 593746787 888015585 542046031 267083524 626316305 772820712 456630787 764160113 258573826 912401616 29081968 329464998 796993556 972945009 846742105 617428097 205513630 948001829 649091014 708982390 745294273 503790034 177286646 794232310 837290311 645436691 741309566 490921890 862177974 516247433 724162365 855696618 83581018 956254334 167721041 485188228 308424423 174762478 632479753 939820639 945599311 525127662 195909964 87018382 282870656 160215993 573546399 678411679 905153504 615074566 96635099 256976320 98411053 229673656 67133533 196322897 232024889 488202656 190846170 559057359 590159538 883724400 157480432 424506738 524516144 428376074 168408797 364812206 943595728 296658226 961308115 549117169 232771780 535768316 72897662 286840083 512710051 240378490 40809626 20222592 504462887 452854862 131563163 618044357 684456018 647731432 743328293 149362042 23481964 18257865 400690697 895877172 55115694 33551638 68036689 500224417 673358938 748828736 292524601 372698264 585063705 263812546 801386043 94137398 316810092 397570815 476876828 623923601 661812030 707588983 472328333 975551687 563770612 379276105 518021748 449114181 213238536 238478728 320854883 478426993 945184169 23394757 40784363 453801656 283298272 211756589 674143049 131163936 975148053 311217854 611417563 459529700 648774603 484885408 666051148 169142799 522356690 274145626 939719274 40290825 756413509 260344767 650985014 799401419 38182418 45756519 217405760 964963983 292374307 411451021 978419322 802501969 183819194 220470945 687093270 126692469 198464639 865352710 641164137 36799278 883550583 772287099 350846648 781580685 656566963 538020144 260459417 942721599 219936368 530762769 430046880 127943998 447806049 673336247 307367677 253425141 437820334 437713263 40814777 81013424 801212969 616560597 229486625 897977563 208091576 508607771 165984832 884339019 75845892 811274810 440293706 618857034 575896823 327505252 195315918 690638459 512810995 481374499 311662499 622343633 391101875 263499392 301363641 359882416 650721721 309877964 149350192 259547954 560909640 981815787 291619776 841706798 222402176 702962834 828568048 273244047 579302002 892894458 622617940 950052786 890324981 81447737 916538526 169807484 398064746 38055704 164580584 925475599 131824942 48483662 613022107 458564849 880543352 888041548 509107402 125937438 941116438 929905593 20364655 197435183 726894534 501878852 319793271 763830082 956195812 784667924 272695723 490279691 903839294 292688994 632857075 659972300 466023604 846523895 576500018 84768338 96171625 140344415 675923054 288758445 302070852 689063299 871069145 616288232 525883562 870593638 315343948 870107700 775669285 157302975 653155388 770750037 254492372 54894046 926157241 10381657 933808528 175323508 540929105 812273884 733702128 462583727 314108900 965831603 677668096 709911322 633946465 570827877 583400524 444731466 480009609 510478705 504055817 807238657 157032268 999968936 560052010 675900352 890885828 845324406 881686909 913255911 565379390 580676135 884847170 169017046 956866075 40631108 876496012 423021051 36948613 598167858 998492956 292896311 539999293 721767846 970207220 130814869 572013467 734844389 702925103 407210936 597607345 53992493 828554625 161677537 803013225 259976098 839893262 501449623 447097506 517661279 228107423 960328767 754990495 596881278 515126448 536715671 325973202 151905969 348879563 450109412 924937943 108123280 628597521 6820999 212179520 891661009 696059459 902179658 279299219 666660521 945963284 247736743 350140136 106132447 516079707 502776840 179673417 485972795 654357866 796539446 139841226 960121469 236290361 539479146 944567266 82916486 391012937 625402169 296683094 513646352 660783467 11655066 758530828 83485341 985791507 795422925 690137160 670993817 78230488 683993479 549891104 415725979 84291628 594076220 33907847 77020427 930064453 152939061 505560137 150391620 184866299 387633142 201765453 579506411 530287260 75595932 33196573 848009419 441998805 739577793 55428543 294881692 109629324 343853789 426973682 999990211 796668561 716037278 902336354 409950239 436729826 838474219 396008629 50951785 205796800 633324505 110653886 743974815 352086799 987411464 894475167 776294922 704497429 835948975 845113660 451602146 131437113 491097713 1831235 626789433 98484262 696341933 281287341 866919180 511310 737028402 636192921 975054631 664849131 596387741 830151865 260792304 341060750 781656446 607205284 290982225 277493639 990525817 240301701 755021624 730962752 767654805 758054917 55562357 534375405 846014072 407604344 833822492 684361459 252603783 201581315 472953174 464595083 746855932 187772579 158304867 929122730 491571607 905734988 734199050 59029599 482239005 123643741 247000127 971681696 586934412 586626210 464268662 431976269 661767915 405809036 706996867 752788380 419055140 824462883 693500589 294028256 715884379 173030814 616691758 204499424 380884134 760552893 986940548 45097333 130351118 772687428 963023746 931382917 622083799 112075092 940932729 139372504 620291257 885281117 207768650 49644022 594921750 85009884 182157200 269665266 254566077 679733715 291969609 544534776 470600461 431600834 347376241 322543441 592291919 729264655 138094565 399784801 97076512 228626068 469634263 409466027 581720840 656721298 448052767 958325738 498122817 115552028 937048779 398299681 806569812 580388276 995736003 924006312 469608687 94610046 267449653 66026880 543133508 121583398 483451088 246100970 971840111 744370203 629313334 121095747 706430462 845254079 296467634 928769529 259397792 721005585 801476254 57066408 715128679 962125470 192166366 328550493 635979195 412326038 687916010 221855946 162870542 662844533 741827769 184796636 632893130 844445322 52816720 417378447 128930666 171848490 116385456 681444863 162371739 47450012 969959868 50040158 790246291 485074959 234447996 157505386 128791771 135232295 160705523 199960488 60142042 768774062 604568342 96917271 953960727 842152034 87219131 5163720 566709785 920077721 404826111 294664255 160488098 197929366 55976711 644412431 205489281 435199561 277478914 246931000 55479025 21709407 62982494 414740466 219391939 794969805 236549769 366211987 307545662 280438532 695167199 253399740 468777798 621377118 321286648 224365840 425609001 652788680 798004016 721264993 250577479 34066293 360477761 575896087 923698134 919943816 552525107 781446527 346277269 107736530 242385005 613559511 531799340 654916293 38716358 121537519 330442584 877507197 807746510 109433436 993668280 636831686 421778633 680327042 840289785 993638201 975311841 517275615 723864056 799572582 774729100 350844684 256187064 355916352 489400959 635531881 98156164 22102664 482654636 844724899 983419157 54890155 745627109 992258139 89804015 30179989 780222173 695308476 335208042 115738099 87365121 15844634 63048109 443348741 765954799 252917745 732969712 806559201 628828994 809920 113753182 856407859 380637506 358319533 735594424 333571544 118492353 154167705 13133624 239958986 749724757 997542422 883688857 155888674 427035785 258232961 11889158 78093964 754043930 213858832 433823565 359559681 399778950 189063130 349950610 453936212 344970616 228043428 83159199 37628762 499453118 697829229 866369137 389658580 966323562 617741341 120586235 4461581 115875771 76175042 28159391 617088062 684863045 310275996 150918289 645077447 611084290 30364015 170942826 242797594 514285938 430780634 558957047 243425002 41720444 296406209 969925856 454282817 530567710 841953522 156898407 271319178 316619455 279642043 127237660 206022537 746902039 659525446 903322733 768279793 46662345 463038063 35909199 581912123 245025000 34891614 448743769 214937130 640276685 752155205 210357500 865047435 485089342 115207040 771256403 371474202 817536577 926709371 109463186 838683741 550707720 670444852 565749449 580766976 491055116 53433035 347307073 117588361 204483388 712892969 201893412 731031753 893301844 672705261 440689577 20192825 352812770 657121123 300019138 718137811 686480990 392277211 286299048 972042810 875132871 66869230 773772675 141286087 534825431 65136036 94260462 403938608 491742865 786416094 837136332 335694441 953109916 985669798 681678990 101328753 863797454 141691946 513126053 195319556 962252838 785427624 685123803 813883593 527634015 93014085 945404722 353015410 265485465 296127664 1377417 204743193 972959013 422559570 75673885 674798763 993050564 260840974 79086497 830455618 411465269 561277928 53139126 219914225 358528083 959263444 463046272 903707565 228238419 705719339 32177437 132508963 176868336 853945962 145298834 852563168 268638543 30448149 732995685 196180773 164150216 443190528 725784319 439922992 551482342 481465723 892973625 633910774 491690880 510511069 30254572 92225050 197143516 644603891 581891253 911469062 667007073 502368450 881679200 520618241 467183673 418107895 523740700 439714034 474337307 788459873 570313224 896142229 483735220 232563638 914531547 682427027 273041399 329221861 586219285 996176011 470663440 258178638 181855387 142099168 409063729 720730538 184227132 531179601 259623430 207203289 238776425 131082953 536955325 590939247 716684804 737366334 704847524 273237777 940808124 233605741 985630128 254555199 991726998 87622709 97951751 728590240 508038158 19154312 990990764 212420127 395065252 723634497 73486401 812628980 187994777 282108961 887849360 218166820 57095437 387404176 976844439 843347900 418713343 77250109 983983345 52677626 746421287 421539603 524359291 62588622 833740427 75897698 706561147 241769930 179946972 970806440 182652653 595147517 781774795 195440003 234933091 596395964 553902981 739141318 252358850 996098805 236887789 589032574 203257091 288292217 556556613 538440914 401348985 387242936 284325845 670103298 817543605 244541729 689038352 626373312 997762727 293583503 520155332 442329539 709789843 355202626 660565369 708739566 68813503 964915137 422148683 29075841 384478287 313422877 166545399 558847728 512604640 46106118 461592066 761291814 149666250 62819305 102281665 211337881 617303903 178941579 558304532 940941499 321125133 65956358 824087985 885578584 665369136 890929566 462854501 134828820 880749150 783969353 289716040 971555562 284476369 325513795 406053762 209266151 132822547 603661935 754171926 786801467 346195160 995126327 723735127 786396201 857365692 963498417 526361377 518108483 846763548 826224673 509789156 750129917 389622211 120043756 375577693 49859019 284193097 138600732 629987187 694687492 216238098 334930563 391107204 510664942 51940360 568823849 941376239 160583785 778714927 83622296 397198077 478289631 601813573 884078338 25945277 600540046 858717042 534533736 736920910 340653373 247588382 965186343 987704263 20840860 740759917 626241146 838501317 467509196 674128920 947277026 885437021 138623557 659592016 516131515 545044391 6328231 251748032 586390032 944061666 136466682 210774125 12616810 865985054 530252354 116931104 898114568 261433545 413333652 735462460 70904951 415277462 524076334 953425217 106530114 137814277 337657191 930054495 229736363 43829980 816015770 453884280 90613016 362630288 715583491 74886662 499025388 356659995 782886665 372050489 910619407 382872655 473589497 469711350 169153241 476758393 548796443 960892381 530995315 600716235 334483045 971514267 300140290 230427386 69547540 503610599 616195976 630947557 31190117 20118686 354464245 547237713 62625034 492300500 18968750 107052955 776646212 11788522 122501925 836767836 628942607 994298734 217364849 27244512 141211295 213850556 598288868 247052271 825062902 864680475 712103585 540159482 848902512 985029781 816208884 234251677 203537184 478186843 263644622 775103018 937538854 503494097 471175922 648394490 230341039 9738263 279319212 171899964 279018819 634764686 146836984 571375900 344221009 398086825 622851582 889554451 33758849 684039476 677470463 590426081 474757159 204733314 572012463 52326839 59892884 60295802 284637124 446381945 659692274 144146882 858099884 212843218 591816621 371734184 304694299 849646387 758940567 173519468 205929487 412966045 589188700 188911893 907943165 691984818 641273311 99642191 705372953 177436384 400228804 69068786 36194911 370935154 416353281 36086193 41461846 950608021 3305173 340393574 650099516 152509411 768883636 134898794 428126715 870524517 419523967 780866535 456411390 219735891 887111531 688976676 342598257 887902264 642109817 153196990 623859212 624352417 648304280 709412894 454576788 361248917