4000
586188942 710272355 914335293 620042416 728614332 142776961 881892453 472739918 41122216 673879063 633669690 43402198 247592128 406169051 806678422 832100792 748814585 51204989 763770001 782908258 229071048 828735430 284107989 775070201 361271302 812538057 369086271 174742042 825255425 823498786 817189844 358470912 903317991 348585318 398226322 203193393 78308689 120814261 551364757 491133359 391201169 650200055 434019673 926273496 951358351 211566627 816293255 976031983 408541282 531465469 686778654 688977705 921110607 752570697 956905355 859437387 55287691 80783132 351180389 981826856 759271194 544576453 404410258 395173983 69827140 986057395 935858151 395954972 767358350 779754392 387288069 700810691 418664382 499986639 838048107 901905461 524051264 253954802 317837857 148404882 365637812 168865401 949217330 865596544 516852950 176258229 802812983 558021141 60051328 139617233 221850319 501056193 471596123 121887271 255105045 79987139 163874959 965359330 147783949 406487083 135234158 856363034 150688350 172486381 946614190 735634526 552790781 578597100 897788560 867429478 912131713 112612349 174165495 65846379 805490462 517036998 986465303 244765733 995703496 931730659 656615224 723903788 922918005 514321360 199708245 658134244 246544222 19748796 723784031 674156463 541391584 968834302 491100109 718339555 140715173 366557626 424573565 302664630 674843210 9872241 421018878 353729124 390186317 481508887 426365953 782496534 366018125 447992167 753887937 64501079 533447357 609640057 216101108 930559758 13998236 242615060 500373503 966346671 735020390 841194170 1519438 76463191 931904925 617426812 771226575 107484523 979675437 301660460 223337392 519947875 586971913 60293181 186483737 334939546 83395807 585120452 777382241 858284243 271746169 114973009 880884468 581316810 540411579 478105267 395928594 857803833 636558130 873970007 645719444 616245602 337849789 650161963 14166415 464631599 509860172 939442205 550244912 550675301 68306443 587097520 163370752 601539293 704397575 8072182 448492486 670559794 398450522 344936617 905048439 169449287 821904555 105841183 888366750 422253303 515470728 8855781 655906775 270113856 180399181 985181971 938637540 761926460 933286544 790558811 474818513 775705132 606875457 382767343 351111944 110034942 676192592 115437653 19366426 858524500 382351749 39814148 52694665 963136038 183726650 790036771 58703945 923098251 454676236 398358657 804676343 100200074 289350086 653511322 434092220 302237499 509052540 681278068 526016463 74787087 31198680 324353855 979953985 393806643 871361209 755298509 768847924 929448104 504835970 671856914 794149213 627752769 325162398 533851397 471266924 976276674 848352423 813785959 677339338 94001697 195313621 668501070 958021718 468689294 92392064 182437858 328670073 557927480 924199917 943019795 227012148 875921896 271926329 991357912 239866358 954530230 353002482 715934663 93296740 156620702 854954071 306390103 684432406 661307165 136057844 698662705 421383342 539371717 664643104 429042728 390001735 536445120 862596345 281741411 937656693 689327417 400258951 866535708 786804137 488113178 315562437 776292807 97241763 260034533 620391238 570437775 891311026 6187230 311585644 185483509 320767715 573014198 890211982 459160808 848174498 887052167 386792431 901828474 64049954 322264995 759176457 615482394 832123885 283254558 873913830 279634011 252136083 736482638 851025988 960583799 486978913 232324225 597533204 78599305 353908844 79015289 594723794 799383723 41309815 154846343 153463275 416705044 669469457 32055433 471822400 15154680 413751683 705375265 995699811 619624335 784349673 89485536 194578268 222881906 222566894 9153221 609825224 726437363 294312974 769880479 259899331 192742736 633771859 854419309 164413552 645883707 294413165 108329236 224096469 358170409 49702453 919947348 440950427 969540121 129034731 553352566 180822766 338887266 348820846 343361122 671026874 930790830 446059900 202823580 35310056 252879445 701719803 957182765 410987023 889451315 689098074 982092865 468637955 829546826 911064271 908866538 858807205 610743449 902600966 822497507 784925589 62530549 928661822 469602862 350230998 199737556 623954393 640629332 907917491 841558280 878185654 172869923 575679129 353295187 321414645 702597637 582966471 943950797 649077852 877742629 753789353 292132825 180142983 934555590 41607274 837482896 50888297 683752783 720200743 575401350 488325085 707291960 229075949 214983785 287154283 441685822 467375644 47565070 148336847 934791852 61786116 294684098 170787655 71389168 84746174 770449478 478922027 364860292 88051067 981461154 515292575 189455026 440779727 827532412 531187347 955810944 474338356 651267533 817477978 716664901 823989074 536795535 279580729 805559764 180776360 606479301 628855299 905870109 830802245 869018412 565015864 471648491 791052962 407752567 603106661 34557186 961786128 375761665 547315186 820309336 493463458 984595400 538754347 316767199 434124828 667428283 355384017 673385714 732291439 488052918 993306851 365490712 504802515 790368168 567065873 711762841 827157637 662732676 432931859 232563438 878758661 872782502 456754699 914004394 65124195 966156320 164813587 758569117 890486508 483126468 915092980 583516937 108525507 356434956 693756804 171648445 210216612 238190069 8541569 127773330 529025459 888722915 119708208 462436595 560148276 338572600 921340724 222970524 216657424 955280099 488554852 350199445 819936891 520510475 75933630 329181594 426193001 17695702 346080054 896400218 23010297 201044563 781655870 991200658 527213551 558960316 28923751 854493661 486207854 675190782 9399408 767123683 109312455 772464751 972275134 192361649 618312598 866203297 951060170 53289141 384793553 157189218 89319937 119994302 102643390 908194954 860499821 598383865 637431661 446537256 481270972 3367422 112855501 882444281 242376539 601181354 694640761 745811964 860396517 143718953 807350502 952221153 249677539 855070382 834700783 691395464 879246542 598859086 918679239 595778400 189598885 486235507 634196090 839899318 2917906 48419718 391508090 816107616 947690173 156063448 441907929 801772828 396890274 176821336 896356488 620781869 465527311 543577121 478681828 764877945 871044895 349866363 482285829 378742493 587196415 339983402 116009112 317906555 928450676 212056835 665964665 477424552 625811296 119143719 39128947 895852633 859433818 123151425 265880196 355972230 183670135 263868908 388092880 795322672 324137217 954899843 792123980 124350356 51785193 146043285 215902269 95917786 593632625 786604011 686340678 124750868 609813036 735850349 696042820 927698968 441653399 801774361 997692699 356246872 899394615 76043376 673729272 430941923 173864353 61843660 653010523 858510126 279355062 898799923 315328376 171037221 278298503 317144993 2227094 620723377 289333304 700356175 920761732 715038207 375648612 466788981 392194744 117172932 372904402 165295189 691583117 730468756 540500343 896033133 269905751 857141169 891546745 461436686 677461391 769972034 691216884 978795836 395745386 702769598 248903190 277123937 686326075 225997584 334905818 236866824 326573142 656139122 787250001 139359978 8908530 425636395 522820152 427519408 386873983 452454936 202594480 800703399 878148508 462721093 144907700 518401086 652989762 495371172 25785078 217706654 533155901 902268008 280919004 44048741 12273560 63684728 923236330 51862783 221924547 359641959 415020289 109229374 799149918 145467404 681304528 372129877 997284433 254227223 488878588 345355593 137324834 973884253 868303694 702319255 62904697 344243066 87905721 399038999 247376948 586809358 912137639 765131426 494054468 165822793 299517006 181381660 332850581 732516572 736439871 950457724 352700507 403680087 304969823 924039269 393279914 310113522 450893479 533525821 25966628 993933006 36362180 157830774 760300300 513820699 744797808 501114630 571628279 445328481 267531487 154548491 997152460 791040518 751914372 473480781 788890206 442076060 390936815 970300214 180251160 439182869 860798931 274827902 795650242 391128355 830187736 168128693 997310155 65848895 422967027 605774054 401293285 978762961 816302252 814368072 892548268 256551827 670794693 209894391 298845357 368655249 130205134 814238956 337827450 605173307 959671607 463728522 229851413 889022800 523698066 892600752 330215839 333295515 248918064 40489875 841947703 216758777 768599710 615497691 709041887 28671387 348020151 692678913 867472952 619942445 34728671 436379110 243330996 505862515 913654208 216934673 993712284 409722947 972524781 163573645 700631722 305143153 981819721 222171204 658168352 650372996 476571306 723658051 447464668 263354657 77096730 492082741 274079332 816627973 479862257 603360568 178213277 374932616 769072774 660152374 525081176 944128660 92557813 943258954 617280905 163311390 152456301 89736209 720370146 603362148 332923548 151992945 411053394 878403855 350786773 336045242 987681554 270195343 514423766 361479102 607773759 120965265 149907948 19000994 747648018 870902788 799292678 339319817 586733822 620635476 80578620 485202717 88091272 214363760 108455278 316706956 948619010 464016910 410713726 687372262 747210163 584179296 888135590 591662719 352705462 331023997 38946551 561288192 497688035 623298232 978194508 955824630 985986922 731062882 228360926 710601179 165855127 124660697 350425836 11978751 813711603 109687289 777013758 256768211 422645554 72705468 525017070 116752240 263602908 987068680 727704462 711725895 253798782 664005826 77628389 820156548 98741265 663300897 863161668 899962895 966812806 180739202 808192624 108803555 497517966 635190362 307672189 423535804 4959398 513276362 740389442 842024157 236422274 202176614 917704786 125325783 610657036 904545638 508469566 858145184 199684134 90776595 981085988 834857395 6747222 982761222 656779703 581587611 441517404 359057788 417944214 542354401 55363699 779460957 877826187 632901330 575426921 945852460 602073726 157974346 895249717 608103123 560599490 680213699 691309240 900082064 910143428 623595545 785134864 533515306 764066860 194066987 625086055 387762812 794293650 880887009 643143841 5427177 636338699 671727908 511721382 196076050 795906518 285996969 175965047 701249216 259951224 829502889 609096975 265625744 548854261 235982599 639047294 645401638 878832184 207283106 220299503 471858516 525402354 187680500 356410575 972804663 27467810 220671490 834400654 377453722 818172382 18414534 873111420 38170039 311741053 353216454 556061172 608528734 371411622 316260401 422258947 333025046 267932900 766627079 988957148 64707892 392252380 604643692 957319863 797875583 701182920 31065462 644935350 656650238 596239553 939268077 840802151 675407063 149098606 217539479 882372793 810445570 477075645 955370703 141723418 924036891 362520908 28034617 805570107 826904246 944202979 89087117 633552305 243578663 963788756 98927766 523057876 739133329 925248522 407747945 3122050 804352433 696931256 343374183 901042679 834342281 745367972 565509826 844216871 15136889 376420306 679403551 14852626 583778066 60811505 559785493 23874068 477930373 932901388 847179246 898265066 602437193 790050777 700885855 743311789 644390247 460162501 202548745 133344297 400289213 292503845 843104156 483643229 155066605 833990694 516902658 155967266 585596158 127791761 637191668 743890617 76966769 218756636 531914257 16229352 455547974 60345063 336327920 650436942 620268584 515620083 956723935 262835052 922941198 93469515 710381993 3462346 833064145 140477863 337773604 241678230 146299697 980060127 463246443 148547576 627654803 767711890 368918692 4194598 23274924 994764541 511136682 953737947 849548436 551920329 997891981 660466062 14945440 139576639 783975702 131346225 748687456 320904601 63270292 352794314 50781813 9289522 515878768 686151082 222488885 407051302 277640261 375689882 513751856 284175285 820536644 822965556 682550836 774993679 147807204 855287180 719287459 258671641 972803267 534101393 194905750 992410868 996449395 997383478 305732787 467096403 809919218 823627897 199735154 221416544 216769743 867850041 591497916 44756739 663322569 885031964 956323832 66984799 97734758 521799168 446325072 891450699 296821981 624625165 108882741 480321596 962249922 882083460 491646900 845841803 367791440 846838793 161842064 43412565 90610023 292442199 662792840 652621170 474700109 784117938 420209580 770678611 252767999 717058958 945081416 567654978 40275151 319358029 228677138 544341788 813911172 925638370 687462433 82908157 306982499 552598781 804273726 457141266 983383485 42967063 87965810 632035838 674617372 310051123 354492776 905796781 128832985 576755927 712614612 370610540 329861664 585589453 839156701 264580133 621166368 100492052 198932941 251239926 765953928 219984134 23763673 664574415 811059316 990388461 720439694 436019390 986379096 721736165 482614821 271618386 208578599 531282215 389944684 688371900 126360932 234440876 413755323 792152202 852452309 559257235 501191779 440685177 140246848 735066312 702799366 132382769 461211138 560146930 821360903 819948327 694939960 615867053 839757406 386696693 386821478 776710148 418363321 471076773 409429208 926413193 82137630 365169216 660100418 536506198 719578225 847665699 303199030 138926273 602870584 993758493 662329000 959497330 838669448 731277629 747456707 274133587 647276965 245986704 121717978 350556942 220980801 40587910 121737270 430498018 771421147 468288679 168075767 662843582 844402 345017672 408409891 966807588 979216613 155513995 317900923 170057881 762434515 357300112 699197667 346416402 204931512 36254127 570208244 776976866 296486603 793902595 866467947 947702306 992979483 1102708 688476896 107585964 866889180 321523244 679579076 472778643 56133680 483632191 415433352 477571739 17662315 925721977 174102820 388067183 339493510 29675514 772263823 865189489 897300964 531793563 706696547 768846697 149489062 740505594 913098411 503195394 636104030 720775457 152763310 365412477 990258644 341688908 403526581 309800045 247116959 180453951 101787804 15944421 376336418 216116921 13041871 564755649 325430988 853948520 5976641 148314117 828122613 453108941 808545790 51920682 366815530 656432511 587964161 465841016 743273241 870077476 647991453 405147479 684290132 573600232 248569777 99007179 207954819 381575337 691613563 934578593 861046686 987582918 298686525 786271476 57299909 725524909 256445840 629231054 582993086 615764935 947687317 747232983 899176180 553723943 275281659 230886327 752079072 299236895 375799455 371559207 142306216 938883381 537180213 882569258 736204458 51840724 331829780 582941163 213584696 159873524 323038619 895119564 850277940 766012918 862462391 914512864 904161449 116555665 153918456 48628431 809810166 914751447 24899096 764457460 739765126 730475790 983004980 660150251 213177363 124465265 417216630 998242894 642748022 39915014 151572408 590157847 240916736 935910598 388724109 125899282 142715759 858382808 997393313 500925536 381808276 423900483 415919980 754379505 273178306 720045620 740395699 98230838 10487333 102455182 921723173 85862747 181097069 219121856 478992213 172411076 523911230 958356708 49675266 829642432 750537491 616190124 775428893 160551176 434203925 505093342 177086509 250565837 510025043 544216549 859698568 87714250 423122676 380582075 480824283 586535335 577160349 915799332 131333198 755282622 294246045 259449750 825190056 184858985 269662817 18861988 911925296 159072477 824514004 717988198 134007975 723836211 785086650 77627606 578730878 127726248 32957968 889140175 797178935 888578648 155802828 279883967 588498580 834557712 912300791 23752667 804683390 350350085 713411808 234557870 702406492 280207942 898519457 548953925 474231487 62009779 281361636 587611225 701388401 912355530 906782966 910359322 288198583 66838380 894058503 681998762 537559046 552631443 41912478 616583233 368999551 464994011 812009396 468462366 405931292 9272514 39212123 986960005 257030856 684851121 111669480 72119825 324597106 437140949 144457676 185584395 761802672 94121331 911495346 386287984 623902908 217149580 11917092 333562002 486343814 912104531 92545819 89038099 960271054 383047842 918195195 393305706 552695813 234560221 608561875 582082718 376414740 342939472 19791262 196565735 572931344 746161188 845643359 547714684 406942026 324656988 888564646 305371087 33404089 357545030 424973904 671776249 327154166 145431163 806081824 701707666 976754497 565307676 277246105 209434967 426798726 675793094 236063062 293746038 268967701 494784275 745971799 330152012 677198526 182663311 47238678 101763566 181876435 268942126 271265043 848536235 387135919 177245368 671608518 70574261 427470346 789506779 915482763 798082505 663355236 146977454 761161604 881652948 550821865 303023620 136174620 342171898 42647256 516434916 952999976 543852336 668561018 556463430 607173581 405738615 975103969 421106315 67352618 886696068 769000695 304834708 405875056 966138977 991224361 910019717 325508752 478360284 627419108 293954446 826684683 536940555 593017581 813005317 922706360 979730754 534836682 417638152 833860848 635508121 570955418 467500582 215640936 43689607 496070306 481450333 987126245 617473310 370887536 238816976 558706205 978031390 360532096 28323405 69062228 433203391 947705908 315014336 614758575 275229059 164903293 597440961 139638567 92297100 888283878 519558982 596683131 756119627 260081940 91166751 711448136 131044399 69219995 21475353 646819068 123098874 548590378 970440728 942995193 983799028 205867233 242053282 713036987 344704653 298784603 138730751 961115795 987610198 517619727 505958635 599108569 947728898 797042160 481319132 467283340 251008897 940312696 797326851 394627507 535467233 381941474 159878625 345430325 543328560 411892306 846129697 426421500 229312290 759078220 402212547 980415276 235469232 883919791 343570265 31549556 808666539 767204523 102237799 911533145 270290554 246954077 673610111 623152260 188808600 845746522 370045624 175615261 377127253 253564698 896784736 895808711 78329719 951491945 333877017 668060990 247106821 188865414 964719473 512886198 520333343 370578896 851983842 871654255 440539865 421366708 561233600 529498090 905193018 997698545 942742952 865109480 1631210 64409100 892657867 756160204 657254301 577102824 957349829 597501187 451898773 625208273 701369954 331425859 303009562 352915994 566402063 652613053 659544585 231943193 500858468 400245115 72442025 500070193 945381804 815253523 451080276 506950472 65622435 899689886 822029161 302605701 794425400 59377152 898573910 679346520 375114514 341976451 108668454 671067359 283697173 363324598 470247928 138386717 530768056 112148374 844000522 534861348 884910933 403525881 592357775 962181110 391426653 318511282 198923140 620178134 980193687 122296753 742785525 408819221 603366448 64837858 744362376 670492404 392641468 599376303 640617486 811399978 934266544 217161180 981019698 99677045 738334980 232544584 160522215 280911496 666414894 486274560 406990335 850507188 763900404 26639336 710767406 183829418 960250363 250294925 817710287 630462027 178839544 652435269 509242296 424063769 182956973 61190022 398009165 629274080 254195488 213416847 520087684 178023329 852727136 797077652 275571029 731825698 358327760 227285920 921989502 977556656 828834340 439030715 582498223 576175471 557992489 490036321 161946109 738978091 770254721 603917710 495303731 230726854 232643647 636916588 403984588 703904285 941031994 238200524 378632008 783911729 263434377 577843692 805173433 661609452 724000148 179487278 782683678 494351023 366310868 429123368 300631955 840044386 466805765 269865150 509465057 147025145 512375941 306544598 32966345 621391148 545657075 922615725 656195472 982553565 605356347 189324925 256939625 228065716 959915870 939033821 666085968 38467537 763359250 905096373 34447533 118026879 461770539 753238694 189339812 823473300 777155544 422509890 208448955 882146234 536799664 12488652 593952088 10996894 923466743 752374924 7050998 967508373 889445412 286469722 509849380 450885755 65600761 821497003 293635312 158422379 407956227 541696350 393378947 427235844 546022234 649434094 495841942 789446327 548576412 724254899 704793410 3701849 386791489 515193029 174176832 818167230 848869865 94704948 331202378 314246681 54495677 60526773 404518139 479314166 526426857 552590912 787803522 200908029 153488871 48745977 347390908 110073495 387204798 383858244 398920266 555192552 431024391 37518221 892911285 554553220 148085890 243173209 5399637 968932674 208101694 872502581 296499471 399535138 723458149 527108033 869218940 840551656 158120000 272624442 687707914 605738342 725496038 97229837 514511315 349867184 411873902 745844992 981042703 838253783 868810588 872656174 61924706 125053474 580453434 946065963 146232033 336940785 118404010 444616448 169924450 218862895 998198601 21170237 879985529 488581511 160210847 677919545 146274167 531311072 616497771 218028557 426592854 371310323 885327607 412390295 217219091 651637146 515142504 383809988 25045258 923839327 992413811 771663079 36503427 177805835 621118266 67338835 671271948 982564521 264038793 679989264 830477012 979674013 11224585 19403900 402270775 205310288 464043975 776423930 677659141 457422148 900910782 927158468 67987583 356820199 582942363 793611837 793573377 128567686 206670516 196914324 685309178 919824492 28460587 944300913 369272548 59111359 310957931 603485272 408041129 508009489 304464139 353779032 74683226 954421210 428289155 93544962 576311660 106947917 145253592 546660369 413327740 571468091 322315875 83059407 581676871 354083813 805757326 471235788 694461249 75624131 495939134 310938794 839291768 392779941 764512060 171252127 594387329 193199071 987116294 121322475 872147284 678454455 45459849 46008854 8113519 806939516 373235360 412203763 804640595 444344108 319065050 831985128 470927015 103313357 88242018 98170360 830357605 302460005 43284058 482944211 963027386 437929800 297570391 590457727 134284902 474925860 992542830 951492535 240910837 21451670 166561671 6282229 915566369 23781393 69745430 73584723 368009057 353139141 966984466 550450543 41131281 637316442 604445601 215538682 240280801 454143616 581752353 483425295 926065722 698796062 914572360 174868018 315202646 597315611 765984641 964951413 953797185 304572975 641650312 712801216 585532492 448189931 339400465 45972351 112129758 577519252 813555683 397434747 636359968 579839969 378358219 568506139 130363213 175083429 513315769 616951106 268500987 424629961 862846606 784545544 255657287 682408961 211568788 60854993 692643830 895988511 605329684 172528717 191510089 298794169 369742220 314868966 973886550 132019958 935853849 970360012 356098457 864263525 570690427 395321315 427663304 435007292 632604824 864282665 474976106 158558899 908791433 209225493 770733114 386889383 344945486 336217330 465433203 383592277 155139834 676129482 520252688 1485864 277879347 342254041 825210460 841496344 908144121 121557435 422021265 795807936 460610127 706615151 820405964 223865886 333927281 356148640 673805269 534305093 861847199 758880787 813065326 832501894 279339391 886591779 27243614 555517800 375605053 822854415 251734327 261272528 842586383 550925095 168026070 291986292 316541973 106829107 498592929 37172465 936657476 576344510 994978878 592714934 589159014 31691821 192341842 415389428 119211666 434992362 639973308 806562946 378380639 820970668 592225535 220489252 135359637 209430499 649853844 556580438 917039002 216063797 676916334 140787843 792493889 971560761 340683395 631824179 995441547 657731973 169542955 829191133 721375960 1395805 71792192 97176074 915820892 682772119 305156112 257977780 205539140 904980170 673462872 32368993 512801237 604939283 752340322 964848971 386176685 780424899 210632031 139105168 227636412 246724150 592175902 505817815 634059406 551173651 456336382 519703457 758556882 282783446 985394546 720044540 854572925 946353792 127506888 223392834 965962006 953320125 596775301 24387081 400198768 675256491 225961610 234410437 944412792 626614550 793067319 893104941 739917657 878133566 596029346 585926158 337298241 749517519 468296197 649347109 472311059 36029947 443342070 723401354 983637040 391356308 123013772 148595045 576788429 918669740 851379699 300117922 33006144 714715406 755978589 437564796 702531037 108619096 243216330 590994823 220909014 676130385 704602666 65699737 896955338 986399991 646322793 801165187 743197075 290393250 16847484 846065776 929759976 899426494 921611670 391780405 471957448 796069188 851792617 16747283 826700443 533490599 863546094 750205785 782563473 60356046 738478987 949195324 422854883 494922886 98812376 447770930 773735688 720134748 900284759 32794564 35047146 317822543 142716842 769644065 169745605 772080292 87340021 832465661 95127649 693981804 641689753 53885728 474604427 648026260 380163805 810188210 679591326 649830079 815546852 322583560 346222093 652047240 519098735 860477363 390180750 36937887 927683685 23087962 245232243 806944723 675145772 835649993 928169725 216907195 443179745 573108095 922227180 229029206 56267137 55299335 285518439 122261011 179441971 582743947 326215130 912765665 615340242 475665768 133538906 917330234 619948097 485572418 225245550 328246715 869477740 609174768 767061801 793398060 278218578 415352130 308336348 70145419 484609515 354441701 487777638 566028222 405049788 562828999 996040125 901313102 499618067 594898329 460272658 90393386 703534781 189083755 596919376 927205447 960170223 334859984 680997253 383164180 797396231 857012092 501614600 142034426 716806405 950840889 642410309 830787069 591973317 752206525 989362637 459494794 679550806 455384753 27638184 94862091 797584903 711038011 856647427 755657260 764459362 988962383 764001198 766790690 318812935 150919299 730398633 311211011 35714648 597530081 941065687 825163983 816545387 354531157 632444385 992455081 507858345 753151476 559469686 911352550 874366331 302730875 577678380 644372138 844675088 493216593 131202755 771146986 74834163 295514263 850511911 909413147 877621082 850048263 924879271 471164480 852714592 825568476 693844861 768204576 574080255 819943941 851082565 967371454 261687443 185716562 646779174 871741683 261317197 372660316 905666141 228342024 389371009 226912400 237009107 170343868 618066349 218501536 939018133 154435486 737850809 77735237 34694104 841105811 203023859 462332648 580042660 926384185 580083059 928097120 425171946 165792459 962741414 597283539 808661329 276943626 66297416 252186071 712032199 866631702 768966392 649791920 534549330 282469664 110136263 549435473 583593156 568564439 774782729 262659254 988881194 867057549 920962460 239880985 875544705 706128561 858513894 637517520 946041123 56652138 735657850 452261887 513407134 900264610 875611622 671288495 538736144 586077129 978659462 661513054 688386619 783831366 985550544 833146052 333757397 60811961 521585966 24404844 121136915 280871393 793707672 167985304 344525228 912027652 281915532 523700347 123156725 476093335 641734188 565887722 86753326 632238872 741464920 346565899 669915972 594261424 495288721 440477721 102000350 295266817 101769281 824681737 244167440 558684699 526664306 543910649 325564866 943287809 872591269 785133223 410032274 678988569 925150812 69748119 583104044 99545466 275738746 201458431 936162896 752631922 147875407 599831714 209417499 737638224 42143580 225628287 530935852 694678350 733248539 35963354 944265304 780462378 797205707 313405381 257209042 756243550 937335862 50115667 697464861 547051106 253127383 104693380 868090393 131842720 290964621 102127482 355192339 962731635 280370447 637770521 938383624 589793953 412657780 968683295 300002813 572085716 774218311 959545371 376228820 423583691 939194694 416223404 56316146 710351670 51399591 964397850 577829283 56343171 494748861 260191774 599877062 489081939 604090834 150269354 826640900 896042478 144185329 131632564 500285927 683762853 204452602 335299700 677675824 280531133 539597406 863355135 211420178 243334401 747809992 160230963 800614993 828454277 712573047 942906561 298306623 322385959 339877614 220530577 643457944 863145793 621566134 861124097 394165710 758454654 955962357 992730800 4041672 677072185 617153540 870169676 122664490 241927872 645877827 263311892 620513308 625134308 922258791 662891466 51406521 271888898 737395600 955716833 712508487 826200506 622737237 432032104 423157637 253013346 438581239 764928854 584494957 129739470 837635614 894695826 279097380 753653110 587078157 306059199 448844216 642472530 55249496 565696932 862946171 473166323 592254028 392024058 95464419 435395207 759825463 463031179 32274924 444787045 454866430 688530509 105483396 393407892 392094272 516731320 442007502 20488937 679528516 500628635 792791015 123423163 902720747 212497471 266645573 509418286 651161741 538915 291297882 887382839 282336439 19914851 726204861 417520244 949662672 643173578 613773057 120210574 577313575 717617692 665063462 146780824 747489961 73922278 711291550 663365417 638281872 921864191 574068170 238222794 828581490 859455767 501710672 714562487 495496179 96917667 38303083 93933646 360898167 464388414 891930871 984918901 228447299 845950657 929331596 579917513 500573289 667116555 157769018 549336707 697298025 710245764 15825933 322112839 425972507 249897522 968105147 36682297 316316107 327672965 605643648 195354595 907277961 206915653 139200386 875742176 15899100 273055416 24410450 624781014 981219014 66056945 963239066 305891399 151112496 395665111 766809576 370803045 631374558 875734726 381516296 697244367 335293373 302282805 311713217 94986305 217453312 162670405 604049121 40830574 920249712 311514119 412053673 802543814 484431327 262955205 992835635 703874681 680842081 254326567 711782629 125607451 157017850 668651601 743199273 446803931 859242825 388172051 670459806 777516744 732704860 564464451 571728663 946031690 172719632 475993818 228050704 666496901 654898405 673749296 350954843 642900399 863434641 602636004 356586437 5224985 736733460 862351420 108361142 622024875 479240607 949877287 890857579 506790375 934055139 244395712 315946947 80881028 263304671 865511668 288704523 753603357 337467960 783842499 994969682 825821969 312142308 623859704 889350767 33308205 256115087 972582288 693550964 349925964 485940408 321371898 834423757 295922796 974319134 41957423 796818035 19070745 292973223 212623354 778903904 147725764 87625383 257048880 458487630 228917538 307546535 938248740 641251177 786967425 3102270 396302616 330137872 604242455 102150353 895823101 569863131 606539255 826962330 698009869 324807984 926731824 262413704 534098461 120585923 107918335 465497004 986433243 130235745 628470049 549799590 140993309 534037016 573658738 282452191 961801223 25641316 606852339 431560179 159567856 676764704 5140571 779886957 468264736 831333854 721554965 193303206 872651577 274934088 962061783 835269751 182338572 354303773 395576523 568198159 139723532 728861479 209848887 393087262 241482329 523415779 961713325 735196119 666755580 959148047 506751099 301756476 454139343 416665434 252515168 899660825 441521189 536763023 884990743 956796949 643545729 326788146 306858437 216361362 596949894 646044648 211072628 428221676 445660447 597433936 525884605 308847277 152189276 607818989 295501787 965725568 655309828 24922940 101647079 399808972 164151521 701300596 450636157 250685177 884167597 736827200 833233439 83244991 116564004 996663542 453625799 445417579 829523914 106536303 783296153 561178683 7375763 85662275 526906166 668091095 820919505 980261048 34989873 750144380 299696321 362109506 402478805 177891353 120578283 133120519 682325281 875912057 207131320 211126279 661701816 562055561 239511021 735062872 409728781 160014699 39496837 815059692 48431554 436554385 785066613 942355933 646397920 751282367 845735600 366308466 852907980 762358596 244783728 345444759 572113794 252830612 406543333 236246000 46495778 839667887 163986472 405031718 735198373 736867796 21279731 755104095 441906842 474125358 780382737 384421051 817051242 870449532 195963424 149057634 946267287 660663427 221184910 73326284 491958159 4244065 83838188 272980029 618772276 577983789 364184992 917659806 217758961 835090381 668243275 148846658 202346530 558649436 670534774 871202425 450268214 954187464 204161771 639597555 121379232 709602433 983882760 476319397 420772946 324222384 168697092 624229245 392157022 925488764 646461397 926025527 742733902 641526536 316381518 953942327 761739590 443225157 981400289 909266584 75794981 365820730 102791399 162368699 597564067 418709427 919443654 271871162 809040780 569776481 90068066 973738594 30273615 884360289 436355333 561045930 752780462 42402440 661588550 944597569 129028063 949946489 224757566 507704515 811249981 813629947 465290495 360678258 511109243 284921150 338549238 834236719 476677295 735379830 632891022 631175977 911264036 903257506 721388269 332674770 343366562 310537841 781326687 248443993 242394883 260383618 21960299 512615307 393313220 587193616 280693136 358923310 427674378 884575604 639616971 532166777 536662428 686380988 566856420 282199237 827307993 509088300 457703050 782630712 406800621 224448949 578511156 792601368 906177008 255755822 427478736 721560095 373330048 390362158 107128898 957584214 228791667 39575901 372401559 950048804 399472689 187227103 864525314 600270528 114192156 628214234 727156400 950813653 21093408 951148835 857557727 186266556 982088499 17600536 650566217 578569485 756681384 864930854 276142356 75081375 483141727 400833808 148836986 463998324 634940154 26076969 628467117 677517615 871783046 303037552 187728873 512038287 222211636 306863701 513414783 17128738 258402055 459038284 439380518 81610390 18010998 924447478 819728357 932040367 800128696 230392091 164272495 381804724 976160367 868500785 613648392 190587008 542325126 59425861 995705934 864309276 723598050 58447624 211702832 139150199 654092728 105395945 847619526 694410115 654479418 530642482 205705066 857053249 291353153 676141030 517144045 69045703 465054781 277962214 760358303 714243486 230424000 250778755 829835217 249328033 993136853 915897598 121761874 247651273 644416733 950284020 961881718 225115759 85054138 681041758 280888552 674135512 354713223 264307569 126957129 538004958 667939023 685392924 884296682 891927398 796215843 514089064 531476233 9702332 953636310 43226568 349434680 445673399 576940810 321083277 569515736 783898597 108296238 657596154 416441209 114478644 70174590 391878928 759572886 321274147 124104569 281212015 645940781 218966878 536106157 326204241 536804194 46551604 525878343 678446573 509332638 945288332 241432637 401146149 400016116 115791249 436019725 388249307 178874158 456987819 827615480 586942255 889322062 662746825 113325920 835924351 595680491 680217112 468093048 126036180 703365610 955289898 10602174 815964871 403998387 193605705 19966198 546003488 147802127 313002427 680731623 895161678 438005 710232165 964238371 133995000 106545876 453048890 813409629 505034030 17232614 104193864 102279875 159877759 842279522 675935310 224783457 120034838 598554754 280807413 384811417 570526664 708230431 732978289 433319269 961608423 282219263 154068155 644371160 980247970 725886629 495824714 787018737 113256084 257417016 528661222 755929069 495426663 578264633 918964691 598752240 941853479 890440985 341101378 288234649 790672135 159488652 518204611 841574810 949907275 919844770 133608055 437415341 420400158 72839576 946106070 119892980 585775845 237775188 802129105 282792782 509334047 138923377 469381721 749108044 199919704 517340003 71417911 546940790 538653920 100490140 641135038 301228694 478453362 544440912 321959215 164109254 355388981 755415315 94745684 691187268 55885642 339452581 417236501 21285323 764034220 24822635 976194071 210533531 21696262 596319197 294225607 431866744 281773669 43396975 818811319 855272992 509430431 148630835 52896350 56754551 331213436 878858308 2127886 290557436 617640799 565401522 56986712 127840030 67544013 674475075 264716278 211498859 392053145 800033294 749591055 656598947 516002823 900612002 345456456 908869745 151016835 343810254 968960638 468606984 77298647 530650151 375450816 23247587 212301660 271013325 638341307 396800993 640975933 391055848 633537120 312873626 910577784 465137146 292677455 87991574 213610887 521322437 707182857 343994077 377884624 802062488 640621873 467810605 969853149 778380325 183728037 316911061 836632963 971060379 971452526 870074230 552187444 489017659 470332491 704883362 571113395 314063798 535424521 466539969 16632200 144738501 181657063 580459454 362154469 380134377 708351099 168935572 874016859 265713265 993125503 488229502 423773178 351213865 575614163 547374612 594241018 218829932 153627458 288396796 736854741 498750525 917181317 70866665 686658799 481510688 724630178 597677695 712982724 5436520 723707723 152673898 81351037 881910191 333493386 836583961 260616423 614270324 112434941 285636690 835659404 308902302 180892601 796166487 318183008 635906933 306794160 941301058 899828290 63931575 110499155 685442363 536473531 455105741 309654841 381964572 409150368 603542863 246421416 227293328 370231073 706122332 827778617 271610795 801640982 66665502 505530352 935395231 62557215 775741322 800513404 558702194 723618176 993112832 73151389 724824463 302972516 170136069 541420248 283954999 574014853 549461111 332790474 995800318 691753524 151689040 852583211 632904044 124733082 61153100 582810752 989005408 739415370 58486454 556335870 402385850 749253036 545537514 784108970 699760730 431488260 113399719 518932559 418781247 733158405 467031223 833317328 349512263 609087758 415449852 811317403 9129341 565548458 776734128 441393781 506507337 669444669 10487137 239927503 258498233 762459511 891845831 880349816 463262805 585432268 875652542 801183705 334021978 736967548 632238607 938867090 62375604 439748299 775722803 163181611 760855912 986395386 878400219 118494421 28196369 397876716 386218420 970803017 826551094 542676167 806927647 931005526 50189822 620802969 87005081 732574976 546483046 448006758 837381957 561982235 961835404 572279118 411648214 364520688 434481524 264387127 856019902 254291404 232641075 540760229 337412937 817800870 222393485 847922095 383550867 832003932 506168174 780373726 205210327 848591310 957391945 96604065 276612328 493736445 711716266 661396669 311142277 39763330 357773685 240020304 3749499 422136655 558587081 511225888 931890482 775886201 271261418 377860109 538635352 46915947 41225217 487377803 835491348 947376083 313762657 748276765 884178191 453960531 760537401 214132236 613903209 597671767 329272406 489671584 404072913 485365485 575550988 484958504 61576254 539254613 12926511 908827231 133929764 871485474 98029718 980908787 962243513 511192921 562942381 874384510 979435795 346904760 618216152 362805559 961644005 506761438 956035199 647343397 168092567 750017947 631524932 530599349 824571457 513846091 290797172 978101083 312978626 124172856 71168863 37485773 619846249 232502986 674406292 383364725 984167816 41523 429642531 76614148 445130732 692641117 172980038 936017593 620756253 15851342 742027666 485581332 908506173 299725533 804157465 78703636 532310530 287637162 414921758 636968454 57579954 359023234 450753648 583705264 528702107 514276281 887569546 849195732 597414458 623713357 534720525 243602789 269133180 574790849 456333122 371702367 845224483 402079577 744572538 881338569 12104112 657078615 610533250 285152105 588329093 855057713 206413874 457700150 645159659 756169011 451716118 943831654 938018900 954226454 218812235 890473401 886465569 996633180 11699143 706071671 405476654 553161911 959993703 510983112 336476321 633799149 292201765 736643685 8779730 951123453 489515502 98652796 712454882 837218762 385199466 479230829 804705349 198388527 44102255 90791691 664001960 709597137 28843658 984306205 285810971 960587071 420374304 648611935 913707131 862685387 748340058 145685309