10000 2169
407111089 567175387 768657306 93325963 661500641 153896973 597621536 843330330 414112574 937505147 496671962 671219484 98371062 326897607 383389734 29371119 822653258 359037085 754674560 710752855 65375115 928844679 857659782 757167080 72802557 443752146 281716238 967060849 823916137 698755950 936254820 41015434 356715098 506525997 282712545 942144675 228218962 919087571 140743267 300552091 453421261 522694610 91985881 735230202 213729023 519487218 198415822 726125143 846497851 68041461 570533695 791484063 526053001 438020696 148066581 687916734 493984863 519254827 447967510 799639288 268856168 755635376 801504714 113450953 127434308 898552005 460150818 531590356 825620218 82645871 178672640 678599184 849242335 373201110 489366405 974727788 666412877 761496937 235362269 536158868 16845295 431460172 368447634 952926540 84675365 857741392 73458130 956714288 43341585 396806371 631787664 858936761 144865854 991239922 108805619 180168585 104201040 136421552 3382764 787659561 758829151 230565530 820195525 923149030 722167137 603571482 215419557 902843525 12465934 3279118 438362809 447788759 289920356 907880510 501004354 768102823 371151487 362724894 97360908 491927976 330276302 726989546 942543803 324283188 809562843 561652859 301476253 243176700 100068933 35072288 577919952 241468294 223307210 939593590 166951067 380812053 766136118 865455919 874740882 416094052 988468617 327423035 412689519 549079084 939231494 202846799 345367999 385651394 34024406 659895956 522953850 182199245 252207981 856002270 79361317 552850362 15382012 450535561 691076129 569603385 341080367 151995309 640021910 628768004 656876279 406780023 551363722 241894850 20549831 849269530 935033341 450588331 515279800 910600422 678067935 983687673 726194751 240766777 878308427 918395172 701798608 212550995 290969559 624794853 693644321 363391790 513852336 166727732 762951825 152913878 258531648 584985697 458176358 928338258 831690381 978517636 141591171 805557828 701394868 315102418 510847118 520181343 149215342 898283336 152792030 82202687 933417022 267442233 544707578 512111671 700231101 619815780 337069664 460959480 272455887 676950241 623160442 556207369 885028405 607140745 601213602 454931870 774480918 814622456 333298699 637487210 216557079 95760168 949824561 118213465 987088405 613187423 971103708 551615736 553877608 388345695 240076412 807315196 793056635 963375811 812578392 695055069 954187886 277709687 535776299 961258513 487245111 65605228 696600387 782901252 435468550 681775153 856214835 814598848 740010707 904939174 971531779 956528542 370843516 951286027 556994077 774016132 937547614 281859316 796653409 272748426 296299333 67335588 292752816 699974110 28890056 288694417 841367806 686562484 864049381 236708366 857474997 499941522 101628260 839366606 270593658 473280010 235626415 973621238 643889419 196909975 183346977 37760127 580097176 989647580 463505553 665161101 984637674 231334875 851551478 492411247 857288915 762958127 55711467 238741653 44940957 773021525 770863071 321465146 311974460 888701664 574306916 350485773 659897085 580730747 979752913 869031970 332758724 180512834 867686454 642744987 240800435 455897918 250512928 8876778 211785075 611867877 573437221 172240670 316306942 164044952 866328931 508945956 128887179 532539011 390872994 714699534 94095913 138761738 502798422 605152526 422545648 554749861 706317226 581330882 899502915 355436006 888199240 370077485 254042471 986230237 986477406 947001425 466003305 133104160 775539351 556859317 185730834 736067896 762657953 619913782 488109114 855962862 580164188 824329600 979698875 71432106 476345266 380504212 44208392 505227655 788733983 909005012 261055772 256653257 817514956 752134301 597815715 336342580 315532164 886878026 532360892 581658879 69407611 401666212 914480099 563459170 298608714 737406587 904435048 210554501 416531936 369824487 192657799 897974556 262906884 164457495 495285599 916578701 531374944 993538724 228073803 68758647 340180142 175305170 146023010 570389735 366898143 396857379 820218970 235859417 72339623 962547402 787840467 982159683 987343837 96575438 724428060 866825967 496475546 990133193 406712952 186015348 239397148 66301727 737911254 556967582 809537880 840576832 237976701 997117650 937340216 844145233 999265219 991994710 785739374 314234791 158671613 12481855 427538903 950090929 139825361 948159684 117427164 652325925 193772611 621803831 257427320 260703824 444471482 661938125 534223137 3891231 93809178 255319530 750590785 920472687 880647496 559656017 641617211 625925103 351014623 677038880 688309341 109939744 69654110 856009848 76123873 155962293 472915633 760723096 506753438 715539992 756195141 599280888 859672857 173560157 797799062 757471720 850798221 593647652 424093037 448765870 798279342 646897520 419262796 920001299 957324149 604509236 909196938 562003952 903669948 796810564 977737168 461092545 597332191 63831795 171690923 407477849 950378462 433948715 745577535 745705619 908151515 437580973 133667196 825450732 590250049 455740084 642970260 161338777 834348792 655817901 964515846 818201927 948190206 377217234 381900431 559743039 191330532 63159206 376857518 882910902 695247028 829637054 171325779 962880808 787136026 915913243 341332205 526654333 182349996 408111763 884634800 601165055 433757920 734161987 669739759 799560557 726708435 954032616 383866418 660709180 347535309 59127111 817225267 303530696 875348885 714134497 705530195 48859251 954766750 496362206 467070730 10745026 537613139 579573913 554020338 443621699 655640808 134608828 939699096 561512314 654396670 452256557 464489203 94936554 714171744 616813809 937716110 140197401 598160941 952585326 113665087 604631452 984380065 31419277 634865546 674518444 59903009 905129853 884606850 831043178 157320363 973363483 36549078 127858936 181177 236465232 612010646 491220946 181240406 712175051 538774347 827596862 81264261 828681637 667462054 509661400 576644773 602746565 168453608 355690441 55788958 548313855 81250182 370297798 694886221 233213834 519100759 154291687 215427734 519542204 238006949 609753172 4296906 758450891 264596852 369080964 521646162 16369652 824355852 167611182 171484107 237117330 975923474 2907660 589203943 494153847 259531396 551720247 497130011 507210689 138971709 452522576 167353280 895698485 674325509 337849856 314359724 215659880 941459085 470178281 266074132 775620304 7346798 712902215 214724166 34252127 770110643 333990042 397483487 323678104 999313924 836155642 101269963 199690004 824336946 899588823 624406680 909834660 717035186 776222969 593878217 317858247 967843252 711250187 925746408 823695347 869450425 413541711 163131540 493763709 797227763 395389027 327511614 755210048 968982769 129497456 409101874 856811402 526885668 999825327 872328533 22206496 358654537 134393097 775331283 892546634 444450467 631033564 614053184 897915104 56538495 971264034 480959474 932766017 505166471 797748211 828522833 122223939 260612512 112409639 908820772 154148684 905535278 946964532 576813312 846778274 868773235 804803469 311148474 776003108 353430198 71042728 132434531 282810611 817836476 859883384 743178125 412387009 686000722 725797142 136921462 522015563 999202326 982854274 650232762 786245283 616756918 431670092 36230715 20128026 312648905 213075428 996419666 433568377 836089506 648498748 689963357 968923207 974172445 714726157 331844969 451761777 329701050 498374646 550273290 577003181 178506916 764890214 311010218 420586688 594460594 509279227 229639285 322047988 624927823 900309081 90281582 417200669 218115906 30983115 36900384 648092832 608368750 641212376 605048243 497252635 550777544 256674726 37910090 110982052 118131479 813528911 249120501 28694731 751575719 136375724 127951834 881116821 266168994 701160524 217801430 161560933 853868399 872623697 104142826 334793413 306479989 182313701 699802509 537981117 71082487 633064261 73874451 750582483 610184873 187158269 826308718 953177049 833556117 145267105 18899797 202382808 502246306 787116529 892452183 51527362 113219023 550304416 70623789 947522224 503973275 458960256 320678228 139607172 883349636 744555022 372315193 476342433 933374274 341073240 703079038 773141957 430536608 27620430 369851622 536915510 588064301 963015159 353461788 496109515 56027886 428199755 160326479 949187485 348276542 458530594 885489698 565699411 409511981 823161076 325152517 46053563 922059894 197482295 618494565 211465101 239681647 61545236 778520656 132489156 481266720 573801642 397287088 845049084 209463788 82888870 101536690 825157437 316139265 692555602 414084331 247458029 930700820 501614864 881469540 739267792 397990454 762755429 670147616 893416059 276602387 878452963 292357537 173609485 691969682 665511309 792280356 985813012 334281853 694362588 801237948 500113703 903612991 668972621 273921999 972995307 257881173 448819641 725765771 725797495 863727042 171215651 235819199 203981769 518507123 509659115 40368177 58168186 188602997 567690706 786744340 523063283 352572134 715155691 544158385 328894579 960466961 176577285 453483331 327927612 87364769 375949192 844375323 913940887 785622787 615232901 218514552 305719522 714786266 796282782 913779921 313954903 795882845 880179611 80241655 809678211 379266772 421169195 292305988 211190643 40161322 260595351 675633940 64223025 855040408 642734 19892301 532163742 583624875 620946318 279772901 28834445 784064283 180700848 176212983 232029008 748035616 804671784 212438844 614375456 669626635 490657492 680031761 194892859 916944882 393108466 994217140 738125947 340415984 403159082 581055226 574672833 121757171 795648965 44121865 126767536 392447009 907843802 300309129 60551174 966498476 112337280 228860158 872328387 373730503 974694421 898872454 23606144 28974852 581159567 502731232 904091923 762515169 750340938 443775733 443555771 95207999 169847144 334633840 664501561 655771220 478750712 88837985 53205854 455638900 866653340 572813554 392221561 950542108 634175684 765447016 243488326 754229042 300245659 169011145 991549634 94860977 226414542 805323255 115034452 680242836 607239822 218557762 640961557 270095245 258746995 784652519 117801417 297563056 589359910 843653767 433423379 294316320 548250605 75978467 129010361 551406292 723239513 713540557 203932256 495064391 229315241 418612374 316152776 969940400 461875957 317210141 34842248 781735274 258341298 704112472 607065185 820811014 779703254 877198329 682599929 655270413 548036651 227595575 837736453 867370449 346141790 918695650 334606547 849924947 659743299 182220664 435728215 413322410 279587326 976128789 448726441 427939005 690644402 873403625 140373109 200089228 31482596 175699814 429941725 996619846 950701417 628053267 286266857 660782790 326584466 126304835 937745971 705605033 866125512 614644890 233284838 615188752 478258860 599803300 90635506 908813727 166031681 589877719 536387078 502959643 362240411 19182376 878629605 105497606 460660773 610755926 314162198 809945666 117894534 560828307 261700847 9633948 308098262 112416043 953980798 206403055 392727290 487535998 84751029 626792329 53075925 435748281 384894539 181689054 143936698 693572949 925868528 181818225 658164238 762032670 87463187 716813502 125349332 460306882 886245036 92743881 426958567 747390151 307043437 680073508 884125115 260683342 312330731 165559499 664969037 926348228 468440772 315755203 143190580 127961366 365159891 52630141 526415684 380776361 602927003 880061923 895794112 288210285 444377710 710848733 4586238 939386869 114433339 167553994 387045059 568838597 461790361 437999834 651988833 793740984 565524027 549075089 611775034 123962902 424402664 898116441 479231809 629563133 748195734 310975110 339517179 469044315 35432128 781651659 715170480 603138069 927384879 141666842 939842499 719788375 695649263 71389559 922987617 709290783 668683408 959735430 710404507 375477657 822403828 207423082 428013845 340656106 472166250 819247877 657356904 461448717 951876858 392383721 199438639 726816111 905305840 838616935 648852995 221718666 199755553 940087121 138615658 694462891 53569819 47726242 491023388 418927881 498204374 198148466 636279850 834709123 963094945 835290608 916414515 114999594 744158080 468996894 907822175 787038009 641156355 278184830 716975443 3484921 104292511 98964690 680059478 342173057 549285830 879860923 768849462 219696475 263811195 442231178 595832632 812190018 393243989 956630389 463663332 980355764 519483916 106446923 55765267 788215747 834898780 596966419 411003314 870192936 484341177 680412638 661398389 287067799 569849815 148065912 567731045 402536365 174855227 452340485 89841613 493466719 565878789 242748013 188196501 84568900 141417729 292288707 247039460 320421589 191600525 281370862 769869550 741139969 533950189 638217799 440445455 37527478 798306866 265305489 161019448 115820467 122607791 755610720 832005466 714944562 883051823 886461809 437001207 884667959 548388750 519711164 777417361 265414457 254584506 986121403 368506506 972148663 439962682 883565885 536642585 319724794 186388758 966801779 155499400 96851356 821115485 485161646 812778622 800976358 57676234 970634909 351957839 356539755 787972869 387631817 329290715 682463404 618620420 693437020 804081967 255186977 439066581 811106822 360776883 660084513 133179178 387427433 28216403 345400797 394061613 43416718 685618702 874740304 805511945 31512586 277459343 564419725 290126272 413319965 538462202 112749719 641487531 600897683 868839882 839684009 637821940 938651531 404335903 807205979 170165601 951807443 99783172 763111102 861542230 275526941 760354179 570315684 129743445 676505280 790168412 771740593 334381518 377325593 74029448 767184486 397730702 748884197 656087006 263487498 101036576 872689382 131999856 227836796 674494122 421857374 474987370 182903320 205459430 517570472 171222249 351587255 179372276 841000234 191984368 980933623 377459150 209426 961141965 1935182 648364896 132182476 535649294 895729688 625530012 97478639 837105916 207546792 835079364 40964421 216726918 702059755 261198180 679852713 453179440 140797257 174339386 726506995 921976391 462857615 534590144 637811653 246068157 477555479 731491863 974979033 945492584 935632075 35934543 686348413 750229294 44653471 971129859 799885429 141978009 886893519 945879478 546984496 679086310 124752992 605351310 431849265 434491062 887451823 608230606 138939190 594700984 379727768 584779539 32569441 440245554 622604960 834893716 845180776 173252767 334516678 329260475 558700999 129185325 87063560 700104092 784982090 921365878 149790134 837007594 96143242 134942735 209325091 793203708 635171005 494823936 165722322 673712414 470599600 721422774 253039872 608871516 687640478 408828261 237989289 595936584 479370582 724530484 549989000 592917377 703736637 502086895 824389106 223865470 327348654 501986244 349712205 942563310 734038086 409263993 611493971 299602613 498994266 225739018 424629700 634258622 337327487 594374750 465256179 574466301 896998998 800868524 17860793 39690222 378047122 870425159 337918978 711713004 811204891 867889104 300186667 36844776 770742792 617740060 163660383 344467143 626790168 99138103 923875890 680906717 734626298 82566142 838708504 265156125 639719005 263646810 122571798 525640659 858754113 3352723 456017825 434375173 621084292 69888878 273369890 666084469 249589646 997001871 756588941 231835447 393667195 485616094 35926770 561940057 455144164 777249241 520590435 254617391 725483363 260535329 606659045 173128677 327322761 458137680 474575332 914029516 238234233 748716919 659010348 833649439 670767153 833464675 534211623 237305475 840330320 14650110 846677972 730068161 302895349 569029769 583505862 122148089 558052391 49205682 611397538 170164652 937182672 785581567 692703102 952603426 663437195 763538375 906396137 435516783 83215236 432555835 574660587 651291623 424216000 361098951 984315268 32508744 959058877 713429556 519327126 72086988 724363182 253759744 558700435 432256608 490835767 895258895 987929784 475877621 451093564 150953260 664398917 384422757 724221927 109586618 467841920 751725319 809070851 598414940 464524981 965473759 226831640 488996674 165479759 805442830 995442209 357544379 77337102 359021021 548628632 187407469 547643226 721929285 66507693 194227959 613016040 109076501 182186889 364171706 419605995 249288189 707675213 912650497 603147628 865501632 424343792 200230172 480820017 666975155 638183348 427413965 944481485 281556899 641973418 153785954 162867414 136023931 847575187 79048673 48346917 521840470 901888337 513479933 487667389 883859431 786115103 566509262 834904425 350689590 868179392 838634166 608962144 332966490 22778074 854559290 120878509 617641163 83239921 945407582 647648921 504287235 992359541 656929027 799429697 618066540 209589022 138275238 911095578 668298733 677877131 743744395 83892829 493384087 919611644 373732351 300635032 120801363 486288210 197276195 249800645 624489804 907894308 106349863 814995267 570205421 616507898 327703224 258492616 304703770 311790339 100420493 667339807 108075651 203283143 377137588 480527004 340954839 570923105 77583818 184296827 659243201 975854218 251128534 143692825 811098797 248385520 390370170 642074462 734336284 447366872 929856867 176771789 684708949 179601810 934255215 390855108 55473332 966084650 494520122 82909547 826395188 581016151 835624113 935128732 486428480 885108326 202605141 810750649 777470086 219329419 782781892 746318787 42094018 529898298 401486390 908296371 919802603 477634959 507577850 306230692 603230524 739601922 620829588 225922287 383654540 380032149 416620699 282880920 218015264 177682600 418161846 597176150 787934149 659162590 278310739 985931717 752694469 222267683 210715110 700681581 37904410 724791690 745239186 494650529 628165334 842897835 77983172 64567894 321977582 368169690 109619261 597200116 147971899 140499033 189077357 502576615 273365544 770112762 99782486 657827874 769545777 223885503 970088423 905392941 376548934 717923353 776194622 904024511 749298932 842893392 179280901 782253054 376485541 994593803 731309855 975612960 92655718 746938250 489881293 738926058 69814005 978782134 475927425 624067358 989886084 110792793 581301076 229473243 377076794 777524345 821039894 687983881 226218215 149074061 714326962 290594363 178236342 962048043 211099932 67561826 400687557 685150609 528023123 151742573 612076019 11476764 252739314 436065973 221438751 927231176 757895892 734960835 284552838 616294088 646819841 876891494 940199639 555859577 671937809 774021558 306164871 638434035 576739865 310693878 747686892 266909148 431241092 633631122 242635053 312663561 3402126 935355133 693593708 207685425 279166055 294043794 974109874 500787962 482248017 757401881 456757606 304516033 909965837 408298924 951426971 512277831 62881853 502062024 258058624 748882965 4784213 316510389 15873442 678335613 823750710 18897785 4859530 932984649 478784136 742680138 902882706 818544449 323495317 326132742 604652711 210782007 139721322 847034404 349151955 425642210 941653813 732803190 960699074 766718933 550792995 179719115 866373172 76401356 662895481 11810432 748601369 405494522 607772082 473283780 483780827 592534159 674174275 948640027 461595706 330036376 969694455 74365995 919332512 531919337 823215804 615967222 898391549 318838402 903248801 679811481 899800790 356708501 511271947 308968150 767982967 98398991 199018122 578122639 907924587 427368082 79651122 728829220 808125836 488816428 141730743 228909061 607885418 323133391 1885823 163401763 433276797 954962397 68751653 94717620 284510242 41233070 144927556 953440212 714732638 122611322 901410537 190189272 823789097 982399744 310230991 391758694 237759357 340471994 224769783 511773456 91197208 560058747 77874478 400884225 774629990 639792063 128067933 846499661 408045893 672820424 199976714 82826158 331537330 637562102 711474012 420646830 602624609 607264375 962564646 287294844 925255313 283979727 117811052 368110034 477641019 782772392 546651575 51756891 620006006 411328510 82310024 147311043 269602611 589847138 525651034 278544467 167359943 695016981 222786093 671150569 850314693 104621525 642951079 570248727 756865954 449952913 380621658 815211583 192209505 345738253 819897318 711168619 371161695 901861817 148455159 942370284 328639113 904746003 85696646 129450217 18561232 704231707 206685993 606387149 432161566 243322348 672555740 76765890 188370405 894576022 942780301 986618816 454932117 650263439 793337960 101080262 636074795 547298758 467695335 394975084 856321019 870798491 480033682 538127723 306664904 133033973 586265510 693006179 221157874 711079812 590827154 395756725 631404963 938329199 987758294 213311443 504239759 89481529 461524256 706554528 772032893 78217592 385979310 807609978 57624747 606953862 413266336 117982023 529027497 6583328 871188533 658059071 571362773 549503259 749320946 367263820 160011902 907776480 756774528 853439557 800165930 419237117 505753426 806476055 587720136 315308884 983678951 368621567 454407060 528320384 625903754 77750658 26861136 881505924 307528609 493389362 35880661 89639848 187145322 567869681 27858782 861701925 838398227 282847657 849856028 323680449 408449941 184980826 292346409 151897800 277626858 686512080 151182884 956675241 390454720 309920946 285038809 108145488 513134406 774642421 229060463 19474226 638615283 654668218 954780547 70440696 499399984 265068011 700635168 494134357 610426554 554292060 753548600 225019857 60831090 449106894 39744892 541801261 723821736 830832989 395302364 933298968 452419814 939013553 190905015 348886334 135453915 374984316 740593456 849857643 767640620 977094001 93067693 863643609 718798377 132477869 15581923 341818825 799482468 523704491 825463324 221244481 571228917 497844219 497641953 369070520 782442819 95635802 232657094 801742599 505582591 220266350 622428590 329483185 682480871 945647906 504721518 596439363 730902898 581268168 992323789 411383073 421211634 441414287 802716556 777447430 639366212 676389345 671902060 348555722 882810447 261015041 684563356 161693407 232491934 280478415 798420053 666824874 314595531 348214421 854340837 778309260 235302981 860072439 787319498 612635585 645136105 286897806 309932465 247972171 343582140 839195539 315876672 815295367 779737067 119859229 937013930 869950891 437765899 257429944 868024353 182880226 99317658 551232077 641494575 823583117 81185360 796687244 760292416 981279844 838445085 417496947 782114384 536795512 968871012 924655041 63700824 678807372 85786695 720119017 440536512 99031768 582636988 783265149 568185895 316487097 767008642 453211243 132380231 427876120 432771033 997837473 554824343 569712133 729927148 440655720 466803334 452968755 339900794 646690200 655299628 187929289 632753238 849824992 46906165 116592768 870191436 304359007 702877705 636064884 834919707 309418542 472119738 878688424 715089800 493714254 62321442 78705307 551771372 495881408 293054376 58536372 768560986 634963822 694524215 315627366 288494164 533219084 392207364 534116838 324359590 975987340 391513758 928930550 665287948 90508368 861449441 384170336 480344757 969113107 926013775 318548632 897392473 48960802 714966326 710311491 966390879 26296232 964600602 788413480 545540763 615006318 530478150 989682990 832023732 402867781 950665304 781343374 288725129 802450546 31563594 749416275 865297968 228471554 383063028 444355558 262748129 413648729 488395977 836382861 984561613 420324216 395214764 317713921 922321010 248951680 365305273 383287766 342794906 333533650 883092499 93979627 3723623 816799935 954852679 476194204 260940546 332806229 748898702 163492785 235667004 11618195 45489202 267634949 962400627 959724434 173899148 385910655 484926928 596837031 691393557 13784021 544868575 745512932 239849853 831578770 444445500 70354368 11350663 716252544 157176958 959789849 604854881 808029170 167571284 552002884 752604678 389491259 839276465 546073780 42754937 387088546 63646840 988263086 272623941 724203796 964225163 328654830 393503994 301671793 768448926 236278473 947933247 648551269 118257869 393986610 967698628 936447367 843198845 302073388 420388639 556616521 578758645 186038641 195942130 44298879 783589901 237120749 128580059 394219905 376415526 284857579 670800230 83410352 87481217 769407428 538724768 493345260 924996029 435211934 105626085 140939075 428194406 857053371 471189504 704955504 192940015 202044370 549996816 195998410 473605073 113801531 345376768 333081041 657364572 582101862 623385683 646838268 131877867 762743249 928288765 983602464 83716502 225119995 72391213 259487809 965702539 800831042 102843459 240557426 399391571 282526190 345154244 423593402 950255574 388834578 483697035 503311901 852231670 815890307 712043116 223233542 2923129 29109623 826158032 156600256 143998116 632271449 797841146 967420730 946502802 993003544 705917733 287427223 136045262 277104227 187029732 95866159 198235170 697631269 660159682 434502329 593816357 368063729 590373921 410565237 875124337 986122958 411709078 144312191 476650269 107105622 711252384 838936769 375362190 525963431 908213444 76242901 613413942 469764425 621476483 491992506 930681031 379904632 910867607 529715166 574099534 83958079 655902145 417417332 470352829 487442512 853626423 675236180 546308034 992927159 732009925 243144485 425520590 548071306 512515410 568684698 47860213 265097638 999346328 411849997 742592581 468261207 689629126 22813585 822958110 67462834 794943579 454419889 821223834 372658247 346820699 11761198 827836204 226915095 412820835 502141757 274860133 525726144 911730049 958571648 741975686 234989487 432500753 840582765 838289836 344537430 949034335 529889251 280027461 325181755 849590925 342663712 682366720 264527341 589496090 143340262 330473570 559638271 311165585 715465877 494441485 104386542 623855654 264257241 991946039 308253691 830554857 871052227 285869797 776987122 761183945 314890684 587357406 441096851 885307321 476120457 608642609 391492298 829639862 346210133 162815547 346840074 2570680 345927880 610905700 933377811 772271529 343506964 261737224 731279469 480214488 647660623 203414207 250741086 768640385 665935757 134530692 453915736 768055989 169163262 232503911 569966514 889657879 782761276 623786909 813361603 663044914 131934178 725440369 232653453 655960868 618991525 327781553 596109760 855846721 264547193 546841267 996070230 226786195 569609671 748086974 546764427 703213468 850430035 351455679 646608103 112693683 327574780 108896918 920889029 705443010 528262939 230900581 734598788 182263895 466063197 684065317 129656422 691476859 95028392 475038205 571330105 483177835 49823548 681012186 749623208 117426788 806421041 235807501 183548815 518592018 946548269 494481414 63604141 502870042 279151816 253180659 655806639 122068138 640394631 739443334 89381514 798774409 631898984 327922976 705927055 222316439 152645520 418868033 703678712 315118341 402911759 593808129 648218209 543120551 610234058 578643977 309964460 258105248 833416246 656385586 579866147 102518436 928716099 751474001 958411371 980343609 199010272 281655283 441404274 288097377 525412120 427101858 442327017 849506222 312616702 97911233 77184572 915917990 929826885 82928683 160634029 664655871 980811963 772068343 450433160 337114306 240501664 436746437 478270012 90731123 891099195 675569176 917519197 320889775 894317192 295735977 147076301 900505254 849263829 495269108 487473711 265434129 213498457 419847464 629193508 141485591 713047578 559676204 608614524 235783807 967958139 770812726 199400410 877530413 12109942 783542548 897506174 965051245 510164300 233109097 191574172 188593857 762667389 153341735 270571544 179481856 63576554 705412256 5665252 138116846 929206115 691021002 997724651 90830243 444944766 678138824 848491254 872769166 335541281 555344410 969468459 151512453 699459261 481781596 876987816 925668292 471302922 183583296 242192608 493250135 719543016 664747376 609911632 236724124 677796342 344017335 999240491 368124237 348227579 849191635 189621600 55853896 379652263 100610851 600021791 853957077 553978073 305156572 796981958 453999277 941332985 168913891 783813651 37922479 122748169 874332555 712512245 210992313 274881228 598585821 22247288 414682783 243599271 721034364 237842706 43620166 166348052 592806420 550758973 218833928 36051587 629962314 472231728 530924269 650666805 688011555 111211420 304690837 495132737 81248634 397307517 129260052 370950047 468217340 732705530 948875193 389754912 697144203 163944715 330006562 276351755 82326728 71021553 43585798 244868130 852139609 855284730 972234783 634206194 308768435 155065800 285432263 521088531 833758044 502377618 968245992 468276685 964512349 177215418 80494172 537137709 101761689 273651779 350826911 165807425 321796876 643441632 557841978 451251353 998753786 317930944 311636008 461706566 919444989 20098505 322313419 789477938 500698806 155302247 66283350 909060871 234222233 308514547 751885884 262910545 641290101 86511432 837938734 459469369 122239151 734533879 782368956 618206068 979989945 548927312 306900738 659560783 994823283 172870604 840980080 796011418 721081047 691070971 781952868 329046066 219490652 230826494 363277694 315828326 843316221 192719955 462756600 382987187 942963270 528811676 794198977 299185140 148852067 136918307 746050675 484403953 531643190 36148977 942165936 429930824 73769622 286222276 904631256 337836389 380800180 277812119 282240250 458795777 12052439 933712611 921614460 644437788 686721503 988677674 447532476 672023640 436941327 102264935 730093378 207795807 706375248 549939994 972844692 457187728 150574887 689749256 208329363 754670118 666648426 82289103 974562101 529013159 277331267 130264283 434393004 153653874 667813788 720121939 927103555 915511605 164942757 785384152 291434788 182254580 683637732 130611416 75427768 53820457 299142808 892048521 8389106 395413627 33727558 644259279 101669386 41954669 384490222 868716472 829360273 153949713 999512714 784079793 715016950 452670194 231536871 744133540 373755181 518129774 503506335 88793034 439832116 165972601 756355071 183628452 597133325 274775727 112526639 657235026 12735389 684424354 617975155 525582077 115583108 598290961 902121598 16479893 694781054 90436837 359930438 533782061 882231308 880310889 449765122 639520280 773270574 766596938 219657909 42130039 27679330 746938653 841889562 529949036 308010837 341452532 148748715 229730501 887886406 25690592 164359515 883871581 953460084 972680843 708302508 364954896 265494624 804929719 835419500 713991885 860735740 374285109 488727172 448428802 828291203 204490185 548450900 887747635 949041160 746059733 85049682 871375878 903240262 484354200 375433724 458549873 800835178 570018949 293345480 695508580 536584148 635494300 231170932 463475083 192648988 490274974 511074455 514920276 821438536 9834990 897205531 462547611 606418557 858008401 233405264 632562988 780297281 178837972 92711996 943609900 396598379 198658669 332448000 145730852 126899328 118429505 164939975 7327386 590283353 603023908 203305722 53769264 216601590 203295210 587465429 962137434 129577264 779030555 235093837 853699966 64068540 232251043 537290850 261067344 554411848 272410217 142150242 907603269 150722785 567210529 917065271 923016969 11358183 438167854 565872807 474491494 561057621 87562017 712939668 351501984 770384696 901418221 250710143 62237706 84163552 698794945 8829190 839777305 60422560 952211219 278338351 105474096 611711761 111500678 799318598 288598968 507713813 868745743 195329927 224180073 627896783 386432383 592887309 682213513 382114442 348641876 558735067 273107422 806432237 189141143 430605187 164444994 130274165 538836472 953580918 890249116 268971883 41800731 674046193 617718464 579047874 905771443 720181749 811281418 600194897 625871739 94464225 936519030 322684582 78069420 187883006 742311617 405595638 964324786 513009439 145250618 912006140 812172763 787514703 118906501 357330021 666259944 160751047 104356801 889778928 552012422 992574435 944649984 95435804 111423803 346160707 337432172 115970576 532294631 984897345 634155449 210214770 892355756 743475515 401553394 100632442 666544410 858908689 293977567 365955498 982803078 744900566 944037069 971394191 231789525 414263686 789057852 960823768 273885080 408288831 894839759 158317946 705626103 630721837 140130443 561978127 883887163 373790428 229390645 703888457 7446081 71056665 273787502 546379322 207288429 363076763 883355373 25219904 46411948 158974182 980349197 248291840 623350561 630954715 715261157 623540483 966814025 668332964 520143949 14774583 332466533 88116346 100459549 690286114 902224405 195132353 321922537 378307211 463658181 53428113 964730702 98045388 742899486 368070250 71500738 174508017 8966503 306341012 650747327 639826232 855321752 643402846 624211245 581030885 104465426 910605843 329925268 274393189 464771338 1243849 817472735 791596767 446759885 177210454 307979554 49742415 331809102 560890037 415373007 946874463 688744962 326239373 398170792 456271770 284994973 57372747 684938880 728595365 347814026 427021821 217527905 113967594 491917786 379985810 499343234 435315720 193849402 916500315 913002376 791919400 76297974 767975429 285147042 943823096 40482333 396935600 795140248 140700358 637736725 519384550 778959646 847059683 371369836 589765176 740555023 11915400 852524406 686446705 999390013 857972021 711438778 804064530 432213333 704317025 194090440 55241230 243923336 785160251 654954355 174663408 351506943 671052154 624980551 639212422 34016942 630260065 245406875 963628619 223220932 185974862 76043601 433504666 836439342 848647887 889572138 215351543 181268887 264133016 781850921 269994772 593434071 109190330 184725598 298873326 379086561 652205154 947553601 360426406 13811477 313969426 470503364 502428147 783188074 626480739 629175692 584753243 363783829 170945004 21955153 961097032 897581497 383871603 502856635 236972777 299629333 654099516 48634770 357911361 993215093 976481570 816876236 397646938 168855279 349520428 885733652 802137105 60756292 636708708 820581192 972569498 253896328 375350855 996875410 534330083 43799081 815901741 150606140 924525845 780091821 47985052 22386781 21673472 133595113 272769818 233381465 837213143 227051159 316957613 391223575 876322128 779799020 179630294 189172511 843476338 325491572 471967187 448528353 321979008 349187899 942733566 647799365 134593669 987108808 150897896 23309824 712372876 904481392 697718488 688714025 528556991 40463806 456112446 398668515 985957525 921103368 672658529 904411354 966160461 94376122 334552069 515120127 958911753 428970089 124549121 921952230 521576871 400849971 322303118 817177075 333702598 351712212 871867710 661399023 776015865 881153799 387602221 441285366 745997340 561506800 448912636 50017804 116435473 775017084 792317288 996187673 997473598 980047534 768707317 655744174 743686604 447718732 955178639 53262555 466318422 638787600 782561486 909145257 769740487 399970617 614643397 425031838 460575609 854706886 761526383 593560098 716117721 353266534 659850637 513989434 370703727 397300652 909882303 800390027 898588121 485039268 181129986 923058666 902031351 531305710 222613373 276642752 686450444 687976870 707719513 775030927 35738824 509457296 914420021 251159546 555689012 141958464 837260594 344640241 76757328 867641178 690663559 373870167 927503299 40833690 733692083 753847456 362551649 936270244 750367581 329905496 122106578 311056594 718916964 878680433 337376736 69820218 621664258 392457222 221515181 538278000 868292148 700827429 998263553 639644535 208396737 721562940 464587144 618970656 797444842 345655834 815419514 731566880 974943336 202578399 9655446 737650523 963181679 991859332 603206032 617945657 574710229 57206483 98517724 179787317 33791472 218832086 136450565 744748885 84319605 991293179 532096746 404590418 240570260 79977708 662488771 959665020 405225412 420250320 114315728 712433108 864303761 702735210 402036681 723846466 531521719 287187305 656371875 251225947 173421053 95454929 17278943 886805957 374290884 412771771 499848024 378347301 676965635 921013755 358516943 674348328 727370108 180709087 173555358 362358784 773918908 554071517 472429575 880489013 737529882 42603896 829640680 145651808 90896584 722198448 98150453 767878333 25299202 740413667 60136208 900857308 63562851 296277033 285286279 73751818 142031816 668615795 545616261 229840423 238311718 558786631 952352283 544319215 921494485 22980721 77992162 98887527 115774717 196279290 482367 332386844 666390446 741964200 653528012 810454515 80151411 333065966 508059769 603083490 692138727 15703448 493613589 26238202 205662033 126290577 927525292 815930778 668858464 40662598 863660167 334504301 22009160 466532130 46024993 235957987 675292107 546451433 277136780 777367004 671161056 248731813 210193434 892990396 557480023 561777139 497940674 834355371 454897587 233155387 158210845 811919157 271093051 421460818 724590543 453834612 426927690 593472505 548163710 216322188 283589773 699210308 533067722 293758224 655118962 7788201 276665762 28136276 417539456 131553324 545257329 976460849 557159897 439419012 708037829 401326358 672536994 127941211 285998850 14166868 717531558 542616955 826175390 365678844 37716823 866901819 849189019 295116751 812700323 917417600 781741613 134346648 261876795 650352707 477304086 321381321 704976002 907656568 931430966 679111874 549330583 192098176 918060029 366602638 810665149 29743291 306717643 953295042 504704075 821511274 474744583 123132591 67265796 224906657 746302499 278840261 92705988 533232562 468658867 624846936 210319807 489474469 355821353 208820621 68030220 47713776 118835576 876232346 967275132 903429 678546730 654665847 739264054 113798227 574232641 339770204 180114616 530210228 784595710 796274439 496612166 244568818 317733799 676493525 531629595 724707565 488433952 689679444 21023440 983681697 330978073 340658169 249316372 998222626 385840975 820387626 259094745 405647908 447837851 359370193 463622774 589372519 628953403 447070138 112016395 219929076 362740939 526986336 431235545 807632942 192202073 329951265 573744385 247975683 84284893 509568969 737359277 993665443 453089408 478346378 735369487 742929076 957530708 412926273 683058956 16694532 356046457 175528441 375686144 33196315 652872692 866048685 322616133 729388117 740512054 719468106 113962046 740210022 393150224 874968205 186504941 406432789 751492181 136979070 518689132 744550449 107123861 452766065 71537909 390367399 727532615 204101158 641114383 698196347 715112384 8854160 101292102 738356434 449021019 556567177 899337027 129909431 139597802 343988042 120948662 724408526 911930708 942455207 614973683 641373278 550207027 954622000 518475168 482849299 29460001 847965873 692337836 621098346 341892925 242641361 642506976 431187255 50364893 626615136 787723054 998250974 294588999 96785569 947771320 426520979 237438759 354209061 920958383 597261879 131169773 540607765 108355622 895827092 572388071 996817429 482479858 387497639 395876726 992164360 514888757 215331805 683722627 702767143 825736908 429059612 413849259 805256890 983280850 619729231 465602773 333008207 622650957 667627711 189531349 462889588 466889948 358747506 936280740 591668536 486409469 222363515 491255079 725993648 148104145 8201428 649721435 762221256 50705737 846337138 132057309 115150454 365190813 483210248 54001356 608143709 723304468 939227049 252570640 799022974 233952567 376181363 93448307 588258818 958622948 592048856 729103075 465472257 447897034 879592333 4783403 467150004 95495693 632890004 733931120 730543897 591639763 334406212 613535266 954738755 249760182 951384826 216784211 348597832 28011052 618595910 494479475 18156710 919171425 708105610 836498874 432270249 694878918 743808612 965534447 440888359 764005768 703284567 633413117 568514465 307205160 669016924 443480863 906332182 786667960 107015998 753236920 45669724 825927276 212399611 657016763 755071381 346344114 849906227 57547730 304739581 15965011 639254344 983796220 462392217 87374830 669319677 838990165 556460030 37902979 753867926 866546535 973502260 453411496 368483550 32151211 92237860 654811626 399534348 181509714 887750993 151103867 699325841 966638574 47048442 55863143 889590086 983971511 940442884 398749847 764651581 121905716 242591187 11587654 710129758 666006137 801124734 371126366 852108351 134585822 402351293 137875438 50447953 576579653 589480367 262481123 509617369 764953759 648693124 566965994 359472887 437662025 837777655 281386142 970770052 854383505 48769543 222768216 327797083 338586114 198009372 328823658 732238491 431049602 895408020 699532850 96794763 435071965 857672488 935463312 496876790 441190026 218935487 966942824 367141493 389344477 814725873 197611248 145949810 906699029 111222624 895068120 762042437 416565317 168407008 666710594 570464906 887611953 146648076 992037160 120358112 464462012 177042717 86969413 913175799 884649181 67260482 453787635 351870732 504197121 585309182 762025012 103955655 548772098 523950701 133061357 823459106 304172454 340528629 268310273 834076500 17924291 574646534 4421552 42925759 72153193 717463831 590982092 497670364 237097089 879568750 101855016 980959622 428562318 501989469 283216888 776939850 498008603 30241670 668347357 232459546 96043173 432771490 467628668 820285240 977311216 234275381 940359808 434212053 650061864 337494807 992866846 941684551 470267273 761559776 177433523 803243982 537496889 255625943 55318545 900013868 672573844 955352060 246103312 460874756 961984974 521346160 392520443 661172595 306768245 41240273 642212159 142249118 27732084 164492981 580304703 269801141 818863062 342838684 231671212 186046899 557312728 593402660 579503237 260616133 193428656 200198429 942402319 611667970 672345516 568452890 810083371 950459737 943203930 948874093 175729408 895997194 294317840 160115552 268283396 120779704 616195616 364485441 639430157 280250716 103001603 390547959 888796172 483713187 937742215 963923222 70413487 307921778 761775977 59802083 158085744 871859772 670225587 576183746 503649625 992562385 609245387 99300516 946697109 389404806 607698840 536116841 428324176 540947726 93628315 99320686 439623080 979090906 355654137 905332145 299455802 709488556 507307551 611431483 404967551 94173166 791991192 878611160 966987645 367858971 7175336 483385461 501007859 448562800 672154814 24911484 316925987 706207538 947620302 330043760 253435691 694007883 67413205 830934264 474980560 243149786 349989353 566584797 33486947 908897890 536937045 274945084 740676746 973630946 175901693 110807330 115484725 17789300 787765038 81952184 886441755 205366201 264424520 662499458 621727718 841258225 854431046 564015682 103893703 356580449 953043467 163820131 343183868 427044357 518631329 733633621 465778592 3383740 501592791 766290868 994635774 71576225 980903596 551732285 200187917 19087619 877987257 3409855 659736884 164343638 252441906 318280848 331126618 694845451 137701775 796745991 887902121 801010630 24725225 323590798 709068780 83232809 615353731 978364246 609969199 507434601 261950352 453269200 892169190 229116875 405191915 598582311 328869660 564107418 362118569 909769272 390391018 889617469 225964588 605894587 366585048 105294999 764105406 943383682 77894761 666225314 911804546 289095365 744849768 780096094 749686561 725466880 366798913 248697778 884936393 933565308 43608097 227479189 620612071 716053247 166818776 929375113 54801594 910699371 931096933 488969167 762090584 267174630 974927066 126040556 481207401 454447526 998512992 256505064 765344390 322850686 732621422 621467863 649074817 267271629 491382507 305512564 248258477 442353628 820548798 827459291 975732325 681454272 434055278 138247481 956728859 13876932 650822492 799534395 331390323 232847051 887629097 745503559 558909666 844079716 989316283 61839474 88084416 148036527 676173156 919405667 30409104 210058771 336099285 691230542 50459593 107660277 497210244 834487449 913818481 184286567 76300417 315471397 629815980 866907792 212380126 960137215 915459011 963791153 897488177 404375519 661639607 113681275 62735809 687694192 849334011 432632046 257215357 872828166 759772182 943332961 690131811 239664740 892673923 122314053 130089890 269914158 467208559 892715284 872081922 485664763 678796593 602856285 853362224 484196369 33993065 705155683 926744964 796787496 525824984 909934878 123723143 780673443 645580108 820302991 900409486 42719312 554179290 881278013 296834301 308946074 218075021 669799573 817697321 571426453 243949349 920966944 910329037 828283461 963266226 683670044 274477894 303983400 996989270 463420183 293120689 572214632 127080677 460259236 193288535 564726937 237940707 720182316 288712107 920538498 837218149 696563122 226935021 419684967 998097566 401928181 126264485 377276294 164469573 139227538 583021483 618567132 231667317 575079871 338008847 941786188 358616344 300503776 192455614 914230477 771249789 129761897 824377873 447750400 990330010 333999174 823958885 898808666 623392590 384536929 146196380 921541294 538511622 893755819 332962940 59373573 215380030 434754313 723410263 677020110 663060054 838635795 327673050 856057756 251148709 266410211 636601742 345779829 85259835 238118015 913035336 450129970 640329320 312685666 465172017 771437905 956915013 937633540 696927719 472562798 910979313 509866269 920830636 993551731 943606065 227005008 627267509 494858146 295564462 120913557 125093740 109597770 616898006 5165549 329457200 194930226 102778579 883306106 809837715 659975385 963824600 732432915 929835393 867188310 763866893 994174485 249169386 57809360 16699830 459654362 304880736 638118819 926019920 399524094 219647531 232194762 605188739 810852130 144576971 332197715 447881520 546576816 723625615 914202178 398232842 254116014 150216965 376650387 274951267 367982667 380959110 837612180 691927967 51641466 730245383 425938711 949565182 885771390 113818800 597036549 827165052 262198957 729782326 193613740 567510110 583580799 666018334 428519145 60472235 715574800 755436154 635994233 973258654 521239935 448174728 605446171 653153903 471202213 480069764 821064862 97576743 814229237 243794064 468079583 903674440 475945691 449815153 954622765 668170927 776494577 875245506 351892074 365210183 222930957 94175173 987096866 501862387 440439111 531929828 843778468 627118002 747311984 706756708 838117543 745241774 471007835 245973725 515052726 419568902 157270071 748762750 675568601 762133102 327720683 464552627 35226624 249221864 299684315 491838710 393795196 225775607 918694007 849525021 292539651 543255536 388074527 149809947 766239252 50089660 854874103 465900050 754038924 179433413 461436546 556504997 441654487 527627741 235479716 587521545 765503052 59673024 805082057 514492206 58527613 711179903 131345061 728231537 415542533 323980284 509254930 253863930 995275779 130808752 29173573 992000618 447520182 245655232 106260940 891756986 92814093 107971160 408354223 371351363 627111135 215125888 635189046 947099318 855470231 533504410 500012721 11641507 673546133 700419646 647989029 55543139 345906361 378945519 603852183 113847028 684373792 702193192 125351969 991887920 224949880 648276117 568380224 961567374 263802507 348007809 614799890 210032095 919859620 855753566 102010252 631031020 842222938 901155243 65825087 343111851 82148593 606221674 135020573 417135252 476226370 985028669 171275958 539512811 685063621 897895436 707850126 334411498 389555286 613415953 769060540 609561743 355086160 728052203 12903851 331137209 860074009 153240044 337371191 609132953 744484911 582864926 416153580 598613652 496831631 619467894 97165071 76461593 788300134 214128332 794171685 610589882 739116816 105714612 104482374 782589415 640299917 466266691 543132012 272965913 211104923 570143242 480349001 515260372 176040486 486219444 29172742 357019952 987176668 255764724 359104120 547565073 856875235 216013244 696329040 265843546 840390558 76919485 523418370 594703180 777511555 117586926 806454291 158053609 137406235 176890101 943110205 53095729 872899707 353294086 483220446 174169945 53044447 585421911 365357586 268285204 386687801 404475701 464130155 911932963 935862861 663678059 361713926 204560204 744465231 903824107 592842198 176578276 708460964 990148950 320662083 442039620 780065495 854474291 531095131 73972632 843959847 729444262 61222286 887444163 126848989 122087664 553856625 747702092 689308253 434451162 344669806 329075242 411986992 647753829 577575702 134158074 914447913 946204042 545111863 417147348 88423675 765073997 223221006 549872337 182996311 322832278 43091707 243659625 229528416 788976794 639777468 29958690 598384315 488430051 828203756 637632640 111670730 613781926 299352699 290341974 867273833 639177717 758604957 38951253 769129069 493629176 578072990 339143330 942598519 913358419 890398980 893515637 788673382 121145924 812545791 219739028 59376084 114361906 688619016 895880203 730396815 87812275 380478582 882436736 688459555 968976555 961586452 535789857 955487950 473604515 562623729 273861681 354922125 713452609 741540366 811123479 551788584 980259474 512059353 699234595 855480406 195070595 205622074 507009148 819889597 65772051 419755950 778826452 75803970 487554946 119176186 824528387 729917853 943561114 303157365 253537367 521041351 995449749 368553892 535908054 558054875 962463226 569447300 888514681 161614437 939509761 69789646 83601954 234312129 309112303 728756206 193714574 876129373 399480340 39409220 822707314 388500065 629756944 298440076 313726151 771666961 939313454 716506967 794320267 933437059 678482328 566132209 207514207 857645723 81712272 119254571 399528128 606532506 490785045 424609874 535943985 960866778 519613645 815866462 611213332 310134990 625951635 458234822 105962116 802941050 553995484 390695208 243238206 264807128 37392090 580782300 436284409 597272622 140274141 348808191 352630072 88028942 602908761 554576088 67845977 645365490 76449819 478037711 418387485 994411109 313613473 7946858 622843143 935766868 454561969 812403157 436933764 427547564 667673599 761027713 54365135 355352326 516093996 497108635 314195768 785431975 441465111 653166871 722179462 797928497 670743238 814226418 753307817 937618709 999585383 720512559 558317575 142777483 294523121 285380663 248886406 885910214 265679551 495878136 217039024 977130505 524406829 223828682 429189507 450284005 749578880 886210795 300378202 168783 176206867 669790172 134779304 758481003 197011806 975096552 41144199 100875670 286958739 167848847 657069789 278966649 24025563 233729749 987899268 433547769 569845495 224607509 75037905 705183970 224539332 722194172 204304437 416841105 856214988 207162277 399902024 133825290 751168694 534754259 575505639 801867093 865826202 557392144 709096373 292429125 301865106 426304044 905644256 694193258 737705583 847293396 507919474 888318654 626540056 229383245 983263978 451342591 555637018 644343011 260525123 290549838 194460504 440614040 987072162 547818880 238064395 845770632 907623392 952268678 735329156 35491610 529396056 727381549 302163439 639977510 231866764 682719938 16774182 643225745 624249663 563187229 198216492 517911378 893765109 544980681 779466707 966174594 133665259 686300206 293135290 122223294 456393855 559920535 375861146 935872270 613333747 705328704 902298722 900853202 561381682 543115357 520746630 210567352 943493268 192732343 724475736 761652372 151904805 432806455 655362053 593284062 93766663 801468939 493282111 634168025 701226704 245066996 344567493 987497744 22510318 565583706 390456497 600497223 38800948 278446043 576687460 347264967 233066009 141803652 359174286 804031416 399670508 660392674 937361125 603987464 223794156 418116460 415972835 171992115 84604797 83745497 386553997 655863126 182297980 258289837 91376096 708168714 155730612 90868201 509028881 916474191 937840224 828968953 700764926 424440665 979264226 188908976 277522288 437259055 736820898 210203284 63906712 32407107 39910185 904890295 890729262 347154130 250426539 355203031 464832934 126013332 261848076 636607994 91844431 935301763 392488081 724403189 108971709 240323399 840060769 268316547 255110098 876513692 973265422 901024214 746051457 294836946 692281188 160499114 103371010 266589036 258232949 713632640 331611665 62222311 892642411 263513308 249332348 259171468 303115616 448557288 866952712 363631605 324786426 196625405 890966611 702398360 657603690 979500769 204365186 882526296 466486669 357272090 93411749 599320167 350046821 943385980 687509956 298959927 995571154 352301853 365481256 974394920 101598350 943255924 731013703 179975411 633522412 257387199 884687805 933635833 561343918 671367982 705936674 960610968 886603519 152819906 373910680 638144940 608317349 859985842 781530827 548761143 92909812 81484988 782521621 182392978 640482810 165673809 670825695 80060329 142429000 944958888 307203335 551953048 141781027 869296334 571296273 692234395 400741473 29312970 529232730 75454163 738474453 279006218 281275947 958942858 329887033 247183020 300197346 769282844 745206652 62568412 653132349 855628183 819445114 169800726 510892616 698826859 663137660 933791736 900499421 940077403 374530169 931300797 817792411 59112548 111591397 857342863 967458159 943758216 829666764 906968579 590632007 798365377 502845028 107356486 87669489 164926799 799936437 80110070 375085670 382929663 334340520 892789155 340631552 234647978 500123391 16809381 623931028 472984609 512541285 845037716 898397600 701259395 293564680 550160004 162726458 630617441 951652772 312603272 611861764 862924374 537596105 667940028 472711823 905778151 848491537 830408783 817179575 467318290 384192909 427656711 760785864 760449820 992611679 97158875 895056284 674238378 145567174 494992001 956314590 500801093 9895241 824721070 3453827 382863967 703523640 866803764 702449332 597343670 347823642 936450904 776141669 118401040 600687035 704599591 238538257 361637944 556433501 846301504 6499089 860027846 800615543 698377826 324320776 468209793 486394944 931541107 558008357 492553712 292574934 686653480 396230544 932661911 519418151 408286536 62508991 367145521 179190683 839360738 427632634 279368505 999914662 827053288 960453132 166229146 330226866 731946359 912124742 36699301 581460750 574588815 537988303 687674011 137756589 882638027 670319067 948854102 882387229 894942620 312070203 670353892 455787168 633358849 570134460 371670661 150086836 913429080 584016098 276255252 667664924 608964782 656857057 232580467 625796418 326003912 764496980 560359796 104546830 750115587 690124206 649563972 604090348 431410844 136975936 614271911 381302696 429441900 662480354 903888794 600802403 774839851 198108287 11979627 181543030 100970283 899398917 537357978 108877091 114757254 732764175 508985527 966291828 472840140 763771202 6065919 834818775 201396095 508380539 252211394 29622087 916279278 501695803 108761991 359175149 75541377 539480458 993225320 854233018 284696031 437558260 932760579 208244768 241100984 647521258 510032638 900533067 613746725 435937468 226078232 562849080 919269246 324932619 1124139 704800483 935878387 52577093 607058900 944343179 864932482 399827244 307997376 247556209 485851424 304007024 884828397 397867995 237816516 156059424 763542730 306449076 829238245 956189752 3202729 969833981 329686927 533291335 248838303 406998755 120339360 925715845 596757377 309795907 517843657 477195947 318796237 644579455 359656261 499980676 652642614 513597682 909337374 36902426 576454966 507866239 833019318 868384627 926719005 169851878 231693789 254013668 549765475 99059400 294109274 926775534 133060717 665054429 130822738 527023976 228519571 441965236 420112579 356853688 849764119 890686486 343842166 271089441 111882124 235253455 70472695 167481409 956416057 516179331 943800554 153918935 508956052 879395253 977738127 501304867 651538990 586133175 784932349 46651910 355879790 943492862 580426170 635032073 364590314 904322623 533628245 294951953 933385119 851365230 834061509 136458299 703694983 832063471 940131078 326921092 76388161 77808196 662145639 441770771 334000990 637754704 155024620 245424170 941469082 753844403 112579674 236933452 549127270 694599650 29260456 927104049 859644943 662170232 486673170 401052242 576909657 809042708 863188039 652216163 741996225 690879225 620891719 85577044 161371860 757442223 946742736 393582003 18019468 198810216 500244167 658373003 348433960 902930501 494653614 801450159 567772717 8612516 248717559 961899657 305019588 595034756 178378582 554855578 575584901 458440641 585260779 157528500 484151070 12231734 517281901 846535926 402472194 526094401 442607136 402792993 875035585 69717919 111145818 64381301 833544310 53393047 176589242 695523154 521702208 688806281 286694592 67666364 789652976 763978156 188324621 402674631 569338969 595056233 177526291 923464462 104062304 521076655 394612795 621042043 90094230 585318181 299784317 399852339 732594398 501851851 127503634 851401850 513447794 924629985 613438891 421761745 419207733 888655927 115134136 65813835 100094459 685200325 281700202 548725454 860125637 838262577 585217986 380363313 155119824 19147554 495168721 529267117 495941268 237788837 254910954 193417871 280046875 753725148 965685807 768271354 812715485 536189132 178576714 378881871 456245072 981461339 365370915 208703637 855577356 352685157 694507137 21784058 379007756 685405405 537606146 983843385 98834227 789244814 408941488 119133911 24061225 411724157 582518359 839620612 934156481 994750401 726010959 532545948 612386253 761206425 750562077 778649834 711811519 448515928 393421299 424273786 200647447 14797589 74164209 715483599 765355303 127996967 212492437 19096425 868835353 959134622 996706945 587062388 187709764 967517745 301909287 507790882 756450621 9207349 405505037 642973658 844032166 922204196 712250326 539368721 206333119 434407571 540089502 885919375 624632559 26441491 692409623 941470389 73380251 301890641 141834833 763722482 671902826 217307697 528609260 446699988 957835619 28947474 356955422 951337146 618499830 301018584 550180566 3442653 486174094 195714501 613039613 329711063 128765570 10319087 445200601 484023517 504081255 407851638 896580974 998495850 455792001 178279512 646203577 406762062 370196376 721875231 738602547 556391588 985590679 616764281 370708156 312837315 263884131 377309766 549079094 5093751 433879681 567521258 975008782 889936127 609800686 813341213 284870642 96997373 364482856 218404582 104869481 91794840 609370653 804588517 83169177 302026540 290727782 983070482 282256407 171334622 623848724 278081007 562977879 44340020 775799736 948906246 36160306 889175787 77853335 558733632 203461028 251337754 48517539 449048385 615571243 796977387 795967015 24524172 189619969 431542139 321863298 481536324 472595577 628394604 327911793 252773878 462649488 244682873 723238441 872563606 442715516 798900240 976661633 494390895 728590918 598375898 906235731 426345490 10627665 967647989 841000910 80833162 825658101 235732960 460020014 872479401 229294128 557627030 839698171 939704127 355536728 409632501 805435368 726322816 199312265 186421806 675292329 444030766 625004856 347333249 753987673 953208589 318812695 746186443 641005241 255787578 648728575 548264645 407629001 931498708 11083436 47901766 856406368 304180176 201380381 852663528 419777257 774753448 838440385 737263841 551764204 746699006 45514331 995879300 257043071 520523712 328478172 148571321 149974713 966685054 244569530 383494423 853605343 240721118 670163303 281626374 409895037 755692182 56525418 566982370 350935766 544522901 426973124 970389478 323514557 32918949 744236185 997135613 391397224 932817084 73151623 952406516 725178350 700588090 161094857 49425566 570545265 392220557 959129442 996418157 89831189 833094389 670104830 859181683 151442741 642151378 199865141 822492488 813934919 625509316 207849915 11805989 994451893 614806560 927511649 55785596 112291981 620331394 604718922 155957483 233246933 419083635 377923678 522402962 187196403 126909134 188321929 845127535 229553301 684106687 56317042 536944590 651247446 627569618 683488449 376065853 470247692 410091494 218946684 233625334 590879082 737778647 698607423 871570190 653552239 651653232 696176087 860733992 84600716 705227265 9022917 755922435 308789574 77806923 261481718 434476591 134500551 549215667 565016189 69846632 363322477 747813510 158330451 999485056 49621601 426086798 817977375 679006880 528734931 168457462 704644184 857600658 798043562 722560267 906812829 267656236 133940050 26069463 462782714 54727875 183101798 121810930 315921628 829617120 881538801 433033081 823715200 52395876 452495826 398910390 788553072 982700135 101654542 812001505 994596595 63563181 841919042 145352765 526963784 641777214 340351919 153853842 388161916 725968548 341516585 643571029 335557133 318565124 207296536 38961424 47460336 192357688 81770460 163223934 322188906 666904728 837926954 341388891 56105151 493214930 568095495 274603126 516991365 887234532 341096321 862479211 818298157 499467437 883010715 295047588 194259312 542360719 339000808 373413977 312192075 253930556 494545794 278638647 532959121 114857756 695367087 526264176 645542908 183814567 903947197 31571842 454706195 845762842 32974609 567216120 173276334 560082414 564662584 312632011 233182593 306078854 226128384 929238609 246450003 23332424 353985121 739010219 470634467 499541143 826144764 962028490 70826781 201672415 897750632 374272927 679068687 661704076 911824497 956386509 645360672 227532164 48953796 74495819 88350020 66798008 475897417 941982933 538020990 324224905 254916231 258211462 25150029 799490741 167185295 220739760 105388032 347988802 656447924 876152440 138874939 667790905 148864607 62887139 290605049 449095753 46480585 239973855 394654613 134671002 412567442 553557713 782585992 473542208 822463516 803735597 953078192 697022822 282331837 653140268 862834735 270485589 994122736 811110302 662622954 319644816 951919005 646438628 628089162 15515366 371702245 600895971 172238713 961839455 132104848 572203956 727208085 748486369 98984346 820088255 644943689 10889915 371745295 378324739 336474008 954311584 813505097 486625747 770141204 861753185 586445192 86228862 100042672 792249288 696140684 535042360 441300742 147235664 534322404 457882415 728960811 320041337 414402423 143582433 776071630 98434494 699009890 780392168 142976594 37912047 247471791 303962271 825883451 975779348 178768486 311801312 795895778 335393010 130848896 228167909 985080312 744867725 684017714 491200415 279582620 107271527 826516989 318584500 951117067 169942220 602317458 914642347 774336199 389838759 126125688 205838573 131756552 374395410 891192568 158023906 365896532 54307135 125963369 763768917 151397086 752599284 140449173 325156045 380395613 897616145 409674960 703065828 416944553 148600595 715041259 211179017 368341178 672603816 184033322 981141573 847280248 728640883 179550102 75255564 681851461 772440550 281969919 462018234 120413507 951099881 985124425 516968652 298956053 125954076 669098980 278501187 429020402 182633453 283651285 656222306 955084 431546399 891282348 517811191 189511974 256214737 12883588 978022262 368939325 591674621 329014620 923487259 5229929 205079382 895219904 651175707 835536299 449174947 4758284 86369345 9498120 143535604 196146086 451343408 176515598 3488263 408022619 654768489 50708745 603266215 285790778 632552153 946485932 265937822 281165020 793790512 712379759 869012344 455674702 766165667 776370370 127329038 212914463 329224075 422876421 330076157 901242774 801020908 432999595 73104245 485999666 448184745 338887579 96371155 307115077 402494134 253215928 205049772 907337481 421892789 352522953 93789985 786329591 594608610 624007356 269860281 570945837 132308595 202485284 307063858 104585654 673904451 679314868 332471899 851684463 473897118 28979199 679119105 278627895 837844758 358459828 231187555 637129208 923379682 277308378 109973969 117181417 548150700 843619427 896483407 771078546 814886537 659884594 955317760 502893401 102428986 448188083 892257875 123576860 327332901 823850115 692916628 417245054 82189865 228209561 464103710 9503682 639386816 12808923 953104757 33382616 103455492 812419520 736730601 712404735 597684399 889140482 141528145 812612103 647585252 887342431 938273807 239442626 501297600 310274755 441195066 906054160 120045101 959492391 484113205 472089191 20667741 43304084 984559483 804695872 508906176 717988386 774836207 436226417 84416275 912154382 295907688 590568644 184280966 326702051 967989977 777891310 153848535 757841024 709256064 565729798 816625132 184360786 58187593 217281876 962729319 759220336 572130248 208704462 673569554 463995108 204628433 533462613 892156566 499406869 413362229 406358005 220705471 132514711 557540705 329382935 271601212 723862065 915844574 999916968 664751538 544660033 841663548 447055005 810650262 652858795 229556567 90668670 229824354 869581599 534562303 924436325 752205336 167587169 741486256 803181799 465623021 661975708 351033052 128648588 2704388 638105926 784319499 910847302 874293373 900833162 322148674 226571173 140939736 359542938 923342923 197435378 257574274 787383821 950941094 305060145 130021276 324485167 276078074 733374195 299596914 537197695 584992375 448616761 343653444 837102193 833795340 969133322 254921409 285641183 409337162 170727624 862290707 387748034 81810707 271813265 311151780 958568225 537003280 523370849 386956223 868254858 101364630 383228254 294009337 99471048 184086804 512200974 356969235 130642113 302365519 659934529 722905872 183739810 255042383 243031090 582492080 49899478 705621979 725995479 157190510 214450353 41035095 952704656 391843129 696057896 546599585 134161257 839137194 138196337 760878618 928649043 633175703 693677440 251393257 203721460 160992805 827042173 575738864 948177951 744082056 838929657 93539454 126059336 878273549 982971681 253755508 476968392 496863711 448817689 550684354 305959846 245622626 827200612 461405500 870434555 162833258 415529165 701996408 219641435 209276346 906552186 431847525 198100713 52459759 705861455 749578151 158435070 959193733 554934764 995924788 457445716 549193058 644666852 104324510 722776753 685743413 392512205 684354634 284479943 682461685 348089516 192993190 971349381 26527690 240762467 272804512 493890702 885634525 821865789 609646307 671592345 912641460 880580369 677907296 768888543 997798684 451077879 99293632 533512275 317248829 109444674 753119516 747492919 196171928 160965446 815404548 611919424 201230024 796203558 168240734 822135150 169609877 409898 250202731 169970148 956021811 820398328 965385904 976104332 455848378 844157520 330322652 429383991 887676873 380076753 296266727 224426871 492516613 808812787 230847564 100103128 649738857 143772054 24686832 659486734 950487332 25954379 83699302 831421042 724030132 762349507 35721084 460709789 490224333 859552471 164610252 438820562 896249154 126809229 623726509 931464885 506198346 472700837 22663285 129074905 545782059 972503726 933749119 826900817 21241 47211364 78908850 738111616 272940156 866959859 785578833 30715388 382469864 903925773 65522515 21844297 154711289 844035631 397927206 126895309 134672988 417334328 270957584 797749226 168134925 309777098 322483718 117303179 910436062 981974013 223292895 810293387 1190716 348778622 925826636 892630106 555660890 102779431 732268018 326492220 442601955 968530714 789378576 794318860 460140018 794823250 648346648 267926482 82155616 167864131 466838213 691270207 282715235 276479106 594722010 954306543 764896853 548890937 549476119 161958242 878069112 428122092 74866274 423243382 46269399 958275061 592067124 73538835 797245370 931142149 370937355 786504199 828365404 929428897 5070275 648403636 208009883 953056740 242661861 827161098 103833811 453374016 54389782 160052877 907648450 207997311 135645867 247069669 792005047 933627932 435692784 73646191 458931482 716088811 996345722 127990258 634127851 636918922 518333884 946426670 806927938 296829810 944008227 298826518 536453284 559299302 594275603 292313444 873605896 806404842 121973186 262066590 152127567 250254071 153564355 23153195 84396791 497407715 669526382 919089902 928589168 523940653 402269528 609549324 942976547 749669605 859002099 385193742 374166932 354045071 647283916 402798105 569069198 175344022 449830604 710441509 721116682 652699843 875763496 222435555 772126424 975857881 145912414 312237503 784035764 965056218 16924748 164384855 795573013 465940306 203794625 662574553 282714159 110245233 74820684 604757214 15407639 383330958 496401744 453948729 735018390 514002851 999213258 473596271 87688293 174788337 672865421 994529382 11605229 753497754 914949369 194005793 597966176 2595251 421536184 103438724 265148835 574644044 151344429 365611709 891814628 851412610 622221708 505975242 810447316 476638480 482276137 625086786 98295130 232467328 579772921 780688912 850843986 237654304 640649101 508222168 252208691 597380806 491807686 448796503 192523065 201203198 549897502 625317833 253775074 351687383 327995468 194255830 857512430 69787567 442978413 568969992 160758009 80452882 629970660 256614118 500037117 107109122 97154805 862929691 240725848 301693712 670564609 332499043 827412786 11782213 188659995 474123233 860094502 998703401 237539545 174830509 766827536 457407928 408176236 722803728 980539965 714623689 699054571 555638471 678415019 741373047 958201567 484636966 978511079 274632610 942799046 274423190 105379369 424061837 491964688 354019570 318553119 416442353 547002951 243572131 227158906 516487261 666564350 60971471 72663228 592976064 525696886 833796093 681146416 695799875 696552373 541789215 634229755 297310248 287758354 507684919 383492733 353083424 338729880 903094200 753887552 396088423 993602171 155905424 368119113 678962852 33955761 829738611 314527727 899029503 970631511 138963125 758119036 740524569 807695821 107735610 136635415 508907951 412576462 265013110 793295030 579382850 92453865 478164316 331762556 34957719 150007064 651230729 625624995 266643756 976640150 370691113 897542163 349930186 875874968 746926305 66449794 823827161 919868703 697496341 306967915 791106263 616799788 865649387 543138318 821035110 480446873 695439241 678482551 431808319 405020600 602756391 451172515 147763819 478934518 302397267 414466382 800194996 790978030 478444762 67656544 264911581 266207094 897881116 817841420 349128784 727856515 232578586 440607242 812154472 78127228 227827979 578565257 933381568 806336097 63144164 477711626 910308118 833119814 234971888 695681639 890498035 207461542 677481142 271101257 657837302 750139171 254500453 866010207 341477711 158930673 95275051 529609697 63475399 401660346 527102424 268130066 549790904 365738328 64209886 591333268 753119100 444319892 46648652 858705231 236814026 615480433 488171874 537088152 488947106 867408237 486670390 299802713 673382946 820534717 470702984 425362003 567753552 903736944 293966738 983415328 573250819 749819534 107512616 835808308 167438366 211690221 481729035 397226017 806837586 894933341 609322866 666080412 883292337 275853701 884851780 913545291 165715544 577246261 305545325 490507018 88269411 692654043 130831262 439035978 823094789 772035647 1357097 732454141 538516452 328364651 502095888 343897535 191574506 771435267 857100459 273893201 919082882 691638643 818164201 668720077 241087386 101166652 921235535 354456789 984944358 289924973 933237799 974512156 871953829 871222241 125492808 155079573 769575143 879500491 598308564 360465647 486123554 927273954 582428611 488182631 696658298 788086644 79521811 225111698 72494762 784612025 496872723 688334239 398552602 293328238 272404680 212579621 158112493 55467195 375721802 608484358 42558685 404595409 430870332 177393491 719916394 442801803 404079967 801780636 56275207 640460870 549435481 205181659 348822717 203786188 318120364 614994795 675816439 196656167 635286903 91780336 235917227 34816355 67462844 237711908 856018800 27995068 556993353 588347543 657860360 969164687 678753193 974758497 122590481 360925118 940382009 833407543 577519807 647045869 878251037 60821110 185144062 765454611 870268833 894143717 956185509 460321695 852858726 867511458 128817359 760802712 114942490 788950570 951605402 976719689 107413332 901986843 721370718 934102197 190938765 855892295 526173567 181418277 503421364 636664072 501069777 928129284 40109964 881087961 680329115 10905008 618485358 721842257 638802019 305932577 333081509 282512506 545079364 883049066 828753074 904580395 766533471 846825986 964632700 812938580 554754010 250379548 163420617 500001272 802521192 845531364 29087071 722492554 563135911 825794237 746394597 820011415 495499918 962510133 805944865 822079464 877319973 981232039 708518010 689463617 963494397 297337425 412308317 113425111 800835454 20122609 997917289 562697258 508711256 9539358 415121830 114438935 740290204 44528474 495553026 46052094 409492224 862456402 233052077 694112888 114703084 568444803 292536874 993841408 662319127 560679556 709498124 316597237 239340678 672967437 325358619 671642264 855586502 463526743 180526887 354530183 754791408 742376596 252050573 592205107 404533749 960131332 507999871 769268198 181064841 892297693 833790466 580043940 110345993 724266733 10301351 910158488 411337564 979742436 391509356 213010678 788454462 531195476 199915702 487644625 715470857 769075601 891008943 7251553 796833058 999129538 34321134 522844159 48832928 389317760 392719270 449702587 950869982 628696488 589066318 483006949 671799207 744426778 339015079 791030002 137719903 379788489 297587336 848651340 845139403 452015667 36957108 562052742 531487054 810663205 379637105 543398230 324962585 287357710 480868601 384964728 884567775 335701171 502735673 368830978 870078139 904830597 359118495 819525677 173915865 663861600 982702264 67918684 189796088 415563778 825556192 930327912 731900796 468132118 320476509 809520417 167723450 747810145 799153041 755196089 132070944 563682248 387814577 64209166 494698656 596342887 172393726 441049610 709951608 619080476 574223755 163090746 72098905 673720389 470928685 227178832 485496102 503590701 437877279 226947333 815601411 277057458 12165706 464105601 665035139 953851191 719783431 803982579 24972133 387786417 173958489 195443884 397753339 786758123 201094923 312867296 664004585 639983747 186326740 932939039 307791580 535963986 715190375 906552571 260954987 440062222 437231749 382613884 962604802 190231615 289170141 414132409 100880417 589371596 989032411 409910541 834337036 365660569 195128756 95675333 825683086 169516707 723948197 532615325 983094499 614981766 883889561 960295739 227801779 64034534 120105623 936914553 987034748 341331809 442428994 6446034 150910001 432083463 945194570 397469217 296064680 698981152 409680345 41834777 760444487 295850982 892728903 216495849 843407190 750169641 50635804 816245288 11100306 347819389 415048074 289045496 599961157 371505463 514754111 622091911 179500041 593895908 7291395 537407938 104463219 90783704 440310215 679134838 763694928 577265600 44496819 74130121 188643909 91928605 676037687 301020856 854781448 183635253 830349647 27086744 30752844 182882840 827515643 995766402 635837558 423967839 121391348 164497080 544717837 60774385 210427008 226439196 964024426 443844185 148619213 957263862 610354090 88298242 183847274 382722216 143064753 664876943 132379350 394305990 46855854 217684202 386584154 836299932 642480480 251835366 863800719 312645052 520536178 738814815 249731810 508566406 461345269 692110036 731867941 768616463 468148430 250286759 702793178 997254417 409464997 954789649 124618256 589165452 579272146 83275776 536232974 440763136 147356495 917590470 464354590 565476350 498749896 977035708 827969215 861027222 529512469 97654971 45914844 712127608 175859865 311344586 999407600 670459021 632099642 486228089 306096603 862301861 469898972 704110599 775168647 306362070 103121501 947365294 649785093 679356362 904805177 520160275 778799262 213195221 692783518 488398006 996752099 534996139 330615974 748486589 677210956 553835767 540683798 721264970 53282440 895192978 544829414 717323678 265227010 467973626 481295921 855096984 378023728 99902678 16886880 675369621 220353721 459025882 425206367 365493880 903903492 470919835 397239107 474494406 466678877 865081389 744219105 266574572 186692138 905872302 631376392 612526264 320736397 32142992 430220251 850443900 42136581 849418733 354486106 607014246 56142380 391297938 887778525 956217358 989591535 179239629 586929042 870208484 201100940 554890197 559957733 986923532 930024857 417441013 686035882 260436863 88808561 855704773 200054705 480440435 839784430 705777122 12283696 462913602 625369121 332762525 904533241 140066131 405476807 702547064 762900326 277082003 280723851 165504075 979692006 359629911 813049609 587538304 143862483 907205477 348317196 664601379 243461290 643056715 718018331 378569154 523063386 134334670 367539376 265740889 560920405 32125330 925573903 271310207 625116165 119262852 665130268 388508570 667965766 174055762 884834619 970818616 838867496 595969656 770417631 309186830 59730729 543972492 935219254 303937996 601286169 535271207 607043105 972862675 877391449 504212757 337857912 514654351 287498910 301502740 777398321 77011337 918161086 91171427 294221273 3537594 700785477 505702578 386230999 121193616 95186371 305755447 689343042 936077479 725851145 892471473 465437362 984189513 29874214 414421513 866330256 130252972 753057536 152791238 665632802 28459702 466860672 964180125 158169111 498154816 251933954 107450852 900285569 414049620 108501250 935392846 330870230 110546359 876119717 443537189 614437206 804358617 505631959 398828617 476527893 695461111 848227887 524528400 430580654 32048708 760315911 772891099 359303561 239207083 237021082 574039426 279403094 350371656 16382003 682609722 390434024 455376401 684352728 990833663 181625543 762217898 239148644 176310678 405907204 162881165 968209191 940832036 827718244 498827733 430310876 274008240 442328627 449523571 448053793 13012101 749856372 236035667 996273013 139205625 912654336 49027704 9927924 265867401 698118791 882709757 135709208 438326775 841331411 662204418 166164959 872163559 971995091 522063644 430209051 685185101 399802428 456007397 195939647 924142270 833999027 650481397 409060180 676365887 457558495 954762403 888166315 176842750 890219733 574630523 781813660 882998582 795663017 861097279 750048794 94269966 399497213 597259462 14094245 808049630 687129323 850193032 479983173 384697242 687312426 3555376 632840350 239903119 32345403 109379631 877286601 835388542 932022432 365181813 879112934 720202767 170724402 26256770 276123912 995127817 535042900 345927587 679086732 665371641 950547769 126102958 545262731 776763843 996475790 504119365 834151209 4370823 315548256 785075213 715724441 312597606 215201914 999556114 297662115 653871169 378301162 52692855 375654786 388507599 682262995 326354719 360351954 151573994 531703779 313028977 957445701 823735632 220607599 673805420 425876850 638678441 148263129 435247065 88586251 683815027 383169186 526803096 340176297 736520752 344161995 316403711 510048752 225374385 113620569 556783061 60888371 270325737 689126188 562272870 960776468 296089120 871354268 899104215 704583491 279755001 327596803 583292405 655416860 923943685 854889431 265987400 86791634 344847474 780658633 728849996 886151490 313443824 928697867 12023502 875127831 266204636 587312139 420120036 597951622 501920867 301547046 151209621 181586111 168907092 319004916 704397103 454434921 370815851 10148015 728975388 528617159 138404412 66423323 863501923 959886278 682066947 283302384 615921850 621323292 550413612 999609343 171729869 329579688 140306618 172012667 399506187 803625244 543366631 229781980 730863697 572463710 723013566 678961974 995561234 655874504 840247299 477919483 697130637 955321689 22010801 920649992 55688376 487555950 27330585 105639022 666269940 407625212 226732908 927917680 785881833 316458168 667356661 272524534 609413069 748398897 413471407 132967663 733853556 840748203 48216648 489238588 254668884 535084726 612541257 446146027 210605885 67370698 91668156 199467277 553325341 973605660 676691530 660402749 982798541 488817085 886305817 215005707 874977153 246463568 264282812 233609264 147903765 743466922 635850349 124285331 45925010 908965379 83700407 526988287 976146693 832978109 581856300 277886964 892244672 304180712 637672250 759183554 173034948 540575293 587860389 215384138 864130856 374253948 207368131 642366960 709430680 324618215 764121822 507468285 547114634 732203867 519472190 80103983 368105177 319372270 951119919 628541488 871292410 885353335 740822625 846837596 578454921 830353599 248484517 658367002 634347357 366209219 383526025 526199310 348775412 821196330 267176221 784645939 672029042 362169375 709574769 666452091 220669323 590236779 865697178 778268438 985553848 661012941 176588390 470154344 437254958 554077942 595198297 805476916 17509332 893164752 196947530 360426772 243741516 398270971 547360991 80595389 298298762 589875340 758146464 414591017 591414903 117850639 96550794 454398563 488455628 20071959 614440065 531745270 150750331 621622653 560430604 713413471 232550001 161764158 35732892 852851344 634706055 147170716 79428265 199968700 200174147 377191832 939611546 833552157 962615907 11821027 602441660 823297520 249123110 54206256 617872375 722063973 205084683 637914323 942314168 718599496 361619048 507122322 477490077 16255634 784955757 611539016 40579470 645652141 475571167 395432934 170346014 840362351 271084898 995881474 954972851 929045710 959600898 171944157 241151267 676442367 782054942 275712445 2826486 140084018 975564469 187458258 419561725 357202132 741501640 830098142 543850200 693630432 180005455 8202330 775594537 51709534 542766092 130018091 580876375 639637700 724107179 856558475 294425735 565602023 284658630 431366674 129859005 912741204 963036900 789413631 939581222 861897772 793844906 958067677 984851704 639805385 626152419 83799832 939644224 44359914 976113676 860790792 894120530 227899009 963394680 513553320 932230873 435219259 738179167 111920729 847058668 292818399 682968943 230460424 407359221 932095220 875063694 775762145 525935462 573360580 635328426 42304053 875999809 175294405 777053492 908893170 43406501 219539222 418660191 422192149 584937260 218763884 842745229 180791535 659880531 871433053 793958622 983914912 729895389 641805302 965864599 93063973 465246317 34821050 56490652 759893660 237395457 705070278 499255924 827818161 941695777 322688515 464541670 26652233 293526043 950646959 284104703 566374790 311539762 693496859 318719857 161090941 924183835 542885527 126074089 187999849 478280882 35059814 113715829 265154025 706489122 653235218 617853875 541375756 70191230 596048423 956592961 475710194 11760850 663431711 552995699 172852015 211761731 638932938 214753357 932320670 832348455 435827025 537966092 521642290 76907789 303332155 103206888 10123801 61887702 378967894 371638324 466413421 495235493 758455113 748735591 498397428 871854312 662500170 161558864 711686816 736862324 785648217 166911305 861680057 952287938 787033881 101414443 209134901 743772062 797023237 535458493 557011919 201472465 182340718 933380217 229756866 734178036 254860405 474347650 861844165 299204807 225826045 87864899 570611485 828397669 992747399 389052244 291739790 881979418 602356057 809085856 414232731 441431131 647843831 633938865 774424310 415226010 88235904 180858671 469103622 540588498 11720577 632935450 843904688 131270133 342469846 470527889 703865044 367086917 104251338 991095502 271155959 424252224 338659056 620805555 613041022 538863697 573998401 381920289 991121001 613422224 414596177 21433863 418408480 22981054 70053595 915291321 740071530 928882194 402081815 705070252 345203260 70770151 922469611 721265977 180702577 787090710 28747551 579496382 961917459 929213781 92630142 496394472 256395484 784702874 909829753 846793583 821256294 4475415 855667923 34909960 831581061 706236390 787370387 423616450 738845092 582216280 920178782 512571077 180287994 550943181 961085489 440176453 957770106 182635342 404281109 397356140 608754356 923198102 921208679 306442492 72936991 656499292 53440927 486471823 24836934 334753106 211164435 892075224 767319335 431042931 907772047 126804512 129738398 430661232 805827470 733612723 499381742 405477830 540491538 344688606 629324279 426940632 17052942 707245216 996433029 661630139 533490416 781409508 427022503 260077436 208048711 174384449 340772790 466593729 695747120 457224433 980951316 22857825 380525005 439702206 200757208 30666234 214621508 351146893 833385457 449259193 905011913 921680335 256122889 478343611 550809103 937952420 430699601 168367777 703612849 740355198 973502933 299911013 206682677 897354169 166651482 324401693 379824056 998411668 817436600 262712060 515431524 677634005 646190662 121318386 955479597 346059141 676180985 669656524 132849003 137556160 196810996 707886684 158932743 297020069 851573206 678602678 95398611 135615982 177803963 761821051 829066773 452439616 57158977 338860259 35698844 321880918 733655598 421712457 575672473 873016682 659374772 949831536 769435038 240279695 456195540 602237947 77019919 556406667 821027401 851336760 916004025 614508464 664508684 745294024 733799150 602952169 647421732 263017912 912114095 814110558 551801221 272881727 556302323 588382690 567676354 68503971 174532791 323957332 328925710 311527554 520368189 265894405 412871584 151085154 199249241 912238059 22161490 467233609 341103493 4213609 265298900 646061020 299042549 642775544 977663030 949421507 983186655 991338581 840301625 909200927 178147689 771145062 73083454 621005028 225837976 527629153 97840439 567557599 677305095 507621101 97217313 470687367 880287457 612489072 697949344 131596941 396040128 730027877 354431408 678070054 926221767 393862075 955332765 163504055 746083653 604373336 335454893 914196717 754753520 929542459 347284637 589459077 415901970 218111374 596078084 357317106 999524274 178626386 364998491 457052261 220298545 613259671 594295881 760813210 102535771 814233542 780174031 55745360 745946937 383331090 33931236 77764430 446259129 870894230 591608214 126525188 796627510 521140436 129230810 690128982 461721595 370280811 6191711 226112041 280837715 706365918 741142810 249381652 775686250 38500001 346435515 183990908 514381408 460520824 431805275 696506789 673783971 532793506 290939150 817748928 68195241 577779940 575527992 815875537 19256816 265494446 635150158 844414608 358775573 184965317 991247652 11881982 729877549 859673627 28423643 846370034 51027845 398649522 899060219 519115259 332004196 817706568 355172042 503886134 308127592 329400593 383064492 532027876 197008291 419039583 704557040 149239183 269592067 466031984 869557912 815785420 637615503 141903889 961872911 630050884 212212998 137243053 608014836 779385422 629211285 872626578 656287450 646684884 107065448 745965123 657259639 987600349 355211703 741673741 89950178 219015368 35194845 247180899 883305969 89973576 614444044 526650393 906163082 510016599 88981259 418509671 168314937 695013819 549715876 512834986 137958132 99901856 305068938 431181362 896479024 615221208 217996543 228819377 13535476 596714520 667476076 868357008 656401093 656752483 405959260 473650686 986421102 896021139 795449651 791371055 247325075 756487759 917272091 275350953 220280191 112493600 709798290 236011619 635207468 642518292 440152308 790255352 886216503 885253602 566649294 798733469 468226928 164254272 209963495 975354004 815065690 353081245 576901814 248290704 615674304 277305914 807602318 504055891 217658400 626367193 519743245 729438803 166123703 660827733 534766560 387875554 750714748 411296132 191621854 18956371 743591065 656055855 148214594 16101625 37432180 134412677 539640819 236460570 687604715 376746396 449360005 543556483 157772610 622759773 729499214 961689724 485872493 355216559 47185211 755322958 417741088 745496404 25718204 762997828 10318742 577345480 757776959 707260774 983189212 59940537 222705879 72530555 823757239 441772009 280304935 203539342 994718694 299275539 117331952 840198338 397845598 961899620 146548206 962631882 811131630 626935627 65223663 453392665 364646702 420313678 361005740 724638018 25547626 261395980 491740937 188497652 861094514 817354009 264696825 404370650 131985577 496571771 26886599 51725995 937019771 773608167 220826258 378001507 976897383 920316719 700702861 532970298 202680501 173929140 614262317 806705643 608916319 262212552 657013731 374205415 835146165 900181553 189546119 292296441 913109695 727611637 675457722 661103357 952121306 490319532 932597374 222883560 562566735 963120802 130187802 656370609 243765092 639813069 511697284 892089864 633407515 65631116 567454795 251800560 354746163 798448645 52349612 781727896 452072526 62213181 229690216 737110082 843183827 202258236 512620416 823630603 788597303 49468226 192748420 303402873 910064171 24535330 158013141 260454354 293083153 145672822 667203961 938861193 395050038 818818335 327348653 803960545 216661229 650358728 717970577 667827776 473657341 426329804 2854984 522167826 212953999 244530482 26619594 273171842 782030765 103153546 317028349 473999403 169111404 979530435 56023301 634242048 289078681 93313110 412678224 926038263 659397488 458688363 826467212 343724724 30581472 811364981 580207914 897146831 471515053 418891828 58774205 596355537 955089045 476194314 779660983 747363534 435146488 146180322 92478277 133589851 635211570 663105390 325578967 987716917 73877616 112374046 516521647 15186048 759043205 429594344 37095716 182774882 833291825 53070139 876219231 520053311 217184011 109839881 222542316 533057629 570792303 260637144 613437343 84375111 716326180 334207939 630456546 368949360 679356523 257651025 583816047 814548585 765941133 139027062 514512830 212129443 890932123 428859701 33408628 208611457 396577610 703707302 371453574 726733971 575279055 589233102 894491868 227122302 498793952 637291379 258817063 524747460 872016203 114749218 176425784 743072552 147727081 254671773 119029465 689432545 786049271 996704881 342692609 237268454 469247309 94866856 522274563 398255049 367070840 726659782 998968987 471035537 555134111 494284728 354563036 574955574 771687228 558365501 980230824 906178883 453359769 84824350 352745180 68529274 397382579 587428041 137502824 808215954 791806813 611306544 436457138 328714622 697084149 155230381 577392659 943281621 111188818 729230754 339867039 978186856 360983106 44973428 529345698 741049793 122975725 940384594 968151945 265472031 306173581 817356829 187488600 772631900 202476328 824561911 1064334 66590583 952028606 146832212 685948715 516965671 82861754 636651974 836940561 657377176 687563995 442796114 688035384 528197842 172610475 495282309 166639695 954712888 997409651 508243885 15821750 250715281 479254324 440944971 576029075 585588866 283812263 716039504 43793695 335434079 381226904 357425956 319333234 277493558 412815566 388364501 147519667 829519423 657432352 105503249 836572312 586968812 744334238 622961568 310262171 468593805 424210871 48778738 855675834 389857106 611000689 330324944 825418248 55964449 548290470 432727506 805370764 885100588 649833465 173953929 95014652 895262142 427771678 340386982 402828305 975366923 527101492 4459725 758125029 801094646 822364191 727565812 707870541 232052502 828046027 686871052 622544247 185538238 246013173 314039773 479332689 436131815 255463987 795640011 976121561 851579236 586015593 643286446 527892913 105531282 30259426 815368167 197841945 514045047 628229929 916744677 507085536 192815741 819773786 626400171 597687990 133831533 160988680 705387417 582671696 366484195 77811848 427480649 216397279 623635476 519079869 461444973 209258981 391960460 204655662 258955661 105319070 403719675 591114698 311036605 946381999 600042030 165233034 795458169 474920853 678535982 452270423 193855945 938997323 310800922 582882968 955083945 650894826 748241221 244442174 903953484 791603348 10889042 417409617 818440056 615056136 624348828 71023763 26900871 21127159 606071912 431776695 304034167 170313996 747023807 822193896 455363738 27132863 234568247 56689081 941290704 553356499 717876580 806910028 265572884 196284660 239379782 114830902 869117657 711750571 771859628 555652046 270752285 48553328 334553472 964147947 671293576 5789147 190126599 221710550 725145744 712763204 4580497 311626815 787617534 502598843 795811722 116861032 442131649 118156661 635970918 539363829 922498712 881569737 120021296 361613115 456988348 83498399 179686863 636885626 326465526 687917031 272050227 965124602 665358610 591464288 69251305 703772985 227648458 365633819 734609000 375462045 882153820 199402931 453265679 674053265 69224017 266880725 796701366 49349549 158583814 488614788 936383044 237946590 303790611 229266233 280028673 752100662 973803223 222137927 876647797 538257413 738670086 923527062 622221642 894557227 911664881 508510071 658605617 772102743 943982313 812227205 424861995 565334154 512529218 39589560 467734148 489486107 739473075 120177328 711965951 539832449 984808527 530708371 307579943 803081400 903703767 652329478 670839016 371984828 761486758 750132635 745077833 116314183 429669356 91224525 209412047 834516556 635535052 914975834 175579039 47171566 854816102 520391354 487623944 584662093 179695624 916609907 912158310 850233907 256836596 712985432 313326814 523295125 992051270 625985127 62191063 645281435 922041446 445881537 226890893 357050238 358334602 464831883 726403513 371033230 274956115 288508194 525832040 520693282 927381706 122306529 511679851 807192779 249552379 255532942 126362089 232060179 474364116 887156464 546290839 744417342 130798317 112375843 915336126 118131924 202906342 667014474 131203579 478873435 258441490 7634654 887208812 286541876 272308339 499274743 620213476 665490334 668211583 253217504 61151119 977375094 116092115 692618346 228845986 181042976 930550388 151291015 254451357 409291287 503158818 977347166 496102303 376847007 360137430 928532284 678636246 187659952 170807053 134284935 360473746 532176353 8671911 304574712 65852331 882866697 768588176 736846979 291342252 406287383 130824213 343524065 62383965 614690142 935020733 626550460 250325835 464559256 136883992 823413804 500610960 785892586 905027379 393252148 721586036 870989949 694685694 833900249 877025123 992425415 979448434 41982767 738140765 894681384 497627015 200274222 464771029 219631783 335654689 879105191 676741744 415830819 224917773 416427170 174901509 391959688 160579613 161956782 271848408 568714528 656060186 616668745 255387068 912685108 640644038 264671145 61566739 282865281 634578258 89321384 361749161 634311988 647453978 846209815 635705198 208976618 187115462 375959276 686592368 913828504 247630198 965779398 173512586 253494903 833785592 260247635 371427187 812662730 19455968 741823556 86899247 595906132 610533511 220213180 848818761 720325898 818662284 277264733 348615381 854235953 668914136 938123304 88234327 326430960 510585013 531409158 351736094 216664097 284139649 546518362 208156576 433765546 276397235 335945619 378093869 887265772 395146939 699017240 149646833 76657115 261878605 261072406 418644106 618910000 598392796 122916716 747580189 351195399 801388223 647798694 595531196 996621342 260816332 642535512 67225358 872814808 210504710 295750451 54785094 726486722 797323615 545221100 55013790 66609248 46279096 225918175 55314162 226457243 7511187 65108470 261598653 346515619 792702709 555091120 718035819 185955161 606343372 985450483 677683227 248000013 790421178 785519416 361415631 307719874 443758818 690565415 393915352 917784279 864934657 37013617 861312901 940027726 354577923 156505911 75009081 798823088 208405195 25172118 36777598 327492719 330470618 538183071 235089986 552423919 462064427 341429876 975171420 138240876 518064965 15746166 117441775 900234014 527936558 28391582 61504225 752667458 99166768 275076852 164254578 791780529 80764511 100766793 782376894 690350016 38954584 896191385 15018222 509859318 957812266 713733244 539727890 771603646 134421849 92979692 215147252 498501070 201106172 881558310 286182242 728683958 445102651 228032801 446921276 966718550 340598853 929161244 176334208 307200902 376638208 306686031 201411693 813456401 337202822 46028787 881605684 778353945 725036543 156763444 136067529 123585893 379099007 1249292 494167357 378569580 640646684 505086792 128333935 733230050 99131230 15270291 867525386 163720935 258677635 132648974 573354311 466870316 1862815 990775280 827634633 91122771 639444210 963924011 55717636 519324707 902658429 376762616 498079838 818929525 923555586 406034014 661789473 577246009 463389316 652219051 448832552 304637952 239893589 746609488 74740495 848758079 423766015 569460816 538154234 924994665 329469058 419567710 738594781 583316034 693332424 822299321 497740414 261116503 775426316 545848158 9182693 53622051 196666513 888573102 790454442 272768173 987020834 404990163 411885889 819629505 492684168 656185261 859124888 877397155 82691416 894576371 636881172 210748063 22293060 555099377 123337122 31128192 78444540 761343783 899755965 944318526 118532075 770923239 323574471 120841640 180618117 243926592 846263638 788745629 164601156 603712893 550827943 824603193 19946226 702677970 694933777 496609082 260279970 108814880 804587934 892521492 492764358 476747494 268651585 897744196 168875868 355044027 261016599 660859667 914513377 65721702 645003573 560979597 327886536 516191805 984775211 413292673 583824774 651073522 848496321 148755400 762097752 718334034 251005306 425938440 200946303 940905334 52156136 689738403 389791917 645696614 111825082 455740966 596577705 650308450 691516487 935755632 672728517 196354321 250564952 197782945 811723363 380068077 58645935 465546896 807984710 665345781 967940673 943010100 662981564 194428894 91299009 439730711 886131435 530026295 706807389 376326307 823841264 984004664 791038402 495407409 856993292 275282890 299211107 64083949 153708738 94576275 35683437 494936600 118379887 701399950 121258278 517925361 692860629 95640739 363893028 712508313 467178229 465122842 212333644 492262431 952987614 764075254 878462545 283541291 55600161 412244879 746049231 396603621 269848558 89086677 548704394 748844736 29370520 59712907 752915760 499997585 387724032 992572556 375629748 42772216 222617629 730395231 856476710 898664301 399071008 162095504 593503313 89826877 986886914 17210873 600742506 374390998 749010383 124595139 787562404 811512566 181242432 147289525 76857176 298380912 714118149 680472450 713934905 702046511 585342723 845536658 465876744 736607420 193629648 237986641 188782552 929448966 469486404 198037465 270072682 154546077 193254610 54913298 251463409 273519785 944319017 692570830 383699417 588598313 169080714 542033959 261081121 231634300 585065451 840004959 979164698 369252440 135914064 612021249 444394827 498934140 402433843 474302439 361069135 712141145 78748158 698076709 605232190 157957267 735242807 571368609 367035033 416796321 202880252 755561129 115189515 337431665 361886162 613341264 340126370 897576442 838978913 662086515 403418533 386630786 967318585 677674416 19579925 741921903 43466975 951199216 817281393 1170030 876147232 166912074 465038820 726906712 310462036 97042056 832297950 312356930 637010587 669933086 251102857 454092627 106033236 493657605 40829305 83493479 6077816 822543568 919895036 447011460 198972313 258941117 115818512 902251313 102397449 154939412 762705753 713562115 680109400 905395038 878058432 319652751 694169337 926245595 52507434 359495391 345837578 860611510 207720793 767940977 766419170 859620056 892649963 393605540 767170419 770134653 95287675 915301731 622938554 486862809 176327555 658679884 989851486 918861236 126321818 167950902 229328883 403960254 724962550 228482136 869084825 813406269 400159931 422479638 335738177 166545747 296903812