5005 5000
525818001 960876299 440781143 714148333 335584670 926721811 396656304 549095111 807528349 325659424 426275822 226499181 53060925 690062237 961309293 332414230 192243303 152870449 665719512 799251278 954508850 258225991 687503622 427138903 715273339 76067112 145057599 583734659 133012112 917397680 202607815 778173277 289590848 826112883 34337425 231808486 816484222 357798265 317201725 875616979 964491923 359319793 750047512 148664405 110915618 738948876 445468769 157095065 613340481 485855442 104537939 44764911 13119780 998900334 431721324 401391680 780693280 305957345 382188982 110501789 797416331 786467964 45021736 499240361 333323506 809935247 371279904 656516905 54149892 985306432 811386567 574481542 16363775 857925474 55480142 972601502 948872243 27112868 86481495 339712075 516443001 254014116 497228015 598699013 975433978 277288455 140030443 701914480 484732056 779026072 991899818 157787936 918290601 437989359 48132557 179739607 29736707 890840745 453407177 561549831 16488830 819467405 439819903 378594498 51447501 276572563 250732693 77897410 725581102 497932551 554577885 937619681 103969029 169724017 617789807 536269272 291938391 87169649 369462566 697814192 322154147 996358524 938328236 385978824 895786998 232382366 263726540 370651776 239069667 473741315 123865447 747737210 832165169 680282367 906790288 159617528 200220033 110234537 285811626 191827047 239529280 353996737 67033667 746749164 882500150 311681639 118083180 22612448 378021501 759658802 437951082 952001483 345013110 736548061 352936804 74795813 172908346 480178470 31316784 714996934 126069524 953480749 46425406 169089111 340318173 300448948 1000000000 170279021 466484412 787367055 855694609 377633804 906886046 169395018 654553225 162107983 816963006 273266700 56731245 203142217 84950684 793680752 552918269 355433825 99450643 957436755 642165770 27966758 102241026 925407085 76466906 357032639 693496677 162275687 779798426 434336912 283892798 133402264 57274864 70464676 923377671 404026974 674130375 763511937 864139787 297228006 411869317 643784869 169892550 534179753 424339437 844767237 450779925 187837524 580371500 677790178 99168019 566984830 206830015 66321158 715537588 845873433 159549529 197408760 838488439 800242820 319026779 104379882 937187979 51574893 594104546 791272600 288828459 560584343 173746708 444126084 184033720 346109106 591918795 59829742 406018074 138408619 577189539 310659896 321756566 571658906 727255297 275003940 925459367 368868819 982587582 634648322 566352204 188906485 6431608 640773080 961346927 377548331 271997886 556379218 530316642 807972785 688700497 781779193 486321642 384406819 873122087 281413746 327423182 15087879 914118337 810308842 607274030 527523886 542676148 638416601 543801047 869515937 380948115 389633847 960191247 543283657 87382773 496089360 420511933 774141448 213140192 585316639 253015729 299903136 725858597 593096791 555452018 464244755 6623070 299903210 250318606 605878435 98440964 857572121 891709711 584490774 147304971 990547121 367917287 120791033 640981578 751762114 863247660 133998221 733118229 712471492 133754835 23041096 853469959 552486472 31520612 380382372 931755872 343678208 235034190 420274602 237729838 281613834 79130687 907534209 73091087 118329700 203358512 636184268 291252712 966319634 427071054 757276923 847369531 603831437 203482469 557846339 100765953 152886594 617261975 445866753 703958861 201646350 319922186 112419257 12872105 214501941 710596831 285132228 58811507 334614339 710498724 264244459 999913947 748836412 219232104 930005726 251962058 337199819 96827165 590133329 304187732 292990292 668709085 918248132 327364383 545009231 162992481 447344442 102986959 566616589 465223930 217535855 463013663 990237862 971879975 74907569 841314305 117412845 699367119 232549546 894464105 87287043 833537509 110358011 35412519 435907900 54893243 980205815 181731646 156592268 866773465 163608110 638892903 135770378 566843340 772823149 103482795 36951672 164150397 860094872 123628816 744534114 332310083 823834473 478750104 204703702 748377779 703156068 103788484 509725150 277124602 623514763 951450909 795220296 48662503 921302464 168703659 595889477 278069681 91278645 116023945 779696028 89715947 349316910 107636064 295374497 32173048 742751967 906919038 45419573 51518880 602685778 493098933 422033309 356313666 717210791 435343120 697162460 233994334 364349761 657804175 990820338 325197177 952707112 611788865 750041441 907712349 310050986 715448543 403876441 17681496 529113995 302034286 588512630 321164786 874834346 324984863 990456056 858069843 468011121 743728050 815410120 277866415 499643498 984181598 147977380 643221995 96661363 574993537 767623566 797452657 981844139 883260317 538629055 61204894 269024699 21497797 766193790 88941204 405175543 141554373 646464177 371368881 79791323 743202965 861827078 975604351 702043775 517097894 111020673 950414349 143766457 129797134 115823603 24660291 375699746 882429989 300522395 184685208 996924331 78000779 503323225 416145607 810461738 296471888 76139830 420789172 311648279 33450133 615118944 923258871 374816469 292309709 655111526 700360204 770087429 992354259 284336688 177534594 61032032 948923102 415526797 254851870 373871098 352845304 799544086 205351163 369773924 22043095 191619676 864555227 608940596 870595775 969510072 101876789 220502741 930261500 892291864 951575152 848178008 626748408 865643031 959398528 903613606 596138940 857985977 386071376 760836996 50862305 229727818 422965066 414261182 50736378 534756697 120802370 913112398 491364367 451751042 226037721 134380061 523681076 192562510 233614956 583480856 254805936 858047473 213895596 12926182 470294560 171348350 555122537 157147990 364439393 548092429 640792585 865291292 738305002 179385694 694901868 67211498 385864523 367647013 282728235 962857410 714867328 94708543 273253158 497141630 45384539 44378895 405391668 554670314 972793184 912903145 569604686 835082774 341308709 449319000 273387215 371361865 232373103 173974240 533266736 975867094 211287353 330894007 275357494 693450230 179687350 677996894 150823728 34147263 125434304 548478518 152084251 301621405 373707438 383559787 246810781 401388924 387799275 268611470 542483572 350453720 275286539 691093534 271242554 923693073 609046957 306904687 257035888 406557618 541694325 431006011 669971792 871599783 46314848 870199353 501115470 739002619 660754667 842004233 106376031 641978546 931923341 726091098 151077503 867352824 928284319 354975653 867481246 624907262 279627663 967949483 965717244 18038485 572383904 375222323 864862701 463347227 428089862 998527083 132669912 783612905 738910291 95470469 256680589 843310478 128080514 75200408 804015535 921338592 743350319 207807755 224726314 840671944 18628411 648308568 209260007 464542876 867251121 542175013 45265321 724516489 514308175 556343850 819192709 202031041 883983611 44068196 37230319 260837947 32170998 882454551 968543435 434133945 394301141 759131808 2337897 643919024 842326910 396620568 892948972 359311115 815399241 825215550 485367333 107872673 979265277 655632019 732541895 406414480 46326054 139409015 907925064 363654342 678331479 443436760 457531023 254873832 964750970 149796527 733534743 963346438 352144064 90309639 682533463 836156446 32558531 250858032 625987104 683871731 90066292 582340164 207174475 312917045 243236101 97299767 330186658 439159124 505214012 636469462 837084540 268459062 5277053 682558101 724600518 478298926 608128860 551263218 21319025 262045974 67697279 49627588 25425418 509119301 720206858 766559298 467270036 951053041 154731115 158203807 114719829 150913671 527855965 145419247 296086286 265294432 272940057 20922614 744650239 881038299 126296609 580150185 273391212 679000320 189513306 663993967 696876756 709445133 239412124 228571214 953759140 352630729 444074343 498154409 1317103 229972346 227322985 37204966 500701536 17021413 496840972 452044458 745693040 545703712 60409043 425385460 527726017 53970448 854631248 293256049 50866468 561958784 194623577 814254479 92003948 213419638 546558910 949639604 833318690 177554384 91847684 845336477 326350478 416899137 508107374 995022851 173812584 112619821 333764360 897037971 171289397 495252397 588333215 219603956 868285702 733325850 688943884 88031630 885685577 779170373 628911784 989297506 950633912 712583167 55791590 798855608 84861420 660658751 156389126 282302824 382930232 225879726 51732894 844699533 768748212 532021656 843742337 940835376 525666299 212449815 22107763 225434257 271748953 857912679 211973482 194527511 395408241 620142273 50314885 371298174 556260748 63832255 294466747 570825762 15795108 817202779 257348023 721711115 146568407 114971743 937379782 680931951 160510110 419823216 174273971 91476613 991536845 831755015 516855538 514866429 703890358 79842843 643741143 127901284 881643790 249256086 178537462 835127588 855883062 271941840 46560965 589891798 611541910 336754265 125358276 60356226 226029155 820970705 809871927 119963207 924677252 165639373 399380749 487929620 823602688 85130848 236798889 683610212 215362768 207123848 687418897 195374421 159803207 881948020 766743892 638528386 768215550 417180922 717999833 216284178 256828159 870253454 707655749 531147254 262824844 720719612 702508421 207842850 806255032 111110451 634712240 203025078 126715553 957256599 170646615 871249391 77055526 987441743 20864315 486052466 356644291 147500476 838643570 291308764 24733616 347611033 94996159 980354212 536168477 613186606 193475099 21044694 814408341 231181775 650425552 381151553 376939279 113516630 691271295 386566824 494280760 881092270 867119896 594101129 611232263 795286036 486367360 188572357 151388559 148007987 313974951 611804504 611839046 876751227 29987680 896494844 714961937 282465921 770479745 52720840 592497726 301913147 445164561 117504569 993847531 330822208 808055867 128118842 503644002 817744398 744366862 526769029 604393891 886381984 625771592 843194954 755815841 993862354 115471714 656633430 861434882 569417777 409482310 4001717 638884785 880542379 906687970 569538483 481133835 597228069 701403355 169133301 701959590 213292349 399492300 851688294 102327157 950080842 936666878 447681281 912073797 766109836 34324328 148123817 322202488 237949643 590497185 383650313 128324227 450695053 70252554 438058733 742830866 101869919 187066347 254217065 571963402 322196470 22984828 604058927 10306554 975212336 510057201 512900569 217545740 103198121 221299645 50296667 269703026 118705379 773300128 201786942 868159717 243188426 36294497 272299025 538752549 792091834 368643855 766134102 423720998 76703549 764483865 111061813 588868971 552505562 653790200 363312301 979379004 237694249 943727393 250727036 295050243 813313819 340779986 893673219 425976813 712291670 537712067 168542296 180915027 963723839 885901145 777949279 707712011 977890697 710147608 905103558 270362019 528475857 407740223 7030331 734888854 138973725 760738807 521487421 903173384 180092697 190991661 191557514 789230280 389887502 874366184 564564456 460911456 711866469 77230860 591211853 946413313 1408508 194452352 235468868 290180358 47422809 551180713 946811872 386634206 171297597 620451038 119358305 179274780 111630204 513901923 503845995 342190684 982792773 803865160 532961655 542126462 829564081 782290357 973993344 109969787 221291407 62422997 580613647 614375017 215741074 933159146 438175908 965855157 987066336 4450201 361945784 370372390 24938064 291873810 62710309 319194240 663353915 713905542 721470799 45575841 191268139 871460183 831431812 559017124 628789293 897455257 151713078 415364036 334144192 680146082 816706130 621663089 140448773 924598586 644656763 396659795 298760128 969435903 55216898 846568001 516932554 968188995 385493612 483348446 21655225 679812218 53305418 611660064 80892650 102636054 362028068 343966345 389433362 509262541 285536565 367063103 936347892 424741897 248654911 937127692 876668691 120559982 584399339 562647425 71825270 617437293 887343711 4256186 568505053 897703031 486272706 921381360 376952472 652909289 100173067 188092128 783682496 340627899 986363816 70960667 400110936 615708978 109035122 952514415 726234165 951012748 900688314 284289193 225474940 583598550 625727441 275583076 697043138 855648989 924902442 886787067 516004944 835786476 924597090 734528647 858607650 237569602 100735475 807341363 939214358 392436266 309834637 165878995 14619965 403225257 140712022 209816682 678610703 660271042 263939149 776951571 925333293 877064787 416695569 432405141 210614585 484238439 476294891 622036882 784960359 460277603 752502504 831330322 357294220 682206820 768261779 478560480 405325612 543273223 270493508 442210809 875908640 68715160 825100992 922544535 775768248 237710328 908852814 668766950 74323008 987470638 136466953 683535659 556262600 511827670 443264763 936159748 117730726 978243788 939605764 926675968 85003979 723888698 580196880 623687040 313262871 116722169 350116936 541381608 930124783 67168545 806519963 945459849 569574746 929673842 849789115 702079501 922067467 992064255 287755339 676390460 978041362 965462901 145163681 473551426 6510669 814131115 917191690 922949324 266897120 668964081 605637030 101974441 46319972 185703982 594536081 14263202 223466711 516394816 726254351 55297731 226100010 755067644 463414580 319601096 691320236 44300058 406330146 312241711 437640612 272353182 244719837 891719151 11650770 302390442 961481084 516597625 119926985 755204530 728064183 181499160 434941981 326529169 176106005 346673146 191655035 280876277 134983516 819735867 992722186 161923223 947440309 385438288 957321818 312131055 422324399 615346953 98110318 786510502 309492764 484714230 547140958 290491575 234773170 515791765 78368206 423005824 250827978 423896850 854866484 628127528 77327911 57065361 843206879 624166411 929202244 152861866 956150163 812183841 559056936 495642364 759755286 909766150 597177137 83908295 158331465 243996591 492180275 403771404 575879963 746036718 873759918 376014581 554741124 45517321 733232518 266671386 379075525 231552937 556649166 420517051 959748672 651822311 203224705 781326470 713523404 40364461 724924090 22855542 393425645 197415778 37922913 480417113 180379228 888706411 703034355 69078942 231545410 157132565 87698461 399932919 497375365 745263257 587723684 902484839 857995347 78375431 225099300 103535564 800890854 321281008 498433481 326257262 402311844 121825270 358892952 930008101 563806589 744402560 372119842 280858777 898531876 413091054 802463595 428247116 90615070 256125164 582112397 999184914 999556708 192996566 359536800 416565933 164452634 644911243 136398427 531596555 707962977 712615099 372795449 750926149 307868071 295805903 965105725 947765055 225689784 281565408 18882211 668678317 248966123 113355230 973578970 174552662 297903866 204012593 140460940 632881979 719259282 374995062 678183486 170961276 778913166 450688865 255101436 246837218 455417387 62189675 159666199 200196401 51599226 274533319 287532258 561787916 258176922 596115548 511790846 162184281 77083279 429110844 720084404 893772551 640412331 374191453 636466811 736779001 480126765 76011025 135811493 982347140 676089348 701790990 721318998 139039440 31370752 580637523 122754516 590113690 263319730 407942486 696664461 876389719 75866439 36990470 763366865 631004034 184735311 385931784 684230361 113085269 854028764 173614650 878674130 902390921 384943829 877291872 349057016 284494913 384909782 217225034 287746274 887539894 540046399 933911186 859958528 404921419 560877387 971784624 255678791 940251963 446611989 549440208 171049622 301143863 200162567 171440825 129181965 569989390 857536449 328340790 672071654 677719489 508041896 702353857 609616856 430970138 767433831 94646229 67473836 194114889 3496765 389032980 464501061 96912227 849677360 983942813 506202646 235715946 899431586 71096555 985171849 173807494 585879548 647052183 180365489 679782961 318348248 46970563 775082490 891762535 184101697 355336138 829014995 548137722 164966078 979806800 988030059 256556490 33399987 72851868 432974647 549608415 398554156 469244000 182355484 127902021 57372064 413381572 157634617 462108439 116733585 307030784 978553152 450398494 451632277 404363677 923024666 313799501 236296936 798046473 968589119 616178462 27848776 3129739 541918736 221126184 335078502 158921323 38527880 360479841 971031745 972780992 890264891 754967009 109608597 507653186 279255183 160695792 767486896 335949458 63243249 218269902 133466003 449116368 262613688 590368641 283507288 732330412 689953751 547847697 741365682 292809746 177886959 76645860 893028308 764849636 74990258 44998781 592235173 792281775 63624410 515623473 91330135 223047076 12541707 268059203 123543057 241918715 836519095 568026965 538145873 847463180 131038652 688868261 236898349 860046119 490673190 289654904 137231286 691188468 518931902 206677029 460208713 501294100 661617291 8461116 913039900 524702445 463785625 77673887 282835287 456454606 888481533 225925042 233158807 14163366 294542033 987464799 238675754 259306711 797717058 199416439 409593250 926450721 747917574 195520644 880193869 614032819 833492522 530864201 550535792 894748841 229989750 359352387 725240972 736073554 85610233 63650950 621500357 909784926 617368519 133875900 953350778 779324665 628962150 486884139 232683439 131625337 754801476 699089322 912796660 601477011 836840670 567061783 464618942 88908425 146788302 113726948 166754951 616233027 184416372 890992600 823305330 877609783 783087435 949741482 627934529 703196275 292299346 516048690 225070963 134513792 29872321 949426315 656707053 727898638 709271154 984727178 109680398 153149425 4389765 734133868 450450688 424198699 849700721 551188852 17602143 840250839 739590466 153346293 181978656 542625252 932307724 237071074 279787036 331481277 755691827 452313512 361279758 965556367 394329174 279590229 315792529 407004894 570242138 324295228 766873958 903518996 29862222 987711889 369933469 891459018 913708443 940954463 655501802 888083321 206483672 166405093 240565615 297878444 212329197 242270925 581744753 167043140 166353181 950582615 526768238 918382211 882484864 602926073 513708528 139880889 293309772 796553759 890821029 983802064 872931160 635123623 220545390 377632435 302880063 510823142 481243322 574415547 486836043 432532253 541329027 690493119 697821437 90893572 171669978 226046079 742922147 723060626 274177692 503249652 402026259 319278136 538589972 693083727 32851199 87675031 744187154 263699877 74214346 45366937 205411086 466193727 221006926 799737616 136019377 666576058 12618813 776425833 163291406 981362060 186195302 410132131 445293892 482048771 415022400 4600736 775574916 736075140 79456267 290718650 460159983 246334457 368798146 680382263 368510000 220064277 169801524 283222761 140593635 546351765 205502989 583252030 516375535 62297981 671106679 502393244 628101981 776174835 333452985 502359056 747886146 340424072 550204214 206723720 379347136 904384918 447380220 355847365 723203047 841858839 687309813 151908181 510386155 127111730 877996899 313803112 663022980 157537178 70263261 966812751 239725648 436451246 360670790 900335371 779122135 47916240 65857132 856793782 824971356 184816252 562119499 516364748 855244111 523252600 26750067 599559168 435048139 10821815 193888699 927120702 805981906 72521743 328337854 258045409 44597418 280017661 237017541 86403973 503272913 504494823 230238334 902656054 863632914 840630104 547620764 400367843 35475443 263904899 249078819 430018274 465626048 124445948 717510333 479861049 201739718 775586637 897060003 449374701 895726502 31434661 464781544 133706653 446275147 49457159 443530204 321233379 980104550 478013590 114340440 287333472 729652008 914710773 431361873 19820831 703051804 738128735 162407409 231729354 539354798 557779192 542403766 204315933 347494996 171382299 627266610 729768242 692584293 648272154 440903748 77325033 98181394 854292870 34289648 793346853 972221482 18705161 466821356 88018010 391039995 166793844 257571694 74182764 578620462 139065503 173613808 16959093 106712753 311214710 321388953 136011178 734275217 897033500 377129661 73870004 777772927 225715424 944251077 704790093 533625481 810206637 914586582 991195764 957222860 534087018 392779726 879290993 793103869 584387485 873227978 196955375 813814202 169815615 639673021 48537227 853843671 54858421 904784720 740534536 748922037 195142385 318282021 635627689 553719494 485249174 48990256 302627497 206611443 178849 470373734 586054862 829678678 454784192 705428717 12401244 146684955 407244590 939001827 231853291 539952607 491572665 366683863 414510096 198337047 859485057 428158052 190658306 326855908 35848922 704351721 403728709 636291821 825013472 896546531 745821786 466251644 43371528 407939995 395652513 116023916 372451678 108985303 644190476 523826887 523036842 764414135 43441153 261294186 189124342 1221562 508393080 282255430 112745645 485255813 842096387 156035216 120707284 264447376 666792076 1168879 315476801 188970142 455285113 869434583 751759685 535765427 809930722 616764345 696927623 454564145 309407934 293993257 598870013 46626689 174425728 712328399 299413375 464286344 744516163 675639909 239406291 576730769 675791991 218057120 369780537 141880832 847029829 313941083 752943225 950900081 786681487 263758412 620212836 908681743 181837706 19124693 292287937 506485706 534473192 798151711 24947706 232084278 697361320 227336968 267601402 600351622 634721946 964254240 955636479 120064840 768952770 319301438 84634234 150048138 982258141 502675024 292336205 40085392 519795083 174538617 675830248 337967954 923010353 222124123 850606720 498196934 575126203 337927767 481440748 671728976 128460877 188957712 176166141 18389001 142824309 223606062 408079503 612731934 432028226 543939401 575691454 261543230 471074402 64823934 701937099 164703593 745563395 862293885 458423180 745991873 506851825 467235646 331838469 674098306 553199641 707571867 335072606 584489558 823890297 884617857 717784262 251672981 914941743 787244634 16191526 823539679 39076601 471206825 922687957 754996997 69781140 610490051 807083601 9994084 1940481 955889836 752239786 235406763 54474224 808953076 330836118 915943854 2107692 701725792 271276822 420525396 927575182 354829773 794312724 943745236 162588956 584211127 371465536 551874382 717792105 25394469 311982440 992075421 1305690 126670483 792972166 446467137 51090300 14994508 503933618 836269027 517055815 86664098 241778459 807813065 452556345 135510188 259014615 192583687 14625976 33248351 434313563 507413666 881162872 881367760 733910200 378242236 862977878 904672806 375567268 748959112 194900643 771421938 9262368 293965377 997362244 783419397 271554175 523370831 476468847 429942018 203310751 800732964 847302894 86458951 23664573 38881659 632950278 789029229 750489088 972363247 255455330 431975050 934550392 925787303 768313444 683097965 814575978 788623112 373346741 718899820 809294815 556767259 123839349 91602252 179839747 391594011 206773560 558407779 876428482 67134646 412544108 210994413 334146705 253898678 987245267 258562388 84949564 788873351 591395088 879376260 26229257 940364876 866792197 222872760 725955763 779588413 499350958 174648677 321323008 655201832 734885541 238259275 759127481 622081706 465242717 517734210 33839656 133719510 980729691 312928126 491365324 117962018 899589587 867195581 463362964 541486716 955623591 204701737 224581825 354844644 957526954 499954818 268009662 637142050 12719437 913117082 659115769 281059696 709757829 695087548 659167880 812887691 366791607 667943497 568828229 547624179 330010281 423732412 958103574 956856611 315097771 69987822 893618471 405568528 927242200 388243438 423808267 286704205 690217866 381890701 798471597 761243014 333237842 490226593 844118133 96520967 284291623 686000013 436008565 858176906 523735279 965643679 468157213 707363094 367199544 929985612 731005278 430153767 994607910 725838867 344902981 445529020 265320070 744168701 650760744 293470455 997267429 111188263 157514552 157154271 253285615 393337651 986005603 816565305 374637589 667149668 289590472 208407433 624578539 528741357 638054989 272675040 187087825 96016303 498273810 673890802 281442274 998337274 549899411 565633482 42027330 895353268 231216259 784610333 316157614 252673398 217479475 876389278 298745615 271599079 285116306 693822444 349495072 174857863 666202495 822874180 471100649 559214166 89365928 573115710 717736396 161580328 268493172 954516112 958922554 48196482 697394117 134257606 701334130 636915857 174653897 298889793 945565267 613481611 877118361 782651473 980183481 232163036 803627746 776264107 74745468 70469687 765659304 584359198 597002014 365188814 208617332 154173311 83183151 938887943 279384870 114540801 765379581 74740329 444499000 861668535 324234688 782573420 126291201 633133012 734372109 858015366 724200373 898563728 938276741 267024360 73280532 841724451 292542659 835817397 173637086 604361571 36708169 21957552 499911089 239622088 495384581 44108740 242938588 307612864 46443713 268982762 303691606 92140953 822848 202534379 970975542 748254590 851309593 357482403 43939293 361999603 60307930 298264110 808408159 521934291 732876951 222711703 564694723 625435277 445239321 324692834 569734268 890998800 835226980 109571166 232454650 426944367 936452152 296355205 450115589 638916273 58132871 544799208 394524870 318386368 234933373 436824773 195906012 30704521 406579484 908852243 621920420 617555996 467636205 182845775 236270970 315871783 764504116 455988229 474243625 561332579 319967279 831631671 797240183 981445618 360435433 423709808 129083560 253969503 184389402 681580510 627219981 544393328 239449585 84029378 226662950 464175480 303981253 158595170 616758640 366624363 464439127 534849323 669521741 544901302 67664777 860076291 996865388 840913956 579593 241191784 711542582 594195436 411372270 247758152 317979110 832775318 972260882 161094304 14593605 176622563 304963304 582572687 145147728 969736506 407926612 362782446 178621125 404384385 164405488 185085891 332094088 708777703 558011326 5386526 582744065 152866055 908321085 819822192 288268570 275452408 834093183 936282841 275243746 785148290 960458367 476966250 877063508 906774234 872952894 37297649 444800007 48391666 939939347 250689520 773209218 845266248 95021805 821885528 840766666 116792069 898853601 701644259 871361004 187349478 249135350 983679048 104824766 782738884 540202371 382633515 68497672 117202405 282843470 283284071 380092327 418778650 274408229 693930457 202801615 847430781 324649418 300070732 617238749 740337128 808153370 289096349 109315595 23807316 749353640 685006874 118032893 659524080 733758274 76565922 656600516 230456501 507291786 707481895 274706833 664262262 628775496 394655950 894001650 664545403 513168350 944763521 489014179 745610664 127288897 441948250 1899280 690948942 48227539 391923234 726024578 16389236 567517297 614050521 821125534 954710631 711298975 604514509 453138317 46542768 645746099 854678780 651708601 807367910 222858699 472707346 952283804 811126972 764854623 822107418 813213145 911651065 293836287 768049799 753757030 363008515 582012583 235482274 538384467 180121294 586618931 777890058 16038871 180132378 878763592 178510721 966729392 563943065 261699880 835997630 493721515 77140882 512390378 524200357 709232896 605323093 808515524 732299265 93328057 644694403 861432343 419171975 354611001 593962613 250657610 98808236 985512065 344614672 193518343 693732406 700509601 17360438 705246157 145563989 49162848 595887695 66667333 67751584 216949734 951079773 469202586 426324069 502537195 951854337 72466475 272890787 445662349 232949038 42752245 531952721 801745969 38060734 220718488 57906301 27432620 605625449 931820996 135511462 406058112 807492545 870110744 795317114 179194732 859361435 267864763 802798259 724179641 505234308 696160085 681480642 283207380 623188355 39417797 880398944 221792586 966378352 762467055 573923325 127149819 204012393 455347984 662020390 647339075 83402608 489621257 331657905 188224268 409947679 9426641 209403662 90678186 100015109 922989103 581446775 63626333 178628510 517623496 416320095 367901501 674398254 480006839 873547162 451447167 56758003 212464853 181051829 77031300 801555901 371529655 449078030 97925126 791798180 930163292 664100696 804905367 539443077 904110696 586175933 729529600 417023952 999872738 588369413 485470454 275845118 851265329 659706061 590840010 96410686 547735533 836925455 7009147 669439005 761151600 206266501 11330541 80691936 767404863 940545233 238807622 859567146 342826165 96836635 244574164 350509276 347001689 281014593 916183959 624299226 991920682 381071507 634746891 410808020 866319128 64997090 348751339 252534359 185720060 856484868 71481332 895748041 292655285 471172824 553138026 823421093 340341998 126110889 774012882 449494347 138737937 299498371 274216126 125746957 98186524 121186954 462668566 191041703 785573848 100583650 706036695 195753627 241455265 327834776 64187646 729134481 639434040 55851895 604990037 996269306 411912364 866893485 828181975 59484039 334469857 977176196 208892947 219451539 220060004 226094534 502841150 977604951 964688480 741538153 42920695 499210949 426397769 642920095 398425036 746689873 989843742 978766880 924409435 898122947 735735578 152001339 71425067 113512227 143875381 312194072 35667272 502297155 481105840 279117461 747706621 664940539 566612932 763809484 611495526 219353493 66841603 325495164 927510770 681691091 417040536 870574577 21683677 781407069 868210800 484912035 238487039 757613072 246702898 92796512 289085106 374723473 93124581 891303876 776646717 556570999 500924866 317211344 31319027 435552417 468820169 411543111 872191144 686885591 936460494 572420932 566165465 295910515 996976532 254004088 858704193 341758944 390797159 921491795 738653772 603644338 852290847 740932311 57264145 678849638 937315845 289983960 288084557 230613274 723272753 894863032 42069549 958906564 598764373 308969975 159563948 502958520 564001874 257977985 625691220 684129241 227724374 50036927 65506343 186022384 74176286 289998389 409613931 599720253 216197537 39739795 237203160 544560454 228863838 556768337 727072528 586520666 864242547 413501029 18649651 755502189 220668350 266773764 299895944 300566048 345001527 642478686 640648741 19946116 943176418 229289766 865811686 337886531 774564591 297384696 926824 810344031 191726750 880084400 255452299 688979595 697204395 657973475 407092365 893703098 932145201 661785742 846172878 453694719 522543719 160695904 428144818 7911433 149461037 112625270 983689453 218971279 106424631 190437254 8889468 835105880 505721278 35627524 577924960 468121335 261410643 29043663 264539979 831946124 300500515 674933434 689413373 33045983 987176866 359293157 407500300 789936912 622826564 251006931 644461654 105763809 619910980 8703683 110323026 88399506 854345498 590239952 42285762 330978797 560951710 618728270 10348102 97992082 711436132 610581777 592533397 813387195 160937870 404996982 952004190 904266073 21452428 897808156 570235593 188464198 172978958 78403799 645733632 687810517 154328310 13861377 286656616 983405928 733347739 253075467 346514053 452046709 140027378 529158761 799673083 534773656 210239084 562112515 345548065 248096753 618856682 986087822 749553927 856026850 300073466 977902632 182138230 134423677 597322713 165862877 643674332 470504151 772845332 549870876 129424106 110089837 369421032 958825184 193835131 107268190 171795910 269582968 843599539 369224730 265744590 293870544 771117892 29900938 307988688 668246165 738787731 302772936 663715774 91827745 266845996 917370696 300051603 96009288 861061524 376806247 669636839 335319947 658048567 963932718 889261507 211594919 722024464 147170215 903146360 299969387 302434712 25839237 746724231 488877445 143220726 501425421 767096789 337020472 116641137 512225785 432880068 389199737 713322814 224104579 422370178 551472216 437526676 629401991 651055914 859684 927128106 697957780 590197154 365815984 19216467 95179380 338113819 21662892 445070753 174050733 900244695 610865992 5654088 262011630 432387493 855940809 748118473 615886688 594370376 28062307 3234579 271819226 328833080 808822376 124695468 246085877 902194625 579945073 196447331 499116016 114816939 950078873 965770136 465263019 119590054 676944466 828003960 939242117 915411215 693134823 758152923 2966164 236882748 169129578 409401666 491606949 951397856 110366705 949990880 11578469 267285063 579815752 584649622 415635161 956521827 916750613 262789275 725649752 744690713 754706257 166033621 360022379 684641330 630105180 550280041 894878366 235944597 187153988 364039762 917942201 228642463 383799099 698307222 35814305 530615219 345232468 709985192 672215374 514762328 931892086 264806340 209587781 42806597 771355978 937486287 285971087 15592319 916626624 218589245 308245071 822316272 210302415 298831588 755353740 352952592 24928458 349893817 184869518 970147983 360590052 911069616 622274634 227900178 617216473 709924211 232560420 833397622 866574536 508804828 701207811 958257465 492096307 175138035 439150868 788314975 916034285 414547533 387887236 917220616 659594849 664547940 992168455 30671392 364519393 715611866 926216325 999602519 378764114 713467938 302507413 268097813 28562700 183923854 475659995 328732076 990061225 286584610 658751952 698176729 47621774 196045515 212906591 570845261 595302431 772407039 89611010 177640713 465410326 779634633 669663367 459890702 600079555 668002133 128714564 811843754 699131268 861434550 552405214 561004577 51124357 785640995 710798072 964607472 148746734 959017382 500956759 421980493 563915664 974848416 838288649 166892407 544290548 931378114 510990490 752207424 947625110 813409860 648587200 474085236 829931680 396441900 361356298 206175500 628948691 906902733 562238954 995013081 547828427 521310141 778855528 539514235 848951568 345419386 302425580 298373216 878390690 769603103 59107480 155005352 119471773 113617001 657457234 783877585 512621817 173120382 913265757 973612369 877186478 420895581 72431419 183510474 4527152 581734040 792685116 261079037 896361637 924465046 574587309 283484903 476776323 802274437 167286034 378285962 873294505 180065619 562257526 328437350 388312554 357708689 910884570 680550765 84155054 802309073 912548934 41339954 184958622 848199782 872563195 663333409 437436243 522366708 162468467 228493272 207860574 143681557 95542078 376919144 74333359 25857506 30351581 445222891 601803845 436471633 203217767 62783087 557691304 159549679 489479206 247749392 467241088 192325622 115567725 215686192 18852329 716858516 142569623 54200216 520897202 856989523 368606054 805038253 632882476 753539202 372440449 819255034 216289600 449316185 981059592 16620633 621732558 675038562 182046723 257020077 215332699 150760596 253839074 684896357 860623411 817711470 77110234 695780019 251617572 366541523 650625102 119532067 381827810 838188467 123188600 208944905 690299623 339423591 532232181 212689282 18660587 83675540 225668437 307446308 918515554 669338153 171281776 766900359 944873905 69743062 583638870 166154449 335329732 48702715 928798413 893084909 610153660 600270430 771365605 266027284 987616530 665287105 119522311 32299532 492280087 706882224 583499092 917134180 773983742 246591562 26484544 258613891 396301853 147110568 456184715 250342638 319419394 995969937 102982825 226486094 382222584 521203399 191597096 809039833 837349160 388381384 749322574 865544992 759066068 440586788 792991108 500136135 262642474 687629180 546651544 55629436 409174603 248660361 634516824 659578565 221151288 291541764 611319978 36020023 740969688 76092641 729071477 354788145 937863614 863740934 781882423 569588846 133682151 678065731 107729591 590350891 622675159 214141834 625870935 288292865 976063278 532586400 525848558 280698935 470971600 541220336 312082569 477027145 3048247 168883178 529996582 168074786 19952185 282682808 436579379 585491577 774126420 945438785 753161264 101184566 974010299 889898438 33528572 469184930 351420342 79549375 168843381 62193041 127534714 674640426 664932616 776349068 233527079 472048501 983951570 43702902 462851303 775292430 270682449 899274858 764465662 272612090 122372691 555593030 135326041 317962141 171780194 941389282 273634424 294912245 98000118 459045734 915926181 673753592 90963012 722236741 503084122 311850144 922015422 196412245 569686439 517386510 610744153 647965969 923819393 461249235 279453081 184404520 209229860 774590972 978495237 168961937 359792093 294849546 927451358 945775682 407616045 407331966 970133592 311078195 86541009 465890463 263014942 120808650 285715245 280275425 472824614 853373059 475299244 61435232 890702017 536619280 828898744 778344655 16203142 157885004 143990209 275076007 579352477 209248255 827585607 21027730 582460160 661538813 673787777 931773912 13262155 840783569 498834034 561473905 233865511 30626885 747771995 242580725 498882837 844100256 10679932 128059347 698482081 180633653 157186804 521324017 208834667 404301399 672551836 539788645 117856706 8362356 826321854 464120024 136554911 81716018 117635913 34107292 82026283 592749416 472924461 95228365 373136706 670045606 28137908 744736766 28006191 876374684 753389888 27833742 702221489 395988077 112097682 996279448 56398237 659148780 543550194 501639365 786921769 265976900 201254289 222357650 22561528 672256799 184527652 397654679 217228031 736371628 618381929 661771948 916611230 246158184 377282203 978932747 895586735 740137378 207838816 531959536 87728232 121914180 674507545 250954196 547878587 314606155 162794600 556334740 284910902 342097365 816249283 47191879 79151159 660763175 566258737 66290718 87564585 698388455 592335001 124330446 65915869 739060356 443880811 565050666 138376600 922832020 917463840 248691075 729767370 473683427 775605114 456954740 539006124 124748255 180972308 763511661 475092506 379050972 736941542 955944789 84862130 194114367 288456846 162270151 954786023 841840147 607516953 93323248 535032188 991405875 672279395 758275749 566911356 208257109 275079573 435409027 848366135 828288592 719073735 50851181 194204014 214741396 183676356 43324475 94852385 198715107 470272273 367266996 44162620 188360236 213735731 43817123 325190469 689757276 342104564 49414259 827423475 203979584 468287226 136730805 55546792 645831232 434198969 352626985 641555663 105595019 382119761 815308364 582806532 336698129 107763489 148817107 175323079 317770850 117710519 397279914 474894916 920978038 77333591 262386751 680233572 86967649 1 896832783 233396605 814281066 745289198 374724125 156012351 275190271 925970428 142102045 506360457 570570140 748494489 849118605 730877822 493216061 175044558 892334970 851028132 627916757 926759716 113318290 121064742 505502411 527952651 493913107 153603685 683520815 200431979 190288577 336857708 662462540 41952736 708454273 693350822 904894856 291998484 790835914 753851334 492087581 636654590 36530630 431598825 815922791 299278543 850992383 513136292 514676253 145923450 635277703 817044840 595029074 657654700 850724193 764924016 80497674 283459347 552967633 742169144 230556111 914236397 541138557 609520558 774486454 496257647 431324886 760192348 922507976 294715746 442099751 629376735 155955022 346734294 29497030 619527294 628787383 776808039 581624789 290631321 259520113 702009167 389951646 457253734 759710203 170090103 889243561 360781417 396301479 158965511 723455342 923533605 167354831 4956366 423756799 731536025 771171584 98115638 707445812 160240688 664236428 172497042 24642237 480806524 14443432 353424068 391063254 262317032 479909443 623605511 907117781 727018596 22950556 884523967 549568124 260035231 461823657 143500764 204135236 522297255 274848173 229998509 344126742 111681461 700571385 115746489 815639160 579668377 176340220 403214617 119283782 407622476 549995337 636142908 625757427 752137903 279306216 68811814 809327729 994034421 43411495 243165543 248431224 116698056 271188701 471076271 245736111 787171737 394096812 695362259 222219681 165731815 685358920 816841555 192163547 756874768 748314093 226299990 186865636 301972917 157026061 69222186 167804901 34581667 483033243 454451564 820957728 949157902 321253454 564511041 162849590 167624536 532272634 345574849 178436141 194710534 276188411 655344956 279632309 151669099 720661724 860848089 805147958 775384423 838174827 155512013 880798666 385752255 334575309 329416816 220858950 10774827 613589472 717747694 484834072 403028912 910236046 451482148 560685628 241376848 487456569 778466516 287516789 618033981 805954728 251145829 429006912 386766816 456478236 999282826 720949916 140451201 988547971 849960883 432499459 82419128 964231181 88234672 532637523 983093656 902876983 280818560 676952675 552057413 333449132 237992833 682881671 866461722 842325199 883409829 454036382 842605442 84317950 708133616 993885178 724104442 789338601 525498567 366290211 271958336 929520422 566253971 485526235 622802091 27494819 802852850 834030861 824154381 365388314 325437307 669847622 615554708 318504412 939919859 295041512 920532890 630137553 187635237 534347381 201651923 35703655 246462349 926906682 99911608 733057514 663073435 672471018 686922923 594014736 343965347 494763026 842393751 777529259 617193433 711472393 815265932 313764748 989531143 727277269 543631789 944406449 234167784 533001304 15424390 469664567 796085684 19696824 746177353 978728188 584910099 618902025 585747390 727331326 613136946 759839645 597076216 164091552 630858324 620813924 957867140 241201699 675525317 181906572 16189929 775221784 363890606 125187010 6211272 853161264 255224330 960789838 891971883 132009762 931913304 662910250 77361529 683836126 162882280 672415207 360932236 727774869 723787844 974540426 9832774 912618950 497445245 4749394 164507408 664997194 244189745 771636611 424902414 938360456 394733270 163323380 567388447 208504652 596798502 481300134 915774494 228384095 795349061 660407645 97846239 77650194 104796159 706009539 295182996 662484702 918384928 207032878 9965213 665666933 226725887 654381357 30693510 63418091 241593198 452525174 269829727 249904967 371749658 386563376 256802206 480539902 868171465 875262470 623502548 885398903 921397813 619176859 100794664 994366266 341087733 532662663 138418652 105541188 86120752 2333841 744774716 577448218 430101264 980160873 984764695 2166772 702671562 251990907 306344290 168430930 605559086 261170709 737061217 274885704 794667243 203658559 104507560 59764585 527007175 357664575 956943258 437592151 672641420 403651361 600324164 28370097 898868748 308614820 495488648 573123372 637342846 647449452 630719706 769126611 529442153 131902140 690826489 729794444 441859501 28097954 18361409 427177377 523742966 378242436 953080825 710053440 986131120 990140733 136865348 656701203 469196841 232056618 714382762 713758557 269075234 72569306 183040669 741417814 363313799 134744864 177963623 280359661 267917918 667800433 36279603 988060650 361319545 942492453 276923112 800271445 719461602 225169329 43709957 456453850 599776743 882281655 835899445 463362600 962481166 191017688 485077572 270336778 934220398 824189569 714716019 132852502 203522413 64542507 839861281 508262924 253383696 362584832 87411081 803757975 163276296 458523399 3337547 455451851 402658319 380096369 760112856 124647927 38673800 250343121 496691212 517074231 322520715 417893974 146342774 565920669 405974528 148216511 959109375 692953953 259846156 831721589 897546275 30299506 476376746 637963056 987295191 253938404 920939161 35124918 313631009 327927095 506352162 45896104 69610173 429916194 585423923 863626317 996977338 909264414 70434489 582178136 379053346 101419147 211109420 755976253 986645597 537535511 123411207 372600377 744363368 434308326 713345952 883955765 467577921 416395468 791663942 794591081 369129606 758361017 321210651 35213132 56304364 727397200 588996600 310138873 761247723 997471095 11367668 402544948 376763917 615722152 141311816 527013378 882972515 279752787 903820166 238683225 920856744 221814454 811790082 344629799 323201547 169861021 835059677 159041985 879786977 947162166 508836944 266088924 146363331 284458618 617512864 150484407 505912500 475719214 902393107 134462380 836379030 184518463 175714616 44188607 816240198 740434267 287694136 498211774 316139153 695277872 427841405 327354923 527002593 170853534 798634684 933570921 131451373 240589593 869947054 832980341 375663717 50297687 784023833 748475988 980447447 450579905 456672094 49625448 634904252 835586549 732687520 670385322 320789504 11286022 135664523 782140350 317530189 510090616 235823920 486094718 105125912 291825048 462745015 546374298 808814217 411035668 625218908 106368331 476105175 959827369 248148345 207129871 128711560 512298636 133353628 677938461 198370194 218536410 358255563 697920063 739290906 990304095 214058721 354053403 123843387 342941212 787922241 191809894 785009706 446905337 437393724 156455231 319910291 262912096 240449331 444924851 117494144 149206040 997467584 554224676 825543233 930607900 37472122 681767682 109794530 880207046 19909039 872352652 216759776 648696134 385806692 433351374 329844017 652310032 262534069 990463668 219467906 662785040 23582349 284615759 752238092 264599357 21303463 308360361 282647347 51482490 698567619 936903332 111234470 419950275 706278350 385242364 129004720 280461155 275474659 366940790 672253345 722152426 639719487 439513441 315550 900278108 672307678 588142144 311522496 65750630 558029793 951460386 561954559 229077476 359224527 113029042 877056361 46302079 504368812 394485544 341113377 565017643 219958323 662490948 266100400 205759068 10737879 117016786 872565049 880583879 540825557 569344841 951483061 2446150 580243164 44058168 679002031 707649299 589813488 794745931 676454566 196115587 375449765 79792103 899355425 314510260 263463441 250166476 142171126 138738716 885391847 117974999 739344354 571924664 408662347 642333968 865809574 741907865 630064066 59028713 115621077 306610963 338295371 605977242 412698575 320119115 270767991 600526332 41583381 513652948 835140335 234681266 175531961 1628293 131431501 613987710 167524803 125320615 579213060 58613447 664471491 753893587 535622165 44669928 281167296 732304415 649469732 963258585 969158264 142942072 726074384 266673330 164183609 776458987 686970870 746096928 67265998 324704486 125553716 239504623 716108106 782670276 155253296 427125528 299071007 524273271 844513181 49969688 440467996 76215599 538329946 746687035 736966040 877066237 267545732 49866811 347450512 47323485 253017630 240245843 487017827 589957038 631349310 591472694 665949333 622504938 35278828 549879198 437495716 395548232 160356171 214531011 94198680 167333224 85509580 619036738 718747489 617694024 498876092 195253354 556210180 64177631 829881961 359582995 712599891 413320998 167200420 964078328 936254413 829772433 975948293 131627180 231081086 374713684 743089432 650550182 23453197 107983150 657902483 386455775 559238295 343748619 250400875 432568873 914319897 967263193 201260822 762316635 595164139 95571865 372660735 310104278 166750743 498561911 372397725 187223665 291916065 101829650 130565152 198819129 754405030 665648327 144124104 39805394 303021309 161131896 932063947 691488361 981035613 325506998 547445612 859693500 176894437 35028841 540325648 405130574 603760247 210771968 932989402 40451041 945523262 969067068 25532433 910337672 493857368 671468224 334148006 884599409 3620186 383862101 939296465 368091042 786562033 549564704 877644728 469736313 471794842 228494535 163871723 918481563 734261505 845180709 454708072 655706924 292077608 704182050 228430233 354302247 81414286 887014997 713207783 520312220 780413106 593775188 271119503 461810509 222958516 775428532 173998100 336571106 674475887 131357275 535282611 951904608 30658086 925605712 898201486 437579997 45063336 849427416 491324116 256898679 763114454 110915896 73198532 219578004 744399105 416588067 900543019 11585676 125996896 388967045 868431522 162426884 795892556 557038051 922775880 831137685 516108047 187461626 140894192 285675165 372086339 948164840 664876543 538277011 112798172 689470451 780814689 79197291 5232118 874271451 251281884 772493353 275556461 667171735 234482098 893750872 882212629 203504310 692963337 978787707 774974959 790066433 185252120 722216264 744060863 524216255 247129812 455084134 701072347 877551345 168416275 233390446 907413462 101895266 243647759 820138952 179441668 240413235 409757109 256433913 587936529 13851490 241535249 231774274 760953239 374108428 621847804 68685449 502556802 205022424 973281907 71846763 361972761 833078622 801314337 857013735 659570046 351711520 672620649 619309472 436541236 91371908 580307775 93611585 362697212 198112745 385436252 529819876 55171109 726937622 359792800 334183713 534036467 595618063 304735529 903183212 968997937 587227265 183577585 751021275 867045634 80710196 413410670 213101783 683938651 534794239 182127748 706763634 629660069 893281514 250578955 916411271 664626125 948293613 619156073 953837408 875762261 203177021 401677962 934272676 212099657 48182574 846911376 442138499 17566569 356571383 402956998 744946712 432271875 284180931 338259081 335204647 529021778 277512000 764824409 403551327 247614728 663558432 332070796 486030778 66582783 92428794 316103026 689916103 103914964 157402912 650403287 732679019 976529792 108415786 6954666 242422977 787509315 914751799 242959788 4331688 332771781 566052444 232316945 457556046 506999730 100574110 969447617 150644885 813946040 759239690 607715099 581772033 196562272 577563472 476372885 565073493 955663435 22312293 871283985 841837913 776109625 230253269 210507529 149997133 43623123 207524386 434563980 909374803 919782621 64374023 936192785 972660169 427092554 176338034 998878382 463483055 187092092 102393676 239640172 377198038 398850555 875497693