1700 17 52244656 133062956 590969913 537843775 966518230 317552711 313730041 948747539 498890593 723453244 913462649 410286461 323600046 832142027 679662059 674679277 766184524 624469209 254608463 904066418 185206900 234009 323976153 476536551 96957181 973572239 159837589 433877877 686304541 912732126 323230469 819805681 339732735 510270242 654202981 741872191 91526739 397277977 123491251 409300297 655247129 63024193 166523354 966156847 281535921 146548769 528562869 762576437 226540667 266853151 892882053 290871495 572399668 583761965 272804281 322068913 575184127 841297986 967030837 795462761 119857788 573437628 208364676 553668353 655779244 27746442 70957999 258411491 675612657 31087829 632176889 271370558 55279221 941053361 394844661 641856509 809177411 662481547 410143953 885374156 197042193 86516351 349709501 872331977 235869337 555485873 64585814 464208856 534807025 703703033 508010637 812507926 458902355 102707874 933450911 153885356 287462105 403060574 262697913 658657505 741835010 428163795 383845041 723351473 553528065 569910374 692959333 54977733 723123011 743496511 585116701 746749961 908173196 200747845 305459489 672550859 743852880 629692629 878461421 938953017 561822558 866293729 626231481 32524911 407556606 254385531 137745791 371739521 787843945 153128731 804954529 979402757 120340589 718756689 305853601 70613451 622445349 739990229 352213331 519878464 378571103 2061581 505725220 700251405 429046085 806004308 599173051 745479517 859652561 574139561 228789793 795629153 215643421 7538823 145180445 4911857 692490561 892722932 438356755 126120237 241054007 160427856 780062582 835128785 416987530 635998741 943417981 23952051 79998081 218481473 758925519 394432921 725917077 642083825 426577201 614960626 552683379 735239275 988718881 355224621 103117161 470421430 242724185 84675977 145920461 23037452 126506751 676984849 425784121 617466837 740947566 447600108 262460595 362774953 650317435 343326213 872458689 604840465 331300793 849806857 572383777 226459085 756661089 928080745 760638900 932315185 543869061 399421983 551596673 38667001 707000511 874221037 465928000 573327677 884521412 949994751 480018301 748283393 481606454 25852561 321196295 424579841 481281401 868484757 985463513 25259419 36053058 260750079 711404501 751410485 922770087 140889691 712765010 710171589 457721306 838717017 789797237 499224266 939507906 287613301 493238262 686432099 694561597 800245993 939692141 894585311 212681881 814964830 161011633 135012121 898750963 262643504 811631030 892905751 681947533 11442419 48801941 446001869 340447391 476957153 723820433 417924601 893393645 280409633 120666341 935384763 333699591 132693081 732739184 808173340 501552971 587634433 140056081 965792091 981211349 811463787 113558556 204916461 359699457 386316681 465171309 403948953 317589561 852726214 743290096 800858407 991911936 640131835 264651588 764017102 851508147 182438699 533624360 557614901 2788701 418946685 161200243 733345918 783130495 409338731 162553864 342123548 995357869 572278123 903144532 573703981 387816556 394434973 340184798 95765598 778483835 341628852 298838381 489707621 338511851 510544797 701335033 586066110 11625585 938968041 382405579 519263749 844872141 831143246 153785009 161772545 21111114 417606609 897708590 739321651 175304161 766770891 111337588 236840871 809976485 665641126 206623353 816513371 240207575 621687205 845254011 3709511 546800719 948358383 679015959 576207383 998969183 485975484 462170551 850009873 737199721 16041311 125108999 715020668 175478280 645821945 762894176 404165413 424260781 192557966 670649521 869793221 10167432 288906598 379335606 948560005 108885605 146896251 742571911 96252606 206782881 967258543 352219552 935022677 712139401 34914861 62351381 863776163 682066660 935556273 644917681 212609445 885337361 523114377 73978862 885650341 413908501 154078123 445885799 663281429 630659329 827608671 845988623 629792429 657187921 611109659 849053947 913861769 215302253 5333185 290899591 620747198 180525656 985929697 822963643 108848250 699227804 986490814 163058769 982529841 813665873 63531133 268048617 186508071 25686652 258879893 245849061 931667585 993249752 301220001 819084778 908488235 944843283 416909543 999612782 659721798 132133876 444320905 698888151 125060851 235633861 540728742 354960844 846356415 23246761 121290106 230104743 315747201 422687493 690373689 930099505 130605255 715819991 420119357 132826715 453319406 134911809 107576384 995782459 560290025 899668181 990499587 739614903 212935051 832145911 898142171 83395121 173335465 461997301 274712251 486911993 895144961 136032737 456670375 9319423 15386051 162441801 855594551 81691762 166981777 282620051 388522730 427645203 508528100 222254000 247560481 284086323 311919681 325314762 648696641 158915849 413578998 156208924 327107863 713780185 632663136 514319665 920397881 59584681 135575713 258931849 38474645 181079767 263751961 527438431 59125001 797048152 224340325 564554463 608748823 821067627 278766940 401370646 427644395 189530357 441460665 934346201 245760584 942415085 526425643 487191591 699781765 704139771 239910870 546701453 689667253 370285873 572240881 971007191 150767441 747971816 938997674 11103964 871505313 609585801 419874547 747562997 375366929 226962740 741147001 162719657 78450285 428728521 48089441 263186287 269812011 129618837 714697416 915065138 977678393 561393471 580814502 331885664 626714041 718443661 407295502 933157896 976081935 64802916 381025009 390815681 615092379 80340219 378074781 74667346 437046391 455346151 627131401 21931301 766824209 564960622 29364623 562132917 586527777 453542278 895612620 878398625 324432976 360778327 449819905 571061969 818534937 706091263 402943019 924929089 429181992 420260362 945928865 271744751 87951329 999482602 967218574 728248125 849113141 976348781 438419151 842393212 683199681 678057321 979626289 673538183 27361259 332374801 999656461 98716885 512538467 602654484 103796201 214459451 61975684 486626261 624540808 627311260 182901741 341711406 312474113 329781445 928254009 977972991 16171191 329158080 485220774 830394150 914767007 553928297 56428861 991366291 134815336 299261975 888911867 696871472 50057215 424802040 290021099 181926377 794574237 815992318 670400529 738976555 939741821 237085147 510701668 704927026 556377212 822939051 342360575 539007395 863141291 900771801 756052754 797951345 458150849 379873333 905936811 18292498 313451967 563911609 122771501 49324350 261718135 939308355 576028713 902097379 796944217 62515845 65979889 677303221 62267681 278405877 303475752 153506573 887532905 908965828 446762849 939531986 671585406 486548891 591861446 857970072 126430477 200010293 221159501 645099100 872259797 37975283 193847801 450578937 999759293 175428619 618281631 576088993 468471216 699543539 874008932 516761679 886360821 243712704 560416085 905521897 212816319 554282301 730919051 869029213 330341285 863934551 98218913 62973441 485936195 594367014 57476584 151932151 527515225 487725857 711568681 650145499 136158341 688283842 759287801 701405211 751612833 234140156 722079288 798753411 34174091 223911785 907119041 108928401 120554241 147070629 832170458 20278441 971009039 780251773 416800031 874799600 231696657 801835691 954818751 306398690 132290630 717659405 287500560 196371344 309429457 313635587 381011465 838183484 613548494 139349635 341199273 541777601 419793537 633883629 839975375 274501951 426609396 996577373 100387617 420353651 504093999 45620157 647810785 360080377 71056009 689786301 863865942 87764797 511520286 226153287 760268547 932680067 823157003 129017117 943294801 949124980 255556335 804454401 664310946 106896233 381413701 107017238 148495287 846176825 466433376 638384181 830456291 177493473 33122569 613152902 488774491 329792129 624730036 45431212 76079801 936060733 911029928 570106153 691510801 285146051 302742321 933485761 784028671 681609165 829471207 297014525 633225787 800499613 884534689 276086747 944386671 137300741 382151769 636308865 290738716 82274692 337317477 508380008 645111681 874360563 162306981 171077714 577060273 989376581 155210605 457724521 326980959 61104806 909183501 818331689 357225501 506345670 765716321 13987903 881343743 532123609 85836426 140332239 531263224 837563116 884847409 963244280 177718491 657123524 906191817 523617153 778517023 798939141 807108653 848996702 552499128 241660221 383254295 499444079 539457613 897606265 193044200 241480791 629128601 88147171 570688325 996657022 154573871 176530522 690733925 329375371 620711966 770051521 406113675 219903781 772765401 308531441 425139122 663226229 56308341 358157523 752550036 487839185 67089731 603131147 979765761 397138861 635719929 428611542 15659886 808259545 200953340 383028097 831644361 473616681 217652558 754763969 641111162 400369943 636967418 47694568 635727761 820941425 462742509 180024565 648195686 108180707 388668174 481661503 265364099 177535655 741287379 854208421 722478491 898023381 736001570 448160001 896224001 753763425 118778723 127128729 769387351 350530487 412673241 421604561 38841506 324195423 167001909 431017581 957960201 162903953 594883049 935133333 648790071 195858833 716626209 905803087 201636051 383399293 317281666 422625741 676762464 843426217 74864001 307149796 535121225 549556720 801286429 313873994 518954123 550668793 827244461 288373761 335825321 163497883 620920001 630813302 722636186 119776601 641291361 165983199 678179476 907750935 946361461 431926401 627339034 810306053 98032461 230875865 310381291 415430953 616464241 630320489 833108281 993299415 70477226 142074471 183197617 486879857 24799500 895585201 618441473 226166207 780198657 65334297 246097017 391668113 360620341 258133467 887808071 287848525 470928541 521930488 526949629 28513897 651262548 330488601 6536237 988411321 730012773 473128160 611263162 174626601 57673386 898606581 509862525 10971287 324636860 109767251 271943173 569263412 993759906 62872417 520492710 962626623 384401095 978106073 532043253 433249141 568102191 112369197 251857137 303995583 446929161 191840175 218721642 71667805 114626181 396115665 674798031 32062451 564644817 197739131 422051 807281431 513456837 626689586 801476847 427726686 286612041 579299181 839099201 536228575 766237557 842875867 202418049 720506265 262803251 721028072 843573367 306383711 797832486 886328161 427318154 99496773 418785959 525735873 773918658 858062189 809646341 659062897 691464325 873985 589604840 967782601 734734677 509484151 887498751 67268207 365000501 868181785 549798857 415042575 959094497 108964760 135440586 775402153 314842829 313047451 405754681 236131481 279685644 659711593 70864359 342238321 606272967 409241627 312406815 973637145 213550221 13448284 600111894 874914496 302019672 493126681 804953716 131055417 426312853 642084472 946304207 992088165 942886897 145985060 232806161 932664190 397832551 504220207 809808585 540693457 678593105 926263236 551207949 744408419 195096725 322330575 657638441 222887963 118005027 650842126 820468205 687332735 979241433 533073671 363317553 811882401 978247711 191924305 410126551 658314731 253726753 841671523 693726321 395517836 792358721 188526616 194085041 200708852 544684442 418107257 876810781 985537276 259590180 505143201 530238229 863552441 943860765 280808553 507943261 852241464 145152753 142045441 779417825 8685581 15529876 137648089 187277657 874125626 930791001 767299708 61777121 935502406 894092225 578374349 767091591 191761835 592396131 992558821 347121017 277092891 991655289 554129473 522256331 604786030 801603601 17932063 603621107 317276488 554571751 830811405 863647009 441067521 948276653 71130711 298028277 722931893 835374388 97028334 521611681 925200049 181490201 458041001 557390837 211658357 870891537 586737834 575336936 822895963 979169555 508282905 603257200 182785520 694247409 883933221 602062687 63589829 212257281 650314227 229688931 769553801 194290288 299477613 738911585 188272051 115155253 519652666 817243353 78233616 946576601 836944001 583454693 861205951 305781273 251313123 663698537 33485733 234382257 688075723 169863640 594531489 675665741 431485079 12060635 345160696 390658971 266758248 582297313 252342233 100920058 495351936 727404632 440420094 569763692 273445601 514030565 713911217 404772055 141032929 580794619 687929625 44193057 169626051 748281872 258256231 513177685 716079599 88294757 600534306 609197862 287377096 951910739 395968641 127073385 608021981 360625331 683026014 889511985 629731406 341665029 649076801 448443143 193607136 817276481 371747087 632020469 940404865 872449861 452283393 879928783 190493789 128687197 666635501 934248357 668664969 821490461 894922345 216762889 467901156 895933539 170081221 188411729 335869025 646402507 898385441 507982297 65533895 682863322 719568289 58655399 155905201 981929893 263555057 275886133 124716376 4269576 265288546 902875914 87884682 939829601 313528793 589375001 850115721 614536829 454640673 905147657 459560001 151412737 922049097 811733089 955207750 985543742 986087838 158744561 647637393 18881751 817059100 953126651 729953017 691352609 932436877 469156633 116757062 673218563 508874291 771421960 855309179 7000241 71706433 587673837 241538817 65295517 967842608 833963335 23076293 786794236 278341187 451246017 650283297 632761481 245061267 745543973 144953065 492667161 501673065 582296858 437110629 530640129 435092984 348522453 985072205 942786243 840489 166239909 162985281 83917669 231779213 966220785 426443211 427688191 496648121 201459946 831616345 321108566 413247012 620690787 65982685 27950337 921002401 579659614 834218740 919723262 938315283 155704671 256384326 96232333 115310382 956664391 153621409 660708409 952499229 888638895 143610275 893974288 84006096 49835381 380200491 762627573 352190049 730438009 921340039 292332441 668295919 862558172 86085327 980946769 851936258 72987557 310157521 683026353 664266985 836167529 254662445 517821449 697447857 86930351 240839707 774941965 535626396 672529681 706557825 241777665 373548707 462389872 989740001 142155605 243833664 237311081 17567111 975988033 991261877 119223203 223161098 286849863 497804809 852679805 208300307 359804951 667544793 708138855 4139209 342550521 57620951 289504201 528926401 13647467 169338825 439377121 86245389 94507793 158949726 452114361 345093197 651848235 811188019 233909223 902210839 343586179 121486981 435054525 742124922 336470162 426702376 865008061 71465738 780355941 942902105 337120157 635488769 554858265 367845811 457808243 529501433 93286899 497840733 354605126 174086930 564709201 509862222 187363857 549349964 880107451 376986121 664888157 546089665 51047387 118005813 759914465 624283618 726712861 31608731 248883621 364222583 328587028 540890517 598481269 251520873 45981095 248016184 310568281 613085956 966983165 17238797 116898176 231572075 768364817 405382457 755654484 702568501 630138617 845295111 669295408 706400013 972183205 979625879 71805441 687030861 703223478 233739341 739906873 821082417 53159507 710612647 7712245 322283875 808249171 272342469 99119041 236689665 560902236 736333129 879728349 606399056 22615683 77582381 64832854 634235807 950750051 184210301 103026061 679074306 373136486 400810233 716197946 547902510 11616353 892967909 345243431 92222801 242063151 332120177 165939705 586495231 316409496 775032321 869320381 489025876 117308074 756486868 539646953 810347161 931739017 11523231 437122451 743153601 180903201 391199721 473387079 713602730 855070478 929965362 140440233 126952574 340347485 685658247 98067937 296843821 379809301 923924415 992167329 771382985 206325833 320775491 589905201 47123771 202222027 259761837 531055651 693341657 752600186 399573734 568520071 364890868 106082845 456444578 871122903 69927389 855146890 338405581 757311193 988680881 504923577 187545977 620293146 131509673 692129206 753413025 416307611 251696670 691801185 6240455 520537074 996041313 136926905 248441871 625258789 792265529 891358161 982404433 872564526 167200670 467171497 381497442 677023003 679632963 908759696 2908021 140822553 908374015 662054106 695788636 114398622 426933261 825866147 887410829 456574009 728748729 166886778 573855051 706338555 820329065 332853149 639434881 576518487 145906197 806676975 31033246 771616083 955556501 440517890 273126726 854912337 544387345 518274001 764143579 84796909 465047250 808835229 979272211 273228470 400124162 669018433 347526553 763463171 582232001 173219023 329813580 201173227 275052227 495168453 496481427 282250026 484597881 384676946 229741131 393343146 3653845 71427522 391041314 721841117 717860321 950372708 903414611 622935427 785794881 292254314 113245874 608339601 68799689 617836792 762282021 35329825 66015711 611446651 712468245 273042691 799179596 31779762 439203721 911786153 437683946 435161073 747972509 685426599 578944426 805083859 585538705 42037853 445829385 113171898 129265119 911849969 861394281 46878135 439973889 932532217 10905755 180197941 518625197 439638876 957735731 269319991 764831101 938572753 289148997 743832447 850224369 971693827 43565431 513374063 888088529 265362153 387904769 822906061 433706025 629833401 46332201 234995547 503284301 945641851 530222948 594693225 814946649 289483833 701640045 848422798 627048219 884412133 539781901 203717427 348419101 634801902 162022913 432811993 381643377 266542693 329656891 905621969 171606666 710049229 4456487 641896201 651623769 75268301 522128398 842012089 823772472 126838873 655893161 217848402 420932398 611581617 464345466 660844253 775103293 305313919 181412395 214939485 265343305 16438177 329474791 348869156 436984631 561738887 488876737 920006317 951525857 63583410 456004085 768543193 424594281 498772841 892446442 85497825 931018445 997069203 773463585 7576033 11471519 296370972 1677987 903734253 680706131 5302299 838892883 293322532 482422937 752830001 937479481 214231531 490018601 700198981 563425365 972439981 343781041 93050773 292768021 416596115 232002929 747358941 608320291 754970021 926972161 588292993 482006695 765618185 20040826 174333121 248155741 541187021 835100609 943727262 116362176 762986541 815413441 325932117 778106921 935355113 671956461 100971201 722424865 951605283 400461659 709609311 44251180 180865595 328006713 910909564 14919849 35820249 272153239 271942072 866275861 641470633 498127021 562858161 886359105 67098633 423311527 299547117 362746421 716434675 181535025 221824376 910746800 381127958 659638721 934880007 887697576 480095105 829000143 723659381 27395163 269556901 156074318 505419819 625063561 894712371 412488376 798464759 81209461 897469199 912841417 433538077 800623068 931823631 453699969 74803376 255872481 608370839 61650711 166503741 815320431 575590517 611344471 512553258 720930920 993192753 263244388 311078915 856374116 431251539 166118575 836977916 174383511 554695222 748993785 498364076 722747598 760570221 20615125 312505585 581382716 497487551 63471919 919656577 617705009 167983711 684709632 738129906 339936226 426146799 901708863 192898557 745244859 671800392 19893470 955764260 484150243 80018845 969103945 177762821 261951921 642080334 913890326 538714041 871816097 207228691 455185865 961399956 887476465 365367428 661495201 792653337 522727701 623525181 639391419 85711441 673186114 13997869 477461089 675284657 617530304 701975135 837487420 91968752 284008181 496383963 539950026 204737646 252358771 242570941 549933483 993466900 223457921 133715218 522081461 51336204 129288746 543278990 643529811 49054164 647856641 239306953 71535981 344562946 441207151 288962249 646766930 322531601 50647924 328675792 944321205 223548918 423133165 420739221 501722926 580613248 582634625 179952424 442025245 232603861 99391375 325370517 361208061 2865171 9897768 74790626 211698881 272899417 436864035 246174251 254068513 637469096 317533185 763091841 994823076 266419731 758527555 377207459 169817874 735219569 502362013 204637609 258772638 231340373 614752785 953732126 921062111 298079346 739599599 257412273 580208061 846953231 238051585 188568489 415152277 844510345 294175053 866149617 80186863 222001463 274401301 452682457 297814581 634355091 985961613 355672753 885469063 902967261 515972816 787140933 23745716 430572112 760442626 35681891 633390217 780646485 749039063 159144896 728377724 40166729 98310401 179763201 433928147 367527261 647568606 624040961 250353201 530255270 722920197 20974039 160654174 799222771 188670357 537636168 685503897 739336431 767213041 278487761 319651141 368057025 874672632 912554691 947701501 837761757 216275809 484205646 697929865 284324820 997711250 647853274 224653437 467807491 369804797 78956209 451204951 578285834 550096972 966442501 746036636 722884797 988180040 56117537 450514911 799881916 33336558 386548897 936350069 40105281 389952781 540650655 359011396 276036801 677530806 805553077 206934326 905838049 631070887 908904801 987687494 265125101 119056913 886030731 424288181 10732126 952213407 439968741 97775561 438745101 463254087 81521301 862752497 557847060 118366619 271560417 754388158 404425254 704704235 539248909 447863288 565206433 712796733 97456001 425602629 982027541 97698493 759911497 805866851 206365241 877065199 194042903 168705266 486093855 617932497 4523425 268714628 203498037 872687355 953816500 139272601 1545918 393895589 471233072 445662345 837304214 646113461 278569615 701769057 272976636 67274141 222159565 811017025 213893744 822408455 245175428 501018169 739545076 611074035 951537333 964038516 181045316 522796679 915197438 224994436 73391457 379946509 591988057 6416101 153422235 925113301 63794281 553360139 965039057 331564996 635363504 142653329 130653597 312827137 289052912 90140750 204132203 824660506 102929266 861409057 222339693 319306209 436919378 680689907 20769073 760807610 170546859 217352951 933394702 29922886 543902425 814379773 246209969 244590212 486988801 717012951 633626545 638374277 698933374 300459175 989662313 176612989 55979436 533286510 424427445 114380908 182820689 361745846 224064473 418281895 661268598 157944934 330619021 567679947 160408741 380987341 641242157 254501084 263256001 396958027 921363817 929381713 175347375 8120865 497454316 122554198 618611945 801410982 614226762 415315889 423587635 809918589 744066357 858331889 654570602 2180645 471408069 257022961 244880649 408690861 961131926 460552865 599466766 706814881 381681957 640213252 740396838 710211281 791049488 357323781 338020507 473855401 41362231 147877896 593031464 139390314 105685479 529494447 214270257 270792169 628373206 266233051 6731417 858253562 130252390 353249089 957664320 946530763 156654668 559071023 962508128 662764433 765949271 913454046 67120727 865184577 183082539 30881999 318111749 14483469 144506321 233994895 390220311 94093531 986684926 305762461 29072341 205274847 246087151 434451506 875669401 140845983 769101761 829900017 459275933 190098768 588474207 365861881 340153345 910194496 388551021 826741993 859836823 687829955 483189181 802054225 55371173 756602657 911104941 899259970 402889331 573335381 596542582 520607072 954029727 78365997 796668950 825310152 236503841 169710081 398196165 681517860 691306291 894885518 318068101 107283405 682712223 549115675 229109433 890193242 410703389 166255637 522055837 89639301 76750581 220380162 812878293 90101281 348698425 939548817 431522421 472943141 986790303 23543791 980906081 285122907 535619009 666754787 568139369 35459933 286730381 523041269 44108709 183778281 22651255 323032701 366812985 967521773 682696977 769168379 52111149 223196087 959286355 950314941 312068537 689375039 734515921 440069482 629422456 810381160 760377285 767861109 247443657 253163780 484984866 634397151 22405041 766960067 125860594 348966168 522053493 992668929 380595616 385490095 463450991 121660446 852563029 335480705 197421825 480657399 655650269 356362981 733696390 491886485 243252801 907744047 833083521 318038749 842232053 403541576 14606110 195594081 520262371 182201475 594856481 526876327 666134041 707959704 884666976 296155580 489581021 447677207 223436085 389576931 635446561 585714656 989939834 180587919 61910977 816101339 748135071 541812245 983202951 736067613 92826091 314646759 693664777 472952097 692000012 417193149 250227561 429276261 650839691 785120641 855237731 166563138 360417051 866719258 293740509 192452426 522711681 157357411 128820061 783778001 374666601 211563546 376086885 215272155 85871777 522799772 434083086 175851884 855580385 760408379 190992731 793385268 241822469 400636856 880413456 316930434 879578200 882159441 540260031 748861709 869972713 107601505 676148759 963414296 279291191 52687066 208995411 17123109 334515986 875576179 64612675 184615551 315947281 392125641 467873261 822844411 814225689 366967551 922943679 730927176 181055389 422737103 162710875 470969542 852695317 948974721 238197239 312847798 738497697 204442444 639965738 714483281 66025003 294165513 86703309 66870043 449176704 950649581 1380142 966116355 984601105 153605353 860031269 361730821 450014676 904087081 308925129 297136293 376692259 77201938 736240201 794764028 834993629 493153954 984393089 988793561 181740559 935607761 903458091 595042797 986539201 513047867 272082620 880072285 411008815 794169326 807269841 954234417 117203239 590305486 919374767 971923950 980497151 9063143 326981518 524576643 975430951 108838945 454429613 956006682 34283061 905273257 287168806 114563291 501372099 358276497 120054340 832578785 250789830 474679057 592351410 384302613 357583553 919040189 240752819 98112338 189543199 47449313 96635280 925755316 930928161 346631629 397106021 499571796 544862231 588646871 243858663 635503821 711104099 611792605 169375811 997533945 605019599 368964692 861061885 285555065 228800884 713640811 547753551 201886443 709058836 646632967 870164593 916156061 648532341 278478281 348014997 191001786 406325601 844796156 984250357 415982431 504190005 887929529 60777829 719714933 719973169 456023689 657440926 191070823 287847239 648848533 413059190 445461443 915940169 582231848 866978467 956722030 946233689 77471085 830678481 300006687 287647233 975461217 204772959 192782410 196371035 711142430 336660661 599607432 694172457 54516773 653566851 966100981 844159141 951897457 258641679 193811969 274953933 445470416 278738098 926588617 784627085 44131526 506474701 920988481 140611474 695176925 160600139 257642642 942093941 618807119 79319745 289535615 996353687 402376273 433967569 444402248 60173789 383199361 442999137 898158503 948126489 426212157 833680393 904741365 366395009 152987935 903692590 517153989 87177365 506785979 543573249 229989409 508736385 433374786 259311377 987413081 566986704 46479001 855011351 551568803 370957064 644803743 556607857 306649361 543309633 622821297 820366061 934827488 248134403 415352728 546624761 973228519 3303613 834019397 57223496 219709273 410444197 61456921 475856580 747893841 725432821 130506260 132088861 16383242 76927881 494795899 113692779 104314801 420995395 648007251 256658264 917561117 499439281 258989961 351917392 146082871 612347421 976644279 530659501 130803201 819723099 364065857 390410656 694369981 902750225 612670689 644918613 849514831 434522941 615395586 631418751 793236821 857306881 943190349 678071553 929843049 327470273 726581193 969686705 982061893 461362369 996405776 286288883 16015489 393854542 670423065 487123361 785601225 531241299 68189955 305057296 280241559 410522161 940396560 551985537 124690753 349120821 109192321 225675879 405545758 42797631 573372123 712171809 388493321 126937983 386378809 160428905 284964401 734003441 122306893 105460131 764043981 302909619 409662821 461162147 416382169 611289589 721295949 241310709 609834853 851948437 809201291 141699441 455050761 514698001 619431294 773853381 189750849 272420421 272754137 113008649 463424833 545402448 661781295 77510369 205779173 510024901 357837692 382397041 261047633 734300705 749373037 863803272 88959593 259592896 171220437 483144827 738724906 755411201 411994746 929817233 640386007 178354989 611367556 871871016 516803512 618821906 925313776 836024693 866383998 182454273 239543189 753034071 764472971 91706761 870966890 512977289 411413269 448385554 861944517 149999913 377346165 807767453 609670931 860202896 667850901 331114481 360665133 675531945 119914421 652371953 741627616 472991440 797455949 197986051 88125137 252857135 923482036 107075161 779572769 77350621 79852984 525149807 15928838 609545594 749065487 258281831 577662025 973856897 384596581 173917485 459856541 833841139 654068963 822732973 333735684 382510659 984920449 511378119 428180803 757494660 619784529 872687273 947662977 432739961 701835897 811250691 972131226 794045281 994843341 79104129 214198819 536049431 749895208 227723089 608183361 205070735 176199182 983096827 298273547 320180086 548051205 562678691 909980879 954745771 360823565 234679543 976159726 157852180 587426061 959307162 635608605 42651431 274201561 166329751 44968329 821849248 444553899 255459237 345017177 324516901 573241493 982432083 348013051 337058260 809484951 139150536 761590255 996964481 661823593 212440779 777928043 899425456 648985916 996425175 730445243 293433671 844428237 831281377 106091831 883584007 211276708 369452065 930627575 104325081 287747597 631973960 98699413 331050101 429522346 130563509 792772774 955134043 766790626 452179983 700211569 592701343 638544773 849845347 168407053 321258681 453552501 205660360 411750101 603058296 457924836 704413021 859247473 117574021 443437552 612070501 541969777 15583807 481372394 265891923 414364959 712227733 882208621 169284509 236119581 75893916 727842765 965062877 545102119 867328351 920068766 953055037 730853828 742846515 389871790 248966524 265616381 931600421 419147137 536926361 949321927 105731310 613748649 734027501 14621369 312799841 631567721 600749061 851843166 312257080 75733777 944908863 925229749 503651825 661659401 738789801 8146123 587177626 308740167 319723706 612179762 751559383 130760581 620351146 192022303 428870261 454749945 538466551 560124081 706613053 518141597 400709976 449387957 98064874 574120545 961287681 358251316 199955121 358768751 536710993 164959521 771430720 662393460 398872881 891570368 308537990 59722237 542358881 541501349 683503846 780871172 776207121 508833907 640066505 947043914 25562025 958103313 139675120 182783142 221242409 435236425 217646041 886245820 24395323 425448777 733516001 408235912 208583197 387375569 797653441 192413721 930994049 691173817 155614655 196994751 256364407 191652861 730078343 511779941 621133553 967894981 505142221 242735522 265819233 356630765 403863773 486208416 519519334 191799877 889847589 655298561 597160251 803773591 861377913 108959880 319808387 941525801 151390518 325676036 160783241 595519681 753001649 996300163 585504225 640302337 444668364 7024186 854514881 184051067 466606948 869774461 724943669 149451265 741406265 44853484 859592141 943317113 449912794 240196197 991126165 942772287 65471203 591826989 198837529 69158003 106590281 53194999 381462713 668119297 991693953 130044803 240067641 575587388 158441973 739144787 572125176 221686479 402195899 68332058 141296399 839555989 233800136 443649801 543630109 348359329 527150882 651767569 512609331 614580780 736772091 604871976 483852691 857369629 958545671 374288562 778958032 376882209 67737255 496246385 519011851 205778426 668066350 416944659 576340209 817040801 668085921 5898507 903577186 293502113 99496275 898216698 19334801 459718156 826427043 677703601 128659721 813322762 214018167 42062063 660047423 504391113 410966873 798304357 316150791 8991227 271122465 330249876 592379049 900861021 289054961 194169231 765440095 396572131 472532347 839476801 21114873 458765301 564713951 713331839 364006399 388301179 456256914 37413831 405299222 844447591 357128739 718389893 369003805 789152801 961410401 128340571 73879381 593397001 659009196 826173129 964220851 14591730 191000041 673712001 552121396 816178405 851636605 795971757 143690867 464801553 997708409 499075775 854249953 475801361 823406041 898364359 112661251 937041501 951099538 144532000 27458483 407418076 367040135 458358109 482054225 584494785 396017509 664692852 965535241 82688991 427945697 271718801 177975366 523108135 626567169 471031939 846369381 74369059 371551281 711574913 802589239 778263696 841146167 30989145 91891397 507206294 474126589 134799225 440979343 147551970 565509141 956343408 392314197 406979905 770047573 570631369 308062897 390663905 555296794 217272520 931656251 354903997 823314093 862940001 143471001 650719361 666296335 210147663 58724611 459600803 318496219 287567581 572369749 561867023 45791609 49044592 562505047 202214401 847476345 364659481 316107649 535944751 263722875 295844641 567894829 899813068 466854326 799354590 811396441 689573902 776395381 698399126 38702181 525336292 559835202 83763521 588415531 350597057 120001601 829720947 139607801 802137201 819941253 203405361 169716101 213165251 517790785 203040015 618008853 388444591 381432033 769796889 498541570 82439883 952990661 144734901 149510151 531777281 926336413 511222601 640754109 514286148 461809681 690275085 247076196 839440057 864325053 411213153 380602678 486423006 288473726 228755188 314735767 57252203 268143144 548317789 596696097 479658761 643206081 317414961 260883599 853569891 142906281 515755705 723485935 86729725 506101353 575840581 773490801 652461589 912437089 10231405 865674166 986492401 409493015 157951889 959184301 986819578 589740075 596726306 909520435 69472428 396379604 317621455 265992751 350483391 60845025 304239059 809292371 246594161 290891439 802074181 277593075 6226289 652487766 689338197 354144376 607182151 220301135 6052489 75652681 974010021 180247121 705248152 482627136 180182265 634639525 816078021 472933747 574154553 222819354 571244933 839590374 107524509 40950029 58657970 416336905 334821340 912995829 567677381 59299197 153072529 235210279 640361245 837878141 708652097 292245844 570169185 849416709 156733800 586813793 853729357 54277001 354069601 621833461 228102227 366106509 371250881 671079041 903047613 315044641 299495253 829185019 705213473 281031942 532962626 548057201 49488961 826043265 834302688 108523969 526953804 657941201 313452861 878889675 104666197 369174156 721988755 33656518 437027181 813762693 539912065 627121411 705078051 353659126 735335865 789990773 384510807 185385233 466723758 875241166 7463356 363149541 739233709 259462071 541481581 173235407 251261949 723278665 269887958 266081365 607101051 658898216 569443907 812820353 814543361 142816527 593737189 995181017 33368391 684879644 557149197 220735640 860810481 126887793 690835256 985846949 678600095 498804041 976598291 51784965 154929841 543512373 525254529 608329981 934598449 773927171 225955428 846534721 909327161 99606352 551394453 598976533 428582865 444247948 931434753 220533771 374842817 905414581 109626125 541660561 543779121 31915847 855173791 985403131 834564661 999747974 48603541 719277995 777987361 626924265 76749965 395910869 96935567 261745889 498991409 160598585 79244081 456898439 266949566 509484129 743278033 263352501 603466689 816719131 737175818 64570521 553294581 774894839 685048279 775140351 307931709 33211731 143197401 280613761 412630569 665735884 613113271 389510187 875687723 915288581 6688401 68845809 460783884 42039376 464625321 536097070 311152681 845337281 814117261 298867451 929991052 279257079 455066461 745983245 405084487 439150646 650944124 90338925 219323699 485020385 971816489 475444649 619043133 442946586 35288681 428789385 890009761 194043393 320492101 118692907 43996607 44686501 979013601 76214517 191498801 721963551 228841917 867246461 834163937 409450583 575760449 132253433 297884005 920907361 907525169 127801089 514090871 199333085 459039513 474941691 946281397 232607223 578784761 384716953 231094239 580723925 927998961 329844722 345882075 34954514 413902426 634088521 713562219 456586121 962082993 757266033 503069379 672362513 177153096 694185321 706806897 837749697 71435651 579296176 818432153 398435217 457057130 122209221 352227643 991717987 286281951 39275195 790595486 628183945 220101696 942119236 744525178 54208017 429381931 623466953 750181433 810570221 356128201 203171797 913563598 574194341 278198157 560883689 250197087 150791854 586579419 9836225 482391125 775620322 642028305 456833473 778757673 170645199 566840111 838081441 411162516 51229185 538797337 420211455 238915161 383170697 455008737 511248682 888678001 935856141 489122489 881601481 879731465 15859197 699412942 97710450 311235633 844657200 570967411 592409969 924520365 113259800 420521603 659597173 688976345 273987427 972245357 220028137 448809455 775517921 524258673 122371669 682942936 134239528 491413386 494997096 980484137 52849839 466590414 744755405 543626215 861273023 221133951 592099671 754210421 642552862 186497013 952145905 706147112 314116606 699918537 896561218 510799755 970826341 627967587 91823437 418389851 774315667 343576017 725002341 734793777 262068346 466409282 686755257 283463417 415695096 530482817 208211955 250089329 230307774 588923127 601981841 672062860 207986730 467420377 500352977 830009241 946531041 423632797 186334313 981902103 614142015 541417801 656288667 703211433 123715001 344404177 140617601 385982087 406488148 88852047 256285659 436678141 640424673 124152705 967668867 891036400 392185761 794702746 768886481 14033729 307118721 345792001 22387725 731975605 844947937 336835209 641350599 134235382 675272201 929543736 4086526 255417113 983548789 337265209 289633369 707458641 899306001 487636249 678893561 81609271 556142257 886286441 258532015 223253743 997176879 93341641 272457537 473081516 682603041 534617234 855994841 793491699 361990201 726414377 884796209 524344661 736532125 502723611 823773469 907037619 99140805 644715676 732666796 946355201 187199684 213275088 549540393 371641241 376403489 263992385 502856143 537880489 721812573 302474459 965555193 408005935 67656419 865526691 243078235 139246801 647238917 899703936 533860343 862609827 77064881 422164710 856597353 703368031 177775521 314548001 435413729 68426301 92005266 164803887 230165815 600473861 247889876 892233913 938597185 514726256 366532889 959481657 226183200 766745041 772714161 97626036 73219306 214025001 932402898 817390611 888437952 677285591 185569213 421061012 387773889 716679473 765563181 840718542 469128121 590277257 252299961 186412215 359917626 715055515 516996591 602417057 467533369 678871687 794096052 17557376 333856619 825492115 250010742 811393413 828598917 184695241 472918577 821084041 232425825 109515454 434583793 703601852 114057061 904195415 840005561 507026115 987814465 135835061 216309851 893532501 327852381 343103823 780820021 339534411 458423611 506469467 842171635 300068569 976400708 35587877 36773125 471371861 585521177 5280201 226238876 558478941 199374601 984363449 39723983 262224089 970086041 592082161 406086874 861249886 503606603 62688041 465591748 417880406 411818713 436103993 236977058 72963153 211835821 70539471 233386605 553081775 780161564 69334825 70257673 74817666 82671735 382968375 591833758 280500001 677040793 811550821 578824415 690078629 75781521 202559265 541730398 135054401 128968951 696252996 821540205 261682291 584497953 291247701 276771813 800106403 157900401 187707905 521631901 222100472 254028884 491098929 946589400 845119465 919116189 29194554 632501953 938671761 352494157 577629772 838507681 633809513 261116592 472383711 863494193 219837168 943292068 491682851 203461369 418252170 403278037 356149981 499235815 388238521 165727051 964263431 119871486 275405611 680450477 474742529 592705626 989942023 47827361 60018401 72376209 501462747 237656993 400192371 344995345 648970035 909354985 47919937 231417333 986068375 543586093 489347916 770619961 461387961 256873925 538545457 282764333 354714095 402592731 184423973 39303015 513758877 635111553 50814663 408378503 673625793 942083241 951861503 643429153 94921605 595167639 727286805 76480009 440021093 914570702 207666353 994941862 71941175 241980471 992306150 813514943 146401776 560834405 303610737 535081844 617994969 170588440 909264101 910018954 223996866 226974017 227806635 600590843 150711937 556986417 711269388 957641394 963108019 319575695 259551023 634845124 923317457 438362881 587284435 132735878 22051772 810340579 488957247 141226764 237035226 992037797 29660383 639352820 584584981 381450287 704112001 452797110 258766898 752115307 286941967 405673890 597887745 744429967 374512689 475474217 38294706 119440433 985344415 995609097 830517251 971937935 835746202 776527181 951500853 662057521 327016018 511226165 441403216 258210651 283269091 396868001 470398900 825826923 349782544 87517983 629564441 146942501 5020668 256149406 468753750 135967675 985637341 336368907 133269761 428735885 598194785 243837118 467987799 819764433 18603341 146603405 206500119 30985671 260794896 877506785 106904377 959476651 845612031 545938401 899910781 837238633 212723025 873316643 334808309 129498333 636311121 626108491 323324605 872241171 251319951 239912107 298554296 743454397 543191425 908666853 183759209 333433617 859977521 52915201 152266349 188337153 152315328 856010306 920224927 146793186 150802281 620077031 727841205 159224927 702911750 253672801 214801527 338560397 974318109 160634097 343947555 92437086 249825361 789733745 855333329 137044761 483320675 540431726 331805417 532561903 62960405 22620925 147839915 431443961 890465714 947217755 422759921 211967241 255400016 487622653 292257162 773340648 440791377 472191785 958928595 908110479 283466977 285236097 922540621 585890982 840186785 920154217 291934658 382781181 851402636 326860641 997707165 317658897 368963354 581455241 588881051 28092316 309327266 815023073 369247086 466455806 112438723 481480310 516169381 926334503 333274817 786889369 985813231 368794201 376143358 590284789 159237771 941007267 240055999 714526801 968155752 457554873 568428595 708781221 424834144 586083443 722812544 523807391 554550724 827916129 839892621 9653955 765130676 151084725 663243920 897619801 215594081 94420941 484357811 189633249 661002549 813325918 286269671 374179113 515275319 282521477 368684723 734863120 989872049 522451095 973042971 606520397 323106501 836037384 264273575 825892086 901616873 902367294 760991415 776615916 418905253 606542097 791708201 164234737 507007781 652034587 684922261 651122881 714185254 291419984 365725173 820003731 953471626 54624250 528277355 657000161 699645547 700813931 232610756 72050604 525987461 373502881 248705321 429300121 396393376 61334561 592428481 661616801 573393541 898216285 949665445 103652713 842395006 193587499 173346481 651603968 255662506 69512223 985360262 777254965 528510301 653397821 757661603 56426111 722793961 31202873 114442734 744213687 361911568 117685676 360262673 648078181 153561812 228327561 314127457 752409061 886987467 448020855 20062326 964408990 255670205 73436839 676984854 44030749 314751336 792247861 80990021 511292995 547250041 52152883 344372889 656339521 847522603 875058911 875236799 867877851 514591593 906499353 846704131 16915265 426916281 799484801 13024885 573762905 600943201 161467081 255622979 967568538 508517348 536171137 87546827 90373291 570549586 360987841 178441870 305628353 3377097 112138437 122687617 252924729 885054913 949457693 972489631 188617168 481289801 998850177 148401883 670349329 843720031 274237362 472764515 356942477 241790705 356071745 909391513 95281673 883941571 883591215 21504961 786241426 983873143 234860968 700163151 385422046 455452133 788013681 640578431 486563291 853988626 11629181 450188353 895260296 365498213 611423400 649319849 530364635 593801021 990713769 957663456 87116165 831959473 967022511 565995817 574557156 495971873 45845323 225003512 612767886 664116889 842637431 637126371 398578726 995675955 835789781 405085248 906748301 467767965 399481437 970969391 723433207 245769266 296090629 723835041 22521389 350926661 38925741 491771091 496154206 548458301 310375169 447447045 860202659 463474827 840947445 334560866 96321175 218928351 96864001 14228918 831361845 510704103 33434415 492940514 448783748 14870184 108864298 4687526 44198793 700491129 509304775 574739187 622138393 72639749 827643769 873449544 772976853 196205894 463637241 581261121 570389656 878116057 857775056 32652377 312801561 779119579 404399531 741509598 782326971 173029761 309364784 37564476 239168277 793960017 895494653 791283225 923077399 519170842 344062154 447929673 23320682 121017105 498397271 481835561 200124673 391812580 804318724 684275565 984103361 460886205 389896492 436509971 350516221 333011969 922100605 46670748 243607937 619004051 253064805 39858276 47698485 626849849 612160617 619540711 44599297 24911387 873867903 437150081 463254821 624227861 828769469 269865980 852815060 397335953 85447035 945180236 360572121 522441551 730290521 867422521 139518993 492423016 388023675 72968221 281871521 536721262 372496149 481913061 543402081 261875266 730669107 74821290 602345201 991697906 488341406 86267457 369104950 468374982 347645284 850727731 719110785 396483731 784092261 480853666 921837381 978479761 779776689 501305636 532479408 801327144 232508761 505260101 385979698 168825481 949791849 117910695 896029857 953277711 529526601 275975301 927427930 149036056 293094721 402907501 399282512 348324581 714957201 613719939 224253366 662282526 916203425 271805333 686036085 126059286 165111021 326156801 262013245 807703961 825547161 33530280 390348953 705832175 270544602 1386931 74411563 774349411 455103983 765105538 294288177 213028993 851493969 104978855 150455041 751332233 889432301 777776023 873434119 242357373 128220557 471562097 164623482 165911629 730940907 115074212 523926051 846043778 533204218 703936417 964640599 408025462 317936200 488519417 628667903 240891751 798141981 938707836 315323605 993922410 201755001 173475235 693817336 319838028 187726157 756868569 886043109 620816749 764216388 939936471 400878100 786314510 945958573 558912089 946762017 395210442 477020913 970176291 123819361 144946081 522167606 467571207 293216683 738010921 945083707 446572646 595268833 516911676 201661128 458310611 697950566 8376793 148508081 610946407 969953593 996573075 698481241 54714461 380575681 828849921 315821220 666433289 746772993 529373658 674362149 782771445 489724737 562121523 180162313 201575666 701947137 588882112 202986290 971720949 792124309 22313546 210403631 636735675 244598916 793987875 274701659 362518121 566628326 946514050 129092721 765032497 506627941 393130531 699714501 580904521 359080223 734257023 693475217 280668739 289939301 968123147 499034801 717206689 321966893 38805651 314243081 487823205 130312321 360260681 347207927 600902039 968054405 13019943 560992661 635823075 214228561 14729361 783799101 421348781 787188785 872510333 8733286 24318637 433462193 866502531 136387601 317733587 642650881 89065259 516231373 72271031 77431251 564099033 108431085 375753939 474400361 977096901 284008129 747873681 926645215 304573410 786155521 547064561 322643739 551735720 605193863 175094530 288766276 458829101 168986808 566708747 578757031 344889789 498009361 747032692 889654593 890557535 838409035 243113197 467455693 664071119 494001123 669749135 25641641 134824312 247163299 328490049 63220141 438606387 629843936 157842315 576714599 727161496 730385744 914981725 552065000 960870535 984300881 818692570 901158615 994681601 685443847 79881734 135743173 550935485 378829871 824703061 238665809 486810281 492444391 713808019 522550721 958846755 346682704 840811268 952225501 86802951 233309419 724541645 470503911 379775599 455545995 17748496 21831841 534490687 202777949 320795871 656386171 824707973 591446662 803385361 392581121 52219498 793466615 417469764 232889831 351587685 12093250 108142081 364560265 199433725 293332679 577698569 250543000 385250873 430130332 1787838 65948925 501257121 898498369 28954546 644942599 486933893 469739529 931974109 274481308 110027981 111086001 656225467 284423001 856701822 628317681 235157137 797016095 803791905 266709699 497538765 887977186 83705661 816921969 687707501 204978445 209674278 545906637 56868501 502168663 226360333 456839058 784543093 313611001 133651691 217062607 555268600 1654015 846756201 944602676 76563449 423375370 967269122 160377936 974905231 285052121 516794513 517090187 142232611 457167101 725126273 265795678 184429326 713096909 735718401 773446531 839774289 929864617 32749517 526647727 559986703 275249605 728783961 646294226 394290507 713652001 536535257 642748737 655365694 746766081 330927988 650818236 809112801 320654436 831270442 949888635 426508993 858032119 456282247 202418121 800382393 658752401 354835371 924713587 858611411 676112231 956587323 758982767 436581337 503412015 432652973 294957355 993325853 334546817 93340305 899010049 579822113 279178756 684066161 647928145 217694251 224212811 575555897 333841033 947682741 636480902 270940301 351514641 390024839 295070541 798149444 374532711 264018571 404876929 145408401 360105928 651125445 26324607 485488758 988625089 261749937 857278849 982962279 797147301 412944001 668691197 101176549 791563633 953145201 715775454 228747265 651494233 671983661 581912399 954582105 212862273 247167999 558094001 143490633 665648939 997201545 489448001 595511617 832115898 785391617 234354827 890472285 547951878 10189858 290759261 124039575 48800213 630848801 227996389 155117736 380035301 22548009 403719445 792750215 378333127 327213461 892445405 31064185 599924886 723380038 239799421 80948289 510882119 594835867 355654381 655402533 104873575 863224345 894544512 310478958 414198733 592118126 287554119 614119297 941974445 619717936 43894513 110267729 634137131 233692977 247795613 979309829 182521345 333427323 393671501 281943209 438424229 310251 341928847 984366007 733105169 45675225 218390221 680215891 689747087 874275682 942486133 101465011 355366171 229907253 234273345 817909145 33689093 358231148 905958913 346388016 654223336 702013879 104843016 674303757 941102077 334304483 403779482 459835882 333680781 75976977 801285877 309937601 676752951 841175289 24955809 327330555 461503004 619074057 62161241 694907366 563135551 46305249 460463145 665464651 234607105 254202539 978631969 89188350 558703777 257225986 438637127 540937941 49110163 462328801 535687743 19577276 226555751 763803917 753099581 183355241 575564182 103768001 566963161 952072180 256486260 668824729 775041543 827464171 413415055 665230225 16912793 239185947 497161751 790644641 381440083 804960301 245192077 750905330 996521956 872614653 39572097 755231971 653412621 1427707 374954541 466813221 669105579 797033781 837085893 349188696 925104397 802763399 689061222 726311896 818693409 795354513 962903400 537980931 512977463 652624320 612491620 63673376 256999843 328232921 169031105 290547862 643548399 98442411 844609731 329941857 247877629 445729911 430250037