5000 476941853 841690245 458359835 703658885 214080591 352567628 165526832 458327442 607740057 620445345 368680413 604773862 505699152 544873399 8995984 801992330 959064949 960805708 456457510 901825598 720746373 909283045 366496871 742349110 553310060 646059957 666944034 997706971 405157659 566901137 423747435 712364677 221709823 453655022 527142768 741595960 186707690 961609600 461544315 950901639 151469421 655784985 272730035 597377465 160055580 695740637 98628477 598551257 140004789 521829371 290715651 873608121 455787424 631037783 85613349 588280567 589541414 841821404 751364546 865314641 542619392 675163290 105152811 383711955 700992894 820313865 525820533 900235511 59545309 775998695 66813225 293550958 655611970 803797779 477053264 843669649 766844151 890963256 76904241 295371935 307584813 701010464 627577630 940501830 140781617 487265618 796782668 852696039 275014746 409553488 110182410 397921480 70635597 607317779 451251505 932672490 406940384 977901588 303212368 732278443 237589139 512236001 100507778 538827001 282810637 746465591 295946673 462254993 37188253 421308982 579274603 929643790 344936043 648134672 221815890 828568418 541984629 705000204 150389805 884095060 776708880 904809698 167849355 727503250 247562245 804581891 445730132 871109536 207545360 644137953 420350731 859200659 421070785 925183398 667509124 788796973 38374380 191147687 249111359 702055050 156166756 801368289 448856683 909859933 611164304 990673364 272270643 325002675 116868011 180358912 285525129 740671790 402083546 478717516 122527816 798626332 731911000 801053017 294943990 428606822 183488590 461156676 804186666 912457362 358462519 489323940 416763156 953275217 608565794 742925440 236406246 602699079 34085969 177156949 295047800 357776483 381162196 422963319 11825974 951034797 163453498 900192400 74526592 617830937 182157033 329751835 337868832 854782623 278302817 698348309 713131239 898296848 221048 351633362 407427946 554492073 305011921 397929856 200494700 868135884 669625306 704647960 320514646 882939031 161307782 903599897 131073245 582376030 327418241 401826787 602845687 915310459 195690296 661128717 82211009 521952072 102915774 405613950 247354656 748097221 545091190 802012198 20930354 880323418 224882133 578515244 568586463 885473920 446501172 620443387 292472983 315511821 521301600 950909001 249238276 925374572 372613061 985917355 98605631 677697010 328362456 664092603 807472398 878345144 38059100 592828170 714576030 715620771 509029764 831242213 149687410 693927557 585847749 847499058 732878982 747260264 146037240 950369053 381056885 926941140 547959213 758342270 37793226 73414837 172186189 748657203 770621957 804284931 282692821 623320668 220623244 303361585 382577403 786689344 43010977 917831613 499876395 624975411 583369977 907929380 246030842 496797328 500121319 865456459 183187126 657254101 970127866 995252097 345727138 922854595 372015691 881561716 43780152 483036464 139722349 789229347 86541463 314750373 221797635 875678917 588317005 659468036 832055259 998254163 462802164 955383051 714492176 802704698 689921478 837386299 484566544 791810421 458475890 888100222 568813325 957204331 410423662 843399929 244830247 934417690 620873361 999279808 192875704 467276011 55796130 69247923 587775115 672913084 47848232 655227769 72643282 248467567 208744213 968116798 118380182 597184178 84743188 167145582 135100369 265279481 721712601 942903147 261015583 658131412 60489144 143128314 415488150 768164381 980601372 996487338 336952750 997768970 275459329 408817589 144866347 502251183 429710856 933467194 444274340 792651250 23171150 802201995 634809598 926206480 1955145 36389497 718918687 793791992 29807545 427038056 479457528 826470732 11916848 700593731 12704013 623117061 11680782 201572995 451475182 533503526 249266069 493941449 208773874 723380013 154733700 691137890 630682832 649704156 433680139 533700524 201497809 260861451 137544161 339168382 206784613 348737762 114452695 687910805 61707586 182811148 566861598 594506379 246557135 697299923 584369373 846778436 176566434 947159261 199870861 246029267 202957682 390988486 311927246 487255591 669344941 697531067 91817128 517073913 194525446 660272009 211111775 538435114 189240830 830720498 184782860 788324951 450229604 538498153 210060736 700383242 544181845 667460091 174576806 877527149 391438325 597599490 159156564 764430981 952328076 968532244 79298217 286137924 608098517 649472832 348869966 915272670 510083347 737657791 512750546 999284276 19776328 242682369 547915766 704591528 383042000 552965502 612126945 922499782 237747396 611332270 72665890 822657423 343443988 448183987 816346296 922620266 230874464 386640188 28930921 888784930 37538978 688854010 141932293 808062287 209105964 498381486 297072829 463797967 508526526 918077265 121863981 571032139 686124558 760912981 605934183 812733974 15607385 90434041 12795091 967603473 690031641 933862361 332810843 441388253 598851496 850016063 76189480 192311035 229683911 399073734 782746257 788857371 291376331 390717084 106306303 604881120 116782357 280649861 485724088 835051282 72565010 666172412 185399934 915147288 350123460 593856581 106557737 175531366 830916149 850860395 403957014 418101889 529416458 800395222 23877149 191539133 415667864 539812774 798164705 987521695 576459605 577394146 234359783 567943227 202573131 412130476 197357820 414411621 122957865 953715377 598843840 963450505 92767652 361421759 436490818 920071630 631423693 875247468 52114573 631883667 81718104 837217344 763307495 992324469 132749148 246443516 163358706 315232999 353542960 469597177 95376648 248805743 963671535 985963689 550343724 587737516 271098970 968146991 379902804 501836456 812594963 886775784 146907535 995831369 463877969 976195568 3202423 261276191 33956753 784575173 288644926 723099873 23204410 462822328 724207423 827643008 411246632 871200880 3849284 124326803 461071091 484762096 78293243 786710185 452784518 825961014 422299005 671793061 424076495 899192374 831247119 901630827 253970444 415907441 720172396 763401790 10833773 22966188 100054214 867638757 422970205 868083895 451107233 510082032 50360622 183698756 424051010 920861760 237631811 948674609 581948597 938504953 677070303 776489551 444960017 798677922 91434679 284208095 484921049 586563574 387700742 424329085 301940606 669784473 471954498 952024033 70102469 699035080 187275174 439967539 2537156 753261508 319722165 628050182 118691734 203839284 662848724 764345825 436791433 882886629 20297859 227727904 442909673 621068957 365402941 411566429 658481889 947120130 28105035 470435565 846887699 933062123 190807003 723809038 36361927 474630389 570275632 775786941 297373735 921420600 40518614 921326048 228194886 291162782 614780110 779393799 37803642 751769829 611950767 822384237 197300603 599997714 238382528 607149614 530917009 722533777 334856408 588077455 314545071 395886070 615687851 951598779 295443181 888261053 387735458 763267070 379143247 400271233 134297378 887941329 807202485 825328639 498365413 636294589 865043520 988067732 920123310 953422452 188735289 603691411 137825331 743826595 236442857 482845451 69164903 554339018 534328084 942698330 344428133 616631456 6523754 497585598 570515055 816663315 280699858 690211618 420158523 939889200 185617702 844420422 173018192 656366538 439654201 770332304 365891183 949443049 225004264 582623654 144763094 263996199 112073541 241574048 397918186 868131097 259809657 270223233 563466225 811924050 262687364 334380994 181796023 539339638 209138945 610797029 729104036 729612591 744231736 802309369 120614202 547812388 704358687 842588922 157363046 702772283 103931812 538987517 299510092 874511546 526225193 763163660 246224098 783768366 253149005 714668455 77867078 951698603 720322611 737409212 39413824 721953908 624078492 680254426 740079020 961441261 112967259 114862538 639701354 733595079 64142550 484522446 132171208 288330011 257557659 492871019 385736437 798070942 698526574 782587901 504197888 516042383 208895032 900415848 132774874 955614608 199801987 304755228 436549867 658163855 2555049 191227051 107499785 754734427 620356289 625238079 381661363 806803105 311432302 720638485 28904388 765931074 297179321 591011914 220953901 848175036 480973366 719596164 33496308 409766429 108116733 663609381 161100466 491563960 132186454 547520451 58111723 597546241 358572818 776407149 353916855 506840005 468825741 501772027 720258966 848981610 850651 923856316 206991379 379381913 76671878 340807400 91044917 936295025 383401339 928634159 246803665 780604246 1821335 497478056 123240096 664468431 272530673 699527794 412478270 507376357 96954480 262729389 316823785 692779819 579304420 702276763 668247351 992676401 487614434 550252823 347517932 462341732 111357156 265747305 467225500 491779100 139253041 604779636 234218230 934189850 499325959 990403990 539775120 941585134 293538329 797326269 158655321 982779621 393967849 741816217 73133041 918792062 710605704 738372486 464962970 740639381 137930165 453636151 200163905 480396214 219481037 317767161 759138675 850354167 196703712 421033399 272673039 508932211 162436357 827483302 855853939 992817037 192968883 430500735 481900393 681652242 247215015 713527145 342155457 466335073 532268450 840331072 68896525 274252250 208261550 621967173 238556471 495453594 411590525 522025419 500856195 835361905 868608689 906891063 132932413 856181629 370461742 491984446 281719317 622265522 26064592 316967275 98042754 459128289 210290689 371305599 236559949 851094427 581867852 651122991 133186948 280108045 9957997 571360778 511032332 934467394 28299714 231387489 584372577 679137111 492051215 926037191 52972466 62710638 167947316 728105113 113092706 585758600 76172343 446603656 232659446 491867491 438115561 502777550 560179624 992498300 42470265 513049622 26043353 217889708 95665640 570374097 571301306 605888167 69322544 387081326 385448255 787684936 498704867 807661325 220126310 250269606 61653292 379006646 11160503 867777666 154987583 794027836 282811935 504693893 457997839 516225550 707715005 867422810 356611271 402414800 51205467 309736442 252016751 988060619 94159668 161527978 223849796 823064540 692919828 838004525 147767561 620165647 292083980 625719056 350658443 588966089 377002767 576794597 57245383 692156927 29299248 590766569 551330083 808291331 495970139 512038361 308295503 789629254 153428854 163703820 14448344 633308147 428191002 429693853 189468510 347860599 461403521 535215537 647425783 836474323 418731483 644353060 425738571 489268743 107731079 307485652 258175027 507015270 499231239 737604998 669758081 865539885 15562419 674524989 308787550 486321376 366651180 692162770 757433114 838347451 356788145 791271233 235700331 281754551 346616401 592112200 61012783 722779992 49235598 119902708 192455888 405187679 116713824 687738454 61229793 691362301 330341946 951985894 206251418 703369816 22043989 831681502 576714057 969478601 120831402 359908596 194946532 235095588 267287138 393944953 278720297 800297058 264642930 354816754 259415903 412799814 189401494 583659398 56694207 444420524 907019620 936592459 88240842 522450018 208201166 640106241 120308842 571490755 418680129 846885869 706555342 846647377 182336592 340466915 251453890 972731686 91089400 478101292 773432054 836636080 637622988 835074171 249543317 680643936 107033260 758534713 591563743 700410393 175148183 470690606 149639665 520539250 369552387 588993475 567426433 768037391 341305454 965359734 235276116 838330169 89767440 110236947 208961532 902321670 99563551 305942708 216490228 649966773 537046600 786641899 364127008 549984895 188452962 647521294 198466086 740138904 91842996 951104482 85252331 977807809 148434116 235895476 227314389 301338836 192190658 589513872 499943734 560729838 797711208 804740375 266902846 549105935 825192670 854272053 101758370 962288792 18834707 432442271 375251393 434282033 230608585 739545107 175318192 439690293 459738648 904564753 201134701 508087704 282341765 698722250 284646155 672544139 555926472 815062786 54809317 837164095 432124742 900045721 589878707 746292854 501713220 595902825 529735702 804881441 58658952 378900781 627026261 807699288 338857061 489556265 317170834 319819366 381546937 738157719 159644942 378927940 504770406 857710652 861727225 983213235 84310757 959486461 217984103 940912821 29554839 112723478 427604765 570159692 220215172 543123974 102638813 553599359 426985589 630196229 174908718 561776901 178470627 261202512 7451323 908792416 706789605 734062451 139457617 271134046 797685138 959437114 522109856 798997513 31692375 52186820 230350780 672007975 203069389 998819876 289250908 852143906 75435408 497979881 11694920 862004549 762896335 943955939 133294071 908014707 199537818 749695907 64571429 224009482 707650064 978227067 283333507 362973472 721341069 809550118 433085802 491782983 214812071 475439596 493957594 571388719 150387934 673013882 515782799 605179736 59661235 256669871 45740340 845145074 759285551 889782058 377419669 851376394 213739041 363729324 128824380 389312942 136296372 944547091 259868612 896819323 854174501 870612854 144698965 486224374 588034428 779815239 370509194 614625107 587239883 873101885 48063186 346775317 914088650 932290357 954401850 971345352 273989262 358696940 611305743 667992784 163759650 656220384 151724023 716426228 266412072 572458783 164273077 334124316 260960598 308971798 184558061 237195023 194693066 683662326 292670661 523693500 218137305 804527241 309405495 399529850 226018098 487303866 143123728 763643238 481027782 672370701 324566520 878713812 80487508 405864240 281331457 304140062 248244224 697296346 752338104 878769722 517438715 712974995 472806754 582914040 159946311 493125535 584392640 782272352 539362331 638236401 293877968 515684037 463322038 765103602 109255871 741687721 284803974 747212581 235751978 787454325 339650708 741423917 420473367 930727812 220364435 998392969 65011922 99754088 356898291 465385592 338784881 514088372 129493011 825311518 371492299 729681322 458957009 870263880 252368361 785304430 62452731 946815536 23724496 223221610 14501429 312346270 504433362 646849531 93389120 135907472 353410227 887407273 354620866 384134160 171002774 930154921 625875909 678625622 399486246 867635835 111064670 187267558 102647730 246908321 41510941 785214211 590114326 867055510 527602095 811799553 510184575 568857299 549386898 924066359 379187155 432528156 402144074 898536004 266002628 441291779 263286878 838882351 179282756 599697507 584780728 696383804 521172569 594008464 725869155 963555760 114972017 888577947 23847344 949926506 141754963 784899718 478145588 904244176 848758832 981063511 194317411 287994669 890296589 950850574 171968763 280155061 138402055 761146486 166189616 725864286 118127997 250611246 94548805 552255776 687634283 938728553 216351668 800635123 674991249 680506318 386528047 953093956 488319360 972739892 161084468 325894451 661409435 749568500 376484748 573555749 32819928 646911631 353921635 911954642 828849129 933154729 401891415 986719504 106504503 826248228 126065083 680701653 276702975 879735625 38194777 696305302 381259122 604670205 647737493 705645792 445734560 782043836 158871024 842518604 338338565 627687022 453829451 933023488 209942088 996061735 840318173 841062371 449057519 542153969 386891885 507840369 100568530 921667181 28909647 749114169 8296143 314552143 73064813 931439935 139635754 564715637 466871952 781710370 241389998 876994535 601815080 974634806 648472790 849353574 417964516 754148728 59995383 435999487 67571528 523456137 622896990 747778962 671435802 872508952 20539900 919413400 602198539 991458706 51978217 421502568 517004614 851600469 309176085 772415936 228449079 846553310 156771875 568317519 287580023 394666417 56484487 527571776 26755112 440855775 257481988 724218576 524173663 757916991 408118909 831806041 514564365 915425159 440816261 780821165 471643989 802763756 567808455 891317947 370263442 896667051 67545699 772689008 89749234 984273830 221126296 859311328 293734062 406405482 692958031 805911849 17836049 179496893 313282258 569932906 127091593 628858960 420675571 588602781 244397067 842896173 576455530 730409302 14194889 262950646 91307617 367594602 463672938 829156570 260618376 443298633 526612486 967021058 381811978 813319465 18208692 578393171 210784458 747649132 557790107 644186109 157222978 228682774 381799886 762242187 644948355 849883686 569604624 836877536 80047037 581207828 25200969 247863729 235601034 347470337 322774888 442051836 126084814 688879257 135845682 441992829 449382721 965121505 375977967 482910074 267530155 440131393 150042766 611446058 57380114 621178568 247797556 928927126 73364691 288868493 56212838 985372839 458663883 855108806 136526599 607827943 310752563 468827459 304147139 964610123 251001886 486561586 100030076 486198962 348597871 878745000 124544167 378208137 264348961 913124653 96815934 524215082 165357725 500970212 37637291 524122215 178515283 553979592 369418814 845240355 591943774 987032977 45569039 974207500 512496088 973934121 158591377 256404751 218788423 532544621 468573066 804732373 488972547 887141244 399497353 483794420 121981424 412587123 37207724 595427903 677486193 908182078 749426202 965301482 117875960 656363178 177116005 737344164 308034440 685803364 145916324 560046695 1368956 943683120 148219882 573335370 118529963 526264871 56904216 123292274 368034688 697999773 621477241 870259997 532912873 810765058 259228084 961285399 96379864 599222581 604844101 877451913 464736228 831741172 533241385 556780348 318503895 399636167 35592594 91995159 89560895 130183822 301244361 431268992 334273813 399032143 717123265 949331301 244930654 294030605 636458715 913666668 749477316 896918312 36624286 545998613 511912763 663348385 365711149 778994254 230239280 302456945 305591255 929625641 253204685 735357706 635067974 752255147 304391784 706488477 157509342 920498016 548939417 652080505 330737934 714865313 429506715 780587294 186272117 888729132 470909751 597163709 409325219 841964072 349072214 603433518 577751144 738709983 279527520 415695019 405799518 924882845 380304349 617383895 47887314 375540899 307316030 909704356 29619479 918713890 19901205 87418481 198508531 901798695 615052624 945585112 22037236 107564157 388293762 900002038 209719948 944335489 709717009 999990008 202675553 327749913 209864820 649591489 523695021 921307798 363283335 401733417 70060120 242831092 979088117 982649322 59455767 508858745 223224271 943761092 246793110 916115236 82902277 710769679 86235613 500355605 502738553 697964383 400956248 950593025 570886839 632880648 290933426 552154065 94791516 252897426 308003326 986330147 149960850 158442399 130120204 651392093 343131421 836241761 97062364 705914363 249267392 279227327 47131547 735229012 590975815 714690883 436411543 715447032 45803861 804481255 633586255 663622543 516627152 881221555 396564109 800131709 505117481 710114472 190229619 831162736 199348924 299006079 284567807 801076429 255152948 475913365 543896354 948069684 164976566 545936098 268525849 324759193 85845225 784866626 41501462 290332977 939673979 993151274 276160752 509526263 421296427 566563468 176384604 206037908 202539301 344532788 106067899 483901689 569790347 757816095 25468192 150773215 248442855 686801690 58284808 836241767 287787056 959879091 47311936 549876965 380827775 922373907 106680242 939624313 698118132 892169711 276352987 884055175 58774933 570912007 457467863 581796494 113736572 943368905 327910170 787102797 771765688 782241244 566700941 736687489 279166037 759601664 106403101 425568720 730700241 981532576 321307625 485023629 794486002 843812780 137781737 548146125 14233347 398010716 565598513 604445841 793764667 807988168 460880887 912834890 752590648 853703153 294575209 387866615 644731773 887100981 496647383 837173934 257544548 618089789 487685859 961720792 437323177 672431431 204660546 435352868 187369790 397731004 672409840 812762680 455674302 632073359 844598896 994264349 719252426 777157749 282740811 996609321 756159769 783029715 114505559 570343405 238764955 708527623 475548502 831052948 14838681 250646408 782092312 816136923 559782917 649647700 83961337 976238344 419486858 938921461 488322646 941530364 168330838 663211669 226663552 266783597 54512524 649220615 180182884 583374561 160033795 494769834 18120457 225037146 710950336 975641512 396111779 424678371 104263763 651897026 147171543 539972343 131945904 389160681 414041077 639535323 238781816 592170916 837934137 914952114 672090857 804359038 312308756 408627534 475166705 994443151 481371512 965919476 386223664 422375837 253439271 886901900 443367935 970697542 444884173 872799252 447733343 983928436 125890491 763892617 534809982 663060324 700758939 781154749 117750802 156997036 149436139 858079337 40032628 539828620 593132693 887555355 371012705 498982742 86383890 109123257 98782644 775812303 340787952 667185046 21148456 983291015 204503018 974634144 706323659 957292253 1930688 563622924 555245241 687797563 843241044 866400025 535802545 904185876 298427690 967134418 266369414 525939788 337604872 879699719 154702186 339678600 682074496 687952399 674342235 849166531 286247462 546137086 289743157 504606751 246024993 463201803 318968567 692687658 674032135 713189293 269310746 470022719 378584413 482285044 519386887 651604627 459308970 637683350 567406957 924809470 34019141 865828246 96899943 382921610 96700501 791336818 362084225 732113740 164625083 478934326 110865782 776325684 818075395 983601484 36805871 726238344 307340657 313179044 542555665 738407237 181386968 366535010 205223694 450448016 108351942 371859006 170488031 700998422 420489902 696973414 461550007 482815684 417525455 822347099 228147358 779017188 519865545 861944616 46876934 264919923 142971851 486177325 303569474 484241139 97999133 722434679 226549683 686809833 883683706 962575564 133008951 245810667 406690435 503564613 497934775 988278680 484844063 794733621 436410550 717363946 124274657 172524622 764505979 838265247 536597685 639663028 182454174 522768208 55902047 581925473 98426869 973805066 87035158 767741257 424643785 938320085 442658366 526577284 377144785 809977175 339686520 521250831 336052551 810255418 147153048 442345785 21467319 871195127 1960459 455306838 262146450 789208300 324418910 468503402 193497022 831645745 1034301 12233536 485675238 750801826 148644085 154800107 687655074 833683444 356867145 872518003 181520419 837261709 174690664 795029529 120521320 823850691 134447227 545764391 760469878 870973181 316264988 862439732 14223915 788048652 414015876 488675489 504357015 912042910 41103353 487823641 202330616 751522728 563050966 619782096 100955386 438083779 55122144 521023191 923093460 979287270 545474217 764193651 183360676 227708968 400840085 522206995 73453869 897417914 177459051 690465566 333093031 461829962 718190201 852955811 585250614 648463924 192200690 938928146 492293331 545321905 614948046 672065451 215696382 431968977 381234919 913331562 415865878 628250206 218421868 538042089 385827425 695309510 100917870 551869835 504096167 945785513 143457428 365842232 899638526 984411333 136268363 242791946 216328743 772987162 68564841 925139325 85214323 186165789 330512737 473904204 633596022 647938753 782248378 981109801 415695940 696198215 152860462 368813972 315751728 851166082 232521454 279314441 43344740 676077960 521466318 733571777 136477204 191062433 62542614 585281721 400884648 536498966 513935380 724702733 482620320 729064139 465132811 786059708 57570364 130553414 254804323 582775292 20429135 236826276 241724696 342197006 518332235 708676861 440536059 882286243 335898622 735101566 345665117 505727176 42290669 54760566 108535113 967904837 131709764 438373928 691004453 927502968 84671512 138547530 369039906 687504541 171770116 957877746 19201716 162415801 144547625 571894332 18488413 72904999 673829722 830778442 380384467 900810159 141340216 634331922 183369263 316565540 211937229 494108441 158249444 653440141 702102000 880129350 323202138 328074184 289707048 822455890 282883362 361106143 287477588 986550491 544217974 834083801 340885069 539996315 61677011 260700439 189271967 278817737 280754041 370136884 338495729 867271377 341135366 890745159 44356624 323857280 201640910 390292871 459157624 659923964 415535571 437841403 294691475 455711419 114576550 669988026 594229726 801133288 281320861 651496433 133335321 928768107 295683814 576091330 802160622 843892736 48638545 738760138 638360139 863774767 708850070 980951635 40578424 879717310 147294218 408222365 103722467 162824790 32517229 571896271 193103376 846032535 76608683 892192733 498747888 652761825 150255107 184210945 70182451 419788800 347127245 836405734 536351652 861339231 472049590 877766645 334088137 661111566 485374814 869834565 84382998 957066980 311348653 609582023 264576779 579054085 375140668 598891039 207960566 898557810 309646344 765607095 112387501 622943003 236570400 263979692 847519822 878190275 477130386 603502852 263740481 976438817 12620690 537080393 276598367 448960785 632067114 996777782 237316248 770219676 880300090 887650646 63459257 274181814 712074549 920399507 746303214 842700804 225868948 406373179 660865530 857829799 729906246 746262337 503809599 644602296 62358977 608571421 289516975 578007751 324352689 354141747 174033566 258689703 382750202 683122617 359901492 960105688 260789838 962578359 58448245 106258387 1741060 239584657 11306993 673107767 402603856 907668916 611316858 881483451 152165031 727119474 277427818 370166332 167504701 782692513 607843591 687875944 134392491 687994932 317496232 820925892 718127157 981348771 17670422 971290949 48378647 486109303 5170275 873138706 925231057 951205903 68541085 948931473 448242404 737242874 158167703 421214549 400102387 445900994 466387615 976967210 258613111 752373429 76677406 492665002 454020829 931105381 35328868 914262686 102917223 265941699 729408291 898433315 257962563 499199086 494426728 685962321 405694393 468019743 656404590 856191361 291648072 634391741 641634409 984200645 530229220 606622881 340076134 694224946 57343007 273963479 270492593 962693929 47373024 925802047 742832365 864947919 205192306 617661528 214586441 374621592 28600688 429467121 109879042 852774682 297209297 422181054 343812413 523779203 287504039 638719757 522437162 617739538 138784580 368650145 320500223 452097892 444180764 456701058 14213490 19540816 173706263 264146390 493493976 941175631 462325238 563596446 222211819 326787330 273097284 931592739 634914135 990957623 61297409 283454718 407837760 557220461 177792444 828497825 366039418 396594974 363622359 365286104 45723570 226570804 263039756 328378300 104175298 846192587 213208528 692553233 240490623 901776595 517077753 866268079 58703231 740439191 45089378 323636441 871023797 883293833 638964156 813630034 127602882 774123602 136003195 338829338 191436671 767482809 54259103 919992194 29147779 685742562 603464361 640066273 343097634 858223847 182543541 675987551 47806963 74182707 785806171 981240986 552119553 707741975 702967139 780497136 565786781 613667056 57707114 668928260 6612575 165082619 247161179 639189332 638670431 823242268 134171608 146345670 767079370 957460100 413206612 972628034 125739426 894565782 46573893 501739239 151862873 434529336 590819054 818385041 371195988 883226464 195353607 867881289 732756595 793290480 603718349 686020598 90411678 885535454 51970112 845334698 70892206 174691004 192315856 784364862 286399823 313761056 690444892 995899797 413792228 688075969 359819207 605800814 282521165 471578990 670679717 819786241 501167413 936304846 127663853 182173990 224099903 401950994 460635897 861638842 85755026 286495996 20493418 292876038 517212790 588668596 287910252 971080504 347403707 377809830 534723453 899570942 226890150 950932109 520738133 805425012 473179478 768972177 48070136 993920147 393280636 733631265 80114895 719535753 78123372 419742791 41516027 933306645 204784138 702650733 288642393 930375661 298368810 424315742 24708286 310269173 122447249 373843113 479144326 760340793 45081888 326242702 243454375 391422392 572036009 644301078 29721095 441327468 204028428 303988843 459536708 815316909 327680110 536690240 268471223 393910903 36704616 988457492 599055721 785439301 145647136 869849310 248626079 734977969 401221859 942425215 551412028 748885560 413210150 687068745 211381913 534603768 227922483 333402428 532400931 847613067 189632814 573507576 310246213 357913159 501495750 520501108 576050267 893252936 619644054 990469682 44885431 712482634 411693026 558921239 7098097 131933379 226701939 514442480 356989389 663794109 559471292 781796627 141489951 660315913 32529607 404227171 657983567 897920647 355788491 437105764 73087275 920968702 287216922 743788311 141920624 948608376 380943904 482543158 194030944 281183441 665511931 686729330 42587940 709197794 650862876 906099737 125663474 222616832 266055668 884280647 324503759 415676219 875018888 932666649 284136445 862149172 178798183 474811967 684142178 984469899 408556347 677465802 139453569 617463050 355278366 455545118 260339089 337456764 427761063 486386250 208222103 964557232 71990398 801212825 431721529 826774831 76753969 177936284 478267788 879262728 60838733 697739175 188247697 409240893 747773267 867890929 412469900 595861003 281772098 832538283 216067817 402055513 544409265 739074718 217039108 455772545 395199517 762624557 664701853 843168938 148180590 203554682 718591820 825387400 485769780 737358880 286491865 967705118 466682901 690035347 93963942 215254440 547352539 931507686 545878991 800733209 519442303 842205887 676684139 993103283 63407482 444552978 153326781 593388549 611372294 638382277 30794257 544139656 480242934 870985822 410074490 669467621 151873500 640506283 252630203 577363674 343229913 873360569 213121224 745388585 237802816 513735119 260240305 280331194 165266700 177767364 636958602 865776560 702152102 755101424 403941314 441189623 142137383 340641497 213820593 225666253 355054432 613304796 704393856 861672284 498513420 628831951 850342886 855675148 525951782 555339539 347906364 426642610 174906134 777901980 279533931 894475134 19839212 74941542 95591053 721599267 119924890 876697109 312983965 703350585 154629488 214567642 416057836 676725352 320838048 482182979 558980004 760873649 574611461 963050888 230817525 564313737 313576071 872522537 79887761 739518910 739601393 992308545 249448036 703752646 619290900 739996725 89191373 997993986 452970977 926254593 613574270 788992933 247283241 719784657 75110960 83017930 106186587 901476960 135706169 676659148 103229678 926108388 5022043 400959610 242959507 822133972 198708707 370971493 472330499 498667767 711720645 794412874 24187803 989302914 537772547 650785292 261450096 497449275 620329282 910018249 349535778 553707725 281009720 682533232 81357777 624066154 131351156 483613234 348778003 914331133 164064158 663824621 342224296 380349031 584083286 644074180 124200498 335610391 294474658 509842493 748345229 974199785 906691183 926605249 203035013 484091708 273197454 778244169 469665653 990727474 833759530 870702479 77344975 360335270 321853606 989847250 660531683 740943401 80495147 716143523 278951328 412552444 749035845 807847920 280100391 890895801 946206347 960890195 388185328 735617323 382257835 422804550 129925646 675148010 317973673 567984430 432146021 958063418 653093147 794889571 598228990 774121739 434397620 928532047 448415642 542760244 407631732 573066508 222004687 350296480 86100583 267561410 164563953 183446093 211324240 554140877 241736021 399237461 244244264 948944501 208871190 332554018 186293442 203359100 377394851 929639039 151633423 363742623 808273556 861053180 442334183 850321796 92970430 547605776 191927191 264372988 57635495 916286749 268408265 371127237 639670762 784605568 269437779 636518215 347085717 422014243 25298715 884037032 528247397 622830945 93531282 373150280 7774715 759604738 94163740 249614674 360211682 554496887 180291446 617878631 770669006 890929297 125795623 141456980 80670391 228253025 613604749 624319122 50185062 709672618 650704592 691058067 339033016 649473058 95282345 887207569 512869667 590239466 103073553 957654002 201995537 567641095 164332197 534468307 264205429 548918870 379848750 833411500 129012874 930356593 68251032 138176259 68764579 355684029 304159174 361630624 463243698 540317492 176201421 654339665 128753975 518545456 773787035 836836352 260967221 768734539 475708867 696145458 593329053 795899442 672986855 748292992 135649718 300061090 650777163 723030249 666465 931061294 488289190 943871352 452334804 885535734 81015935 407728613 416707413 497109930 90028674 235329273 79701051 560974909 392883644 860925384 293871781 924141645 567581073 792555494 112035228 616457393 174501161 309271205 190912904 794020580 585391395 835463857 367327485 936193830 654916641 717079324 870429337 930726178 313595545 473238775 569421603 637257071 475260050 786948396 69233317 541574055 814558676 828346604 369156958 788454943 956333965 956432159 380620375 714101243 682071572 970043754 162104652 975070627 96411497 825136973 252633917 889216837 658994686 743298456 205244769 405060698 14268580 799356223 146085980 459911013 336357668 879559277 961569474 987772501 152743170 162569640 197211829 599558354 173175744 504784296 491031810 776416756 51491620 495742259 409309551 687737252 562543467 726580114 653850210 755050540 41972065 223482530 825887441 904174924 906654534 985446014 80483033 987130807 182982316 680805819 324496602 693132338 395874421 550374979 67450244 849945259 21243486 600570182 169173204 307655635 635617610 705672542 597190448 639825576 196550952 445605280 247996028 547898916 512010285 731359796 192012031 608286927 173015131 894038824 505330245 605517246 659256996 797823583 287797066 488247088 142101751 356122090 82205603 990610892 115468483 849272602 370121614 674582935 207424805 858096922 22917311 928921107 268274603 401225784 256900833 431446661 529771346 769105062 39070259 427204742 103701540 817838412 643257995 804282756 365236157 489226096 195811225 962050384 56245535 90652804 114910601 548502061 271748989 958310091 970936130 979815636 216886289 609283823 70910620 564334771 57209164 818823200 481218469 557565504 252991543 932575495 81004178 342565306 210057914 357293361 568008562 870547686 435235621 830328115 296696936 619140468 263246168 285300237 706463824 720289382 215834473 306749874 178835038 267528000 1119643 796373753 29132974 619396927 84865376 712055718 69696635 354626924 315469676 459923420 439131219 500484759 488320630 856989448 88137620 185091807 607150943 632152259 35205871 812957230 221437861 467886080 587660769 934716871 95681529 994379247 13254994 459962982 279281731 991693721 180775867 934636891 13111629 799307693 35739069 519323596 660310826 674349611 367663240 545566353 308917711 526790856 223357004 535166267 430382931 639419906 165706844 802353976 476163492 626145922 854819082 928888361 268498934 582800141 53765059 378937075 472295039 805425872 371402371 948088149 88338281 316754974 449372810 494064184 404340507 965639977 956051106 967378408 399085121 504864019 481925291 495407019 412837665 634845363 109617647 558025866 540487018 823232148 399764729 634421126 289664066 365164776 213062017 620496430 265610212 997534982 240706840 289808691 263789667 553425093 99116320 970157224 149977844 900482179 213481791 804108206 19843430 599223781 583617553 658048615 160545294 967247786 195321101 552288457 225100300 375000014 90826634 630384495 359673398 659944703 832654961 879100602 103681398 178485087 427551249 603298649 253023476 481191472 426384028 634551925 105249705 475901708 6931650 664172905 219784878 597567228 127517104 167146880 603881069 689868566 144399169 357591516 324802234 950328575 247600539 518015948 380061567 490179760 77395978 240746785 463674960 944491080 363824196 533203246 31680359 861694904 404901733 792023286 193599430 458414685 358684186 688497827 536031249 543916080 49203045 780957024 857274323 901716540 218372278 961513247 208279083 997369219 535190453 833276583 228290457 855968391 469436510 942454791 417883628 707355389 74063708 238996516 599907993 754388411 417840690 690039915 202637700 816457672 839002824 844215976 99573387 999022267 142159697 338537630 382963382 760686684 306473695 762023608 117025175 798645895 170236981 458912446 756403748 940838525 436773850 806332331 48046214 874148264 721487045 886311484 232508231 701862628 836286870 939464066 104134312 995172494 549374576 923393829 149588446 220742693 692309341 819268472 888731174 914160067 373204245 911508278 43025295 771674222 945451932 988281442 713686384 731140461 861563937 913126191 276401162 779713569 334079613 896325026 433915559 846060472 860325640 930484139 417339215 874949623 500363602 898702284 109421974 239471747 794177024 948931557 188546547 669618834 16270370 896747174 177099810 751880506 167067374 884177383 103240864 348385764 559844125 796317878 402297533 934737529 119886497 954304078 896261833 993874254 99222307 901098260 183186767 420713921 487667476 675554531 165147164 288039763 225446460 329808619 454988152 952136500 464346488 864764401 152930053 921481202 506062318 758854893 203156434 497140189 231629330 319905392 184729561 858960081 470939484 683368227 342784353 375171918 71002010 912326607 158774581 304810005 138946224 410741104 186958812 275740956 80437998 133875271 574271285 901634782 301077088 699663389 146132494 250215307 638247639 720794601 353551755 879649863 466608679 960043416 295397408 564374844 479126152 540795008 155218645 581229174 212822457 476095061 251903378 484309737 480145365 671615524 301823517 692380894 930322950 931741623 489394564 561256957 228735653 287200343 679251560 800725091 568194761 661131696 603792893 959246338 217263409 544665929 697507320 876008561 92420943 381242416 271860492 694058698 288404769 922748104 280896975 287375702 118931243 546458902 165436475 871769773 501872418 640671780 106672702 804528586 128756966 337269844 382553464 644077963 863246007 928301734 656087391 956511106 167553412 306294345 3369064 666218478 487375806 886323013 20451057 202193305 399214280 430751093 209607400 315240953 18233589 212904646 584517493 833279218 407920289 676722420 105570543 717297212 115468920 559525493 221820102 852355491 429683931 462205548 48013951 641086025 469920884 788758570 26460568 700097770 434058135 922196790 514913898 957102136 317285923 749468957 260222871 260367277 184025900 615064640 468220508 490005628 305246430 835885778 341104100 821195530 626979247 715435679 513747076 983604990 632144855 758837993 205123976 747868983 103173669 923698856 534945054 952082924 582468954 662372278 142080736 627004058 471070382 715066887 480125587 803516786 119183751 783810672 107441714 697966727 207241810 286229810 29638575 377529878 645234289 690126557 235739088 811293002 89048546 387962263 71865827 826798552 570406106 574264044 181437400 587154975 651784317 716917161 170432195 696327146 108730860 968134730 301227060 580413798 169628360 738054946 260149086 364526677 430948930 879310759 224540552 434942870 339138240 823123313 494433955 877638330 165060085 527023228 616698974 648777944 605661950 959815915 387679758 728546814 881069871 934607818 795207882 799523920 56186265 121459756 15332608 439478764 98227188 145461033 396557573 814096304 276071625 419007085 227923580 729828034 481078483 801149911 690898192 925844412 200696201 716894582 34119867 154264846 31986788 466104604 329435181 421112663 117635072 150588725 396948790 497431835 274726184 370970254 50495420 370175846 555539619 971456445 97115489 479497079 141613866 690952384 489273594 939909431 524548828 671792935 580916080 928487627 278556009 323185359 380715849 950092834 905512577 953749506 21173306 317136167 192913814 953732682 281406322 895319413 224854385 297216320 693071015 928758525 419498680 679034685 8064104 166729371 93300555 158674769 495786559 615391350 437713926 801020080 69009615 900514678 707321373 718274930 193194993 984278873 338278125 749289564 454983058 749105842 35241120 562641761 248926681 349524307 6635661 602218522 496430005 676702319 531079080 850667697 339136484 567879268 287334390 956260930 236915174 472246742 213028735 584063660 730150541 951571112 17374694 131121583 296693973 670058989 627274903 676507272 612523479 911935641 915704128 948903195 547560347 930241545 69123933 107311146 194220819 829175100 211860395 466615769 340225548 407315891 315561568 694253933 117190313 622246741 32297377 630513039 367910616 377105850 342305708 619623614 25783025 156424597 41523483 754235594 191142086 722061502 416206485 431596693 309665019 547131359 682911898 974619358 358346778 424595273 497715216 892567168 314791140 450441063 416742120 573437696 34547736 886779997 817594369 997447981 610322466 626577544 34460370 846526554 100883137 678323356 268634739 276732938 150879407 488957597 33972618 458025284 229054808 794832674 475003847 533108667 514897011 875187580 346060061 761799075 343046624 809134752 123597258 382017869 864089100 864916500 156405494 654819703 58712657 516640260 180126950 559072043 486410934 492299944 567155418 752454235 174218748 777342719 83419008 804833123 133813205 279660437 594990762 834672732 526504618 786343069 397574391 757161350 59509516 440734908 410218014 704256393 166854218 325854611 546049248 830283342 335934902 728178832 99227814 507361737 595293334 911496155 43023748 649281239 177387285 747416735 95125109 678948730 86708166 786490893 619135345 695356187 853902445 874104379 316363638 442661467 459954379 920497083 64525264 147205953 102749367 957866054 547744462 649832482 83589125 436418068 967352416 992010412 693411396 798226236 85411556 292117771 313409310 383472656 318108686 818198295 217926241 702881590 21044998 393311534 169265073 246505677 480037817 990559659 235087477 309564105 335967336 602483921 411820569 499799694 70060907 370027146 293125901 571864776 276048561 610024633 373106212 779461213 41574396 186845599 488908807 978701968 818475773 955103912 88287744 701357865 125121004 692074407 174234832 614813315 611954053 697171431 647868739 813776198 679645442 884014940 7965680 759220798 122502030 235625972 172159506 712837714 189346372 679715190 200688716 935900286 198342780 930061029 595482676 772057839 738184267 748014902 53103850 129121785 209025854 768965655 85544761 695957900 292364463 353194237 162626276 842862890 168417495 304868036 259608980 355418559 560621643 937141421 842101512 942027392 341214074 896000612 589436973 903615147 70226414 305719791 252956423 870008165 29153648 697655135 213566136 303760698 422666100 652342573 574786221 820191498 79075683 287530240 41507758 880348319 761725530 963849433 202855758 759756113 668184154 770778333 888947140 985072959 918210972 990620839 171349864 175498008 808509433 985927778 288452770 484671116 620393268 793892776 269847994 507006189 286124730 508905363 249217413 857885585 192393126 293446777 161442191 944304925 33299489 906866807 305984532 518616211 242308578 290132618 195385944 622843995 588143282 761781242 301633331 961982061 530220455 567704502 225237004 558377298 344279141 347839653 105213528 844187030 45026929 345495760 232225615 290736139 563850858 675600974 192924762 840361457 6446738 859427909 114926910 946890621 601974966 928092793 329486895 461085329 493515007 744724977 13021435 917221733 252999157 326441905 476279918 953350612 43346674 819612281 157117377 392471450 273520595 480127635 730470760 755366018 834793700 854287049 462225567 648455088 373934237 889743604 82368146 200568016 293051235 631378683 226480872 874351968 364826656 412717560 455858973 885074005 236938989 949304709 27324137 850004252 195593975 675985181 33591257 159986312 431251561 797620390 194401955 918345117 472807730 481577928 105657438 744351322 103293779 242596999 691137523 861615775 234618842 661928017 223908989 870185307 95341211 141999056 526383872 803307249 84490194 801802657 471892032 489604068 697169469 816486720 300765594 764802291 195588073 810349307 263249677 805221932 346850377 729374486 282556916 893185540 42903306 643102510 98216041 889690740 561825866 808523864 540902655 608965665 669170595 874414552 165507925 411552833 44800929 904976688 156618436 982757771 405914787 742621359 435979430 622007114 271498424 651293572 221928187 699087123 31513332 954303885 248457722 487118686 111369711 556870237 12039151 221667334 384203749 910075055 745332845 764332309 167702564 548016336 749510955 851684291 692838513 869058115 87873039 708735662 927161979 950346602 290602889 765123833 112433432 132087957 132702492 989537362 772157680 828535358 740610889 927588220 277588451 472243494 588136632 893950848 330432718 745844165 190701920 277284619 84774755 805513596 660362383 925867333 178540310 719419071 276731883 924124783 190890108 667600422 152398876 162737277 341305209 665284083 8955492 417187135 143453649 172004038 326647501 782690898 135728057 151454759 710633221 983930209 521021155 885931864 216781085 382971621 576593979 927152354 471714965 504106204 197940461 237147111 52939247 504023553 36473233 226531776 3873089 116464805 563896600 948149913 358646578 838108793 430047017 961450701 115225455 827003809 145526512 664363964 106935718 918749382 575568521 915789592 233051090 267795457 159795515 835198454 821970176 922460257 509866352 998594678 116259230 219693662 11835396 85956832 92465157 155720563 442286199 460186612 209940527 566893618 503095077 915022238 158161843 314157852 546893546 904809950 38945464 959433431 415215813 688297725 121286329 606728332 32031568 824486624 494401699 742995079 804575150 957956621 359534661 897050425 180929895 942494451 564044236 946134243 181994313 705117182 474885326 527773427 328388956 889422006 381978884 905556309 37296163 920472717 260777054 804610858 61218659 605456593 387542081 498747666 54974036 837444470 446020494 487321805 302603629 370927868 215926417 610499483 452187056 522078693 166380438 276339832 170333434 705722930 119971536 960865214 46425572 509890645 91742855 328255763 155794382 977089841 494339570 515507977 728775728 960882274 476693030 702433068 734795824 934529598 901395161 924027399 479365395 880416482 447449886 992400094 99000641 443639205 698825137 971374932 18441921 221372029 170968286 646781090 193939359 511918100 99360724 724873147 2939263 778705412 168514911 639518541 325247055 629749844 384229218 783324896 469358660 596188799 367832763 776314220 806399001 931493584 358922686 470471935 335985365 780004163 704187031 854523105 542392619 641307523 72071762 873096475 367705670 998241369 606853838 701449850 349077137 431432228 634901872 985104266 670791644 943354199 391230163 953865136 325251062 559102222 87964732 474946639 301447623 867811022 64175025 663111780 272725273 413536004 171052527 237258785 380791469 531407255 164438476 592408436 142091711 252771848 123862233 358165839 198382442 533877239 25518108 391459879 393890215 816523539 199558035 496862246 278662285 926297870 431882621 521367461 392028684 779926928 524891166 849792866 165948132 313113586 80259503 821060162 16223791 136495530 28916127 78119026 547984102 579353529 688606211 822028675 23638256 136053993 563256261 668473111 557506818 632772611 663948945 683564708 50220317 611447990 83032852 128578394 246351392 557686370 883429321 999035771 29066104 896873399 415866050 626251158 684221712 969281513 481828107 593781271 624697866 662454786 170948362 708443984 42880370 985661957 79103343 291431957 108805068 793908475 333019314 984395672 520098009 965915102 430367000 660552278 80336925 787143367 191070134 979687364 372308686 659985612 34435350 971278608 228648539 337698379 113374479 121471613 631957942 708713302 832609784 955089052 335681392 500996245 624405026 673911787 211382507 593648809 582826022 653843773 35982482 857429161 787880555 884418680 390198825 815731890 93266731 379262036 238494007 799523625 762103257 917090548 82500349 344703789 137418951 687600186 289943349 638393256 214834435 693908674 319533916 691364107 279470830 576366027 5642176 624068728 91642812 510288931 521353531 854064004 366281613 479050026 46433195 752223632 63411933 200071887 432156801 814229979 38878422 121118522 171496092 997201398 48472140 482989397 436227418 825603742 436421674 752010218 411720438 602111608 87532868 360169726 152270162 660629949 485164590 507277958 213763525 244713139 753866565 821702072 210700071 757757799 3061335 463373121 5188924 378383220 257773019 643938234 95839937 710639341 199128026 433104630 65403003 181509328 303309361 832987098 651397846 985899165 732953548 984996220 194655980 196950927 263234728 628128233 150995339 302360661 157691218 720815932 434208126 925743405 412733672 856990172 491870658 985369508 116058597 695839864 7004243 353833376 795171666 841884095 61559979 842786022 232865683 876403699 398673210 958520292 72159246 705394773 142770477 705916386 47998066 900373512 571069530 674738464 482407560 766358802 137289972 962631286 174884244 524049158 572402068 722844786 24487024 529465586 623422473 963385268 66354396 88619788 406570658 981861288 109608134 630943583 445846772 971051683 667587669 775485665 777854529 906957780 36881202 174190945 134199374 890193305 273116441 903973437 277591569 795324123 347756073 550199793 487864339 819816828 544401564 594410830 514710035 712718503 102911451 403789169 728396111 946825281 124275684 536228021 524982052 690829640 393104899 878654653 753227698 889765536 465734655 503554413 33126132 384692452 228958203 368513340 43967767 994926206 396062508 628758449 239748219 787393704 275445364 796064753 340850412 628190450 85399789 755238133 238032482 359741882 788205955 852867086 720279672 767779242 122060856 804058528 289027313 689500678 102514308 129754861 396225336 993815584 60527210 259395373 716776933 830739834 25690072 745203399 310348220 388627852 5629613 701642689 119872918 794392667 206593484 221422027 517698985 769353978 89329333 233129009 259563945 940904878 153694639 812846420 735260004 851092103 236319236 498060855 184223790 457056960 440318329 864822539 185197497 398854962 51277105 145684828 624526301 942853174 387650762 456024294 469372558 734013317 77997142 939750455 90659918 743245597 278348923 431126934 68022709 704160009 522356929 834609001 18339861 437395566 395158937 491426994 672063265 895898021 31557552 984287384 727381984 862028358 417609803 762673958 52856721 350266332 463027011 643908315 255230929 815167649 271926874 875035199 321851741 554073379 172381981 848307207 225853081 244377844 72814971 411844578 502646123 759864508 59432314 752091417 141741161 939665384 29883608 902396916 478603515 583783787 486549677 536534822 410125312 958701497 84666803 381104887 73230455 861123094 219884481 836522257 104653901 140219871 721137437 786121802 524669687 647311456 580231985 875926086 268147059 762962302 107690901 870693330 157961380 809411229 450384151 498745771 20894092 142036630 337647455 994160903 193321290 305699751 152321138 563308423 120978332 453398229 286767433 898329212 671240477 682968843 94721269 113687737 584940379 683698277 128234932 730683078 26571611 931923528 26933775 828317597 226334755 609357390 165966619 820772348 225730437 308707153 205820568 984499091 30193544 591623958 453123592 962796553 281006243 367824203 90922439 264934899 352862825 533783746 272761944 587597738 679600257 952716396 124588355 375226093 728945014 872779290 15474303 177087570 143884190 923483734 120973243 245484081 274386694 276050634 186371329 691872580 203269219 936953465 659176711 676827730 26049586 56470172 325645145 533682697 10881870 928603154 439754578 876060628 341855705 915350376 406558222 774841118 313602834 445093807 243323162 976319794 42008426 135451912 880606324 958842810 343873163 778430033 422579886 870367869 5882233 67687910 811788134 869159331 687143510 916902300 448638433 802610526 351028268 786725238 163375269 594660915 56896541 487021315 418519350 676462580 86201358 156084437 476419782 784437779 571882254 922554310 700773385 847534224 527921168 964092337 327701073 764072145 740877833 898210470 33287941 307520116 305571066 762409875 616854719 638606246 603007397 922408433 237911570 772073885 292368518 719886724 12827643 529784086 305848409 936476705 605038913 943927493 587593840 897300744 663290654 811892453 152655776 493142998 479187446 578610330 85158821 507204931 50697117 108203340 542835883 856476610 200591471 377613207 323392927 819167730 617183115 936747717 50532890 394327299 555656837 945008739 300915196 324061560 203280527 524108882 76441103 981161969 633001642 696142235 27826920 317546759 312564153 579008325 230024570 631742524 183588884 989210837 404548078 558169716 87696600 371848787 213427494 884095193 148026475 957463618 51249651 630724097 144172265 820775980 443707947 584482102 53927108 438922621 155735283 893982175 513308457 982308102 96971004 567251605 665181418 868048254 150252942 530135433 475417266 805431062 320260012 634770673 293999207 298755501 499135223 810224974 475288213 774595323 369149194 892667539 517980879 918264414 452361115 872507531 866564864 877831453 434911778 839291150 284845413 879888527 577031243 797162968 300020419 820514056 263922133 306619100 732504650 834285786 381035889 389321338 855536273 860739114 313726937 432678515 258112871 416741741 51757900 192184045 136733642 450868078 46729010 401145163 734473887 854785872 292236467 798289238 683930095 848304653 861376065 884446769 164584883 927029320 470665978 486882665 295422039 926975407 345636103 728916481 30129113 185563745 197115076 198203678 235741695 522572181 200120714 232572206 103288195 674686819 366732014 498474502 635567268 996318570 173557621 532866880 150884421 740564523 172160905 981781749 398887250 556334759 382844951 441832954 176208623 519079719 15347832 70944144 192926923 668502376 46340600 946732853 179359696 750130206 117881510 941354122 55700612 169609814 154050219 323926402 10230273 557315542 423506549 815646914 319256053 960090108 549404377 774748551 683457161 808252096 61608775 207748769 86564876 229010121 452499152 536616390 214366090 940029273 86078135 942609220 109029580 357687866 266993145 897375140 40575053 275169485 501819119 860917277 172401185 377725311 235562407 792793580 34641896 246717446 883372515 894266958 398115638 737764489 359919969 478123670 193280775 392429764 5268775 836940421 494511104 871055104 512944105 602710945 819580678 956111632 210528004 277041659 269132458 331911968 203155555 521055641 217554138 627736836 663744206 860550437 96755322 625948967 320732718 529385010 421899825 534416121 634310996 881105965 75703122 748769511 466282933 856877626 468788269 882837774 89947262 559587891 482077367 685981042 146529907 657347863 187874149 638394471 649520175 802082680 134529582 427127361 352364577 803020909 318785350 449648032 115364638 934481086 138062183 680507990 302541613 488803113 282609327 333497786 322929294 962680831 88080006 540853822 395618913 558246702 749564160 847235761 484415331 724391796 460380122 582596679 214804083 509950637 289937771 536760210 565142608 879832165 877425962 939546453 367354644 743266004 375352684 866729450 718939054 831901893 246569431 866706167 101311490 665650928 507179370 912656701 390502197 403126338 693229012 780345396 128746529 709727966 124733108 990619089 47845221 747358728 214039490 385679195 286222013 706189716 395186267 909941417 68181738 107347741 138836188 140386826 373663578 635303301 308072392 359755137 37155762 673583518 873721945 909053569 99258330 167964356 5117964 766457924 253544483 335973715 364794158 874024249 303751006 823598902 808961176 947760075 299922405 807399613 29497264 826003375 260204227 299127847 100596933 911708547 267410938 313926135 148205299 264831910 577898564 827708532 287079627 953871398 8100290 391836252 339600808 850143477 492821603 896803635 572779055 818086032 128914682 809835455 615999886 796753605 555610701 838821652 458058086 747085715 76944448 504378802 529266120 910377053 812310443 822686176 707204995 890338940 342271427 933429589 484603415 695355394 435456042 699650399 250676964 459697001 399010979 540121128 283440780 472388336 505072638 889203861 544652307 799488438 3450086 587996376 524950907 553667842 134765177 157443196 59672095 410400284 663134923 690385607 244752333 639040574 231032076 896929374 301367064 444255226 15269778 375333186 831381959 987521548 440167233 787932066 18434821 331108996 585123232 926009874 524691812 895149150 173623894 609062106 312674473 724434626 201910940 248133010 244595367 993634621 164950896 315165426 512938724 574591590 927923300 943477356 7212156 990870084 537100449 574272560 41009799 733616007 310238348 508346731 184961611 277591314 196379062 405034745 437542362 700715534 195274070 525822051 150082866 531800083 109360252 790640005 311212682 856840970 376788297 758606814 645100577 826241949 46238341 780151283 444524785 587879430 466007253 687077539 25814115 307412393 107288257 204632479 146212405 548510227 326315508 526754356 712389717 877296431 753729192 767904675 345390032 810034562 647362984 657843399 505721301 727694994 238167529 822506636 59419030 582661755 1994683 449312083 10515433 920436049 353206327 530131206 386860259 954813688 788092678 907133741 279324648 449234014 44339901 577887302 95208613 632669537 550283541 676833939 46974225 266474553 869733180 972365475 441018715 741743404 245124323 742670158 520859046 652404677 33585799 163994083 651199662 795103188 128084321 619431805 738139527 936390048 670299671 965763730 536705595 911874518 462338323 567008454 152774147 793227280 168769750 467906000 524722479 763784358 109388760 441231817 668358410 837201062 382564417 630775217 222321165 297113552 581499997 905390551 237209622 572340762 480303195 554250020 237066524 248892260 326997459 854106897 506937975 824264436 140402331 384218102 39193176 188535860 242474635 684133185 666677583 723299399 539576087 671099535 89772208 335289411 58086333 87850277 280134163 476319823 332064520 534890549 380952136 626674272 221548934 446667039 234686993 812895277 878982705 903394803 639454282 742017932 241543549 634804114 1832030 103029248 806268520 933336432 2533385 748601852 412348770 838673897 233089844 680164271 446541629 596822979 221215449 501345274 410703768 871253903 47355907 124010805 328167232 844754801 567167610 701884600 880525994 967086595 631717156 731944978 635360532 722844497 39666572 186780489 209945666 773060187 358993235 754220204 14155971 777031192 312473899 442727519 598830847 862272697 344900747 363832152 470318727 813430447 228971761 437080278 218507434 588110374 193580453 808769281 241288896 729057027 438074064 714332813 349925725 891983654 380790810 984052101 200095945 928319908 638449570 668151074 183348569 449699852 515427039 547342888 106792217 244787190 229607837 589028105 68497837 691449404 490855799 796311058 272981346 887300761 503716973 961297995 432331861 745505991 422896450 693332905 235963173 435684297 468347004 923404121 228817936 339408739 937946926 996671706 340652383 834261871 66041238 713593049 251944508 543873607 539856497 719914337 585478290 785463642 322613806 928694004 174807632 718950424 555166438 985656195 657642349 976235289 607141389 731558395 133623235 759284505 407826788 890673368 80040436 860146815 551922106 923913257 273962144 517755710 298844757 665708083 245209812 839652777 346142102 969899323 101526936 930105082 142691213 814356896 50639025 416087123 829181305 864857841 24003876 574804368 254270513 638806641 367439432 706924662 363806787 898597698 437546091 878760248 481016946 912139578 388606816 952720884 227302910 501058014 43180649 978567891 136020051 535824467 305244362 958608323 232439378 468413833 371186726 772633387 107277824 929548019 15651300 570804092 566660483 862674693 715355001 981480972 99474236 434478070 371027730 589346297 21286764 153402386 5962519 899996253 105738086 172723620 117398224 649534399 628452023 970726774 30097979 526415321 109548840 393282653 122191737 650322989 93823568 302498047 747017618 982183749 316996782 712461290 114329854 829613334 583752012 819299695 88917121 749963640 323096084 418491008 761592533 841079314 43069497 602458300 909411222 928520018 55309679 623344671 263037181 370267024 206861358 959564496 358992547 717097302 304455060 317976307 214469968 472093670 183984143 881555896 778673690 848323607 649635480 818468584 367004878 861944134 448139297 508860813 138718405 758838035 641601705 648045608 184220644 706698325 484680609 520717127 332423746 697139601 278085482 533507058 142195950 710361574 208257789 641340792 383651145 600279597 465036909 524483016 278439124 701843856 393972336 663029075 592267334 673915715 15626770 563714341 232641385 857630163 548928103 723561694 353576514 654185078 441122022 499550700 440644471 623231969 115551254 819755165 65084822 495953103 914163895 958171455 212345649 365086914 9974874 323589439 90702108 806090472 422429639 595817419 83986289 849460035 395225420 454868383 152818690 758457282 72068748 237646077 339003452 553276004 144310563 380497643 121720313 134107197 288757408 736604293 178170909 324874176 565854293 951901514 495957312 999431045 601031117 751630762 262090843 457452878 13016559 690493402 93059667 190043036 119203912 706086271 212390349 849285802 723428518 738105009 162225210 644336482 112525771 575701158 213645126 531234500 352349479 396288796 321727761 695375872 47170944 60622483 231740403 318002728 246447992 502196226 1643370 95300033 515662734 680865064 348162028 892904800 890911703 899916537 267316590 982446803 206039550 857005603 639131302 931108925 153447161 659288584 48234692 170522989 632610739 892149815 113792471 693130481 423206927 991206506 234411865 707568644 180277210 556310330 364172695 981448663 182100477 328005206 38027069 410182452 155572219 635887174 319138869 900724779 72422454 657518950 517793390 959600186 385945168 952809517 467962542 863322956 413494576 644627995 93934346 284179995 71348617 373094410 403746479 459301100 351626868 363983199 67844698 522505541 372262219 909739091 53287147 643328578 150360748 853926055 474084278 991106418 885527283 910357822 767833276 920210625 12070735 713991740 150626941 153381071 546906218 672668050 488821981 895687493 91727564 782641117 392133060 925820509 29624954 228321208 324365113 849594563 575862023 991115490 334249881 380254542 282331678 576632625 262897724 697439788 49291636 598769468 512776935 798368823 128311745 674092832 85559162 158405606 36793337 997100636 271596131 685537873 181496677 642078914 89585688 871683427 753895353 956689062 61045810 551599026 811130878 856593186 602723801 997427890 342647708 971057826 501079659 689389954 526186816 809863739 66023477 890877479 172529732 256151159 572087242 636695971 211947620 625047570 52291878 385376031 495739317 651524828 105165347 829200245 142059547 854627904 500962311 531164904 336648346 662788039 217240571 796778192 378769047 931419362 403660385 595397732 349242248 802287049 262886888 334893375 442656467 987731766 72859785 830328601 275092992 445273617 96756815 554136747 738173966 955982152 27438445 902315520 228828892 970871807 632507481 899847773 451052705 624521476 575448754 802387545 390028907 939176670 77923014 908295175 39088028 94733218 228767466 666881286 67321242 190450614 129234012 318455160 145485400 743021410 35274915 335277947 638912054 922921635 149080748 860338380 508812029 599177828 552158725 871535853 725851068 850090964 741467551 782775550 373820730 862630827 491487324 692272674 604494421 972288538 5903487 133083263 337808608 775416676 628508438 797951022 664632712 968691420 526835184 532980258 360278895 392842832 568009221 697949087 169299651 225457259 607877863 935083517 292953930 466267348 35561710 336020192 841187163 893198798 482868270 502655315 133414435 296425792 349586854 808145084 330832713 670769875 609222960 950171993 485351126 813760564 733518931 823541504 792298456 863263940 144942513 942287409 169252987 546603576 838751699 997805456 590938008 672234249 289656908 513068846 335176363 782977803 645474563 807841046 340732263 899743690 557183159 711166532 439685064 461571556 498625903 672726233 469025183 831487029 83698724 958305022 412975676 791249703 159386076 413575881 654723263 687479983 228130904 461847254 750658212 805244493 241037097 456668373 610013710 863802558 533029219 903874763 184246372 939318893 283086784 546140623 380676622 630348234 401419861 722854775 108577507 189263864 149480324 275240549 739999660 883581716 512877973 704587627 62936997 462270809 267109793 576847871 520549425 805546663 407542359 949498481 70618448 593998065 342701824 541713777 272981393 444421505 659632497 733861416 332296943 365238874 513888077 652254972 829916780 939559350 208565959 766865114 628720472 732204761 541689848 592920245 153464458 397382571 188426862 391136213 293412890 906984374 6594212 855311091 161011881 379941235 131733679 244998077 88343578 567710410 226893881 699352425 31606654 619231213 41734860 479821980 394099840 702120769 606121454 830760390 243684840 468417737 625550030 708597758 304828854 899703645 171480169 574592112 168904764 861091866 499883273 910801627 104690463 698876207 593200855 958744142 100926855 517089942 377280377 578252862 385477761 677965183 223433956 722196440 359760186 580610337 785112324 785799996 15631007 80923506 624101208 869092464 389352925 995789645 512879665 858124230 468871761 710950158 37623913 629862940 388948701 886040051 222666584 383072960 416091388 857507476 331265484 525889525 53903039 939761807 322856422 662512693 340754862 780837809 830612718 949027146 806134435 959548755 657045963 933224538 445268043 573628492 53155400 358978089 66751832 706121955 157566119 473754426 388585707 936879407 85462884 443581161 754181304 871429882 196249813 198256478 298315395 681784001 254021190 342623806 345834024 382118686 180556064 278759090 793163574 842077532 546190472 578998060 849452244 935465785 282232190 441569759 618390122 967221226 156558888 459314460 751165326 845459112 152651054 747439061 572000543 831961961 20989999 943676297 38136705 329839847 178127111 784296704 225652966 899293862 79927746 517159035 207421564 826671980 82480253 453266763 249152748 684186751 234118175 473554005 245760633 314880759 669699506 736445460 702911628 912676714 365845245 399106659 828879347 995842649 578446596 636896316 203366216 320530499 302928254 614438882 37635833 478319563 449230082 520586171 146490836 333289680 112275407 985407198 748393108 770482589 528658665 722267040 399544599 509729985 580205687 892840497 639270818 807474857 89026025 866824391 75584552 479113616 500672219 924289208 45922090 347457339 330848744 699102629 549512561 798610941 730365950 737681622 205751938 347794865 11464770 958092013 124985310 334440601 693985714 734585180 263781228 870236461 408032383 471988134 49774440 97253803 805135620 998205036 382323859 553964817 165452233 401811823 241974642 600212133 566742897 939929416 438241020 700277910 630602323 891269440 59241583 828658583 199460979 988268999 14482820 123703682 23071766 700096924 631334750 899922600 381841675 580827845 256310296 582150398 67604221 878965263 383976990 749297687 325972785 429640291 60836957 409433496 122601605 578244743 250726253 862280706 20887044 458708056 146023515 792509633 303654789 749168584 120310951 762640524 289524882 723704595 773895953 991096511 617350276 798013673 403219870 557278477 441196537 899760026 55138409 916460108 316425793 563951539 48635941 506779131 345973538 978364895 95037312 612310360 373149328 498780468 591666326 644421075 74888455 284091521 265670880 802313035 349137564 426267656 175770983 591702095 778409086 867853747 98579660 293368356 182114588 584904708 366588733 524870653 159695701 811492869 418005770 919439307 59259698 264591223 131593789 553955981 789608767 937628092 385822733 868662736 206223977 631689783 203196273 985342940 711463739 754790051 845292258 916946224 133842287 254807964 353179551 868892873 720965715 755029116 201122497 824899944 384301959 662287839 256439585 508273634 51530013 748526308 339385327 660354060 397571447 689200757 359204017 491183915 274981466 439557302 246187650 612359154 309995484 873901303 847963474 917836508 154545296 808349271 307781313 685261932 10626424 31390608 528589625 783057555 254907649 770114520 304458880 965770208 69432036 910527900 520047233 550160419 581253548 777524540 341532987 446455047 359039125 390469539 370518914 616575796 15105572 886581918 291391343 767427971 581781629 724964802 337468159 790247150 252566097 905177418 608844728 846190248 447991162 939827793 37649506 171551644 951536583 967258262 314176313 517444661 198024144 360708027 464777463 971538380 175576161 906554236 91445720 422999441 933895211 980766065 488140738 796935178 433525897 691953512 617167980 683311691 832865233 964741347 351778265 828779590 50995533 536759008 376520104 386669454 195321943 586768996 624099014 881498679 563702451 814772588 376917309 613306582 352236458 394716563 262386996 792437095 351780060 549136229 334575203 567454740 380065849 727084101 266593722 647106463 260214874 563426725 91718468 417276970 73477671 149364607 73471082 721512801 239409213 632772052 363055222 498152987 148966620 484926999 536860454 568390185 59198284 178035220 35836775 993070234 141245617 945031021 583849794 858007339 195146595 912724490 288317227 934864349 436142707 886593771 214237267 621721379 543094886 894752078 251554834 873909587 585951830 717470221 112571143 747356158 483856712 856344811 693096548 947744667 226578004 676477053 273144191 434608518 46827580 433155872 809483371 814707614 554641934 644923946 174503220 360237714 694474246 802531397 184326436 465325312 79638340 145346645 768103569 939958522 208796404 631370466 133500082 469391447 174326572 318411160 506451758 665979448 657862863 774116523 779185971 992963192 825373668 920976265 301251059 574190373 91321376 215230563 581711212 616282356 242780903 950149979 375573525 749229459 380678347 395708776 650214931 663019692 355334826 635325058 289994998 574980642 88069326 694891960 135589495 227813630 381175760 571686019 80908711 82508214 180025864 693138804 214666684 530034985 344264430 967851820 199978924 486923637 42239895 676048859 526766581 703546119 420492630 535712506 296536108 329573976 546808253 707548995 291620702 785813625 378139189 425422127 191386541 200504372 487217916 884988499 441460267 774938618 338711362 590530747 539800165 919590394 35743679 587086261 413972382 705741226 250050422 433259105 428569918 547841080 679920959 948191843 191864645 340982484 613853751 748005311 226735152 953408493 214635688 584552377 270018425 750051493 14657770 982140334 589397033 692238660 148408976 415850863 108516644 129124507 151016933 372817482 130840641 149246385 30011595 564833448 467050575 526068272 126517607 842476896 449460199 709849004 531018393 962977604 684433896 799120611 35857174 326493908 356536759 739875719 296792092 775383117 180429978 446387898 262947645 580550558 111149178 566871922 804447472 881615676 495422767 613859023 69297696 797374297 263405454 408646151 178389406 974299689 686881033 982700437 576058103 968216232 726018360 917304759 16808872 459075768 222363609 999783391 62077668 923838529 83764947 545238143 310513547 723655115 256366316 439325761 102770980 893185667 539483811 665642439 385402790 593379289 130132265 790694278 39518480 646354583 98411363 479747614 38130991 339569015 562148841 985295677 60559565 378097735 835862079 989953504 36360143 79698173 860098156 946426237 589128508 641663548 335502412 753565060 278584210 446956804 69748192 882713087 251186734 322034267 18505719 364014716 290418438 874465719 463036807 968000081 22137689 253947913 772565663 970504106 494531684 616229804 407630985 806985222 8266077 864594907 219166117 457811135 617196307 925729966 161085367 169059326 204328674 653553863 334552695 958695702 570030744 749562485 396401468 980602627 928589845 968524461 279667254 846755526 127385741 911268085 39676521 751092870 206608857 658760797 182314235 272310362 197643831 569783741 807037807 948355864 163182993 780871002 313892578 595062437 257369351 940891957 231132913 769199325 180476853 901381962 451544925 896497286 552153109 897244792 485042813 755558670 116845791 759849740 484427971 852371446 378590897 701554190 791013842 935738719 627882068 752635100 277193530 843982079 390554958 535929652 505836670 762387515 35246888 424288266 339538991 391378921 458936934 628934229 23474909 154048391 362285309 798412631 156349842 613749283 68667945 739412080 216906616 637260102 372628532 668528990 700527108 869871044 30674619 61897020 71080319 115220889 671534298 939275018 311347442 373508086 154121302 537829493 743750829 850653066 105978356 812871839 413787956 776272601 602860982 952846419 675873942 699575249 189621544 694037366 314909492 627551516 370703262 651831982 1441873 25971004 262152827 959009626 253792736 545927895 149886301 713248208 708989569 733978730 234357158 535854157 51864454 818919739 91162669 737350502 303000558 954713495 318108614 326237350 490284821 608259226 115225153 466186644 469854745 752402123 969590803 988105442 68978016 837758666 15059958 785525668 448396836 790560981 384398105 494216666 271843473 986088537 391798637 455488555 226734197 436400111 183231874 274772883 501056820 771155786 825004252 845397888 647348207 967646536 332085338 728076785 34018486 512355903 75077008 526223222 459973022 922594018 560546784 731764278 722889037 768325675 51131979 300440939 157482158 359884501 273238596 811633050 554316181 815391942 311273162 565165131 135234433 798299647 264050857 753806568 576840245 694764227 390534104 413169379 409842781 807813335 55155908 64504433 473290254 526928156 13385155 839398902 670917143 769552630 213519033 969320615 815939610 958974095 164857737 915531568 413721334 619410431 468911216 678479709 79929290 688090860 267729445 621362206 344801173 404920003 405382039 889948592 370735685 426919556 756048499 766059361 457342538 926784578 81934088 799356915 379099816 609057365 88607911 153621104 59365134 684092458 513800466 878379069 903819606 983750487 275242903 279702776 566889101 834701119 159015923 725800655 463735415 933121364 736566734 948857256 102439647 863030094 154318116 639505906 159214083 759034574 359311063 696786770 271140536 712101180 568409912 664487488 405652365 964724568 792591612 943659984 239170410 968125685 188262638 942690438 264367542 881195894 114673689 632403708 276012073 420766738 94898317 455603327 792121146 907762741 335734966 369565077 515065270 688048578 343212547 885745374 542077007 727273784 727770146 847802222 113905330 314657309 790934019 973523412 516453731 679343742 347350860 929102077 214919149 866912897 306472709 629635807 570327843 953451364 199363283 347524258 468946222 707280291 163701260 240767424 294997650 600044046 220370987 609354214 737516132 987308226 503114130 978279011 77585701 242255892 159619614 806289239 387134591 496508007 278101147 511161663 303982806 840655300 399589610 818000601 54540783 623198211 454386294 993572272 93501814 369907279 704500691 846026993 319823945 396860514 350495898 583311835 558701008 776378436 498550807 707184831 374207315 390615963 110267101 837821210 644481580 827802351 611890892 765571720 794414966 883808056 71356565 442179187 260285050 296636000 52189763 236995744 276059227 778141140 409719424 675937057 191033780 824654998 542725593 578690553 208974465 751818965 789962254 931549487 237808813 716218744 525384074 569341882 445922730 876612884 554607937 737386767 137277767 862352368 252927657 295576249 344992637 590377655 70833582 283649601 302509562 744402789 401717277 678854945 269858840 397671245 634170663 986938970 588407169 733166078 205604856 519288907 424736899 749951936 26625070 937124462 884053704 915553608 788545002 955669317 443366667 973312058 99466390 490722168 237571348 580294690 423809109 477783346 95625121 313924337 553833585 852954846 297623070 405877242 141419431 907959513 459212710 521517953 91243962 560086620 106901142 320448428 230836379 305480764 79951179 736592001 251767485 383808758 106632204 544945805 31549381 251495706 387210687 413078493 386325577 494115323 387899982 706692541 422468423 990921024 130714333 404921152 139791747 917748687 264770259 611741138 95493847 957956997 121662977 912325837 169166681 800058972 552244199 883943001 517628085 804961344 217331145 598714922 528703893 776377390 33294808 692726828 115400305 524628653 207447740 929239376 136428397 969796475 290231218 403313340 308990704 948916341 280720891 408141084 869301222 880299210 207250889 341712769 87287515 318921040 108282677 867825882 269666631 563154379 154283952 841341810 682472602 914655958 604014021 960807636 216788509 379185264 572217323 893347715 571146170 914874432 689459833 946918256 571774005 888386549 711212411 743835341 52732537 170462872 78859672 576847727 150716664 742689504 328124776 967132873 470328723 985115843 673416985 883464844 21456837 111469393 297156811 823843540 307317153 740955884 793504038 824279624 541514245 757091260 440886133 974653452 212301842 987131953 508599686 646292744 243108573 882788715 435216159 877196226 92166952 809300241 456076617 859642210 446639825 480573766 835399012 989905837 692268105 993288997 742499508 837897063 671533501 787701876 644546164 710258160 92736426 148388754 243865303 861562518 43517835 85913547 198368633 987709705 23162953 832031108 117571207 633990899 541714958 876718545 485088493 759176464 691524919 961134653 674306790 859966369 540364706 985411343 478678548 635915026 596216786 747004731 139051631 180230726 77202134 987663442 481651696 780337889 149871683 442960209 39539167 817522711 406491216 732416158 571855132 928295593 36185843 200942963 154591667 554643400 489520857 833353183 484403650 578413583 481501485 859932260 268262173 998013687 19033588 938427404 146217169 973975228 272262321 314236858 354272449 535621036 219597656 509735434 9432129 251772261 199127187 422175732 70359632 164613437 163999150 603826812 68206324 259328372 400673435 473121518 29959952 984967158 571261834 860363141 517857045 520215734 22222151 825389793 266787394 604009785 744512658 845291515 291606665 791084402 261433711 895950143 115525372 472904212 685116565 834850323 818711304 973257330 559608191 907758422 787169295 892363802 766885987 785203105 26504528 78221873 2053476 95690608 138489423 162921803 500256572 779769370 640790796 717180218 25241768 324810189 229558356 407087536 714103696 829397647 540351821 873727105 76384301 501401292 230952556 957041169 105521322 346238404 319622259 498164381 838668810 851694384 414633322 550607293 639491380 836427240 233627993 807159363 364642249 763582820 330147438 919597027 516757878 563662081 85032426 339436319 395214190 988744939 58756522 460124003 648771968 846065482 473054482 698506348 8720848 860231276 317546805 879041215 339649983 706006733 243030070 422167389 653198753 683976760 74808240 92892964 340015483 633488783 570468314 938660794 283896064 893428146 187683624 265048658 4606152 850054601 103860950 881698263 709535610 962100266 347199557 739058529 23419121 603134223 387172730 730137829 217922221 576405511 383127327 692919408 257100104 528181301 490920192 707842469 451497552 833199756 124178105 217366755 612956301 966132756 536107573 989127831 34414736 545128139 774360768 964969628 462331460 502726123 136982832 966245805 1540776 725127927 284926451 394693846 261313118 465836854 436699848 927461898 95316972 530532677 667061400 754845486 9976205 462123140 99952126 232039500 426426273 429312700 442076058 467204904 560737028 664755255 408257967 902063895 38311045 906501588 357858233 602125919 2278812 41478750 973742062 983608197 403443415 828109293 183570614 597646711 550455716 888174360 800236768 806999515 709336346 724345595 331586133 772630218 131448126 347571042 62308142 811896196 100037014 608333801 803456619 957634149 60465066 130604873 325846923 615086212 364146068 970801825 545516908 687388456 486799977 833765510 510428079 975087799 252381826 936371771 208720587 386248419 202610006 450067388 424797272 516712981 357759056 541627839 119340158 249939317 425844364 476586799 209580580 503751097 438420589 560283227 203053362 862504022 229737959 465374722 175064997 909412584 55741795 407794243 656594947 994691735 96798469 252402689 914641594 944163310 304844289 540362906 133076046 704587540 507039969 548233392 561989115 703328219 266188588 386345314 236282264 666057909 761432926 851250422 539808538 794844678 164151425 652956474 10701187 780632058 225884517 915796755 845843466 974855966 383547024 535718044 717427872 734025567 166468543 965525659 122543061 670947834 26206225 364050236 365535464 375558478 283826058 535925246 447148753 822640970 198877118 931868732 899269768 951932772 372803301 830191744 101032789 574439720 13348099 884519585 331230125 608514982 21263884 990615645 50881694 498206766 537258667 875430060 149093979 492859035 784845775 858170628 803431660 895253939 602905220 824120773 545445883 719685436 696449567 751838578 45057866 969178694 4578221 958604782 848169292 962619656 26541342 810266608 473299209 842430677 240238879 362036875 87015378 401321132 456468914 948095864 76616751 905610392 227476240 818952910 94392813 999188868 153316171 596335349 324914850 335005651 320923155 896310892 45178850 476557705 97896702 663936898 521668412 565791421 396364676 481099720 279729223 488906439 23876875 969697842 11414022 993138723 515188743 659974668 323183625 722164148 512822492 712673307 109408066 115667272 623205723 985611269 144557853 945791113 87067001 445535613 73257433 185408430 220101829 479340213 78139505 331769312 438277657 600199218 398717032 956290776 311513236 818513480 307636611 703689326 198555313 914429709 243828007 278915342 544141709 730727240 235475568 979657900 44917419 980000855 109257437 830935012 60519071 830449996 103694922 237684584 9649132 994687738 33923151 193864118 608359843 672381736 675570007 786001820 389761748 910489118 495064006 797301933 35243026 424677663 329689011 662171617 185604691 952024454 17548666 863655447 830331080 946312321 253752669 420764731 225727167 257860575 603910530 994986558 273709846 753593641 702225318 751527082 103779913 122188016 372453812 570485853 70041775 331837170 380559684 517837909 120370708 628003156 193394892 710690399 675002273 891042698 345613813 812352481 214594078 739504955 369164307 486136093 349331482 500162330 109852584 850232508 186637952 360592089 98541736 719822512 294986851 564505445 217643363 648634705 226992425 595583273 856716864 893182041 67893881 807923251 376267708 523299937 70088166 276840579 453903251 774945204 419299867 688517661 868924763 872416040 754537162 977989731 81794357 773366459 100438899 206025098 65199462 901214295 587271961 622167302 296793193 487866780 597317085 726534523 113889532 130323072 344786809 552176881 536563638 591267155 143933145 855802197 316751606 763720152 46561070 508418609 91027645 339445323 437323223 791961309 577047665 930788774 320864446 843696799 318268476 813646524 544389532 683963268 59626912 95612878 37023328 905989872 120831300 640882223 85818386 776350858 158713642 176195990 509124511 832729325 221306976 467190649 18016512 422449492 186590508 995753677 525055557 682070761 28439888 446412340 679437934 927228803 618655390 849925115 120457227 479323285 421277500 898591416 332212180 528657682 601190555 874373184 352278606 427447690 94530846 591696193 380473653 475496214 508521134 775888530 177533647 372985167 260025534 751376700 444932220 448437064 75732656 897104734 622582705 919912801 55075520 337758393 348838654 670504720 645755940 906277494 120746008 959798080 500188270 814429378 121327541 663901335 259471929 735220860 301860282 736679810 12692573 835830145 131702395 952515224 176005474 238961476 99454740 426397137 82908045 231961485 648005790 866639304 607352272 750181002 45375370 336795101 362358754 766677152 596530346 847743185 37520195 199464191 529814556 745466354 732001807 755093887 398681828 963496526 9201720 231019022 751213423 951037755 315142638 344184838 521690520 682765741 32128980 431384859 165344900 222529269 266715891 696349654 48396869 78685740 1347017 701044896 726441068 728616461 984941998 991657701 303044841 370810209 439337118 707147242 73445491 236770048 545974497 687590261 78901966 370567917 41905811 211039689 89248560 353328083 730081003 772414115 41344953 216041854 620303823 660758809 559343664 720335891 86345233 722608744 564314651 634932620 598672991 768464786 87072328 785117951 62934080 534947243 484120683 973100218 140910400 461806399 533706254 965825473 109907614 751631429 548108150 844655744 132078323 218645717 586211039 707465985 104008711 569657292 58564002 136318657 329391103 663653834 797119668 874697279 432916224 940274008 630535069 967570245 552317822 897265649 267397185 482074121 62008878 569070883 348785157 816187920 531806404 610999285 388710816 585262678 852966396 958681644 306830445 983142473 630731674 972533226 975328047 998788706 595544244 809319973 622874468 808567778 221114776 399473750 268686766 796423353 198619761 660333203 483457773 631627986 67247120 673643842 46934149 931917228 122166049 760636818 357890022 619463958 9043218 986517958 290525959 917357748 263246164 952190664 545872942 983169409 343812896 674045262 53668001 803594105 4250788 970781448 610657151 808422011 286447487 876284203 483055246 608859795 236321775 766391346 10026101 755553837 260329844 631440462 193228699 954717443 419208717 687362066 233399262 362456040 86662835 432499825 500321605 944358538 241493418 547610445 9909295 589259416 55747514 380295393 265801787 324314870 100738708 805764390 558965921 686683879 269803322 869771769 342917700 672897000 106371781 654568709 876766212 985112288 795502976 994112909 196084495 412005837 649155198 718101661 150439726 327824696 658940913 940838495 496612814 524156264 338820543 724355727 362665525 812789883 535066467 606145778 26208421 334385801 280529332 966880737 575252529 681365962 8810413 587560712 704933727 924817695 257018074 575729660 884114094 975431832 437271188 709308940 298482109 392347353 187634655 803831412 57010057 540138225 102133068 908995587 271505479 316390866 84818746 863303893 76843107 400162889 264743408 912412342 353927239 459302071 361183502 578850306 183698315 516561823 622195597 946355173 668633957 883962742 466323638 552148305 354175773 623056766 571449910 727134843 101175202 971673822 320600934 783249989 738527383 983247398 151678620 583292591 317619945 916315979 5014307 630889009 258006619 640448323 179254114 198285343 63570778 549754296 99770913 175316130 635661231 760639124 60436635 947251311 140669946 783488564 485736164 928457504 34518905 555405109 464195804 751073687 114406200 174934993 367295008 382069896 407154368 816317290 469544498 773000073 650703932 851412073 121203879 716254318 335408033 579527854 489042808 617280539 38886862 620651896 521143701 910793027 515700774 912292328 463318064 705083304 35926965 462699185 65475010 376718461 186506681 209121712 812730546 908147767 496065849 899743169 208637311 392816055 484321326 920101553 107856161 629077349 561029897 747652668 674483047 681648973 463176777 797310623 94282580 614833740 354308828 590595817 294149010 810614714 96125232 761510595 107859088 348334815 456708818 679743732 178910101 538435863 502364037 853136560 393199373 532883798 828731416 949576713 108277709 147904250 457860641 892041885 21176823 335201375 803220985 955779460 374149491 622887665 650140354 729755899 119427800 556040881 339487696 726806814 302391346 912268608 183629731 281892361 784358449 951870976 319942481 374731622 120481539 628969815 603341649 804062783 889424161 981321055 143994092 968131844 341871453 770431099 46927246 257018937 102017950 236501852 46162074 815929848 870184392 942169516 336470535 817507634 215333967 296768150 32461682 349853887 768790629 938872451 47828499 464503222 245130082 857917090 154097837 161570150 1435562 480068923 326657711 626254397 7390818 370222720 725387451 743510868 300422701 536833939 245431151 323028670 317469992 828113603 485241606 658371177 750723459 931844840 104041031 794255064 40280210 286796966 130036247 689609675 510235568 928493100 592235757 932722673 448241558 662972037 400175952 714171042 289541182 374360199 510196163 607545083 192138297 924823097 655766067 916397772 600227679 818888595 371055330 554710855 757419225 793080325 352829892 804436009 92195315 141452049 291499552 343816404 145230048 979668205 404218102 923589408 395607122 746032731 134671510 971103456 638350630 828561094 22333599 241458248 311814293 752768998 351874985 433754405 191510316 690649619 433071040 768284389 197430506 607031964 151823307 432765375 748093825 935866635 385011969 509640337 212611694 877540256 259727686 380272233 86791461 725764604 370033106 612343455 678923429 805931086 84568164 680767579 427632661 752835353 634232946 845088081 244455444 270662784 547248847 858397177 339816469 736372971 817208352 927021243 281585044 840616089 708917756 940555011 287500327 754917208 4818123 88741641 77847954 386439045 552846536 705990622 345724718 570782919 762835892 973795644 590827847 622462088 265083355 513433624 37909204 141907501 282343604 618654496 79498513 713221503 85244798 487697277 68016423 341071622 163242599 734490522 173829415 319487055 371530358 742114474 223363464 233650046 662417100 782271747 212809500 868079849 247889682 754422428 337897449 672696326 405277567 416361020 24061018 351983958 405306298 658788036 416744379 968157299 115157783 259418756 508752358 829452471 418013973 964922958 17405618 788932359 554416138 962891122 694309206 732252705 551565690 823742899 442122546 581330705 228823517 467992990 204376544 233976481 926842042 983968200 176411469 678482586 301546486 493228009 311090170 328969572 110716458 977041587 53691069 189324741 364939971 765942075 76361518 733523720 82481265 476461688 89040796 439148482 82238466 532390970 843970680 956117846 83439627 193939329 328527047 664284809 254998363 405398792 535449883 870042145 13451694 180509615 401476641 844042654 35656127 201031001 739919696 949793052 793640157 994925403 94030723 631047102 287063907 576568473 700121370 773280381 478886423 874341059 210198139 289722900 579920502 923871946 537135239 891875706 813250858 857402593 223512852 399767414 309885001 799716230 184559906 969780726 274741819 868678300 721978776 853362766 431027784 665665602 39598676 672756915 208681485 320150198 37707762 745138895 590382447 615312235 166350347 261141510 91035629 130476726 204053644 648986489 29207273 66713886 334055634 884855136 36893246 463527823 68399212 924449158 44069464 538721813 556576620 872314560 624637039 694447751 256169382 849492168 836800872 849813779 86895475 882889638 137896751 929559452 620289325 646783973 265658166 338122128 762534425 903162145 341419447 929491468 79633243 597784198 145144853 197081854 376227060 529050443 669159900 747348778 181722924 591202684 533176362 548259156 5198011 144571356 14770271 993982245 141197080 807616681 539215459 783834280 613928321 841724751 267351402 289337631 443535558 863054602 127743752 463833334 417552087 556452384 103030676 378271846 124117673 860243910 37338703 788159492 527427254 851459699 947556353 959208544 37042797 925856276 21517538 645941390 494522727 860324317 154517704 806695123 120109866 641598919 686642764 931442579 814959767 823853546 130142668 432190180 164005462 984332466 123165935 338153347 724554464 939878786 58673567 641470999 292335713 588294441 236396350 263635546 289177159 307940002 398155331 555826157 189876689 395752439 56815089 902216720 115588541 360203962 113760544 279017809 301774858 848538520 465498174 952945813 3150755 289455673 324082482 783300739 17042262 441287649 116950108 216844673 19038565 125510184 681238530 729483449 154061001 799317445 41298134 538699817 19743868 61457949 472485612 743766634 659687793 684194706 121698010 403097855 276043221 674515050 329412596 937840483 254817217 530250711 94695368 298374107 652518753 757563179 795846130 943260128 417023658 666530247 681443414 945346572 323331671 999589838 445943115 827891131 409080608 456965075 17481018 558763545 466655583 532765593 166050161 564719212 43600376 194102512 86606200 89921576 305802962 866003449 146750972 702587145 458456330 768785102 373163996 895985845 581178970 623978955 303050373 316503366 603918231 670893315 296814508 625157612 402596807 447924001 609977722 832942194 44845639 120333117 481702724 999836980 245803078 590427397 545481975 595575407 352448119 790270956 219870260 940370010 97046136 674225169 534969928 996505031 724600736 741623240 155604170 560973623 414859863 784858400 106793063 532722686 65521554 304973606 4074697 226134363 491762298 706283907 762557565 890061051 618193357 680000086 500929473 603320837 120526572 526799286 556983534 890660935 481510687 867879838 28858142 216862557 43894420 196165529 218675342 715450900 210359327 957397389 394745110 486103558 687980255 708666973 652106692 903804128 436242517 505059609 760722750 894603904 655625375 913571209 306764710 774005849 98976502 743096646 713570898 836888082 36407844 864239940 487901355 794270052 354882523 708307971 186249108 528258006 894084981 990804770 70984830 208509179 163496244 469603118 582427642 981968237 760465065 778336624 183550907 969062654 169794350 226092378 35660511 420643037 104485630 545391069 335432190 648421370 465173719 477831409 413693412 440824765 349614465 553707487 65266917 639671016 373213322 492513311 21225177 225076661 546538852 573724969 4817326 33858147 496617091 972518058 74225584 982138278 507008346 946912433 538025335 886694472 77325299 970124212 634062108 873841402 559786029 633555184 513863102 591994442 1597007 965357217 127595772 630446154 394946420 419591296 84182737 441703893 535893100 600905995 200073737 503748804 517756403 578827358 125362034 726894244 94298856 875114476 219322657 391495874 513939416 971533638 210979118 575270122 665242109 976022026 390575154 769170101 696787966 744488276 417065260 443531300 574743621 786430472 794541192 842793821 71954119 172409888 212884169 936140149 534442739 902953397 893483545 922607267 182735921 481464041 755871775 968469481 495493063 710636087 281070959 292324262 255379678 754061491 515938425 785347113 419346118 923795615 70093615 423716153 631739907 749078494 320626837 966831456 828091650 898564283 173128965 406130723 198554789 239947954 962991517 977289424 871200324 982426904 229019246 531138991 717333108 956066289 648690345 841332351 838045833 994995490 250887006 905497136 344771022 692273017 29400755 909153251 286434687 902398078 275639368 704745760 258430614 579080728 169421754 611169321 116630990 984883732 722215513 883324343 392027181 656952572 320894358 797911592 320605334 980988325 138395927 502874044 248197850 362133060 736150283 820135815 64353818 534973200 197158820 665094504 211426252 691970261 897378207 952058508 329404677 664961697 170045166 362403666 137931614 266268188 602896293 988632102 22062763 433250179 81918181 963584603 12215417 478557781 302498106 869204085 375320142 417876499 920353840 951111970 93530880 475337135 933861712 982491733 156212461 418161876 56176279 499432790 222231147 819875391 686009019 983416116 845176251 882150988 141926292 816561329 485873922 719987218 344640841 760610071 96027891 298293920 515972047 541286250 300714162 583665317 381266433 410930865 60785144 602097768 134109089 312509681 264201034 294208147 61477109 375986844 202496633 881015665 384909830 798684069 365780344 480029483 210565236 632445041 348423302 990646635 23368683 790386121 730106991 770267397 300249933 589436036 534363378 543356636 494685351 802630128 228272105 356044558 571187922 770064644 282417248 472910597 249643286 872267873 522694688 624920946 574252001 847840340 537938873 816739439 552506345 592215664 127735608 484906424 453597575 518412750 102039563 955831227 191997750 457967331 428755803 686470985 546041843 972602758 478485213 866244722 796720772 941916096 633084369 660481032 341969948 490639405 270464609 303591446 670766578 814981571 501000051 943086591 663348368 779256221 66837546 809185620 330484826 975667382 45135362 533513041 326880787 860454992 68050403 74966822 669654184 993772683 225277640 494880195 447830698 720365352 22790919 29900464 77607882 559522279 53264259 710683079 636643438 804629520 622517615 768481881 237583681 694525173 495051838 914920477 12529606 436821598 656957 463796545 206657584 462740794 438883424 597247540 731830718 812361364 9368611 90466022 105450465 636161652 83867886 851872935 5943546 980536227 157062637 469010192 228123157 418454251 232237095 850203949 643523910 891910095 443676126 873316953 728398080 802936824 243204014 270319877 462914564 689283408 10454043 34657756 68182361 616295053 621273505 916659675 216314422 224405344 163502895 192147820 310543838 597619813 617660790 660241092 297861977 939092980 390630344 425789784 265482719 816518997 64798335 478637082 314053222 917774118 84372956 248834809 267359701 531996812 127978849 588602685 811132969 864361265 165259253 976534597 329118414 883376267 301150233 886511885 163886420 896185665 644539888 752157461 44159479 122180497 222794715 715581820 588856271 626231259 86484512 586758247 155959976 175511467 525873996 581046617 24430154 450098255 307667568 975853613 455760342 909595720 260216817 537782810 56117004 430361629 161985896 916317852 14310886 122356073 26341204 989506919 6959793 828970356 599359316 766590615 771646033 969251580 44650708 356453015 370083390 568391283 138586340 587251208 161451497 254890406 448842063 993774395 284144577 353042572 63312284 764513432 759415600 778453568 179098754 833910805 25906490 571215897 148596191 742150171 175627288 446155604 482910046 959131938 188935159 752520408 173528133 948376116 256122115 462288803 302475949 592081410 226377661 384029166 421957925 954091977 262819664 437114893 720937030 839101339 131640253 517059120 19590065 336684071 330481347 438841912 267308709 821211318 108231863 931178180 39892977 910864342 334022192 688078748 350935364 471914235 104775899 696904678 39058990 719231831 214449437 871579974 794563866 885451501 295829320 561037894 511042186 990930350 247359148 497294577 267888091 756612677 678201218 964114436 905369204 959093477 425446132 593567516 726265945 828088876 101592870 512464878 110347557 189322926 515800239 921884585 157568682 928335464 158592701 470742988 672056902 912669859 361875693 806796900 262454356 913311875 761927163 975041678 553342344 719239368 431293775 886246997 14276262 744781744 559009006 569178714 296592531 492959143 345664637 668852472 502420781 908007342 89518422 823150576 276909872 416713068 61806379 857370101 604533510 845242238 336714963 647399851 86613183 481691948 98237058 366425219 109709938 807543088 589339967 937489046 488864242 684446717 601736935 942528879 694902621 737480152 149717021 539635309 83568793 723754836 662740903 748802048 189817397 940039898 775643554 837684357 146584251 213013221 490666742 830339765 416907077 812911568 14299821 341078090 312125859 923995936 433564606 446227804 20143954 333011020 604846008 672035340 525829146 716733161 234665095 976891821 704182957 728399064 95069168 106083503 8752172 581426682 149217575 703004013 160320798 837692375 3955721 45674259 29082868 433319676 322042234 480999877 805255186 924700673 864142972 904148142 51045028 987694750 392000310 967836085 601258224 876148253 418500553 724124732 547472103 971682920 281315315 936751478 106433300 320517086 237414464 336682774 659466654 866601900 126098276 795732344 310919191 476588675 510462126 542688219 304409653 978180125 77544840 903127722 509047137 711354225 31142914 382261460 184274474 990316647 365638702 555853217 358522479 938631190 207936273 280876825 224987497 475724338