10000 999999970
626152862 873788680 211047763 390941740 978731391 536784699 690549069 283157204 220661578 288484770 547230658 506721660 561984544 345639516 865602250 706808859 974899419 895820637 776741219 514846780 176519729 161555972 897800188 295663353 205152016 836971114 904202012 929077812 797241695 596371996 294089946 953486609 40703485 187333061 291856233 255411060 752277684 3941002 932895241 840454818 893729083 529442302 659434537 590070554 695469925 388198901 356097290 73348808 760100481 226653151 113901974 687942645 937977407 374839124 749180241 151196538 400791451 187969002 553099725 901395674 691847889 979222896 726089254 846617143 925199196 77748461 657381812 791454376 418606619 53870612 77455575 199709377 859725039 398810325 200218262 839350970 570848035 240196842 721354674 994321944 260946082 927171162 306678569 943142067 775902400 999592200 511648395 923325343 22998587 380223691 405864912 610089343 683704304 180305114 957889148 548143196 707062838 83927843 317386557 336100974 676919936 990406537 518507511 737779695 592173591 450218352 493247115 130546331 227633922 347652340 304176695 297120877 906963158 39619521 304392103 401916049 56099400 820503767 963497737 721006617 392690651 890228024 373012232 303019055 867729538 123431122 287234307 727106971 149584087 579486260 124830566 778482832 360521033 510111042 569824199 149475830 708303923 401383212 31354849 457743574 706004088 375175684 3140821 441055349 672867082 71022217 427470267 668300377 336951297 397021053 357990552 509202613 372869318 105220313 823601498 45744371 49761786 447142136 238958731 868794514 374841667 24659962 198247605 175488963 402046749 932813882 530149578 429231765 142493720 571349432 710495050 489240050 258720828 444026481 553893552 376196218 511557811 161684826 56052515 53261414 310923234 949766803 4712169 304968975 961160943 103098891 165889532 665141616 535833577 403636249 790247759 553087908 925269989 191195573 774076353 503041714 135137981 663099506 749679474 897641231 910556415 633929100 956093045 196830967 940519749 564117660 572736773 117311484 407895329 268442545 523987875 258786820 862672910 290112103 732157012 667942076 404518538 94761072 725990737 139774559 589516956 668297732 487380689 360020799 624438544 13607021 259505678 444987602 652146784 428034199 603626646 227020445 79766003 383871090 664608889 652483888 649194010 560507734 248492520 901119736 58513006 4400014 707520846 639434519 106918134 658765469 533183038 268379084 270656564 340778455 441240477 679189285 447413680 393585001 335476146 798415230 496317768 358355021 509772338 720557380 99245192 686932318 389786218 731344160 578911830 651019170 340773710 790906770 423946222 974774196 125773002 29493564 28912136 285061568 369203150 165510435 273075119 909831167 941145734 223527632 353682801 716253764 760369146 801449831 328474814 936971409 247514643 300182236 132762283 497365489 538604613 919019364 115682428 474393863 682670840 59117430 167818844 903477492 73159044 720611387 897945098 731005961 724691713 521463404 279893489 366869463 837791726 785200701 105111328 416024347 11681749 24278051 357969739 642734887 426684377 958517803 494121130 163370736 260927473 198809973 805849852 594619100 467196204 477551994 762963172 250062790 299120794 880519573 919641028 763344024 620402078 46281620 451292390 865996097 466461958 516085907 586359076 825126498 306324644 921122605 659726853 433067553 803014546 132234115 912760422 817955235 496668575 243725724 891078067 844421540 229471008 230513134 625502031 329076821 844854471 828969999 639446548 215297537 799867257 479604751 830975250 894442703 61953452 632735043 716278010 409535501 187772124 331494776 707857438 16089948 497211691 722669078 880739871 150246685 325031796 120710469 68050439 859642960 736179348 544218341 163865640 908855082 494239053 663154215 358042948 361442461 351598696 597727037 160820442 519029671 177813372 832178988 390224791 747778316 553689160 844395170 461448561 465937792 35363634 660682953 911381544 243057449 222782044 920929060 37494124 428270367 82121415 389215925 835337841 986931075 705303986 451081060 261764166 140730283 622067143 844593878 901435230 211513071 35373870 72763072 941583307 161884270 478205319 576781714 994818503 848767004 514147967 136131652 53073595 54141664 788267226 305879433 283858380 862706413 470731003 311424574 557527118 417232245 903900332 989812877 456305494 285371078 714507907 180234633 992794324 16743206 781454465 771810494 662493365 970749769 771356240 549373854 212685856 219446135 334256639 781171308 415557169 224174667 750178190 876761217 172223998 670242038 569757960 304021115 474673029 97507659 270769772 642459262 70441774 336278989 617025843 759020955 911593269 879945516 992130237 809029790 498555396 766118644 445719123 598413743 859742556 473055346 662549083 903496864 58932159 121920805 696683975 169116046 437418075 955718158 957671281 35863796 493934282 946313291 541037372 706288663 215180695 333144075 208709142 211689609 284939905 928958488 195564681 837129415 286234687 833427566 793171781 877686818 426115289 343509920 866581014 384511728 834131125 547722209 570496014 345905483 690426139 542464166 783425230 45771957 429022215 932617303 208414089 738953146 365957630 635176806 377369794 210740591 278809470 906868100 475734367 398623673 415058924 470655154 997760506 253202258 286339030 360415163 590242557 993787801 385353904 604226030 147207121 474654033 279163291 445717350 483796343 548384175 963239224 954071133 439113074 40307944 333969933 612314959 484503638 945477065 288732239 609960491 744718248 780818675 356228777 593514003 117999467 982320134 411233070 108563057 472546434 791740080 562906337 89164613 822832687 94083344 936481911 672869622 694429618 760510593 489344175 94316654 666410571 859339618 19770778 42054260 63225014 970770523 917562248 507460045 474878366 790500079 233139308 842177257 662727275 649485239 152373722 819297782 262759380 789761047 895819185 481835813 745881869 189909905 361281333 456753041 923623486 841476198 350467210 408315771 247763093 812059761 658479112 337656069 707793748 165646182 853237171 91961986 555438508 854311755 431606559 883561960 503381345 967784258 481828333 232822538 1869382 507199020 512738183 779455153 520791828 867859715 498946577 138163956 660390070 690675791 32466808 374668315 127936057 796693982 351907473 911424393 427582133 936050267 491449220 266985455 407753136 633369037 983285040 825755053 789492927 828878784 982444955 881558132 609448958 980402101 302197067 4427626 134540113 507097024 513190181 977292276 867542584 301147016 337275134 830953754 343849614 598982939 725403220 1575528 518579572 648204161 334929608 262331603 316954202 513921097 89207801 661974949 652424198 20356066 429533733 857064073 31949571 51772792 571912721 764082251 936129170 769601394 950141784 445685355 12223283 576564724 191468636 594053570 214573220 980735746 889193703 880931755 8496831 15851530 654186599 266648697 295922526 178353967 783837885 471860845 926803424 963777709 405725880 972023122 881147354 212212570 830795733 693585603 924508691 850964827 146993742 684220213 339831599 254386615 521672011 429250005 410023338 367937057 709726175 527419974 873372659 553499710 87747055 30826627 237771371 355722944 903962585 826983343 856343775 455240591 545623761 695702189 660403229 133420953 762543485 903342111 622980087 435306235 688675547 480410345 420610992 446254762 235580812 835321731 322592021 746649929 932127919 715013907 490094175 724510612 188366570 192687028 773503038 747780887 273157976 96617567 275619459 463440928 254796691 788970462 334506193 535610487 844451443 816758944 109749639 125098200 825693400 721160684 640145995 899797177 699725993 323719019 439851913 642829589 466089360 484776427 191194349 415281874 652860253 459800936 336346297 978812646 303193783 257955247 364711887 303881535 814641677 845739661 762985966 903280455 728625143 881200157 526014104 749778467 560017606 661759670 530521701 809519695 641824975 613277022 316342844 41643648 167564340 197290995 796463572 701130645 21916386 868996432 332328982 915259609 741498768 403701823 13355990 878465297 392376490 526211362 49232602 6856121 67185118 401733264 177764166 669439836 460435104 150679925 683984731 98328685 293874661 602062188 104451876 941710266 718547968 77637084 832419690 421575945 11071560 672095559 984222475 747994385 74692016 901477665 683238872 615408562 824957923 143212230 839530603 421655393 129040309 579115851 598421967 27196992 962805249 737020705 863546151 881835298 616246871 801380121 860193443 681310506 219136631 72144529 727038859 414312557 705729213 220988992 416479440 486663390 241033788 283447066 810939362 296933778 181084882 989275845 674988295 634762111 194844135 340805176 233523529 934200953 992726690 830632495 569422044 12558547 991302966 306948223 324749457 274807266 952248945 695516267 540672757 780413493 957835373 827568939 901534840 999440205 77936573 488653263 231980977 845793136 225154555 324002286 705262207 467847380 844244283 175373117 321124718 231231139 24544630 713960919 66763713 192357284 845935894 879182206 69241644 350227098 757391824 50204900 568168822 61188180 219346325 860511558 870137339 643210910 669631151 405891106 14589295 93169587 461369352 308254405 379676263 712006949 299685550 881012375 919326100 574323529 102329730 713909957 490676180 425350405 215589608 214423315 357413312 436796207 463471084 755678483 787015289 692932443 378594740 528795528 155046469 328482416 741982425 535456155 681216638 700624702 286322166 765214463 933484863 48432734 915448993 104780726 569633477 219499245 593939490 49893634 899550092 800638409 743063180 524649366 191251464 682152569 553472123 924364528 44414487 608798125 296066288 338110135 453235426 839041908 672085489 235104923 589752392 572486850 684583786 771775107 365764090 368268741 950253607 234131073 127189627 124237192 755734257 904409775 449220215 354468063 998379858 174371974 403953830 375775330 619201113 531896845 913211039 430462953 782877016 914029498 886859399 239340499 72763095 309845745 101073400 347934462 494036902 860997875 492329750 911318651 700060958 953055919 70498662 502965158 82123204 222058814 770073430 885425531 182900888 650868971 493941951 509965783 159339933 80536201 610519207 778895871 680147526 343687541 61053701 868020849 870484372 832005860 147240332 376173789 999770329 192973816 118870347 40736094 430660988 326375278 86991948 33698215 856250751 972679887 350212288 560992438 14461137 845454058 527808120 239890150 88142837 218333024 833947825 129213831 292461963 660883990 884126838 960457347 848613824 380541697 674408510 892358936 584334229 106949252 126066564 249141159 349556965 380863997 172050938 33464939 952135895 730067523 952310032 142761131 574006256 936105746 930477305 872704755 722230603 993257938 480657920 701741583 564674010 286337933 66562806 724020231 616675192 202578736 514185937 469270904 913353141 17563604 958484532 837336793 687562866 684452147 984186795 569833677 150926672 620253687 402735354 800927594 646986387 323119129 282615739 904136877 757698311 306182621 665767066 584289477 259236046 191485848 272753323 688658642 75105068 933534188 509748506 710383984 754927899 981166227 55459616 692614018 520457504 890727218 959395948 340591456 423344961 53850375 183168847 833857159 72453283 666918399 404810124 733616695 345518729 988360437 132150119 328010633 351835112 783355169 755828499 183677665 364240184 857278398 201783645 749625669 772813620 405847088 472832435 997538889 161330472 778684279 810688263 84599577 387368765 221805124 768832866 407537246 308468568 75937926 87715083 286818588 921197269 660148920 986568803 571267652 130037777 118538206 478676908 900892571 816264048 161679772 819889441 423440585 86311125 429254284 261440561 991737151 168483894 475736579 672132636 109151729 806905288 269833599 522614317 586118711 89621968 442856813 404743414 320233428 927281175 857098673 797366035 563411077 501446751 653306392 245153025 300469341 989560608 625436348 289321757 516202862 435482015 440116241 759308998 313818816 927252198 77530461 769857952 643215948 30512082 170859480 798426875 956690043 225951632 253655597 793023117 105349495 479455858 888928040 640069480 330470234 905716283 21240945 169566689 698553894 352869219 583743404 709385017 301548315 808408880 861780430 887491722 353315883 654249071 13703578 544140288 835329464 52879878 184281905 582166444 768703913 289941964 882341192 516586210 201057956 507954518 926833717 894957546 305398054 19465123 564539331 519338980 747187028 73097537 719956176 341656889 734107219 9309622 756260965 236084504 262864368 406668310 823011344 93262585 667374958 978365881 381858486 503427692 805511139 73164025 868382970 320464278 935789725 375859577 491349189 328895935 694027801 554281584 244702828 407574247 268941272 86028425 892266023 569371581 5511845 106190854 561918173 506273720 413068536 190201478 457176937 750508965 322103018 65822437 444640434 112053673 923698102 498447458 988558148 636876969 27664501 107832039 926267336 365284626 71765270 374744915 6855805 25075530 776241047 613099431 108393758 570015951 147327330 576572868 595964309 483196046 471247576 756904136 731624685 613631950 380424681 229648918 418862319 837925224 104946913 484529857 340828677 767826365 927596677 561139514 502846065 629164045 194152639 765603040 75865737 328231422 810991941 718425163 24034195 149282994 787239305 773344282 536877612 255387620 602506894 298344678 441631249 728231128 849185110 105537929 424741204 404507869 688870900 451128733 479347878 839690410 795353311 394182593 363802067 328510455 359846418 486832023 208379024 773094984 467864951 908149666 910739869 982455906 579984964 467361484 978981102 959898685 631889312 455419980 55681788 548621609 674627714 113958237 356235222 518267943 273473291 268613730 497488249 40088048 440823853 857138374 862777015 225873391 718556417 100648388 346966174 304925701 88747430 965284140 208011105 150326562 120157892 823253810 611960895 723426222 572212411 335619950 553749970 582428264 926018298 21453555 380844380 467685590 459726475 36194534 31940279 772818680 527346565 182596457 286005448 104861072 39552371 896893507 276304603 192834813 294722199 110386073 429008648 699960732 611182808 734781228 392993115 294840992 760467708 757387631 189598978 397498507 960139218 793637398 276640762 613843017 682167308 481716827 116655850 658410726 473712607 499267617 616124677 144825036 73690147 976180984 697335437 36428066 99423874 198205439 400777255 134991875 245426883 987047997 733659239 423183027 711211928 699941578 864035122 468829860 398341893 650126256 646720956 641252543 315131873 576176377 260286073 878364696 776892959 901281229 142041087 602604886 948875061 410523799 474467226 125310430 743765635 993050584 389489111 977791384 784666385 55167462 833138002 703684723 817437089 798725540 327879079 894858397 891384030 197728361 370999746 492352890 707370333 554721866 584641781 805867078 652530723 680654475 878825545 412987554 553166548 161232223 137379607 155953900 226352043 690532568 517733249 597191295 785315895 834325934 519917218 787448836 781419792 473242041 917950131 270354756 574314938 158493493 469129131 534417630 693328347 558834936 810092435 123926644 588982454 685500528 997219831 701308561 472823798 209014111 31236275 601531234 534032909 862959128 206583770 459663599 796728511 974584914 374652612 9890731 911095950 766683498 478309564 417783750 375300528 857669057 366021733 254019520 813049175 205960945 660235109 749864767 828179219 246412665 335018914 863679421 656869508 359838382 366083078 500420138 176187978 110580162 416867050 734998654 117990174 587313261 551019630 209654039 105808817 119165834 204910388 796739910 390409960 263304832 707829596 775145101 564551332 402812997 488748909 874287675 396918211 164960836 299038523 468152369 812594795 817340948 340614112 314554370 526904703 786508995 324392984 877193964 768863385 664652360 595021311 793968633 523449982 757862084 944985325 813713789 150041288 962464867 278308088 902756325 776044867 100997704 728446849 100415493 250606362 839313728 101323025 161826872 565106051 272462971 15606441 376117976 617836017 529745998 84757978 294448469 564390880 578667249 200035194 924561851 833226542 536834467 170921402 955332377 736011013 186112886 232895932 994686446 601751702 32610739 71385809 107359465 627649841 891413024 132608387 734296781 796309039 926597363 490633343 260588308 779963959 81947967 383337751 996083722 588438025 495439750 987973711 50685746 736933764 9872851 77203220 3882306 668059965 738908433 987558322 726410018 424006455 524639821 799157635 793184190 619761909 219055994 343197227 754111585 211165849 731471885 41206281 628691020 451458235 641403720 628244799 959496201 754162334 405630138 409757806 480154294 284935833 797108564 402147482 800156722 285358379 139793651 741308197 170621928 441946246 880710134 379498060 282327472 847878574 334797528 906738645 95680455 854304567 501501112 182250665 116362981 727424757 525084778 404672401 784878053 848385731 64512383 103174132 849035768 216034143 693484345 673924837 850090510 429854039 206345010 722204941 770037793 232129765 955152547 776257321 408737183 518265521 115703577 346486929 265831675 236618624 540201692 945660342 674101240 815745397 702167357 168571202 883507458 825224218 227566399 983927694 394665774 792524395 283585193 509611243 358959458 845256018 677709212 36054870 252764416 109441240 403475607 861476016 224381529 778522088 894937917 422352546 637043897 252632398 217810603 414326450 479150685 981774862 901093254 695927970 428548159 79812266 329732167 404992259 822735285 91744033 380033433 509403494 875188819 948532012 937828010 751818977 346823329 382838952 572271002 418046461 135819196 770465693 313249773 965744600 913044326 873399064 399216380 233841934 566259951 789366444 531011219 249157590 366006177 300541340 695560523 557295637 632281215 268956594 497016519 790661951 669977326 625614424 309473541 268818450 474304336 480448543 176541379 892079056 728795750 706687399 446146093 249333649 582255631 406394945 806536932 566053763 559190054 490900378 231565030 141137159 237872290 851069819 373335629 557845809 76064761 397107625 345377707 153952048 887354805 50565117 487492805 199756055 447570279 236765357 859516638 991388023 642741459 639744293 463588898 191689560 589339123 871999872 161006277 944656811 287653801 146099440 464626459 89919965 199487173 503557682 315957789 431662951 232503496 838846395 886438097 592413332 647282363 107980946 655263672 47607374 408277386 714128634 13490687 617441299 318409386 647657477 485527363 95735660 183649632 13611857 215102125 36753182 479389594 852867835 271151553 807832490 962549234 630053623 102577958 313874870 287010143 83822091 329221629 780016485 656071051 636193545 324429936 385586447 157713928 902789090 231733885 148203225 137761864 823587517 339475183 267824296 599432724 830379268 28204643 425377904 56301232 345376697 288485121 384305528 856422393 117873110 943926986 984830208 385798572 193972462 889250534 960993485 229443873 286974385 35159279 786810649 149877812 766416495 940771728 646023142 978810673 13724923 9632448 830156061 575393812 512028702 699802813 951871933 288142452 83456557 694544192 51610087 826010975 254188036 847796606 202355818 299195541 911707326 13798711 27072586 673416873 382709018 975818804 86935408 330643483 928328521 525458989 629263581 944655726 244362192 969733102 327429713 818067154 537238937 824143 247487615 394465196 402330192 448325234 347766487 587464116 959485511 110318798 699139578 360694769 495815592 837090293 273954994 896713850 511355743 305179173 957231925 127393865 269657534 796407043 554508133 107425839 439308597 913211562 757587375 18558939 666721868 709774536 376550222 631006863 319949926 13140063 636873916 350719744 568094650 193340329 760642606 402478683 156767631 426070278 662685998 123005152 290217883 987900815 56759541 920139398 243201916 331513408 403242760 704229638 215164523 210092529 346667788 52378242 115881286 248502812 227399923 894025218 8519911 4788620 992791203 802990791 633754433 176667261 666836069 520208609 118399272 929582126 312537741 126537156 264365572 870495249 427568770 564979882 330489162 849798703 206194975 298996842 426597312 159091958 727473326 49114901 531376733 991015171 531670675 878563826 679294734 694420179 590949255 653009330 558976657 765931987 715103921 810424398 461406284 950962125 694493429 615849660 985314818 126851289 118510015 339005896 371285930 696751482 498291835 814128008 872730838 70927049 858932204 627081638 563410717 506944973 157084082 788623945 86851587 998627764 93034825 887597337 838229587 555990388 62107292 688329910 577441587 767694626 148008842 530298180 288629757 687225504 96399569 452338929 922828840 160559145 592928543 640911083 530158784 845917946 884393744 443439963 841294177 967634140 531582202 966028914 888559107 988791148 870027734 898184472 101018007 146629049 539265039 312952781 618788740 577296667 123445051 876701667 426511640 619931796 776303454 37715497 153675717 299153965 969808423 430795418 99192159 817460725 857343728 372494362 15397953 993593518 394711521 843518508 245760947 116436982 801531383 545525554 700401471 273395093 486557187 93463841 946253003 190057127 531376051 944769997 63837812 628155518 728461203 513383667 482883681 150411277 330317315 390538137 226828308 365613953 880744789 312550079 691631209 48653663 421152859 580499865 778771313 227936450 620666373 706729612 404829921 111363713 180703662 823983009 196314796 482547487 875024974 455687196 520921744 972886139 353782106 256426346 141970396 988970553 179079783 377934734 399661229 621473077 433360717 573997704 291170380 125682089 69318577 804921182 507983657 666723006 735032027 379630286 755837799 17684458 67523908 998772576 958811629 713327850 444326515 279842559 703562586 228615443 396083421 820141255 72577014 576634623 141211936 366544415 262384258 764941138 598694379 863481921 866679943 460415869 866134969 964237871 323281691 538755253 183224140 21944027 584450230 513530070 765761823 24062373 279260034 495695528 667290676 289494973 381024950 938950023 251840298 645981658 696817636 825351050 467544366 787197970 149510257 546305170 405601290 520438931 301839803 924875178 844500356 237681150 557419102 833438011 525659942 174184372 27290194 213037556 800431522 619428659 204870237 71953980 223863720 911386951 431481907 798524159 73123037 148094529 891792087 738949133 11415860 997862265 848909937 457915718 622537428 359801265 733727814 148462529 682367678 202902949 6344554 284711755 930221143 673880988 16010009 234893968 422812472 966594182 256527258 681147841 619229378 830750895 216515800 344525406 823351060 675304232 518148934 542263518 511665864 106115271 375237061 13724850 613017058 994437595 917544917 427166404 41561728 872086224 191649822 69198614 33788126 391446660 578296168 363173173 470247223 451873193 988104873 671967414 236418326 438317438 711138538 829355319 45966620 353955100 306201061 436766863 797441047 573504150 111895166 994615429 525141003 177987843 965529347 490105367 415066333 798794238 98928556 123941264 678941356 335387168 721675190 60792309 789787722 876339413 488058905 848871033 577833420 924102309 321145140 835800927 446761208 504553635 25222792 457730982 187393775 429705439 480194717 30978461 4227894 299338406 848276794 848657900 210493278 614357993 182361495 928308902 12679649 526870713 347927109 439176621 828525844 350425817 539748153 897427203 685387081 677310735 399227199 197608164 31481447 435033 860899934 913828015 338632055 624652845 659783926 755992351 454409838 898378267 147679759 412180209 366505208 391868715 432843646 107871255 747789031 319013892 695310059 123057974 60550146 59758985 563384683 486228850 752505515 743124514 131056966 7533786 207625204 326660995 368111915 183211315 749486827 565985948 136215545 600745503 394686112 684129282 553478657 311649333 204819361 924119211 240528368 576154872 561980794 973009560 149023840 935346815 70588389 759630154 286567710 377046633 139516877 529686297 348695551 293489175 896975020 876511931 730835583 137036561 770203523 394033041 148127292 504945812 832817258 717096845 392365298 823557686 24979903 236867749 309494944 822678646 74409746 918840222 983286548 542501901 781228092 377423420 232593429 475724449 370816405 809995180 132872123 80885824 154768469 516827202 581194295 174752022 331267891 578586238 326493513 164668383 107266356 267893594 271204399 255812897 880092968 280750700 454835400 482146542 849004438 127153191 341840786 254523561 873289584 551798430 842508933 924025878 920594284 370455497 84392592 273343825 62848642 52873891 608910179 438738920 749945841 818899766 192970740 27758915 615250588 435950890 827671325 987668996 878318550 509302714 424780450 560849891 468884361 972727469 496579515 922980057 947438787 89601120 111018621 26835602 947024948 486054053 982108210 476063510 466303433 494888564 222548954 661905222 387055079 544571219 796000743 492424430 994129926 479173783 976867690 361463602 740899824 51040793 460304113 967617463 947664061 560304802 485086801 238979844 553009484 428383299 803987917 669512792 865413019 506093521 893665970 707405079 230252528 139446695 796326145 539973855 645007513 759815682 979948662 767724882 381501102 701570904 90402416 191592343 401339324 126109667 911037906 514107641 87802900 705546580 386871162 470161874 256956083 345447078 713810914 423790260 219534814 696612732 262477185 886520912 816483773 877490074 52157028 897348634 459462636 230106244 830762802 971869758 829750581 254306170 556269059 870442046 160826891 225905617 568705446 287487434 353558234 440698309 748681921 955381370 571805691 380000706 337397366 479022185 615094552 441006243 873946709 803945503 810446927 791783043 883677152 473411302 855934508 265694617 237607543 972702005 405217642 130641329 32082112 468702033 650016016 777884577 612627794 78051651 695200225 383106080 757207076 104853098 903507765 134520438 921818117 125102815 817128223 381571392 25792718 863192306 74344344 842673243 540673431 366913781 552100986 913644920 46935037 616996944 716686809 826648956 382611995 878372019 363066829 792275417 120442835 426260335 902589920 526666096 550261424 66848808 399501167 171680046 702375478 226634526 917540279 794932073 703082485 378623003 271355511 784047212 333764111 520218058 565062089 687883523 355130674 878975779 365248753 929367899 64609847 873009209 610578101 497384535 679681754 498579862 156405773 806341437 113950228 707096124 633215944 199794071 400084288 389412049 321042737 568637536 301966516 72897373 379413413 636259566 96306367 709772465 997344875 694087958 211511242 796466099 654090234 857093248 22510315 119220530 326609643 947074380 477356095 912769043 369536995 965104174 361824332 119084750 273979503 602902201 986727727 682835422 82676573 887223805 208284340 47318846 226609210 364810955 540095133 871290011 594134049 758075135 167738335 875988727 563886906 89996164 949696103 663133649 591354183 28403152 352561694 720477131 202993426 650902199 86300316 389755615 918074338 2665763 717820017 295932121 195610065 548653710 209634185 883253376 719467128 457287222 33194244 171579117 466069695 558718781 825186269 88884364 652681928 288018687 611826870 456522881 733109329 182905741 250242474 590230498 925679276 401819886 562178678 918809857 23920911 498620770 312283892 869036777 794660274 428499810 610169988 217702343 65592275 604104973 956624401 550466348 436072047 724179498 78382612 630245525 302781286 618332454 685137467 682373091 202576830 809063998 587481224 243882248 817339955 707928941 992597867 356146220 739282169 680365133 240561582 223593874 926686498 11206695 56222377 614274634 496185046 821046143 316746516 874439700 246418047 19844074 575421172 901376351 788560933 899678216 158916476 794124407 75543130 141354690 426615096 870752001 633342907 685543324 899608613 893825551 664388367 82503686 822526063 44852866 249434440 544939370 883545933 117884131 699645537 71508392 597109997 589738490 840916106 171213309 66213123 171253241 563541997 349783485 734229117 177934495 53783911 281323367 652582138 48405683 701388715 23267018 952769483 248322465 960488028 711778705 178189988 390001392 417503107 190131867 711452678 745329308 968712677 730579406 472201494 573985725 534538160 756743415 624888493 412260326 738749254 266216314 863984222 473131103 438429601 31451913 462926250 624705405 973558602 177879613 445151060 462787267 880246042 879778993 779949800 441221984 678842218 515732750 59129387 880053313 842620716 783742387 339700752 257558200 331811954 776747008 415803704 610805885 538411435 486394732 481891125 859531824 742093934 874814970 552186099 514552788 437335465 870716462 686346125 957240726 288780176 756819416 944981731 705181782 123717378 170769701 88508309 997627023 805217910 900840862 606959344 472829149 972633588 227970894 976572028 580588447 87710663 547032087 526353166 971215056 271010959 42120243 506733721 728616003 74230767 204696066 666722854 291437553 137173877 248862002 596422343 854166773 668121554 827719501 22443778 721139564 281754266 248443125 998589065 412398047 22605057 542536750 834354740 353293450 773937105 65486614 339961801 12768011 427488727 887079532 121887361 685123061 883537567 487882261 137669188 916878896 195082784 263105392 105957082 778876431 591461705 467072755 190359936 412906802 192734729 790294964 38726336 752266150 521148316 97087319 346228344 383751258 58624479 337455511 893502070 977405766 803908086 391773300 536373712 196697883 373811482 111918295 942790136 523091550 993893279 29611177 831080600 715099866 41201671 427205774 885141681 574403173 618547824 942933196 913063937 863693352 454489349 130551390 769368876 14229022 634603429 351328148 90506965 988771212 411421657 157130106 336627615 278435948 260709715 633716512 136335772 53078880 488973017 545140238 110492967 268013467 679911391 707224802 730781236 495036612 166186547 540503058 845264630 76206766 481324300 200448305 974000236 183381621 986691136 848212431 221194854 618678761 415798614 633287493 186871849 732160873 600209585 738946469 680653991 736423745 192978413 462806401 807777395 938244188 308306332 408920154 364960359 250475526 366242917 430288405 291435125 916580439 728428457 747309965 435572105 38495306 154078279 412094120 586942473 254522651 922429465 49100935 343354155 855736342 730669822 913961210 478708283 768309985 133485970 938477109 211904246 869271585 389540918 904017715 350154658 252896290 731850524 582962713 179249766 15723458 317157344 624998934 706671644 223720556 739081639 757893282 887124684 623382029 580868850 179403442 445345923 231394794 243482670 492920738 18702520 953906733 767813366 58398553 431854970 752519998 495504188 585239660 269964607 513384520 581225203 839818038 95164976 761670029 72682217 468708210 570410559 726524773 379485830 472255923 314527929 80612412 304460020 858080592 520330071 162638249 421106153 58960560 800529648 302794243 516407801 313857600 502343776 400584563 950868985 388440767 201093318 287567631 550045844 463327139 111117171 875167837 52222127 735224806 229414779 685015131 117743605 237919770 59716837 418081918 579074608 337090536 337122242 532470333 903442661 186577889 7208144 44713235 531599811 926439607 420553033 202526506 502789058 346836391 177414423 469033215 729652823 789543718 89441207 648073783 287863651 326054207 924806793 267556939 249499294 842770070 40220565 666827994 830544061 256011567 659646991 496398934 146741801 914052846 326008988 700121041 605920793 387083187 176517011 770150862 728923563 167794044 279415480 364004995 355892784 456041902 539265875 139268285 297901113 671710315 847172128 404378050 992198963 134866941 738289996 446252963 461422181 803448466 75678110 14564690 18419408 151820015 874435539 122780553 644177531 977172870 909088435 363790046 792782579 108879192 492805322 669274401 957311509 548300541 961971413 362570867 412761006 715845883 425777939 63451395 895379767 212679489 717621836 329501168 239485035 688004006 221815314 208803752 781278524 527376576 507952773 138992133 135982327 929030594 923679335 185700892 974674567 316993112 670168639 486487375 157527222 103884950 258308015 960061143 455161795 701824761 109338507 724360259 822908313 509382896 357315729 567295189 35191271 140652979 747044926 432728008 464134501 613049348 735023463 958976845 153912601 252919352 820048572 873066945 250745211 369746237 518774451 996862507 144712221 699304311 401313319 47377933 904618766 721163791 492628091 768003491 155571044 770169026 814772410 865699007 972613688 402469168 476493765 144326470 873848889 945209472 276425657 149914470 626940474 669872468 80858585 113410747 631445531 991872197 303410373 301569764 976349613 182647999 962352004 978663279 522088176 182060979 63345681 9158005 458068303 229008721 722761779 47851232 938207147 691470191 585232521 424094276 988941158 67528808 653442840 400324324 927330904 796438034 157625293 291130793 207554599 589362891 919975744 564211283 318518789 280268460 795867129 241155392 951152909 885193040 118015137 152893240 25391588 766022672 35888600 991136156 718776006 609225156 162031995 18904736 604539380 130546840 128344750 793460694 395048505 983171904 729494099 852197379 459996679 335233887 451074799 483955668 996108844 736478578 744330968 711358169 835372110 794224329 618984311 213560134 115105140 940531648 87128177 109329530 342601603 546693809 529931851 79927398 215391971 497614924 510813922 466391276 112845413 414205485 198146802 585778159 61706484 62543509 112484019 42876246 628017482 733170866 697534215 303193402 699583620 820588866 641191497 362444279 706346929 888217171 166029164 69000336 734802409 357336746 367492183 366979205 580331241 638916639 659645214 379462540 148792894 595002203 343461328 278288953 1793882 222851831 31890855 948687278 509231928 125087387 209694917 978360039 13684242 652740609 93084267 702613197 331080113 775567085 524587661 225180306 286543032 308074987 652959420 972731995 693194279 137985773 577812895 393337364 50263873 940055979 948714265 923911707 27297517 309132478 753419584 270172050 140671624 599385399 37678319 869631083 377561517 773230160 535632145 471581704 503625586 752371879 99920803 957367365 803129691 24593474 744897839 45827828 752195991 803398737 333468748 45411342 857677028 47545212 958021988 714925011 556371930 361764309 430892772 989771191 964263374 136024808 230067941 534874141 646551065 309215789 812891842 980236664 191186702 69005383 748807115 823669121 617672783 58993075 420767683 757120267 543488696 234422687 112904373 723169664 206345445 461472678 314636914 221282047 175587126 288279422 402962862 284196801 366682934 48946318 761160069 241824135 565024722 666020551 757167080 246943822 279373260 831472182 485999180 557050343 817748302 427456112 535434316 218311295 968972007 628063652 593492306 877516047 183722674 203993984 778080974 233718384 452261668 592060987 103346089 503865103 640263877 882872521 572892989 138176229 797784192 103333012 241386815 302199809 419649703 734642420 719141375 45266885 488973443 161867870 225193718 483355671 115355695 184597287 527893496 285046798 605208985 809890958 973645695 269257790 999698513 160726448 789827005 423308879 516239726 583665310 143397682 926647387 133273495 580535393 322067589 118690022 616298312 684578254 867650592 229655079 875384292 980004998 165588187 842172381 75897357 210727603 109178961 345305721 383901203 211300778 237146825 630726015 757250441 364674209 538576920 581469114 605630696 162507100 662834113 943034595 622424767 727280940 912487063 802316021 278226406 456198475 311716974 481542112 987483950 427712972 362699167 273176342 387299761 812308899 722203968 271544424 118988096 569186170 164418975 789954755 165904170 657218869 686293963 318183738 671645304 322470585 272108181 142944942 400142783 770185284 743775871 107680383 543817931 863527373 424967400 919598503 778375022 945466901 185974844 869947527 416358477 766434001 728738938 717428603 866560114 342407825 577168764 730987557 607695970 536081365 111150648 689717252 60718912 968737753 756170278 740009870 846214545 713778796 399778149 928273950 636025014 777711418 946026211 547493120 736109275 818096934 189807026 837543112 831623369 70075160 445621131 282199207 579695505 591160342 138281610 645702382 610892168 624005852 516152246 517041528 978272262 462364850 77486398 361585977 897973613 188516903 132190317 717247428 340958615 341434149 868016342 996123647 137178520 411901756 264760228 875538350 314473022 398837336 353517779 753925540 15031671 176685354 963721453 11153187 330071971 299999173 892440234 684438397 273608976 562233417 731948 554966272 848823960 88118891 380272091 178080723 674862150 489705883 973965756 355725560 774386554 572302834 106353634 564264649 844244869 966622703 124507485 610977724 254441184 565108384 952869383 575143351 930531785 860975226 837919240 571540471 553046941 109100038 732939222 303859010 893593680 629352450 23182502 278249625 906572063 40762049 673039965 757133842 607575238 316796527 790625107 951133664 630010311 756175749 337622355 48545420 765257482 233253970 305676357 692477376 220584309 580218653 985690707 384163507 554426815 7197642 462654979 450993192 745776190 418146096 172309585 795326544 328492480 550604896 833291283 290474064 830406693 36841259 651890573 491132948 482826902 999457910 355821036 849203099 800886718 790191737 937969043 710608841 77953050 246700753 687081897 464952207 573500562 511349404 104199572 233283786 273139473 734671007 240042051 257786020 287035506 979751190 417886150 427248886 167983130 751382995 411567133 750976947 970949124 12707758 641350991 388663508 966592307 260849591 785789123 280570861 754704249 203737760 608550429 71234290 980842941 289432942 520267223 68534383 7931748 781796356 84357926 805912439 120333234 339504472 510831453 274799756 652260137 428081310 637581551 269184034 755268626 102162173 556402288 240161167 226879724 547674424 366965753 872898865 256588557 772644786 557596749 498448181 624364019 223227410 545122930 637049293 199612393 573185946 374567526 83304477 965939891 469669294 223403814 494319936 664434977 831682450 223362132 246406660 695002310 35223195 665609293 606472485 292160703 20515227 871376378 287272304 184426983 695707842 11694190 449334611 965602351 986191369 551864695 554050295 229469681 689531558 306240456 751235827 796883729 652076730 966265403 630501297 26484795 267549566 247150820 450887171 533796492 244796827 377097709 5958293 135364652 148356035 582602313 373712201 249511184 435229027 570862829 950170776 921556048 314388155 602547137 256861473 4589491 84812176 883595639 12007901 633529581 974646455 730896139 88035276 172492268 783115799 321375632 784763207 222118663 222514995 622970636 88343488 219337158 96515785 537471188 583130130 488925510 179154036 935460748 410707841 689260680 189255085 956432981 208847141 103480446 190490259 37418282 451382355 248590274 322186525 932403910 12340596 558836127 453866735 925651849 938719955 111145925 891770673 156348974 487200151 867025061 38696234 397985628 705333349 9444221 71123107 577703012 261794526 624823018 898535802 738276033 443703413 79881216 243704739 917673747 713783214 682281880 378531749 994013585 860659390 404338395 38149539 216713179 427408623 209627016 660036758 574677496 579852917 73664884 567815222 300868989 458706982 313673382 368612951 466160461 451233899 881783468 547987861 348098592 705447185 460038901 180714288 899190051 754497566 670753380 537406200 860881500 652442447 678561975 608734359 600648817 1269297 445119267 229516368 155748151 630466693 459041374 494259518 339504175 530637379 12456248 541497858 299475284 935637128 147181053 639659812 753053954 815383752 498922243 41987316 304637459 802313214 346876588 165159650 80952657 27780627 847636592 748820699 288089070 584916780 712451930 831416247 866321464 198387906 136817586 97450281 180241009 545244856 280514922 664666682 707017734 700788128 579284115 401096529 239241797 68166025 526040195 49862704 172419840 260374475 660850753 709510011 140589889 826240210 543492273 42441335 109803876 592569385 372923960 890059765 84595603 546508324 218239808 551903171 477935674 514902164 952656508 115828919 312920570 88544541 232085475 289182966 257715093 738271601 574591459 532915090 621814036 649464529 679663071 143949483 323799928 588817449 513421442 889517182 889797785 103808980 111747265 157703128 145703397 259543818 528166015 878475079 100060799 307213557 845268921 484730883 554189254 515575138 166743322 570610449 213613915 113987489 692449180 534901671 252980373 396482891 311088427 937627775 895466100 263715364 145188637 887276787 113912422 593691061 479248699 789395899 407493934 48886856 811849999 897317560 359491207 253984162 206944769 747125850 574528784 698803089 3213804 557873642 8982663 959793226 758228262 717029936 164360314 16576687 611047347 732637343 381088547 281994203 793088409 967879709 531379542 843097948 155303687 110559202 492340402 264351313 370043729 102708060 953073597 514664859 668144454 300092055 795748571 551638269 772048783 238765123 332960393 855980728 527484765 780238048 688772845 723593592 950923411 683161758 265017320 711605398 252206674 387137924 368675443 16249915 769738794 968440582 41675908 793385073 812968341 874860710 192051376 566236492 384532509 677378419 135500260 418922944 960062458 605594611 85794648 727179894 20126980 979241148 97890035 629688903 46574451 999443361 226066505 205242099 926525905 36487552 471635505 243841111 363130971 832522682 130034986 622469692 672567545 261301002 736333473 473872638 943560723 465795482 994549604 124330451 34837818 223494774 933221177 467694484 631674458 373783235 83728111 322638186 841477173 649151961 202494142 47484711 273397417 938762844 619078548 478502045 909506624 266722532 751711505 343692581 563197349 138215243 689000315 228564737 160886274 674601744 951065015 902142830 276010613 847491602 668391697 878773113 302388606 568382339 782252908 863439685 368888175 874668154 486562148 883060788 252630458 200940183 525875390 511643089 159804407 389046354 682219703 819066579 645739087 566197596 796056230 72444188 316301993 323340595 331345284 574997477 553197319 955999889 313223728 508068544 747796445 655195163 793470753 530993214 297984437 954565117 140696825 320488129 185611131 56364084 442202048 157022895 749998596 46229998 549695699 70917284 293656812 62901249 616220385 68900386 437154951 315664748 663862206 323318619 592330769 790274151 387259299 547034831 934984744 393002005 613724053 799337739 146706430 36270604 194339856 987937501 132528221 724062967 897408776 155796981 198901519 779780005 720371911 577421946 7339857 914659540 988812294 118775968 74656730 34479544 375767886 109191114 419365316 521723083 246209097 274820971 750750757 463551871 764285001 446778236 958746842 540298486 464627932 753041808 874352212 800002117 15401413 528502966 5490630 210323654 62134053 658730217 776613171 213315015 276618800 87914173 425273377 931383091 985593894 794922285 139930514 262069279 360549485 872646882 770275661 811501038 621403887 846498043 427999581 219302303 169918555 147945117 403607640 422792426 335001027 510302267 951394970 643835826 930425325 963229095 465358148 73313734 661803067 841193366 350785229 183612705 224973816 198073698 773230245 368853907 870510337 674670325 361034607 297685994 544491160 101366734 23418445 467922157 247770965 475686267 471008867 46789065 675055147 283399242 135763984 262105633 632637257 116954975 255251003 788890889 942972387 555330442 972586960 211037435 874624924 747404577 889907781 658835627 872909241 121608641 759479736 188423614 179050801 388392331 771090130 35763815 740616700 908508148 908373618 261854298 87604187 584135617 423667826 962988892 748094994 631353285 272164114 780481108 282423827 137286490 88139710 230510298 124155134 780283895 702734191 777737398 660210440 377018251 508179709 564013890 279347441 583558080 585241074 262023109 110437690 654814276 33376809 677596518 35093331 91829788 786505635 547820877 296569927 197628956 999288624 329672013 333915920 156246397 564615248 557201604 186218963 830200486 408220873 806638101 48416757 501560803 742675449 953975187 392093573 642020459 620309574 985498951 648604346 937181275 195627948 893041905 209572254 378853888 923742804 56005972 680387205 739930796 231278386 578276158 241677809 656790443 860029582 996144652 480451788 531184591 509558000 843782539 8403418 907685208 138387752 396452192 888148722 609022841 666444454 847352495 705042901 513410587 215762061 105390211 20388741 25266855 741069308 872708557 167557937 374894159 903616732 376717101 261898216 647115487 317056244 976675466 980786644 797340001 955272228 130613472 646013017 105828282 510788718 888354129 722700862 5653057 696627722 196118924 212918425 842376437 920360024 836960343 815034521 827409154 118803714 365852971 443723218 329561307 233519173 669787338 875274791 622850341 340951358 407694575 232037830 550128989 993986712 406994758 921495251 311391308 481546631 628289743 120936457 906639181 465761086 701813577 159408863 596908925 588996141 247431874 647267289 143939647 696818689 845293878 659857608 111975522 767558730 440089615 884217589 960709522 665744859 187365020 286543668 364756326 992688363 145883278 575584509 630956708 828417253 698938626 529323805 613950732 382468071 738358242 263420774 503894453 285831447 406272164 997808742 129512980 263823915 215826905 31512517 398514905 468893022 657873169 257911687 226442535 169556038 284483777 422486612 426676815 762033554 886897585 145355241 289479231 144501122 181976474 987330078 469233846 583230613 27364584 790281764 631425324 797549470 394201371 50799437 697536410 772795517 396231897 982161563 974101045 490317439 712970204 41503152 104720910 535858326 682796235 495878343 814322052 94648751 257016699 595402497 415436383 596943047 158095077 880443103 866946669 997786528 436506683 785064600 370931296 622335238 588555898 238502275 636241078 868357515 51374404 879972089 236027626 978091284 275956532 888721275 276567272 650465536 848442519 901189194 494068506 718563650 664068423 664004514 90985165 892830278 967261512 767146134 139803667 262684268 633845936 781432116 864208309 409159541 272267273 349815408 58166346 68682449 702784142 201753552 133359685 471393683 750416439 466970247 542651361 154409674 332693208 863406326 964026184 337023271 304926370 840981068 106842783 873439048 720372878 558406005 718017239 656555348 243622040 775799972 908386904 927655229 930145415 633541829 800835832 366219775 148109681 747315233 685356310 556701916 20018906 186020725 430445450 161943202 6167615 673626648 311173758 685591408 150558884 66140253 400044612 126946163 820792611 297492205 642877995 755870876 931063712 801424309 848141584 630632801 637300431 521520974 376395565 395541790 568873696 231381975 278521681 255950559 792947059 50352058 354363357 696662024 255656487 667453897 862976241 6874714 16641669 140319069 571432614 965023311 939525224 96061684 55130399 147036064 350747773 209305696 26324306 552300778 108624360 502374560 318954497 221034473 969400121 86325164 28251866 138428222 867728622 828291857 778088384 930064287 830550962 412648654 149297003 670754128 404159699 577734846 616239249 879993893 955804167 725143742 267638688 903315176 927882528 340536731 734291197 833147595 272746775 648746772 739804484 89004501 475460674 39694433 399247476 255816034 991670420 366452277 10740443 277010535 749881698 876530160 722864913 703731551 561698203 812079450 534069259 869245264 476712964 29732867 18907942 665978565 724634337 470815319 358981559 836798136 421569093 96754770 360789184 53369952 977391845 482198183 494202837 608476556 943179315 876941708 873967097 60535604 256266170 201217003 929162479 909279892 358001259 375129385 267877883 676378977 235776343 505565075 287252964 777890698 342311348 298170292 513213480 537941217 285910006 734463599 127063558 457957173 141693753 643830674 411345797 782501727 324514102 142730779 453247639 131484114 587212768 135082893 346724365 549017510 666494750 302999505 45350184 831384628 212829839 598725905 672019270 610064773 811253117 61422240 634214921 96909967 725690878 546481464 810932692 255637327 613793790 280078918 853612471 298295538 508866548 453469728 314384706 778381488 737146529 262274600 18109906 339079569 953405658 165396222 75468655 588662748 574144579 518287294 558716873 131827264 863841658 445619049 860462938 119210688 795396717 456458796 116623456 328292225 313146821 833490098 896655211 917550614 444264987 361952680 70881351 116814136 411824719 19320990 784513619 988243594 893696330 960402937 63538793 891642568 729757827 527401114 557617831 942127011 356379076 968204624 969840893 593016573 590180935 645995425 875918900 73557587 986019123 365328504 719898335 849617077 422877727 867210911 879617782 984845417 594811246 425361525 714377029 853528605 917974519 269838114 646436423 122605012 220759259 453628845 940769719 701658547 53792301 546097553 625866201 204909185 493136061 337515346 420027942 39377316 835978371 114621830 304317630 201643016 70090449 154415994 284214328 408063551 608767584 671189639 234925072 683512622 582795581 398829602 762355451 44745734 138796393 767223567 664957616 534997298 944685710 617753921 534536131 741032323 786564257 975454229 161391043 788064486 648799524 397671213 478225483 424423869 593117818 145776458 332161336 972929415 87876773 161422694 572064455 726101314 731875972 488889370 448159877 249379818 62675940 147474543 853520206 821997120 829806611 753140923 473391275 905442871 304135515 753279698 558045233 136183101 215578624 823039418 794307505 632869485 498018193 310937679 325552936 228204946 807605097 185231678 189124050 199814963 721200828 475306167 456653446 528621524 899624555 204412002 634755282 764917591 42532086 890453867 77789354 723704617 252354089 859016120 979802025 839601152 809228355 130360897 639556607 193295533 565258705 297872531 803735053 887587410 834823261 174387833 282282288 699783562 89220112 187106755 140091032 866551237 436400741 584079107 762312907 863149625 59299664 158549347 600946317 353705185 939316635 821932957 908753242 847520181 894759929 280390746 703601267 892002149 786614669 114532462 313691304 391050389 362719033 189146329 455925325 167075241 986410896 985056950 338500376 876315538 436639756 87767390 636107324 901061944 132771597 483665218 281157353 219748922 730476373 755777009 737450937 731671776 551669913 57997286 822739250 390450117 735154738 199776761 44856432 225645173 822696695 616439955 134743616 762034073 457725367 416942633 888710312 680392539 711998641 290029166 391110724 956952753 310805674 96406036 417135830 57973535 827705748 329926664 905980241 125841169 849980641 600835940 78747447 808266102 560780463 252582570 549475499 824136227 566029286 444072959 914481319 311036257 278680223 805932654 597262808 132722957 515472477 678255506 903289510 268845632 831744563 639186398 65554660 638964784 947282422 771850604 270851251 380327294 990762690 665194948 174706572 606247807 554639901 867690348 532912551 594091555 932151136 54601802 495284723 270445791 613938997 724251709 405119999 474349285 803210206 437660585 115760836 692845809 182058685 486012072 698287079 955416999 181883477 248672983 299182855 313483534 465942247 899601897 323109839 127264262 200209762 267979442 599664482 430452570 568143282 533409332 314212087 264883259 399283789 577050495 564169792 593048878 368840129 928883893 779105404 935455799 361015477 634303768 376909038 229436831 471956624 508314924 463045624 116074035 870066229 423218329 397560870 373256756 209356130 715055489 725316851 619553523 241219882 924567820 286256004 729914696 30935240 623134575 532177567 655942975 930332937 46960447 513492277 803506219 487564461 156253344 575986829 305188636 554928394 180409414 86272982 147869066 139780918 267537141 950966700 667632609 273673319 107419494 939411765 602579954 90949466 289684393 588378199 214132056 456944159 627447460 1500331 93922428 385993060 981034558 471006213 550236899 391224512 697155463 339267416 809051356 660578451 800370759 361008020 964111340 29332893 374924456 178031659 836592279 301804259 34120990 249565256 350729635 675815300 196282849 985756789 956671938 489824257 558512786 456807841 692385565 867013445 125921056 523837178 806455316 663821561 726915849 204237068 791603062 776893417 621161059 753458592 877877219 773591586 484518670 114971605 305852165 948575989 831905954 39066232 220932622 995836975 698531610 563003054 134661252 28040123 779755507 925138482 972648446 54806670 591557505 701646663 616582882 206881209 975391491 695224797 731813153 730605427 112404617 828069571 973649752 633239922 447152060 459309149 528571396 682004332 175555604 480542408 541893954 915851868 369409669 429223450 628665344 445056930 964147954 622642745 546345444 883962180 25615855 580612048 121565888 878822728 67616818 450214838 31437060 797171837 247126179 263022329 237447085 6184949 267895960 552890287 37835302 560292468 507220303 262907805 690573101 966302383 985596673 405655135 976405084 325739230 248165125 895396443 504153686 104453695 713178721 830509304 675602221 642796353 252818556 257273746 312273124 235907783 713499779 628573156 347167861 169984335 434803058 754259623 951137423 481907568 235679371 377202235 933999475 534472062 395105596 163602747 993354379 955227835 5589641 932172918 626750754 505319411 914409256 853816748 612656817 203793017 906989705 548729064 654889107 656449483 365356967 484691266 144734334 874102845 784269728 548127068 988258215 318334115 477348720 342822732 342100337 984133772 143335103 103445382 998499067 463557241 832667103 889802865 208535168 491810972 162607944 36942556 610420046 938153646 712497009 947745268 662221375 978509612 162973935 850340198 564944214 791495405 240215981 331871153 679210226 760663439 613714315 445191788 73617953 730970310 230671795 97915609 676358116 543461158 613296127 90086027 861854297 242462969 304732015 234848347 331998000 769383080 971845672 572004235 203283885 948774299 46072900 723005785 968205742 62784133 226384383 692922919 410059269 885411063 262710502 302216124 941029078 38280830 784289401 546753595 982681225 560097339 142182876 564849604 848109787 996999035 319294640 787362684 338132050 987298284 91468955 555095921 369922586 681790669 389218496 504956200 992645655 944390634 172886941 628059077 400028465 653030064 585792320 389734812 177607258 319089581 990216227 454288834 90490918 78623012 463034226 993954758 360638550 849420406 684046218 754333069 144250727 141383427 620541479 163832963 296032935 818793982 860077652 396384471 831413748 814003029 384655153 825415881 711800108 386410682 773149711 775753987 380935182 333898194 263192847 92786774 53146865 525367303 282938051 252359687 255379563 115565100 442228303 846597699 266103238 296328508 131862649 904782020 765420860 750414133 210189192 225133729 798778263 481366456 827531281 332971146 752965781 689226646 663144724 737973054 863615362 586683754 226100095 76278225 246958788 639695940 579970882 953808772 900772974 755350546 877550787 634800365 365920551 378498481 701620966 920511405 417874321 222900856 859338590 227951977 607777568 94467082 207363669 646525065 243237611 10384140 311516649 256540574 636317679 23415192 175723720 131693815 52560090 349137497 415850496 222178006 277185856 558767409 237143425 214060911 290845436 981815208 141658593 209468670 282381591 87012493 211144369 741257391 804910041 795191079 880396730 856177449 695578272 802502172 474462784 325073163 599495600 734190956 167037855 496547447 73806639 987991950 182006220 144966040 490140348 464243080 686057734 611654950 446572304 24201536 6353328 787912396 128140845 715425382 557200141 6387552 885038706 501941117 459389141 189451435 467173937 871495170 242047962 634622513 93199318 318920314 2677216 717137858 904097054 724297409 403373465 721455410 291226964 655204905 950369751 993197188 463082838 689665671 632735507 632776 595197389 881654896 690985909 298941198 281195489 251771607 684136377 660483656 243634267 782059847 295128415 314260394 459598267 915136128 470579645 491182688 322641304 656743382 122768334 673773037 779313384 571228074 605464037 364317118 381527980 201031150 420287486 44120489 414464405 199230195 364310481 302855435 755422859 352578299 94384415 720846650 200305239 967205166 171436352 625210739 744949903 74213522 664971520 426896345 62378274 413293081 697487074 995284300 31046732 110858195 110711342 677922249 396061752 610521024 222648110 979848931 326409439 217617608 885949501 324552882 998047491 867921129 184425215 24614224 591561475 189020388 446360854 340061969 162450745 720731261 460711491 323836587 408766506 302039938 936202626 324447758 433311421 230891290 889926302 126900638 744257538 525130191 487592874 484407767 928910118 475505459 914173699 250416436 594647262 563105052 394222209 822710228 628807154 91735635 2271592 414917209 167531037 70699128 689488470 725677413 275061810 851103664 672159749 249243787 239074266 227262127 86131168 73127371 284686031 243967405 993592417 256350284 344063062 509034713 583380677 702094517 764059578 806114965 750337971 913216557 824585402 648200684 497840798 928064313 300968801 201391583 501253751 319767537 953403155 746837473 961238040 910299616 729581030 135601997 751589409 8546752 932360977 41632338 794727626 201487653 61844016 78594787 892267923 49541397 981885127 897157334 571750386 518145421 479600742 15054333 697433421 627348818 916390623 829142420 644592221 375960703 821000710 739979293 93787436 30136171 959495723 165341135 786593772 691148637 241652531 80275011 489064875 648632485 240448727 434302160 668165121 139566124 257487785 882892368 767001150 892309635 570019324 926173981 275354629 345647759 590141633 731118791 875736289 683518879 537252868 781193170 169728769 480583114 274384784 970242994 175636182 100444522 432982917 491207317 501819176 747107207 867518391 858356156 392588299 950824300 841165089 679092527 673396766 608091473 434764588 680959208 914375173 304827160 581825132 41639042 653547144 401788451 17326823 230020537 988643579 74770832 210818275 783011488 969296968 399665090 360539139 868107780 700724487 194717724 165749481 285536994 586871888 23507606 80991016 697562591 290040320 865843615 112501589 945389448 410981029 365248198 720416360 278934442 134609582 197042556 281242061 297116344 173765153 145455635 316616875 961470787 600196783 698424091 490588216 919062237 599054124 957099835 301557663 560061272 168232358 745991906 481284722 345245258 839034866 167952562 109811548 550808442 631745376 158279883 349444989 237149399 516036036 55478208 39233450 632221030 629838533 143042327 550555030 716306784 670568324 645175533 510672364 249375568 152998030 133057289 477952484 584835636 502323444 367755690 627862200 874284625 607239205 609226253 867599241 863085816 123820107 180107731 689857197 346018959 808936081 450304961 63656388 506810879 660942992 144537141 597339573 521082852 405621908 160738562 801138256 527798243 304760878 892594012 478102910 894093092 636426086 391257512 289770664 218163225 916661734 240703520 978597434 599495721 578817822 219874749 762252393 271684039 413813903 163467439 614710675 51529281 29872545 217361021 370869413 619151916 541399188 870649985 131391910 687559458 761210692 536178458 733626425 728142691 997965001 793961839 325921189 523929718 893739135 819354929 412952122 597150241 703394628 578773869 356971417 558607099 612978607 241890636 248324175 672622407 477615778 321932677 821184122 740875007 230354424 924457535 427819583 448696001 920457447 404318041 665889639 678048928 965815279 989347129 330160464 499337355 411319828 438923387 804993370 270845981 674346229 492031278 135678130 311840931 548374640 998188922 439639759 194191048 481178615 519187599 679821005 526892452 219189369 946227001 835588836 803060119 666783148 945164071 303945144 322742381 118861023 913469045 821674876 214402572 880118942 49740346 256087292 725198791 202465426 520587656 357965565 59188625 118458800 482629151 380971631 963986007 980206110 688916401 226833587 782089161 338784854 20679939 285375977 898965542 481170828 676024610 68452153 19597804 543056363 900437375 964335275 435216300 935018547 367868015 659085581 184368629 787921032 18229623 159106124 466910846 705356454 118535836 869259892 402298220 683914794 527001743 200896986 830018161 642454117 86429875 799995800 261818620 257953436 621558687 846390767 157851049 46774750 625617102 225718108 115430609 558804012 929650684 216950011 11954444 647633280 517565414 478996881 996683310 726589579 203662390 854623528 114156808 959566457 156434425 918162918 412818758 320809732 33757693 279651750 997007943 593393093 825756354 663773254 599326917 230521076 809504611 571471986 67955412 479389281 29197076 513052183 628394724 50105274 502891439 512189121 701685384 657500006 591335162 652512948 441638005 806025709 57917916 224307196 366188076 152283372 677688979 529049467 423019380 708973106 735431171 712443807 777046496 869494732 391231759 523564228 532501668 71122485 946877012 886889293 7915631 517912189 613275509 424098054 669601615 977240457 363374511 742711453 28567703 980978143 22988493 587592090 443351749 266619956 98599790 605698218 137229072 478709520 25052585 434981655 97460330 911146018 622168294 868001364 167817343 529304449 37268941 498203023 820557181 308466960 158014181 285392444 806682540 226153651 127683067 573819688 639768387 677693474 645600945 408687581 924320872 360326952 545741347 211494871 909651502 221495778 731097249 608545191 678044195 178101031 135931342 533182368 749433938 232436846 942151284 511614223 533121626 466644716 758816350 900594263 707685411 461203268 46995874 345441623 706652801 267338264 439924537 443232702 294786244 185607332 107623895 715531080 923453352 490168925 357215986 792145228 764587185 569584260 768737511 671311005 600307143 245587021 541003540 423458986 225591110 274636341 298318578 92322550 466512004 563475469 21306956 672793612 766414280 474678167 694383948 343489266 49959481 547369560 340244868 149684648 634160994 121107410 281333294 335870593 164515944 26310064 939160726 492255229 822251807 140820669 333930739 471726687 824637046 704749455 177768865 431927735 88361632 691814880 456605590 809567727 153585101 724077803 610796677 246177618 681043852 383269792 631978594 679181983 859475665 920771164 23467765 963431683 528779746 729840561 383353460 639987049 351711710 921783333 235472111 432629825 587882545 596385466 225072613 239937257 739359772 612316586 530496041 748353169 761408011 642659386 405482888 317207233 25849450 41219999 167925975 486633260 265271845 878154998 968658004 888316752 106511869 227757952 970721954 582906993 258943239 754320420 338873854 788781590 654607826 154751694 642159612 240348632 757387660 714378143 477595976 288488522 190845763 30996659 192992931 628430744 144094520 444933640 457651089 618460795 498881570 944882519 698889966 876855652 84119358 346781269 186173877 309741096 148228907 139676857 940164865 697877129 891168428 422161572 846935053 60871892 857103599 318535961 745977449 551235705 386295493 570657326 25920523 303238476 766534958 157139088 304268139 250126379 199284784 647757833 849073400 191820539 632191506 721244372 288182970 853334500 728197809 370534033 968023197 832353011 235345254 422192513 166631942 692186347 801261183 305537407 259913336 417268776 250886231 590077309 878309914 456939185 317393904 785085491 24201811 17102210 316120228 63850187 288251170 329846501 82235593 162679000 8171249 104975043 766987795 828743605 392071212 312784017 285117692 893383716 16825169 466411302 219344218 520715771 746052085 942381993 730008822 96445604 489129194 239368521 977623840 799337778 466102664 604434003 298379397 591807067 715521600 868287971 154304286 59266064 874210876 804187430 547383152 957731021 213011259 820970927 683538229 43765405 847834284 449403040 751844696 866523759 389514980 59060350 535553566 26640341 196499610 136821832 702593693 74766007 722209027 180505782 706591674 315456582 43077409 267985014 2371366 516570851 357703898 259007374 643898070 781372380 827487818 972520029 231839748 52508760 339859100 107639386 51334544 600032503 555941802 967594334 761479958 346631385 222081256 737602828 492920735 76343374 916800373 961079224 393588209 960819206 482791761 852388143 196064744 548191321 77746477 943977021 647503638 903509461 71534224 281352340 565783345 766008030 857586577 46501630 575406137 2157657 780135652 612454770 814406350 928111827 337999728 111705722 349610498 499641565 551349837 672022611 78038949 814528228 139933006 916008556 298951131 497689231 803382363 451122393 386379599 447227400 27132854 176401549 918162499 194159229 785361816 155805852 130540962 333381534 43448896 670845164 468551535 596087316 896638008 735969615 733823533 135733255 902221230 300125259 893049162 789880189 326517217 596215239 208932074 656642865 43072374 237870139 315416364 122569434 943936293 234462116 782429284 238072438 448684931 956094675 497156848 297564287 967632344 796843994 860133177 667663840 40859436 257111380 7798057 94532176 951151637 825964291 170732914 686430669 916989561 84649581 423775125 171069012 724765622 228391102 864837006 789951089 484673909 743652670 98683366 372622377 989977450 143052332 677729752 402960596 150147092 917739555 346975757 542547595 571609272 640683570 572642193 109139645 858320699 879433601 175609356 286290642 923070380 699478140 23261399 44642249 19308942 732660341 530489888 320607326 956740636 893241825 481103064 831376925 78052377 529105512 326368227 310675905 776343971 288228897 419470313 874593675 835190903 620985176 422779084 850706247 412164092 101101401 297779948 429682091 868236752 550976047 610252910 812920011 216757134 929121203 633799796 363717809 826201026 960899359 939219478 853767649 677925590 897540311 811083867 227508953 185562217 74217966 714933304 354008317 628074632 133514630 192960383 393298639 482263026 521360874 490302339 544392548 504309071 96267660 698411507 568326347 952694458 646501322 843838100 660455997 44230491 290765378 997164882 93684214 163739203 239003860 250192792 410477899 73515463 713208658 369207845 953474672 595438645 265826316 566401550 932951059 992568140 365914885 241161919 425298873 839217296 779259300 45375888 706419368 683419884 978823470 89590530 273867502 197939465 101163499 103134410 147842563 34694414 188737636 66731821 808590414 543981866 219988895 185943594 305983932 730738913 54911743 345969528 430853324 141444716 583879381 466921446 89476659 774672799 500764991 370936585 668095267 838843984 834640469 990722150 760327943 670157666 274449442 678952334 787648589 876093841 876756836 479147877 779596491 854409015 325107810 140685592 230246962 751755491 24966408 272737654 42399606 162269123 14759155 801939068 757524772 578199644 276557610 344877087 837495999 911805112 300882073 787538254 454302784 70249597 577735267 564577012 228892274 443947657 632078821 272793316 268199759 446689471 524375642 886100471 442175689 404292324 124300331 655769094 301571563 905575338 158535044 202996974 746726187 697419395 765052662 154994139 292160209 996242310 699279240 314894299 485066929 499276766 560086723 293368740 70032436 566681865 215219002 473414797 869699047 888734269 136131475 431584529 454548070 200264192 179059901 519602055 684207307 431808720 179512230 567688955 946154945 521760061 836158941 546662517 148870694 623665895 28761408 611405359 784870552 630086197 273793327 465732431 359003039 533408963 377244347 944473421 225969464 571537388 860180873 914572706 599833011 627203610 369900917 909942930 530892365 265909883 912810980 465549507 102404081 49883361 245048917 413998642 832005264 169696306 9832057 897985717 539769483 864813427 277475533 649349313 104080621 975481505 3704504 927417171 387302300 309756301 420428653 377604174 39212919 205976430 743734868 223549243 77088815 119282161 456471189 767607440 611437960 557450434 840997154 314080381 932548417 639702500 166625661 278593180 353353934 886509121 57426645 681804035 451770307 691961553 447170302 449385651 501531145 56303 130257809 176609533 400169315 144271938 70355901 256006076 751676328 57799802 478189791 541226350 754463265 671375454 805832888 517553639 12902301 278876135 747366038 305277373 915315179 530925212 318986872 602648573 384911804 617758312 469708966 316369286 123507677 265705524 150003325 781482944 806350666 850176832 42965829 278403165 654807255 805583074 532170405 307744167 98191813 530566912 708267028 328963442 721406093 257403156 366520259 819221081 769719558 540159730 303072335 936132150 771805765 799893288 393960538 560090486 960081839 541717310 514545781 559109407 484637392 80864347 813494247 258837930 851238077 427303729 943882514 478762131 924642482 2926752 986420170 325831212 435971315 276473863 370905238 665703560 339515714 132522564 287799138 563197727 847340407 105354390 326560210 668267748 338723542 798791405 785148778 552958915 794945325 637072582 939422228 772290590 920100002 938392099 425020499 825854850 65095735 812860177 453594925 944974688 262172881 842217221 724626289 466636596 146545281 793315463 9959801 925534063 504307900 170695887 292838208 14130933 275002780 651430283 415519735 976500347 310488663 276952841 597822134 911691114 84692650 556581818 614345037 155702859 444823969 478761968 973990677 567211121 692955876 450677038 328328976 314529403 191035663 184325917 970885100 840401734 408625395 281516913 875424431 339697426 730250213 217935042 796310275 192193505 946506695 682866045 640182471 809660309 359995080 832861203 603709609 865246182 318945525 962943694 903369029 989881929 27881368 930788077 355894990 198982009 574625399 470084861 603714880 118369602 329101665 398643719 101446073 470753366 93503689 135037888 447758337 990872151 601160959 336450799 234038771 341601524 993043855 478100281 973637207 768505778 950740436 944900897 748273906 60842121 961397200 537061831 373147588 551367584 253085990 77594713 251921354 740196153 757542134 726122945 923046173 918048450 606709739 691127724 119149886 951245531 245178195 768485259 902802807 517780631 709612566 666210303 225169211 347203288 279718794 684803461 257809413 888426426 755628565 677868410 472421705 242434674 702258405 393138537 341382787 222367400 798497265 914329307 582374971 261444952 730627 676658951 764775339 536552828 436936708 403419679 280602205 202600527 494940952 466380990 186327315 916198388 862211836 927256014 511720076 802338971 986023542 572202508 419170526 738567841 217798405 769742087 987089519 739543428 131493264 914210935 985335998 633604342 59871061 302615097 122917471 146523475 782037726 569107625 373380948 357633679 994679628 312777686 637170513 618528833 272677581 178970914 608761388 962393055 384398268 659297953 489898723 101687508 563811787 806040239 531607750 599650074 344961557 519023013 201514989 614171403 74100381 216994920 354717471 14345583 361145716 765363123 671301448 104506333 869516257 72371099 603863556 368613871 296088136 269691653 489112824 723152737 568080953 723006942 36582831 852219280 606980597 156701156 2698243 370277281 27629905 757431987 152979846 802090419 283870896 906617432 733098170 46203878 901519031 447270674 42426184 542547862 608152814 806535070 875354495 111805594 514471793 113277245 620552375 975700031 642224722 825009608 54812548 75706043 2129665 679576080 744093632 846896150 636803095 361968669 862323453 712927718 638338279 411378264 172539504 389702546 810050732 338993265 922206298 193464616 604252766 596487090 400469338 548731231 350744472 953694247 852879268 374329394 131237346 326743241 149605707 346068329 821934074 665495009 578478607 877905201 631899094 583192542 820164044 102080775 743130574 510867193 248131590 454808318 374665530 180226417 105202890 391837940 266164741 997519144 742012471 653597318 852595765 86747401 879603862 780878766 345184305 963131048 575473886 860602816 335888319 33136075 495582618 353679590 29563810 258548378 653345463 968991407 189608838 7196352 637042734 63314172 306208830 920830871 516139799 256665209 968515697 150000940 481935927 604352356 119552334 647325142 668617803 976091542 700968989 937905604 19954971 118515101 135278983 997025241 219168121 294477677 427888983 688787298 970726850 659698453 561663386 212308071 485845535 504397483 379395243 812986329 354483033 53852788 82883840 369441975 348750355 878211551 542627529 83458865 49861250 400474851 138734713 889952164 54821818 626733501 769588537 843375026 149888270 318381052 605486658 174013532 530772288 634956496 516689094 506118217 176235406 256458786 176174206 493808996 380904662 455569325 16240531 335773171 206237733 593916198 670678584 525084292 945911888 880114695 241517061 794180044 753416791 444907181 763917622 971365742 702575850 81815037 583053729 925017332 25115990 181325966 123207475 807333231 34646350 380667423 350443469 773532993 874594210 646682684 628783641 446747610 891864598 833601376 986215354 455877790 229247918 433689446 290634029 730370203 133114727 630977349 464692518 238588517 702555406 340514119 687150192 433190579 967958349 440899252 865663428 390833577 350908400 505428918 200410188 968633708 930719515 571475227 963730043 534805415 90707202 736155107 805899183 291612489 325728808 615422033 368022961 990446858 546351491 860864647 385530475 700016711 43364074 53315686 860996650 601799743 704410036 57565462 723996795 251538644 976032526 965784761 524337068 194409785 786337876 172700425 966640980 843949360 724553509 960295083 633073002 127290570 692051173 854040428 438428471 43036972 493479406 408560662 956209150 877995930 542368330 695067764 190579145 99581145 972467858 945295480 615059129 970316160 478040171 95302981 276315903 698349046 115664706 608264593 633654279 151421002 289603401 938102975 420966957 77791566 930724880 871078569 557610361 848842424 919043552 205225360 677314369 686507449 756406103 881386689 645700132 115718260 764432071 46885083 882342812 355023759 527514686 683708514 728875865 941707272 281272921 588402216 9829477 929517387 96654375 183608412 386490754 222562943 171691873 834578199 785199303 694225922 932838646 113719680 323371605 699255572 346783871 528775670 294779389 581899416 224389142 531891703 236543704 827803618 871878459 952876878 997060500 886191984 825390688 808625829 293188659 70257626 101427575 774644677 245723315 575042785 7893941 543328880 403555572 57558100 694523243 94111985 666039676 476994256 719005057 905965872 172224966 534917430 258955577 811718240 468425394 852796278 235622690 575555811 472166475 112241648 18691079 873678648 234931669 790816961 583894485 333113032 956077644 848891385 869707252 917645321 889604861 562506949 893973515 719020366 855961656 245581036 367162731 765375527 500660689 28236191 798412094 919616964 485592047 136148577 567062344 372094927 520046990 172932820 91393800 498298815 121995422 855781110 322135631 417956141 893670610 763737545 571713930 242609900 838423790 384152108 926523554 414842007 449891840 737018740 546233663 233003022 993968642 718187040 38991995 98766518 961532622 740757006 270161882 314976104 217127886 585656448 985228323 11764243 54725258 644049111 531372654 10371998 514226414 281479017 189425907 947990210 559657731 700889180 876406026 556528972 95147150 391698938 993687830 48833771 630249867 384493364 681659465 505119990 921127218 469148802 100293893 206886720 975712397 496253315 502430472 160058208 525078658 936277176 49156605 7143343 611961734 302774730 20983945 331755590 181687564 819886944 420665582 310509519 762278275 372650119 613767294 340825915 419268967 742153925 572958713 761298195 499286366 987241156 270326508 164348328 841957308 926524743 302183074 976276259 611174240 48408727 303519890 929198017 618144122 540954312 726690882 938361849 112438965 740972277 669404851 18532018 539525012 154307934 179623393 391179435 895520517 503499846 473450224 259806416 822884214 302592688 919136781 922656046 189168348 899796393 7122782 840026793 817664414 763379762 802648960 681068163 336447953 655718827 558112469 390040303 654330811 194666801 639756375 846566904 244588055 487333947 750045838 24015120 160119105 495455390 313128700 281541756 34436818 676961862 251375086 386960554 3332909 28624732 251260764 721544694 514471357 894108845 762477640 907302189 644654523 666186678 86243459 412320634 850376283 905667890 82617891 148174124 480632934 31398013 333911490 22405574 283327075 120091309 214858689 695871251 483675344 684513616 557806424 677490703 729854427 867274933 318897337 847379413 391892614 841036060 326595540 788520944 319755923 817297975 399653126 474894649 898614765 638317594 903686810 847862284 583675322 363179768 610317533 829964410 421360091 192783436 995736177 164354937 120923142 357824647 645485464 625000527 975790567 912600934 316810017 549216685 731768940 685448724 299488331 746977169 82173993 648322564 354706969 307038655 960871375 818006233 564282253 451268325 421782676 284638494 314093426 67924901 587479853 486486771 331069140 268352193 736914047 747450552 125189578 98854633 214928342 503887039 998600725 801624182 595256041 242107601 945971277 207795192 707143057 344556354 62832732 76460178 937758478 969664041 789863749 858977132 428106826 605645487 250644780 95462609 368075779 191905168 65395562 278075415 579209578 734253349 895256624 131282457 882305704 200622070 539907190 429293416 62598035 118116976 467576451 175305001 597009922 884870706 128109981 551145814 681266439 262592232 632545346 70791814 965820023 888320799 593210758 969509946 513838687 763768229 41045741 69086738 360405990 695748371 466899431 833309859 237579652 384595979 989986538 714234474 684478013 197049344 377516710 259288274 404497835 60631664 277120457 381600500 891445833 294687950 924727075 196307824 713718757 503185707 885936591 505870024 34785665 312675257 63520604 257731751 250015955 79101716 939597138 129551463 535312080 545997049 35631441 32680708 796901194 730386378 882102 832013508 205160869 308255931 856762573 783726170 427588121 401800502 708406077 878598969 718378297 368020728 7073835 706143682 241700855 750300021 366388349 251284522 32519710 354631859 56158396 319061569 967846045 796209567 625077479 130742740 151765578 321287903 645047381 381583435 953463724 742769003 364486077 294378799 889950166 689670395 347648403 500196143 565938408 629868318 831748537 327370649 301185373 717177190 572325429 568306326 662733182 642018368 573153907 354280137 738890459 110858953 664901930 31811460 521812808 638951219 702724849 964232106 826486428 181289772 786095815 956466547 580033096 613163454 422747860 211709012 422093335 489353025 396279612 153826506 497733525 309834484 571106382 819441411 168439348 378040035 651697304 82943005 304842294 324862710 147173806 174545844 457866773 762876828 498485690 125355179 83990582 330838031 266428756 941321952 953881723 838563986 160102666 130586740 33860480 117732248 440078650 292137290 425103185 141646863 476245818 666469112 140110451 833283807 797720139 56898005 579202045 821478042 664193737 636788200 334877635 707292333 851316331 214351485 603663208 455921845 584141966 378146660 586596828 293880742 499053715 303406376 592131455 448705422 822866696 395015189 384770451 144810020 537719769 649785680 768515471 671930789 600306907 372371551 889890079 959540638 45636680 804760702 630515314 119571779 28072148 776576386 678440948 977612406 857886084 34963982 118654389 618778277 114606081 667927009 401606902 246743254 856432190 891842571 921316645 713494813 916587285 65883195 38384252 678977159 746311224 580308991 92873391 537436502 553432384 614449611 302029578 601924162 126989425 25165226 436137485 905557977 590790538 929487984 72151411 318425769 83620483 160974817 724765760 249778757 173580080 434082506 394697755 310017876 882064864 959402719 621090033 541793827 934998278 290263230 984951083 94222068 327947292 924475240 212556134 569754603 541818145 525815110 909578474 435062562 165510979 412236770 827408699 295449732 230308147 768582938 323481418 839929702 123233359 4715201 144906558 740102149 123265224 795489105 528517667 860610490 986784458 124588436 147652686 228290210 827207003 257522405 235590696 242350056 367652989 32738032 970606416 246164462 993497077 342184615 837816880 183200787 662502829 728704045 817936527 791916882 48855375 68482491 756189517 824927532 461946185 897576088 987531702 55171423 646009268 360506745 691419348 646943516 803221428 204745383 863291700 487360294 499173292 588923189 518708807 427337473 504712912 926095900 282636381 125953735 552105247 374079522 49334005 598099345 364240555 358335261 746739613 89198844 25629986 828856217 217749365 464824847 326183479 109586076 291069784 835695512 554467597 379718563 181572509 837817204 78834339 398648897 474214636 51134289 923918674 758894521 391084214 189478254 946532899 434153965 977624337 996090313 19014757 848794633 133209115 900654576 751086123 801931225 538101943 437065922 196887252 586478353 946697250 392265763 869923213 278072925 759799278 551581595 708305195 570204372 506173786 249465558 715447926 791253984 287926060 296008093 82515861 917240561 954611986 592982194 85487917 652217194 55563999 156384945 165620565 793433584 748650252 376444382 659087247 720657770 647061098 373569814 323785019 509073785 37254568 412772537 118094757 820305822 278748372 116966346 337655553 117403724 124545133 689618478 117177416 701606063 590549511 926615921 779885773 344627643 982661976 693341492 842822392 197789031 673117221 281598081 535851816 711545616 544819800 914616723 75719581 246160021 633524422 90224116 237342480 576987516 699177442 789003957 601063850 747186008 972525637 998746366 191715761 256204701 431286088 762593680 372300404 598515260 909310801 739420670 541343306 732663820 151972781 527529132 349011789 315164164 51104702 603224311 114421969 239893409 814418528 756271124 394264101 756961062 155473862 534666805 730466363 593010697 780296989 479644290 428566403 724044328 741585463 599944751 257769187 947676308 214246918 671481016 333320725 214067947 684037744 386277357 163621600 926253467 930473842 304878055 383432427 121500959 657187016 42771096 77379118 719512246 845593165 857468112 913058578 712736609 446012287 131423616 320965740 52255969 268134048 254125472 640868011 426131895 20635491 948244781 463997630 634184032 149156816 343251597 330671088 331693766 388431733 761435546 46054041 954373673 886197221 433422832 250295341 634348867 7243554 302912971 172124221 388847879 54130511 761995540 778696530 632749373 567112920 582093749 236771848 323099715 934463719 241328775 95059935 893662028 841057544 446244236 534424867 671080359 712104457 748507391 638902444 809292347 974098967 189638859 958112486 990685506 350292072 139445081 980570919 48243165 680449323 207462122 557804319 231853173 276837935 44631312 77568000 139191221 748966227 973778695 995073151 751067526 649187346 466592131 489076184 857795840 66503617 169536170 795370511 660317474 697358075 808797694 514193319 915441982 476990148 716795992 620074234 650106581 124922324 210649118 213895276 401438738 145567882 500343005 672953748 487205922 860066725 859128190 984169633 805328267 562067082 683194432 951610934 162821458 95661535 99660944 727198157 683869417 922953500 653287616 523857014 4733135 422148701 595886487 453463472 601592621 617141651 419356902 697084609 840730177 697386445 504208044 205051979 21131386 123132266 807057374 981350026 200425399 871094334 147371892 810313271 177211808 679202629 861048086 982159702 485355769 884393271 299641194 955575079 794321086 435680857 648590343 78692312 624835465 543763413 18177222 255505472 744967837 235799476 685419115 150094204 109843233 90208180 229018853 234140090 265437478 194302184 721974868 925780150 914749503 49888678 955102288 658248215 908825591 864535481 918001014 122233145 747114824 669244373 325904511 28849768 777577758 82245630 349423810 747433491 308353604 96416714 306404741 220646181 394917091 924468906 736098356 392243489 201209157 436156926 192412004 397343544 326739086 107231588 607965278 615017209 738824176 384088654 637010666 903592862 20857560 965024414 480519322 790873350 630152177 722292240 253623372 871986665 998539499 39819061 542513840 578562317 718222875 691697709 567099569 848771644 509723102 744890124 210818060 341158205 743317145 604648322 912285551 237472777 680255773 996930326 941628147 460342844 950652169 256407974 458921139 557292194 530654754 795712338 153266398 956844609 762440393 563691684 734586166 859273981 706968486 474142416 796928326 491141338 848682429 135414986 990168270 934025980 845272632 426952064 769410311 288940317 460557406 247824928 693402060 392643701 444920529 451398926 475681817 515468973 417113209 384118842 865514188 412141551 413945646 883733710 64542575 605935986 175753294 916584901 39833285 378011035 750023162 261114905 123272818 871144529 62732739 748513344 976847844 734691454 522188125 874873702 591470481 825833616 331870586 805378538 732248092 522140997 111639375 516739428 280198752 489525050 581545843 209893097 125132553 172641504 775709188 757817142 115600382 362783513 120314555 447464692 129775834 299795514 899059811 279307003 184073391 148067240 612618788 838732967 350697784 321415698 644570781 297408745 339366195 271420322 737371466 711508353 942661610 866917414 707918821 356567263 819020369 622819007 186549555 929286224 965605213 607221502 677051012 311664489 551005801 869396387 824560196 676655440 284912953 229606882 728566652 316015188 144413100 234299313 46588269 245141525 878493066 418306428 125833003 334583932 87542373 988426385 580507010 412390291 385546655 546345189 228700030 791314656 198151453 860088855 134853071 798096065 622833559 159159604 40041484 714385156 385082591 385725264 778933001 248179132 741865193 987320866 529980961 337416306 411237569 351799761 761842126 465937375 311686856 106680636 897229037 588869798 646054789 830164258 979350399 157502183 651135675 345113886 328608436 136606756 622599567 966106628 549242831 287641736 107066151 599120663 927543204 934248821 874303046 393488684 901326682 473312301 618978474 716201853 677982389 223437894 4656493 686198033 261147373 49364307 886511031 233239684 99511024 436365532 756062323 942446631 445511833 420500698 67853969 787036209 964792440 5598092 147828694 485695546 1037476 30589970 598082367 224648772 853114936 733454110 982564524 14758946 968110678 443131943 630480714 467931734 44682681 727283452 857924516 453505474 824522780 807100325 93400485 162154329 120224633 73783896 593875167 17741724 61889880 862631129 429108860 963932717 761895169 108617058 27011663 506695592 764863814 241251349 98406162 117624409 521029458 108525171 356017170 622041313 453436378 908477411 392966803 626772133 39668884 87617623 920127885 638636301 409343661 804262195 369688747 615948366 120165351 73537435 380845656 480715706 910749556 827707369 415525721 861080775 213761154 725514020 625830177 722638658 612645270 280418881 977896246 633725665 658679912 125439636 339927029 51200612 803878540 343314375 783913998 355396187 625130786 412416000 460826810 69769922 263835172 938587430 186949201 976291787 994624834 103351803 902900804 406377989 454045730 171030018 310279294 13879143 900378761 832779151 799806235 48413481 683392086 166156916 55661324 778496351 636423622 533647308 600985651 400638672 851146421 607929071 41496097 844867089 840372078 496911740 99558523 489639851 580715734 276784380 179841537 546581423 145890132 918360539 179690896 618639022 876821997 478993884 838839503 539059594 72480021 395384873 198902253 730315375 286084698 47919846 758330152 886635322 381303775 480220713 603374572 429293880 642454064 873264256 197827178 458832430 828426826 131210589 608054184 940177194 31459645 466248967 317127348 521896192 275391335 150239151 158947037 650282427 441067306 518610452 751142614 203622465 441989398 18946838 312297900 606222318 809826250 929234892 935042805 99214866 958971251 289984521 437913979 263533935 721086903 480485114 577039457 982318999 631980714 430621102 18450024 769272306 648957810 959842837 759027916 715088191 808900541 609198366 978577713 642228461 902424911 27120271 248297369 863826365 820476647 973069506 139352943 11009608 644794956 390438052 518178961 401592411 928460671 477497688 256728524 181680744 845797662 328979931 400668792 461985345 371283813 9587801 337963244 356973862 938748127 892538280 611682911 873360586 822803131 947597910 790575360 694749739 932377474 105925248 831535305 366953067 744454335 729950139 564294625 932947987 137738004 749905973 583054566 553001453 607530440 700526260 765177441 599285787 414457675 421617512 644041840 787495424 518009163 775164334 794235804 296714153 364447832 95924970 875657630 544440823 515642637 33400077 325398651 87035473 277841022 186890511 640855359 824043201 807912269 485706376 969919529 336521693 84011520 665296498 308239335 622452791 316315031 616168089 475642338 299025645 283228302 693726241 101750733 341494433 334000084 584285579 37997873 358916680 617947883 226778199 256415367 660471226 442319390 567854360 774132468 943207507 824568102 253828741 632347454 713625922 873014740 783675034 993011721 784945328 583362540 254257959 36945407 387657772 601846951 904454264 237969373 568786986 337179839 7294455 925352492 16917227 403610631 628812134 631008049 334459375 885878723 73478849 823169528 578799071 357426328 21312400 30174979 392570769 451469373 807631819 582477624 566191694 382977799 539427090 294223252 722888312 543844447 686793373 406168748 954416784 410590678 904488095 300700065 387137847 744670607 292569565 658447021 335219823 55889875 2637556 221922954 841327972 996588820 484460954 101490046 985364573 208947841 755951042 839364015 786954860 89663569 602992945 746662035 813409945 621201588 196666795 803130562 225914932 843828224 417195804 867192362 34373010 540859289 79626222 456784178 549511846 144190930 254884464 307201061 888527428 826103022 213266948 947803441 818385191 361239746 395673079 579548340 546341707 749148337 824636540 409421202 133574383 874322508 531795074 401809552 793606342 139711457 946906464 337000390 871430680 940544359 249870493 895576325 583099065 81406987 864915552 933658812 272282483 4097696 298488316 908142323 926130358 768317278 756084735 333898464 539635448 926668582 290836935 866060944 341244538 148896203 449186753 224020832 295662929 171626335 698877134 454620892 236767584 105604919 755277102 953081163 217085571 411100679 5691997 360557662 771600316 856916678 617074385 258368908 816884057 346340181 115080343 30593950 425174129 17752 750077424 912214656 512756086 831321468 917804392 22807472 246007830 684026633 478751289 683360205 759101748 799544054 682305538 80843250 981481615 600089940 618411404 429214317 310124411 134239567 806300316 133084979 524972131 395038761 946065031 810813281 201858505 919645665 910710858 497387890 226761139 517273574 110317691 942750267 186064555 211706882 173201672 50383471 693406440 897574778 485730437 602327071 671549649 417838910 815657911 977860963 10605926 778878180 963962 66312947 786060989 97403624 86640293 459603043 576533493 556478040 10903150 275114201 930842380 457743919 789251902 312617409 915815496 116256669 358987826 485090537 195118552 719664568 907846264 465125381 399842240 767966054 730147388 561465246 41295079 415337771 182438256 693515313 220401549 495236952 422820450 343175651 673428425 62823947 60306622 865089905 32491281 62491944 574273230 564540657 782355058 265119740 91109066 26563056 256505414 397078343 285707236 157848710 483821509 225371249 518287973 79944401 450723919 254835759 589429137 230925109 660903036 979965895 860604561 752847283 756601037 589768405 402646305 146916877 638655594 502812745 590484697 509132450 685856461 746760223 946355609 870072524 506011981 942299641 717322322 152281511 589568721 946156510 944118008 833874458 544972541 268742408 643124595 603144669 476526349 467109405 276589286 961428101 258841880 417386642 435221403 374693474 138892286 7803953 921092681 111060966 862082715 227634979 505926109 906434513 686056895 114380082 284405624 832757015 798615629 964257408 178778301 334393812 418753923 513195332 562079203 814663063 677379232 340635052 780650615 545114839 284998427 863982537 441313141 924210634 420188732 72294846 86097610 754797360 823720375 797558626 836564580 78328354 362287252 166699645 62493734 644143774 848343381 944584493 694491070 283566516 488088475 376211708 340814852 44338665 400959250 243623732 304662618 222224304 697072604 705796287 825679972 266033926 565349174 306674447 317994089 514297298 981865913 950419994 989678537 134227748 461576717 365560717 397392159 164683406 803136805 37974753 836426053 884081206 260745753 429604776 314549084 322730805 345388276 827901566 207491093 721277776 574895236 943972133 874172419 992461334 409461290 119801499 53879727 882368974 523816832 601264598 353111313 288012914 803927572 487155355 666073962 275731776 21633875 607690314 590379813 527974700 724895053 206829733 338752665 707306551 740718257 539706938 607180871 797648418 615269511 245121751 578118606 31570549 608360181 534968675 307091837 119921110 297558831 117440817 402937835 708055661 452020868 208065533 289477920 925788871 219695696 230436120 151053925 59052054 550373845 330142893 634680225 317422098 656576070 228293696 895836321 945980454 295084466 970328717 49904556 95861925 868651714 55591231 192382346 420633746 38033710 376905297 622293926 66349324 553587155 246793032 226731623 877625105 274033672 865262178 707578198 209798771 808164602 181583501 159302335 650054221 678038390 161587893 873376014 41563976 951369889 358351562 975993527 397390870 965462696 463554357 990978902 938182030 175301061 388742571 216900636 664453434 779419899 150175874 125823817 415160430 149641818 726260145 936862531 103883416 333663259 662161454 56196632 824053572 799408455 582229307 755807095 340549951 536635818 319627348 555704701 91809298 847483691 780023594 824911091 542277502 702403682 204548193 120404847 936060933 229078315 169808435 943511066 561794761 799954725 838845509 646968085 583989838 997827212 936078566 381325347 415618903 243677628 74777752 583881295 752941925 716144885 330653184 315033280 254373035 933136261 680121961 249547149 246587114 779710882 266386330 805630131 921577761 219491861 583283683 280562730 464098100 21907838 648758216 38412991 689298335 364093492 362957843 881244795 198487492 856882795 265230626 372617483 813855247 25565744 69904722 966348314 726536237 591370025 626821228 541781246 196306832 353149971 56367647 812390808 566674853 399913951 726739538 903283558 217083597 77947593 725473456 518650221 85089574 549575888 353498490 897687509 425864735 397238242 927672970 120334641 516272619 755722898 391293032 803388212 98557433 166901816 920291447 935427697 950242626 851007187 304241924 747498519 267107769 203568979 623266220 634093586 981896619 517140620 385662238 282780612 559290847 494646189 816272585 994291480 799752168 22635590 2589568 241138050 635855170 792543935 434620918 982243904 815699588 357989010 782672965 46535420 265763421 765538545 495956497 544989947 624867280 43792804 199764762 270589215 279655067 751025757 6052472 188283695 949119546 51517966 448593272 609507558 633312845 3886698 170149018 896259290 411366459 413760102 915719271 639366576 195796692 388945859 769997954 694718607 550242492 469708350 501452901 995447496 995334635 131895310 274433988 155410483 472268656 597988393 924610460 911720454 188871192 117017061 45286243 58920216 778554965 833111435 721030145 141979263 379679074 632107615 626932378 875923927 866833863 32793780 635938709 171856608 606568560 643296298 778862631 66076060 85057933 724750903 373050786 278492023 29250524 336816425 567765507 375945240 256831163 448116737 79073222 444672545 527516876 730899780 255732499 241693993 35317606 952217320 877089061 427979981 984464508 146308166 57936442 837286830 888004685 76166216 519623132 318057696 358568422 723568007 412470519 466919696 744411355 944071003 679188920 253325177 499945094 948433239 49484011 504680621 120356984 211384325 993034701 623510942 57998704 106305585 525224129 902770193 729991131 78524421 696141864 279741214 870948257 422919606 275832372 623445463 860969770 110525814 715933861 904678298 559972862 207724217 836988582 298556090 45777092 816326146 647006217 84818202 905809739 966777162 125278551 314683108 578878146 746625571 815779588 675915989 736343100 191897740 287578441 940868285 362151695 310440745 653384964 1076494 696516100 608960123 370433511 866420837 953376731 245713235 612967128 194647077 709736965 843240721 138119340 681232859 223830348 519191349 785233881 579190305 557697196 188393266 448395372 373833779 829237586 728477452 103557522 388052635 33976787 677215418 277536377 802882615 901569377 310185343 206173467 351271513 321740197 126049629 250100964 146164193 95127624 272450752 988375054 560097379 765471929 512837891 504743637 391287526 929025413 351235919 67544991 541848167 802018491 958363688 598044300 363252554 381184096 501366744 580796545 917165994 788217378 759212171 64088986 687863862 190688038 902056720 304029430 449297815 218297327 380064485 610088295 806250623 340407411 360885846 747273986 125243926 297080708 217549212 464070729 222720750 872512790 710718599 614204398 56954701 951659284 284890612 105851449 497105098 527770247 413415272 754464559 955301124 499863765 265524554 558558708 252473705 802669522 707749423 993390766 544411313 795800706 12443298 373850336 188467418 547636424 897801266 541949527 382315013 389928182 103195641 338586535 502791625 291003816 982385483 739767715 215531459 942736963 838463003 824527121 876796244 900688393 180249306 997655650 98331532 537799999 767812357 531648373 339714055 504940820 755532542 648633275 913605068 887658144 232566292 125160999 495119744 474138118 490782474 942949836 179223696 147985310 254944395 432849932 903105050 684280044 825379856 863680025 255726308 4706244 293278975 409481952 112534395 543693588 215825195 980822703 380626452 147356439 457224859 626411692 600925412 269731868 639542915 610540910 900714806 977924426 307441443 410348044 38372081 803172424 212863251 471107076 472702558 68842517 758216569 680430198 994555311 793188768 924727152 194061658 230891042 462441787 358360831 104258865 39288313 49570013 926814127 273961248 516062663 340339229 122902513 980690123 431620405 433593030 694287354 68994402 580683452 19847260 778245312 76907132 819929219 553745519 588229144 579882567 45500043 428115141 605997562 575196109 831213207 121870935 476358481 510026562 661434050 93079972 55068413 409128961 165953497 539477329 366060679 628049981 162275402 652713127 283031449 490859024 143631964 44402826 511892796 805433292 258867760 248976358 549436276 126609460 332175382 660998824 202730330 694200395 627579234 562020473 463865989 252553537 980623137 567477922 984134648 953995998 431835295 437319289 270260746 146047672 619022047 453678205 336239041 491486171 632206331 742203737 895329987 609125667 563949595 503068655 284572875 954885327 885183867 270169298 917762292 805097066 310543808 562772053 351485310 159353889 650798843 597686919 168294104 97829426 673252719 372837337 466812137 982566215 276082119 330060840 260993529 534531506 357252252 777589445 901790396 643335332 246347493 716826318 923281547 611934938 14458952 464897708 220317700 301219647 615298913 605076491 54374262 402500374 531613313 861355694 903950089 250889802 559536623 541103323 489056412 459762358 454108732 337712310 721732838 123449939 571794697