1000 458466359 322578553 785182145 624260769 252791428 194670264 612014374 662472707 180261234 128839927 796686418 779273051 26467543 135168017 657526073 894596093 192977011 317806785 794151861 663037655 395676547 124277337 673177145 820776992 484175914 157557271 956938700 563678369 380818161 261945577 924154334 603848462 427020714 365458029 757244092 805074043 461039881 103182692 605786465 923031466 233517771 156645035 962811873 622115021 188418177 244603896 526785418 866499194 117397430 440142724 950003761 691422903 468856770 362227777 784282654 626246873 346641285 155487208 631081325 987438229 17311927 180835394 798907907 701211528 120727129 297566248 961294603 821261830 201128389 455645597 640381075 624564503 341514276 484961650 608176366 758252542 320669118 296521526 855124113 780248006 316913734 94127445 887329186 592712635 368491870 290762756 901176954 920551459 89228434 147463076 536245847 928168174 34676924 205138618 536370906 753963041 240283032 147174135 521485986 701952959 150613418 467795047 588607294 576567012 425632688 470317389 510169696 747535347 483124167 146576927 793904756 621123190 35555256 320931904 564174842 703700888 189136259 429365601 612014686 668124848 203807588 241374060 911166942 943848670 133959450 145888208 514790774 512433839 483667599 269205775 528181218 869809834 50228038 453831872 533210354 976022292 245039462 169984600 547735260 785519593 288323368 208240029 896346345 831868791 148016833 402300727 725870848 830327927 381796280 97493230 584305172 611796711 425583321 237427914 622544257 687584235 475464113 500981393 513864655 728442735 438624248 204587355 880038322 506720570 453086526 7277285 992039505 664121526 291653685 447080276 929610626 903235835 239197794 198429347 486172360 637975464 23595488 179784520 537226517 639219846 396154531 504150199 877376335 985051747 138339907 290359360 597000938 949253169 50582492 262890869 652058004 551425185 277689747 268021324 697450758 944761976 343972986 225735513 580086694 878686038 101813920 136721043 536175722 888657845 280894126 498606336 513377032 974710152 47323880 14132767 799863382 683694876 431755593 270622281 527582574 918071030 126930073 244132561 487391817 707250957 261531768 487516604 773714468 711668048 83664868 303463850 753873186 648114444 286826006 377978295 546757361 836901074 289451906 392217599 807224399 973368790 332859739 215591912 840886377 977778043 318347485 83600447 855446196 941206350 202235333 92493635 521689716 657321564 396411086 71159837 659266543 861809187 226044528 334893191 743461186 667797051 70542789 497761379 517534379 707926725 182713057 499742881 594391625 887754343 145512200 372402642 515105827 728342474 474990417 90902832 661213223 615618931 331765352 318022992 531980830 787069985 294436898 423010865 586675251 823311617 181841269 176875529 723477419 596635234 99840235 54292835 941003257 554386619 238249828 281697005 572022797 692747912 205940884 425345367 948174881 582994337 471930151 252208083 989012895 848122189 349678325 443650920 981418310 588801663 414354183 196845244 915737566 534007417 147149051 286357315 630213986 531524122 3897243 187924877 915465773 583460963 132869520 300410809 644732919 738161337 383716211 156399941 836413971 933464622 13660392 68946871 898388848 932681853 323056358 256928756 566113143 790588354 367117839 204017182 538373308 571617311 398204286 287286235 544610013 717798567 54322086 223050881 794107700 881264953 278585078 300336263 628626211 707660730 76487963 218905726 498483453 537585146 285683524 125958367 966117710 506526076 397728905 250573523 991991889 780635236 415279069 58112578 840345857 597489562 99273427 490660196 584665672 990707876 277956727 375800261 580910417 733245605 454776422 375267818 753634272 935896252 67113642 74502326 661569136 968823167 319656164 23636283 579784670 892645685 206793545 269146551 700299559 747678105 114060449 474055808 693342117 612988426 405461931 335349212 585351408 835302203 366790370 263607788 810654537 831459107 367376320 88990118 493264888 762629672 167868705 338522939 673490102 694258524 70931230 339963812 675139107 740747025 151869720 328408214 888114589 749453085 246565692 230203311 809935438 735665941 412405048 428112141 987296242 882758166 266241410 486957279 678549474 565859406 145025046 226163236 585513472 917150455 61963355 82521934 949168523 889333722 76342404 108055321 613396296 597973725 234559689 359505406 997248386 915341316 178691420 303272237 655569912 525837016 140864307 31291591 540097668 901104931 291854552 162511975 808334540 628245100 348231824 374172904 500577066 536713115 99490775 33518684 512176021 719698253 482877577 378445538 657090179 742497723 298089774 354674194 613042361 846230976 43534058 253711917 781205773 624006779 378865033 25851623 580289584 906454815 171789183 18467233 575801322 877421045 437215113 188885511 637220117 887972147 245790274 483431773 791248643 977525462 486168217 405788847 655163110 941284400 288943131 128574154 783431338 537575007 181090952 433318124 648582948 856371222 353327453 182530530 838807102 971462679 303907892 435875481 488114162 887705397 236913977 242766463 875426676 859639977 481872964 383642633 874387876 667923925 399731232 385821186 746195052 579286463 167591319 438642892 761323944 773653084 182391688 342742538 533030963 690424628 330836730 81414219 821456579 879533458 90644527 88916817 995525075 993033023 181100188 330569889 884859745 720177069 300492986 100625969 872057602 622874745 288310745 417490574 556371266 566187762 460009113 458385525 780026059 511380751 278029685 30022975 487478843 515084530 375105802 270564799 803331960 520779965 355152121 266276231 717975444 823050113 40523042 30013767 751959964 794740925 49466818 306220120 926969348 505260817 64807895 160334837 797206202 879677769 209986705 402786123 705419475 721087895 128735804 488890304 899843355 506597060 373100095 307231204 790533057 873697775 395113663 481792912 855342157 822046593 297220153 321736094 729472920 562549707 149927182 473384221 557764808 921121570 305601487 204616695 970741990 969249694 1000562 2234871 930991294 946817717 318129894 55434053 588324964 685051585 382310647 160201196 522515351 534924294 299201042 354992602 884865827 738501040 443928807 62253287 679122327 707791638 435222081 147605567 776542666 775432466 247169154 83193444 813520416 737841954 17009633 17464108 869191439 536277502 66883802 63908121 790166546 743461103 416671826 227081562 714312526 760955853 76653641 334838782 740563455 636526375 223127010 424403597 986405399 604095787 187011704 57814324 586991935 616029805 57809370 274119919 807741346 612606020 238768893 438412524 639719723 803619737 446999478 191464570 516676382 942383093 271497423 12615582 526578364 986067449 104756561 248132082 520441525 521360744 449606285 475928811 816054709 743711311 336793187 31894676 492700437 876925792 5946044 487901021 773959483 684549371 154000656 147189956 563557284 943653214 77915865 155926358 973581525 737924617 143424335 312369096 518475494 668391931 41778198 351935542 507871828 839981850 207055343 328280201 588205291 648370735 190529790 390561361 871330502 533727274 303173654 346641407 650700058 863615387 383297015 411777535 742680251 624728618 205996575 35878010 596336004 687303126 423156671 251481659 876255328 755200015 291141642 317255838 557016826 558118281 412974709 367065333 775229753 771455926 270522485 307902195 634587770 833833638 237689421 306875799 896155727 700385833 248634094 70765792 568550881 919471431 341841212 215788675 547484911 599125931 106669828 148683331 637214521 837608542 200681127 311684236 817257537 833320369 51463525 262708050 549314310 786269062 405105917 317707862 632511621 535041212 17356339 100015598 638165709 649037607 73948456 116680410 848997395 616342844 97714851 78116229 920388418 952668354 479963879 241676190 608892572 865621310 171615077 430363294 616214029 887520913 228810213 467148584 635615820 707617230 304165606 223627900 686374482 686669231 58855303 88083513 915158125 992336134 13864777 101193668 734442533 834161883 303877504 392270807 670972766 971664069 314391903 174718336 994825386 957060722 289057734 207174835 753552657 582851463 274986556 162102660 726884439 685800596 298893430 208013254 748359784 863526687 394523168 181712612 615336771 697681048 404858145 447007926 868766819 667767015 177133038 265834351 746350291 760258167 196260287 71148359 612926055 913224280 405000399 192140896 938926315 704243439 250283486 137833222 896928279 734003177 270202507 431633499 512859448 925620710 142497827 226714840 809072091 813770826 365985115 477161679 535971196 780343419 83360005 164210484 959517606 937285523 77029054 411026816 677505808 765546050 380128392 340605574 619670143 715229875 280697209 275319402 913989445 558735415 186674291 310400377 752137622 548991102 74151303 386927681 957943048 815022575 130288706 157545548 940712745 541813608 11082005 457449323 635521479 949275186 238353524 439217897 742112739 849692326 142332361 268290340 889065025 794917804 161691235 420933171 581545010 566907880 156095810 239780831 704593033 561559353 126980142 36500020 490497692 783129627 45604176 451582133 766944127 865272288 363987691 113717163 992752924 953516788 110291467 363556792 734122472 727344445 264434135 153783096 571599059 853199131 279975750 292969604 807784085 606421082 400809658 204700976 878774668 894501329 231794891 367079008 902052702 521269700 97352539 382053243 812856942 890183051 141708079 407225660 881696529 547512068 364639518 417993304 882515014 910889019 482027416 30872123 965304317 795064448 270497289 266183378 837984232 700949525 180695485 316393578 566162016 680097254 295680015 408675042 895495227 529246333 82286926 325447002 513521011 603038403 51631826 178719712 694998128 605632315 472104820 207116645 727755805 681456626 299102935 339306693 851724712 879829205 460423852 370779894 662307440 550983043 337204029 458977882 888078824 959299275 423262524 34359469 908563240 743554765 221589192 300431048 853463437 951321137 29965380 451900321 652413341 893756316 474669840 488562559 740084374 636982225 307261407 53186672 627914671 715165060 309289770 177317265 790087611 875520444 224709180 173455703 998979848 694389200 401839862 83906712 655093432 978209193 370078069 197832011 743124444 880027390 200116784 120229826 884009226 979783581 92573064 227018592 904033237 617647056 278345970 299597876 716249456 538994318 122856535 51397204 505466643 698972625 461395348 208284145 503253287 937806022 78042655 365818951 611452787 936120663 474938237 246307796 660423408 982068686 185228466 129828450 737127580 764574309 82466834 295006178 901064574 557464971 46342422 393301328 664927703 762413307 239431053 250027244 551727815 955577481 319773445 16012893 630446996 590151455 461112579 300752473 737045907 789153756 367894980 254792706 865787060 629080467 443131179 492538775 641377387 924182122 201410306 121807069 907916553 609497090 35901386 318338082 788059813 596896903 255103696 475550638 590242196 991549704 413579613 254818111 520357077 602272935 245554602 227025998 569803092 796211532 334525397 161600591 958652562 836899719 83821422 130489263 700895462 526386824 346353987 232453781 627587279 883116365 26873224 283609771 590952165 932071984 23060520 318959163 926806947 856753192 335000626 458724064 801286499 529406760 127919378 252339853 537458741 827940060 92881171 323338140 524697804 793650848 330710853 93868826 551193761 665083176 69611684 373001735 846418814 845213276 50285094 65202069 718314369 916399173 84243359 307274516 668417759 667506845 323727055 45519048 729580854 664429867 158984937 469181915 955959367 757852766 75297473 154497607 490750074 536066229 245779921 282681077 958074733 659731112 359385386 238259871 558170191 653750915 330797260 370550822 730231201 563068741 449625159 91285609 645809632 665593581 269601561 200170537 551614697 748077144 46627136 411070895 516946069 537258651 265397592 364514092 730861214 795865504 267668355 49613430 790502574 868501272 267952252 61076383 896315582 872081485 72366356 453325197 911527452 520314874 53174124 71224777 725419671 675538806 318856533 21641352 958647765 959687118 137646401 322774814 904709539 641020857 274598844 200212767 574257604 826991865 175972821 493358016 596088401 958595999 53291180 216774609 511262451 615746327 422931280 382066283 964521149 843304755 254734143 446938550 518570495 727177176 201915097 118685648 557028244 505714209 240487481 216897370 618623077 602353960 347366545 456865407 895573879 914256334 378685581 97783672 766167424 730196920 453494260 469629511 939218559 832067008 400800208 503763995 695375801 748998870 149654709 134494261 711104030 949278868 206194113 468677418 720874844 667963214 481595309 117207321 713089195 585314343 110694854 71484120 581056472 546467266 426475163 175378869 496669493 584562502 196162676 356726173 980676522 749814066 293348090 285923185 610718337 720871741 291736061 17945614 818014097 803044731 159108918 228634006 852282080 714581981 55453290 43383259 748768134 610357783 206318434 368491831 712640735 729092600 380458741 213887808 611954249 916737968 349911395 398106574 553316789 906393056 132469107 381010485 628140521 590578938 317810387 87855341 538701607 839946945 449147475 337988026 604102582 619212190 264149578 121015109 837270660 703587978 13911164 51657140 885717985 779627066 59110951 392055203 932150134 613173853 453944306 210111850 974051114 616735919 63991749 146645345 701791505 870971363 80639658 386909959 984838785 812907433 372101129 199267964 937030480 738569309 160189499 305980230 691572254 618232568 367628184 378977585 981540276 826977567 293913728 356086063 568783375 950400322 151252725 168694536 681455309 942894313 450597474 181285985 526236834 840007484 187627944 447483641 640941479 717303506 347295113 264458606 862049590 625858829 44261149 67691644 650309391 612457658 343673775 367467285 665774376 981056354 51355067 62072141 829706904 705914579 239887611 223392293 773560086 662884842 176830445 108030119 901759055 907790727 242948093 102676910 875096170 887292772 436283318 261489827 701229726 786101618 19493436 320192593 789311662 801696856 181166468 176185385 632551844 625881313 271171240 308886690 890003930 544522628 151798627 81472286 804285971 725800814 446663333 359330626 549537895 636498617 150041628 198402084 655347698 885810889 461668148 97807671 552923717 718521801 31255533 125919534 938075546 609133031 226610578 401034562 526527330 966490318 233126414 204479272 865871179 833438042 289924443 33094538 688620172 799017648 208807105 478928630 987308488 619461965 169002354 141931762 838588995 796868394 154213230 303863363 534407242 877995950 438021743 329221887 720084297 568560844 246741817 205203192 718633452 682032554 325838187 477781686 908536769 531690446 34036703 398713362 813690173 833849803 228121825 447484436 543158151 653971718 93330991 155288100 574111699 745316514 86233789 97443417 622585665 981542530 339140042 133031506 802381625 802679400 143944794 419451898 888016693 605192053 332251554 288219740 861337436 586031892 34592147 487487188 712171487 628502128 428908519 503250281 848385974 856178479 258508767 128618662 587816243 927772036 110358173 54633399 638538381 814383390 143919961 106833910 833201571 814837916 203518570 174072844 717763969 632294897 145266925 437372186 650850006 615174453 302705054 486178864 523176547 775462721 214547696 498174804 978435004 704183315 313876267 205974315 781048467 847433726 130595899 444168472 582551924 919747762 359674383 147280309 805849470 912559048 409911589 471939355 979693849 560326491 323821423 309192544 497225208 552428022 12397153 440649279 823953415 667958306 29640018 466145246 590708121 547048354 311263952 333474456 974414602 625865084 15863309 130198392 502676553 626698093 129933878 115496348 599521562 655587871 274021655 75136700 875855869 524836022 5570998 469519339 995917467 538333203 125806553 415822649 606721446 902208287 276450212 245595067 934741086 567991060 126063162 131938812 752973727 621129518 157738573 180107270 804333577 743882967 157080587 97609141 514815071 559933768 443100487 209785277 545776779 984576354 474404159 101246988 933151372 934849408 319764904 473692412 914663347 759183044 413898326 191126087 898745238 676110912 417715289 204958778 730630235 641788772 346972901 175866171 726406389 602730592 328774675 161147291 729424516 684964183 143842065 73759175 584806906 908719501 243656538 328758538 860988835 891068795 187891169 496345001 769581155 942587263 400854277 18434706 914186857 579558674 4418800 119757017 547718956 689692479 74036738 148288519 653011061 533992200 155863649 40691366 932856783 831966419 30126340 3141823 691143587 900656374 148304442 392763777 954178202 563882883 255519048 459863031 794041601 946021847 282913583 239171767 619965259 963927984 140210177 90688110 946538487 819191495 1874316 468159196 895728609 913656475 476097122 73030010 990000927 830177891 194754516 4863565 953199789 757329337 225295508 291813736 580256940 586554839 395598460 488557911 746230804 673252156 474411364 248107409 876390501 663721737 272171218 78725374 614512526 595093955 111669883 156186468 847902258 652228537 198551730 204011003 655874283 788701149 155944365 372450679 746540784 972343259 155012531 230946679 512323875 796711103 435283051 168126352 652339254 526060556 441920398 301199888 866014821 669603100 278281473 425634871 766002129 964676580 323753440 424866957 764587819 542087311 377752166 110902013 967916289 723395156 358211326 130165891 713868947 742020041 79339189 283732512 684869008 812994289 384857687 373611412 872935114 799794849 258351602 415035739 700413888 716305892 482103582 241980477 916389880 807733673 111821077 124549733 593194257 871930806 194784169 3228178 659718116 558884931 2521498 227327114 605599525 696393391 438798540 374481863 810222452 773770294 439194393 235979339 784450710 766749824 377409115 287178438 733096163 885734700 31531845 448544321 935054055 556844222 229232020 325722677 698836848 778153162 245031879 332183203 799817383 859716866 298210921 71084299 831174215 649103539 110296167 173625004 529950482 804966488 151470628 265785084 836481371 918180039 321901853 202773628 487980257 608895418 313342409 62801805 590361633 812044160 100385769 129180529 664318288 924141188 120365834 321542422 761433733 676343990 283235730 14624567 700373155 873083141 62105048 396177141 786197221 781597150 250488695 92833262 857560722 760200521 269837804 190656565 952451268 549690723 280645286 135457398 559837935 724078372 362651825 361406035 730262683 948493304 46557538 1081826 997455410 742260796 367893734 277710447 746016269 771826935 65215334 332806979 865677458 914586069 361602883 440793895 544088012 818635872 69296600 380144450 576679153 651631882 93047928 501112882 633409892 660514897 473788529 403911862 497085456 630613734 447263265 329306407 615680252 813712103 235181547 480677687 720188416 820334024 407856419 44608361 979115764 947002478 252980068 347678338 607622433 526541226 477217794 61751952 898842325 683711877 234571018 501202789 881366602 804654191 430825798 200232567 603518801 652205950 66742301 383294173 674233185 576514465 368964275 196185653 716017714 895097352 144534083 362218733 596843099 638707042 140420740 162532346 878846623 975585029 184858725 267081177 940103079 804714278 430666569 33548385 798447343 710527853 77403180 392060410 635149317 687725293 424593046 77752526 678502930 575740971 156022304 464121494 933036767 767316191 110168038 287339346 966053680 836336850 364188675 58162951 552474157 912929059 239813361 378048868 938528423 718547657 465517891 383257506 495966038 976346021 138511479 121744677 540424429 666975291 149339521 475495148 887817214 547296319 382534208 261559396 749773150 956395323 277202775 328820633 893729682 633847111 366542720 226452291 645925603 978191918 179763147 396451507 854477464 816224646 458185558 480439851 801734788 943524937 261983601 200368010 630802904 577832421 139606912 262025116 993432997 794143340 390352723 105906242 795462276 744828051 123038900 118588928 830546781 593263559 332189814 491357388 918229046 627425322 347995069 40445476 655582148 987398059 300429199 240642025 800050289 550801215 294779465 209592959 591657421 606904254 123192522 396114864 582241966 608598615 34553162 252282106 734508592 675979120 416685708 448886241 897680213 991894905 146400367 98532942 761866948 567937763 225559301 300405648 717871662 631947337 284469409 387067961 915242319 614947328 165980186 181690806 952573210 927851750 346199214 262682648 592977673 546248763 224702010 396159428 867022568 743317327 38981050 368206778 908979164 622704346 22994274 60053336 941160157 917558713 167791827 299145875 777925926 505226663 472268043 62493953 811431037 718128873 208094150 28872395 560744330 810791176 184667708 29660588 716395640 844823946 302986007 467595024 872428525 685570029 99372729 118511754 635237441 567687289 420656542 24266204 897226192 606867368 95081645 465540297 623316085 848188592 37154812 77130270 875544485 997812835 31194916 151966666 831494078 690489294 346223500 435500237 626355580 661294817 172420760 278634651 803436117 966079684 228521806 82606687 520769402 744240351 373112674 463201673 896567111 643881782 149881809 490017786 977294945 546907207 338512772 472537467 737995549 965905260 218121058 46937202 836538834 546175312 340879396 87909555 979579191 742354416 267982683 503467069 598144438 822688733 110351981 318807114 928045613 968137321 390368466 432258432 780457035 802080464 180575606 62071217 519574001 509796905 320081740 328371891 997890632 579279840 471436792 208239393 959041628 660479622 104902587 110678354 554241397 934421270 446808168 415241574 820416220 567846761 455760286 183479872 742870509 571994392 351084565 39016471 502925144 729492321 471636275 287490108 974430575 822025153 29341712 9344774 565036462 868092328 16080358 279602675 787697107 603271406 143583723 286327398 660662086 892740942 407500282 455701114 760123781 972452471 88687806 24630808 709711970 848559840 97662070 468760544 979952398 554710193 138304724 162739699 790636268 918093802 108876874 70505300 981173387 737060935 236290291 473028352 994352689 851378140 324905564 252031501 756818903 996424165 144630005 341923564 768889910 928891076 329475313 355395000 996204688 555170202 79666969 296946689 584937596 544264617 367918899 454544926 878092488 888710193 269061824 480930114 981884030 739926407 274780322 277642765 831956945 809995825 421059840 41008146 666239799 625952502 474248228 3757445 909411254 868200699 56468319 374689124 826408356 889906451 18818321 462187957 652166628 817586975 271378771 321839996 809058106 622191183 318045419 62674004 783871567 728056234 278366070 327072107 497769145 596855138 116863743 34322065 648348171 699728118 46489239 74408830 963818735 940391365 136427125 9424133 933581600 852770098 115735090 335781904 761120283 822516082 356633063 231494765 742162072 946461973 206788510 272378177 738470957 685507499 343144873 334765391 967707285 759826115 41900629 77806248 498193089 671537526 98693511 213295481 581652873 700363948 268288145 260157158 904520957 886337273 43459068 405985026 877285936 812358225 334878641 60198236 817876267 650399032 432220507 89979207 691438923 907743742 114378701 109041295 777849628 665113015 177646798 90513012 841090402 609806521 107403265 276754168 611635618 512810032 197366138 51095341 747074659 886617804 324618292 277802355 909602370 860290790 463852675 364837391 658547631 783582962 313872818 173205607 991423144 924127381 122946715 305356419 570189974 845771606 202982595 289809099 897356262 777493876 145571984 433238374 750888245 833892043 432556556 816140 940097107 834880359 117995045 156471753 926107436 895429850 240224025 374120996 782555030 813444570 194055659 55744704 626429616 606067397 23919447 368820813 874278516 820773766 204065133 272908453 590157299 688850903 53627539 354804120 565988700 890003988 140256636 312134081 889332866 907101339 54547700 341246297 868164492 789446814 209239380 111420493 784680187 907305745 227991710 193703060 922340159 536474091 279279958 314615096 822713416 618661858 39971741 412959018 568731854 720494932 438479880 423409306 782181798 748046470 194742410 190321305 713635231 713656665 433771149 394394480 743209050 672676607 74077985 193331599 806026570 595554786 453843741 203929047 926769088 963799468 443026631 103007963 674851027 821686634 307974578 228266661 816978928 639125651 299108082 363522709 698712750 860879976 50555626 135388 600770888 691732927 401629068 288078842 715619213 718538357 307578230 280519105 529742521 844350411 276873866 467733599 958472821 825033565 343680890 321931478 691810625 866681192 287815944 497886134 627096414 696967842 303212977 454009191 871539696 521289084 420338227 324571487 866679999 781031387 125366395 175342001 980678060 682734077 415313836 166749810 856848535 578971200 360184212 56456301 766361273 683939236 214502784 36058814 925877494 645446467 315733731 159107065 631110965 853689347 169448288 378280477 614424453 516923859 349832256 277138447 496664033 775849923 389856510 239624498 627309957 805241810 71161084 204468270 906228619 701223674 195717801 75309222 516036835 638586446 353443394 169586508 568539608 573096622 131062261 100595023 867186318 518775483 201047359 271018018 783766949 985240363 166718740 5179980 502872075 764875308 128473591 500297254 988194963 816835535 298453732 112640510 982744017 694816636 261809642 475280561 632588630 956931139 476428385 100978575 772118519 816969842 26679280 47099046 693432129 958349884 2372091 206585484 764485945 512608337 76946711 243348735 925491008 580204357 66698460 469716784 926769176 808113407 346584184 338805743 843218404 967358921 245331498 24981654 896511141 688728927 319334991 5224075 925957325 725841518 322324169 200832063 833114700 833077422 406850621 258030416 509821394 543473756 183006311 337817822 552248623 692863367 385537128 57160657 944075117 584955130 269708302 75162374 522245968 659728877 326673771 468217480 625611790 579145567 430618894 108395914 577716732 759671513 58892449 399962671 701093190 793179653 299226762 82850763 573288099 946006000 20671243 210607053 546912034 721720763 200273393 183214028 792662820 943346070 476796383 89681393 707691728 904231057 173357889 17738366 687963692 828036882 366497321 30612438 685226749 682675227 471718796 281446978 670825413 659491085 430798095 502498535 704902512 677077980 318851177 156788405 861622939 650970598 47513625 407128935 852911423 716925128 403322781 115272059 933530649 864266499 113925847 160376022 531524863 937870087 26417402 156450458 792294081 637405617 201461065 72360500 914866632 926339597 484135053 400660271 861531995 943431656 12797421 275263004 755636827 631014575 437200140 381778081 524660906 608260036 326724885 465230553 919089740 638476483 121482994 256157135 994277585 745272455 400328304 168000114 541784302 630123691 28969309 377371296 842182378 571762105 81806500 397055274 886325574 625779236 56979606 106808209 511968815 712561316 7980229 155714086 541132722 766589482 401092671 165493133 760646222 804926936 215482008 391303433 567585850 623823926 190344696 200412340 959590480 659545928 389026271 11133127 915894105 710912938 246018567 199738811 633165202 628459454 59910215 117057750 588163374 986541253 451986084 501915131 756189081 824820178 152095851 391522023 692479384 921540687 232060236 299731630 808904658 750128484 450974686 127452278 609122467 790349479 84306769 309806571 897524356 936516812 203214898 81469893 754276224 958823104 233700321 35124208 940416492 935228218 80202329 471997218 669776779 895337664 459275617 230152193 537546294 842200823 437213288 305458238 924268848 896754622 68307643 174771394 875420504 616827871 123222147 118820839 527517300 648164939 172093964 56417188 944362073 774493360 258008153 114706821 547930117 844425807 465422310 237903671 887836148 713065537 321322666 304573568 515924591 928391963 372220022 321719264 764536457 532832309 403731639 287630658 516691953 542501820 384169683 263296146 894353225 741319218 242465566 91879310 659598162 668506102 373407811 401591524 709111035 550247371 379998579 294597783 581280093 800272011 88396565 405202450 911144211 849920555 330067435 277408889 591418487 673667566 363081782 19866839 793929788 507246524 374782454 455144144 856136070 850515103 208787394 237170422 579937283 643203198 180466314 266597546 771552396 672574132 304470403 186309614 706004596 798575454 71708746 448115570 820267894 754213575 2516365 259673328 538183143 575766737 97046269 154956389 588669462 605341540 120881936 413116717 614625554 538476880 234179153 302688826 503014581 968210597 385768746 2464584 806552362 636061537 457156381 415456823 550034488 776990870 229573480 74125715 516023203 874102017 39397006 235511318 595410370 754083941 362166113 260976182 590478089 698843051 249601260 352062868 531828224 658019132 149507475 1985135 623602474 691544382 397346750 141907497 663129113 585854480 400595435 70133299 579084145 542316899 245034220 374329981 940566689 592652415 111890493 362916408 998723746 804234687 229714277 408880603 615208622 772995195 476135284 471308085 973561936 972041490 380744963 96882773 585901310 867884432 183118747 278368948 813178592 694583944 291449337 262404891 867556119 746828826 346745316 273184497 956641111 525961089 117772877 141970713 689848390 667687640 457430917 396278577 495102416 607316760 295331198 395763696 993784106 600574666 154569880 489837372 607540285 815894179 334547103 128276236 549226497 593302801 432129028 190776635 843068969 654332723 377402191 151405793 652290176 707720186 65062525 200093574 644671818 563362711 117225817 283132455 572465587 556825079 86420887 409714893 819563486 971954470 440598316 132036553 785202172 890513774 321390345 426837274 812468053 823602146 395696811 233594269 829298075 591647858 486161126 80127706 672781411 556906613 415320325 365224110 616147563 684278158 258971043 229001302 809768042 722684586 80944562 445523254 865805987 748350703 24972466 337013394 833538862 531988500 116816637 132402867 718313711 811871424 314408689 48379010 740090580 910839989 282571133 366718588 928102487 887115358 242609742 378226731 570858281 907258305 324959710 149934203 771590690 943366672 451447384 143400261 773387686 822664297 180267885 294624300 605598616 978161039 15381417 137550649 518379232 651145935 234728913 186844417 883946052 618439268 451308464 429313057 875053673 946182436 6865335 31899811 891988867 850628922 188156762 408699636 892548182 842404042 77084698 251955530 943022315 652684765 278016749 496558496 867506842 987751148 252482067 461707071 957877526 927973404 266859886 487812731 942265979 776451562 99762074 404868015 829128592 637330472 152773275 49315597 711487099 732766694 242407927 86955491 815341717 548742289 245858720 391689786 570528381 907017531 245224490 328940116 930209191 816548077 237377453 391122229 848186316 860940996 14155051 103949303 653839175 597898738 185428155 249178349 549105254 920225207 126264181 61913103 781705184 866472246 150434112 178882788 912711905 735960491 301628638 61627138 718708536 723569879 409943490 10442354 614364678 940676028 481878614 302746759 642062567 790947146 326742695 101588476 718353427 557019264 426892759 275616305 876144728 524270562 399651967 278277517 535014541 973503197 60033353 287783012 573258341 750321745 444484537 373363346 947289826 891697731 142324834 174059718 513084375 522253128 437128813 163259095 833053614 637795450 426682537 354820337 768178539 694674851 260475077 24577999 779928117 886947728 378245296 253475702 918019432 700736034 230674027 295058722 702176916 769693544 111170766 500637440 559013984 574540368 370334870 483204556 572274292 903698489 360917691 58529833 979235072 769920438 164981316 351707928 507580550 509388889 289208848 462097410 835319501 567181353 203973615 407232909 506492665 892464437 72617594 190739133 783121609 904294091 266549408 419822520 774069064 612167725 44448595 101944279 846100820 976956358 92310508 224655750 864691420 974959476 445185092 395133595 884917563 868779456 217590943 428992154 967609260 904412252 481477942 418742549 535967855 532344055 360671123 26140326 589723576 806760475 2363402 307855024 862112598 784578029 26352860 163858850 604140848 683940903 410341634 181186405 994457280 573425428 276285707 19451107 737447782 860985614 66367458 442705285 900641925 702152232 268991526 129511289 907746842 877892797 466607464 471656423 879095281 694659485 174359808 368945245 686484546 745693613 481886306 187717485 886499141 853169445 234733524 314848502 639620410 759145025 296417774 476818501 752020497 648531817 326365760 198044475 715001818 601423408 123115360 76798928 811017259 750649097 305146388 402989406 588639477 689971842 460717049 156891836 515307950 980460203 374888872 243868204 871296453 870361866 115717884 408948932 511376438 537712149 141865149 142806462 588858086 933478516 114092794 62121433 702054631 855458403 446516591 201348041 736963693 780154121 452792067 278901167 659849700 974965993 140687982 151207864 674605621 601975841 276987857 224737709 643336191 900394693 321427580 70518033 486576479 693468206 112768109 8574033 791902605 679062387 9908149 362148807 709591623 753381604 161888494 436757316 805919846 976866567 67837587 409682407 508823671 686184732 185938078 195953419 948039628 969182492 289293063 420584847 840852055 978586850 386064097 463559293 712934729 508437190 246327344 454976228 978688470 863294141 364692514 13565228 607355315 549024006 176769181 252412612 552322140 598609669 170097164 261353887 850036915 917134029 443923155 430484719 667514566 715063099 23754395 402219952 977614389 777976630 388233607 126456070 758451446 840613407 196838853 416757749 974496386 527432515 440958515 281448045 539744406 640006291 232056513 164598021 877231961 659230425 168811688 424273274 546858573 786220062 183135027 467142414 835401194 753888891 293268836 219535666 949231755 591455288 347051451 387470796 946562105 541522945 171053746 135632357 851093568 999734704 285626226 496856802 716152385 893535404 168585289 288857521 572091340 608958736 137037199 238707862 863811076 681139145 480800405 187112728 729811357 832305112 220140112 300792519 693105056 697648378 434743829 113116012 524483799 531113240 132784214 187280796 960906777 537054691 438708364 120454398 908388471 812889000 195383368 313915825 745810617 931983187 388346708 423402698 807048652 990102084 462278795 199475099 626659111 764171850 386165078 141610548 890532839 656884326 216540650 186699484 547155963 848587857 26152015 145092125 682850899 856708710 81897895 94684786 620776262 977716430 160883646 349221422 857592486 850742964 248275348 303479344 973986519 616453703 254827805 132671918 508401714 518945080 172180654 220046972 554423819 778230816 447575489 92587948 922695457 848409158 304088489 456531715 768979958 948187213 119707780 299548656 564507971 783911365 44467487 27798528 529746229 677847389 344955262 214131210 916176421 748291679 68990726 195269716 779019658 942875631 414956787 338516778 985625458 932161311 302565495 39952856 506651922 633072734 43718647 434506417 540369930 551116871 59099401 303557125 526344948 951715501 91461304 62391902 915291274 941129576 170587020 256113427 597753373 711309961 62762106 151162283 583092967 648785580 323570397 129576060 957736451 781065281 57171962 314378645 809930422 771991801 58388870 237923938 958684861 598186982 411636192 232708602 614540551 774929850 427718962 324029952 564301398 907102353 15141772 20386308 853164975 643379240 216468919 368055067 954097616 613647055 227167777 377008525 616117283 619858063 69023610 397431156 548449621 662271375 216154445 123567906 978913163 621612292 474869193 351296788 951233339 556592919 54059137 28951717 713746911 681851967 355255293 84445440 585329176 763806361 43140733 170695526 961873551 517150898 285038324 414157136 833305674 872788352 257313416 293005505 999464150 586728635 277625830 129877330 680281929 623481830 453112720 173844836 764925437 780373656 17924673 280580080 773772185 777487504 306677419 216476878 873548414 621517477 392057342 10682722 515206480 763478940 286458872 203278773 632515859 506195267 178423751 88393677 667212324 973727685 432782403 272352672 623533152 667317628 165537784 43702937 962339109 782147263 329342278 43266493 961568418 788051569 475679757 42356545 983230478 906012170 173287496 128151274 500578706 598431501 223126225 426246851 613870740 828860804 478181720 203311660 693270640 686020247 322066194 40714706 931899359 542746855 59149807 55111219 719418303 997479416 264969335 333508456 564365969 745361471 308448417 37360666 584869460 756664605 15855574 480591606 525765512 885033847 121040121 235211738 740503061 926873011 10906371 147308381 662651251 978532778 96127599 239843799 696354208 613008380 454570170 426050984 790048252 648946800 97526217 484050060 986921786 927627563 99670377 455403897 953726008 637730982 465067812 67773873 538717963 638835565 52590132 82102972 728655049 759575097 403904310 70402366 886161332 590591411 421815799 20961671 912803634 911530874 424735934 222259819 567186272 937144032 342924166 269671967 613203845 573173587 407743037 484592762 736219200 852161674 214821381 21951619 818575259 839326214 329112965 172811466 947991995 595613893 80279959 95586786 924054992 923180498 467555500 458097732 565080553 842770177 389694819 60910274 894291206 943589283 417192465 91830127 748123666 550243707 34264947 386962605 801003005 683368465 222645133 187313906 792467409 830251548 333185141 416550283 614600476 786706707 398224396 95493663 803852189 704770724 106499810 170189628 961130593 935034250 174882238 364170450 899304958 983402268 128723958 237016090 756294654 616962283 311219581 21147403 497734460 744199747 376503482 449670908 895399365 609971180 413771012 500224231 801015169 622943506 310321778 6663470 609162604 556315676 276880100 420442220 737900312 896958543 442957831 263850740 849160531 668552577 5874258 236655421 731578892 646634610 330747387 108646611 922913671 904562550 154821943 469192881 754222239 816057771 297149495 272679568 993921153 763888797 76061901 102538140 681010080 696381662 463786907 274714125 940650538 609094275 325957060 157085932 768998110 743881208 427430611 236825158 854199959 744404878 191139676 76304829 849906064 784664444 121657682 290487025 720290017 535217124 99197863 175277403 893818017 595527794 56129620 181764065 842810332 704268618 210399134 468363712 921539032 739494836 342095983 456152410 730436076 525782434 129005616 80879324 710410537 645844578 173480533 358435337 631467211 531131490 344591468 304346734 537750152 908502510 409176566 287641498 875952304 812177765 337984222 11037884 875874297 662710630 88475043 438877351 912076468 508222468 333706289 230949458 836149930 827026577 290875832 263061516 776848782 598814053 156883833 35143656 763724362 903994185 61728194 13394989 899091194 610254522 318700560 29788989 538056541 717074865 221874729 489575775 924963110 771081209 83344344 218450142 556304488 716451704 175083161 112177075 689922856 991622891 384449408 115947985 820990697 527851529 360862807 279478249 537374858 992188195 371259690 343715736 600197374 647189836 160810758 88998817 775011944 761585492 133920069 448221128 543517800 654350351 4342729 373524589 984696883 649679423 264900128 483284427 965675115 815494852 159396520 5898957 945656783 912156159 295895650 141380879 699287572 773932376 306850836 422009219 694484845 776770192 479262518 116995847 850354201 682389045 420168638 60863600 670169759 717331292 379974155 209272071 681065235 604642114 367811043 162061009 746559625 984127666 209501331 328326282 684087462 877528575 172172734 1673521 762156374 851450910 168770566 335224479 492487649 893695265 234580543 505069420 768961116 990802449