998 698670232 804122564 139375137 759997475 948546720 958527820 470914673 800490367 992917332 995578792 411619051 637268598 354284245 973267412 567495173 672597137 327341409 770596333 38889303 912934271 586871479 927629917 789935117 835482455 865803140 998212672 182737147 755905520 903093732 930618450 172019443 406835129 385792410 992603486 714458199 928832875 312267100 467718416 840539297 882632958 209237438 447917680 35365887 548401758 772653406 994546539 969462753 977911196 447150261 800637080 931853521 940962638 748149527 915472813 694938194 942460258 533822222 644465183 400697039 993940418 894747008 970299545 579519785 717659637 769829860 775156081 142306134 881980118 947391803 988067953 259760667 529699613 26146099 320865433 272192014 399840876 858390671 998478567 846242715 930355907 325872058 481833558 475737226 683375648 166414951 816130133 796860661 824076560 433192381 551181829 767886540 973182381 606749836 637123885 442073772 945193748 128125956 565919456 904471264 994861229 310383341 777755542 155051572 316077305 198304124 250746203 116577497 973428946 618427096 785362010 469846209 604948754 325116545 793727693 449901679 752797824 595080078 911076327 560113433 943617252 672754878 809795585 669367612 783817756 917417078 917655104 232901929 758727101 154906914 571112924 342199585 875419007 910169680 980541384 706476103 884007485 731809037 862658034 558677003 579367686 298739101 442534351 654305967 967349193 447067162 662922358 124001868 581811843 154721140 665709336 586516659 973218502 601023595 896918748 225930631 475196816 805614521 914225733 332693373 602434845 85327902 670229639 437841196 549878652 99945722 688146392 127815101 208251041 195172801 990211007 136411471 320341479 415959599 825492228 876310142 933984750 859990433 916439056 889661932 940128762 50738194 109791953 266417189 554997986 869093216 884128837 749541655 842322619 469261606 553041899 724163051 735187663 529942388 926133188 113945253 389953032 995032311 995972956 273004094 835448650 708232131 994175784 350630462 512990009 449652109 788944606 538484160 960087632 874236006 972863284 726650948 783006686 43306027 702921383 545177684 932830745 401000147 891766984 439074349 780016793 580559866 606604531 362656488 653122621 583154352 815726336 150009011 397254897 273936098 574864156 58036137 667675278 316553819 737783390 371577624 643388819 533865744 815109585 10155881 704897847 211991849 435942240 818422296 901977420 671660744 927583233 258514520 974291592 454442345 733626748 636838280 914428062 999551870 999935948 362678033 674814530 446129746 734840880 820974852 895844203 268116555 942397114 473975538 954910749 639775229 725237697 261049316 803438523 372533490 668613807 962534830 972061519 335311263 933521571 195192238 534290765 347191159 556263596 726636190 817348451 377782410 616839981 590563482 748776032 735147512 892944244 252941525 318699932 519708250 690989395 368737379 436518872 826092833 939931007 232242277 465074577 692105995 795138273 376781141 631100572 796385301 868595037 705930382 870171700 629621000 908286385 103609576 364991526 926259493 995913641 800909110 972860457 484319782 686022616 358581179 835641280 231430452 585650730 341053812 413950273 222319310 728959420 181357815 389389290 741176805 965180693 892677606 971422412 712400786 961747491 922320143 945825126 957287076 977535110 371842520 674190668 890868576 960530797 763391532 848444134 928622899 976858765 950389600 989301286 407930506 716246792 925362447 975705910 553845731 562846824 179283459 302316075 507475433 739992826 427940626 951708060 679506726 875091764 915788024 922259815 152309750 239782377 176143488 684235254 354055512 821559367 802841409 994657847 839964306 877604356 478296825 550454894 83504176 205762106 299161755 608221189 59316039 906840975 889439961 925605785 202444442 683790355 669552057 768420627 179504170 683781459 362370854 474587260 951394087 990737847 269579785 429834646 931675716 999599805 756565405 965390393 598551081 847757748 712315153 849968096 663587026 674356077 691622271 695101222 999457803 999601879 833714882 839819586 636137992 742151266 929991218 939545429 422897651 827722421 695615056 950029772 241708941 334883508 982928705 994785569 743534790 869855949 696336266 734254171 945104376 986618206 868130291 941161144 392469082 709789096 107442137 304432601 364722399 432923289 606684638 621560002 912337345 920190350 945553297 948621174 623363258 671819843 768637656 807943894 316385581 360379125 889510151 994940063 294655260 940348843 901392193 952579659 282275713 430005897 713204034 949357749 963854627 995551934 500502422 617196243 48396638 332607628 736505505 781655941 583004664 831903134 814049648 988131781 215188030 317631433 632232021 885882550 956355082 957395847 690106453 967553733 711439052 994118808 472798819 584160344 850463465 912277064 637403917 891943744 868211706 995219634 737588846 904660845 919471326 919486847 293572772 826694244 418249450 583426887 624294920 668501087 351950196 765902162 694891595 892591855 219103553 931822123 250879955 953912947 915692148 966679753 934878226 983548668 38909605 247614047 486110933 866775112 534699020 601920247 87198274 228388346 47136245 659435490 129584160 576077099 564585772 659527645 337042463 722521646 251643257 325828851 228360947 875924906 218961738 933481090 694406884 713152939 483628192 714318511 935591453 995210743 155825367 596229197 451942694 725802127 312010974 704797761 671634567 845455000 169615909 834183624 181796586 386872303 673535415 833615242 22401514 307676865 868730288 999808637 998368662 999692075 634930883 701209968 473759095 916085558 83591384 210417437 774834706 783169365 125985853 410206759 104897543 488562491 792105328 887700387 584556729 626681924 693098347 773872608 463571913 835478657 801601764 833518785 637955924 834822166 489346522 578283029 478078989 688881704 46561054 685898460 954846074 963913913 888705393 889185186 965426652 968538102 687399784 727041585 291248513 900780375 136694439 558228907 701075961 788334112 693622058 945792059 190663236 526836108 414443084 473584810 577245898 967314495 639088595 744052882 863955115 881274984 964320801 997633773 495623277 876433037 824159933 911825569 774296320 789251797 867164008 982154225 590070947 717556692 90761882 187990288 687994020 867069376 34420647 657509554 854819066 967991019 162415455 392119713 75561992 670157859 515943753 697340236 745371121 798273251 32572689 263387776 409012333 907601149 133672860 392649356 860562446 978725038 957944296 960100917 362766783 656616788 743056464 852958237 588876867 828116910 931165994 937465187 776191814 962772672 856021832 992015975 992532064 996116486 806829462 980955195 343238080 954109104 404283443 503946418 634158774 709027531 669985421 840871061 394377001 737821182 354386582 398080216 232397672 736032014 730397565 974861144 996239520 998644033 885161528 902868129 256311835 997045333 623812113 818558499 90236701 414906124 445239057 767796062 261503615 338664690 211077272 802240362 138124221 966378529 484399152 565836200 297462306 468538482 604822669 759180746 607002244 814952427 725318309 764802220 366010077 571062200 354199129 767943805 290368134 676540341 624461688 666579332 377299074 797893471 65628099 904733157 469494565 883176232 718351774 948763036 633395204 861036601 178385122 734924936 486511685 665240583 390807230 754939775 813594840 854073923 415743156 702711866 655201534 992623386 202404589 268722217 818208803 968522577 878506512 979921251 341335810 659676581 979112426 993676643 860412693 860664863 221827814 320605328 296002389 623528591 155092148 614461504 759373562 810094082 377902358 412497933 372382145 684877778 639485599 645397138 979216811 986170768 632708351 883165063 13100812 835080126 317898877 361163262 572246516 679794762 564439077 960001783 760705088 863460828 13812602 143545034 959026626 968601447 182475548 707816646 555349122 771176976 671614456 914377781 216638819 757542399 690641115 975590062 589318640 793785113 680072436 875217136 483165213 897546729 394786712 836262663 308746069 859175331 74624763 502431771 515483810 597232576 336160274 925846412 613603112 911856520 266401523 830244643 643429102 800879401 274025275 795107293 839489147 968532213 66828605 591102333 467304642 982817269 134370970 451081186 36075277 268423063 695902388 828586755 127555469 855615318 356678444 908967699 380833118 382116054 19364945 918212066 148861840 433262337 912304799 968671847 949298160 984793079 518590516 798111340 290067008 992791744 866937561 870817311 202960360 916620838 123437327 425017100 483636064 567779346 186774463 792999453 937289191 945211236 569395982 765712829 764051736 931737890 502345166 552233883 489693638 658376651 585459534 873086804 779304129 850602604 751557824 989850211 613944981 899610257 857676163 962947343 27476938 611001100 855144357 902967862 338648463 863653449 842702857 949724920 837102624 912597745 988696024 989791525 790957152 883163983 214286159 348175530 382244433 956415020 531118569 853085344 765459841 914144947 168919086 395834752 378481236 974245983 456826380 645289867 755131233 904311534 960418132 972200893 760319907 847123073 537777184 915338347 612926363 814369675 897010339 897721847 938699061 959030284 640530943 760405158 10191998 81652123 174961994 814327556 863888317 966080322 677952833 918135295 921710358 981074856 63706028 139667396 676507561 869245322 115581325 425612643 185725220 766345606 664226824 704201889 574656918 720623941 862504410 902325096 868927868 876412056 904666567 960453853 547844784 909393709 393785661 623978028 122078585 239893070 121291111 525430334 517247270 900520845 788314001 918719892 728873334 928238368 948140031 980909045 695696637 805795438 397853613 679272087 118557612 718457139 132536520 153958093 702271052 981593118 785826178 813113432 997012649 997486378 90168377 530580982 515784491 639109960 930433864 962287100 336431595 567694743 898759263 927977135 673975225 831847563 573914952 778645987 147235260 619271720 656275079 935210271 773134414 924649573 274106605 636231708 813486709 917941845 373085233 872959679 865492606 878700054 931244282 953145538 417065030 450734979 268924897 425079913 478340842 885414339 563463768 595268557 354409956 816036878 425704869 924626980 471916884 963452531 574943320 757007497 841483305 889747784 256067750 294523495 312873854 815881074 297286819 940210644 618741385 822070040 687008994 827589037 581007171 595100712 319639959 415526544 73501667 612566740 349999395 695963679 501889186 624040782 466802437 713181914 359213511 377038848 116972774 670849029 633530918 849879834 712051835 986228084 154105664 430845131 305874789 604221858 676420020 706205418 520874653 613473941 998317504 999650943 826013966 964644052 725368368 904625594 801782377 923570301 479567344 951959797 231789721 236673751 197579262 906070194 694727099 869316629 792124593 920221025 361395726 463101750 507723683 655199182 210598030 813835495 347049234 967837056 505144197 630656269 409491130 482065667 70034377 485289559 865790771 961535262 205723247 485244942 914399786 991982311 97529240 282463556 796584826 880653517 917468621 935320747 477301749 701137287 846136437 941811348 248290382 602672000 556519864 570092256 678434519 894038394 206473134 964439759 512603036 574593039 949915431 987046699 920134378 985653018 491930450 600414257 155610596 630552142 808147275 838668845 298900890 629543139 544390621 984317044 588026684 841632693 688895683 796677426 319714385 542379459 889437831 891382070 482904990 681074588 452228107 817848693 774426090 929930513 972408852 980709089 302922233 689236951 680149082 941432679 129436493 842069800 97623647 417155197 481947586 572777125 58751871 448940140 127486004 213577257 751630400 916393688 95437953 474125857 192826258 300957544 443820052 686871515 827805198 872412153 180356490 820426917 550609853 736278143 964380741 980312033 295120168 326987762 535975776 716882718 676243547 910331535 695621989 785842959 81310103 490669893 318257582 910813058 376862641 458435027 637949345 802121626 463202925 814667355 284359382 652291765 11200768 739031637 130769315 152678587 47740114 111275291 632319951 906474225 150782152 310524389 738506871 757164825 501752556 792562925 310559373 622924816 921358400 994558569 470436527 868398080 522878563 796681627 957731294 962009121 571232112 892897716 934399604 969936101 645323169 945628313 335743148 375093930 857595917 954841082 185310166 552260509 185274742 992422764 270556279 468439780 814163819 820992160 669833201 730513652 207140627 320023153 887442114 892373591 685043649 704921797 633476803 770760330 22460896 815743648 315288587 564315243 918921209 978046831 698949085 967673589 15117405 906553501 571022140 696529045 49994785 601426455 281248651 837409076 190953239 798934978 271611572 508519477 550013994 599390221 433720896 773654229 791501457 917634773 358375334 483706578 762491792 768034433 32374214 54043297 974245818 998157457 37837918 71146787 902973195 994755114 83582537 616440530 95237217 615289941 393137141 536773765 480408438 917655945 566435148 566620659 441570615 933146511 911549552 955497199 34946887 751795197 329053937 469851853 823266795 951474343 852158694 869572752 821134689 899293587 178875064 937637922 330801603 515134190 217130936 913435718 264786342 824977263 235107395 708774923 543291636 711928182 130181767 976453843 583090379 857193004 111267474 698133613 552718583 750078358 225671271 632793242 902063430 971067967 219332665 777372843 681710338 803282273 507728270 767368403 199725996 581366690 60183409 704848421 109324634 682931662 785231371 992247995 915428479 960062060 270298745 796549030 175679395 323530990 874028891 996522528 697443407 892095951 69452661 816995121 438008938 575331366 505982739 659790588 47048706 630896837 270848877 810079291 212409721 516420547 151946401 173721999 657876562 852150239 802013952 824950813 639803980 987918675 607751485 644160321 464374045 478295171 43332994 288355009 592508150 596443844 288947973 424837582 28696046 638827872 765779288 959926487 345129172 679504133 780688011 910254516 127361956 679851149 787055283 860097210 891719648 936901717 706454430 913013461 664563941 756003932 699799450 792340260 917032717 919847906 477755078 754789379 707432366 870568314 189219303 602222845 273425821 890751278 394022138 948019231 285205073 760657695 442150978 585594400 202020174 593467753 367511991 738956374 755690507 967307922 532281955 548260653 660214553 683228333 20219715 614012047 294295328 459292342 141199459 850721467 376372701 548484465 307034467 404647353 235374953 551326492 804416543 814254153 781988565 898150093 282497533 668376627 175585218 475365243 307475861 961792909 904743516 961759075 60439949 969519844 560267543 948037814 499809381 564008111 783374672 818563958 959140634 972068924 987615620 995678172 487788472 754442065 136181013 502597737 456497266 618790710 273428770 944830810 323241435 726791198 505543458 598890459 525178569 855482587 435882642 964831352 399323045 565021073 757881378 928302830 69680888 511274222 593936352 645417348 774948419 894155957 95301965 408420305 803956521 814777574 673248186 732414743 684135277 897185914 565486600 636600836 163686576 353315438 448492910 649440940 986828565 991765400 937249149 969616145 982853144 989416382 943898074 959849479 861210449 874650235 720143864 933151045 758732840 871488822 996489573 999077655 885798318 953285091 24181628 70128849 826464980 905842180 342923946 937202564 475191168 627762323 479522669 660670501 864966617 895010853 659990179 718110803 955546275 995351767 119607915 499022893 217881001 491830781 829876855 959491073 345770483 811089737 935630843 993424545 634530524 707522206 698188094 970502900 675661133 902947769 715171296 917072943 424533340 902771966 254634973 540175926 233324072 355108264 134368207 444164709 908559108 970849912 531343462 747252578 756618277 980378313 873415138 964649080 776509530 910147175 967822572 971019010 590921530 646117894 250472376 818739148 864505823 966063650 226779843 787698386 18047863 795138295 980235435 989794365 482624386 942252620 585883310 909551729 132106033 929363626 373834979 904175408 286549997 772897060 167440976 636435605 479995021 677391657 256723392 518975536 401355688 486293764 65962268 281331335 637628207 951471110 180827634 747202091 38444285 592948145 301410518 468676064 294705516 500095777 507733760 676159464 207636830 850355801 273777522 381109801 919292172 992935825 123036799 804887621 975293365 998892432 524543857 608829108 540209348 840480225 894224113 900990594 619348220 968328069 508642183 574774328 217082126 656904999 793851644 944794080 765418498 805160206 838554441 839173144 818618200 919710004 516695228 609023076 679990012 788358044 421691864 818432649 905324725 994073155 378986060 455429234 509696710 738087612 822492961 954876241 651497955 718998422 342306813 525460240 731733649 825241864 984035566 986421780 769592703 917530440 586755047 779616965 782602383 933331752 551832811 766237247 409266833 961343688 577294577 764557067 780070893 862715649 388498407 643190137 559966426 599641343 741108195 826119689 251405969 669381260 112144793 931316844 887428076 906450043 743836794 887462681 592966577 600206300 498811802 854907169 911807739 918319664 674574384 727413690 406477354 958480943 84453888 967322503 462505701 656403905 421053376 826833767 947487446 958523530 196529642 671192872 658482519 757826898 443080111 466513418 76107617 693597201 88737477 409843358 451711183 666470450 351957975 387689309 511564142 673105740 526615802 741434349 194264997 382790055 377440048 657425572 471496426 884618774 212790201 301731348 998776375 999627060 438362572 893935772 199135976 525379870 584849629 715216503 903832886 949024570 546920971 884993466 724982429 799030760 844750298 953429114 540887674 859224911 992983539 994438487 137847073 395567196 213198586 227773313 57238842 348290660 590548836 623507907 293886902 699122009 612307420 721945939 48805317 612276116 573095453 898550826 535778432 704748904 111304519 747556536 51309101 845929439 595826856 621070020 853748050 952822551 463044573 802101354 494004204 983694402 643989689 830025165 921902821 926614505 531857815 915686698 291017411 971498158 940402560 981243729 788087086 992294912 378801133 984737074 10266920 473325569 307779261 518109382 472646228 867782191 706694949 720270303 852239125 898203850 454458404 533901386 132669768 207508086 41790093 661273037 697879496 884027314 543052278 703417494 489652842 951390780 303391882 452856073 552259234 993593584 12376156 297590846 653016705 665092807 131864481 892160772 175028429 731175314 23502661 867115055 577191504 921241322 909865072 957965467 424747192 466259198 601982997 899074301 763515745 764099735 495456275 554374784 791281354 873724122 46002141 264224617 583068143 773623187 607791497 686761796 489278222 650420381 198443466 403340644 741132750 747913966 69755200 189037677 544011086 635698343 690338519 916152226 749492033 924731537 15278864 388592629 359620513 585629023 395810006 465969922 776685395 862222010 993458807 993676083 233248987 347183926 161604693 259674230 402247196 576252699 525089792 666189920 994696965 998535714 883193542 895592578 676162209 896445711 35457537 589369418 346516964 932065393 67843374 807055368 430280005 472451021 271478916 697058279 871278851 974650274 988220059 993788350 56372688 192817053 821251105 927291632 328006223 356752371 693531610 726047950 438726937 667892281 144574072 716509825 249760781 980698666 311978010 563386374 864844197 904997679 368115199 871854270 981410948 982542937 520602340 898465027 892458333 963054117 627425193 676514982 344928533 957460186 409714786 849317007 683661985 845095277 499432544 660626480 245909539 923460529 327291264 772018871 953422316 971465772 431199858 902100101 392070041 644781643 349180070 780613432 24617950 519032713 934899022 957814837 542333077 906910707 610171388 625789524 443678356 746597205 911929291 991018273 766101443 939784508 673333698 913706798 906901515 920255617 310380714 542748900 634294994 837644266 626932459 765726193 938477682 963839643 272043740 557305865 585733030 876752770 770641000 890038443 883861052 984830365 787367409 895905922 910270966 957895752 673664336 739655352 876141194 950429526 70842930 982629443 77718988 622285463 189100093 694061210 248334377 773642884 439388601 792441201 579531504 628561577 447951278 783892878 643117962 950767282 492198102 970161381 912235352 948402135 138436347 364338242 181150440 551364523 146300200 196597641 58951808 776824451 615289453 850635310 761443245 833183144 280399649 320832563 604117111 738128767 238122558 267408151 436019550 679124641 706590318 786862237 518346378 853395733 681499831 708965776 509192283 808011193 558830896 773258240 275946483 746883726 857837930 907759665 137724590 895470151 370171092 395520583 756566379 963997587 745786946 978040665 186867651 671490333 892817727 975805442 180221100 681199443 409773917 660622186 309123103 607466375 232359333 872815781 846580397 911023974 56446332 482664264 644762571 853344174 888782820 941999733 522248618 895966973 692516830 992477542 496266482 715462819 342028679 988408203 733190850 933371498 77928274 511817498 558614806 942143643 528489299 976619624 26266193 743008340 607673739 957274174 476492436 775550731 36856091 647738731 372681050 549506141 900690634 915877567 476173705 538722299 24327139 650604518 573002581 630293130 842343980 891795077 743749591 747509033 53600214 450339418 898841867 992560965 224909543 770756716 437808530 865560859 438875454 752226218 549659309 787146940 598696409 722167066 266170464 678211822 141034935 789735570 441953425 443433272 436709578 455148327 80853861 343567020 144579206 348337225 466090068 961190878 812972205 951019950 723598412 854344500 581478768 934839872 839038162 973105087 511405416 790010332 897022078 933186155 101555514 120656602 933001590 969661679 605820121 684444554 642170295 783735658 855253670 939800678 240065914 948105433 746266489 761208361 275994697 845210951 902766911 953035026 640624373 672566319 517425545 786363173 964571198 975312278 460812831 468074424 529206866 564564901 43575978 699951532 232216948 273236216 893631201 901304206 25533060 147867984 384541443 991744036 579697486 711892639 582678090 982644922 996461091 999314288 682905481 883661354 124968170 197660233 57250975 482268101 259382378 509932918 694675890 881873566 483735435 728244358 784178006 863888406 355235928 765355481 202470191 321246861 804840944 973198162 562047633 568144077 583590897 749623795 509608199 889477126 498561175 853313677 484557888 748070088 995414535 996810720 962232655 985763021 512057694 534927984 317229563 858253761 667467231 903811142 761308692 888856161 638734819 781041120 984237790 993927569 839570661 962676507 27749396 242787557 847119980 989206973 959091636 962835373 581652805 715097623 907384291 942132542 932360046 955446023 473668011 751213114 447912527 985447908 351714243 419597433 366373848 559779533 754172264 992408082 245233251 481044973 123310354 769884489 819181267 832968626 898932784 987952701 157126781 256592716 894079356 923689358 567304135 951369405 980891960 992009058 437300285 806841070 403641886 502171092 770627749 906383426 345857734 822445183 425377165 930216188 988037333 998261992 77690472 176471166 992786848 998034959 658578501 954026332 409916376 791938393 740111226 793768274 334906060 656165683 867998175 961214781 635148478 675730828 451292895 703177839 347817327 618743299 339460163 663680103 270382867 475249360 899342392 983429344 346729405 946127725 128246331 849056377 957041779 977373221 53229312 151119237 407337367 526725543 39645777 712026197 520282964 849171363 761193005 873969453 764915063 818929120 891515516 945778217 639948397 904715146 258529932 875522286 246862675 376752068 958904486 981066846 576435428 761373097 787893173 955397411 322475638 581455866 574510054 892818765 33711421 978467530 671883692 944480024 904079104 934222914 924792188 926902907 919928079 992836268 710084906 784173026 608109792 744836123 593779839 851756716 188956472 795321719 454422844 637411055 982007229 992716678 715175560 756445237 384333982 589434155 729446986 925414463 836416261 988239623 945101716 993778833 189794259 412907202 474390229 572749266 440885299 573636893 842322426 983841559 387480709 583368982 204198627 522181960 343716408 773780691 874487956 991721665 616727537 924528086 708418567 851037775 408358544 478342011 384834880 917470292 65008234 314975535 668847601 669333385 445155485 681856081 359228742 568299405 31581613 432645512 288196162 571713041 72149023 741511037 441851550 986140988 896346607 962102722 335289119 598901586 807163948 844369205 770926073 794405806 104769898 431734269 476041579 983791300 866418635 961447420 63783044 577553614 595505362 627269561 726187449 902870469 671283810 817849665 263772884 620685710 165378191 201052884 378334358 862798192 414955056 512484353 700430959 901573055 994166939 998203508 571835138 846409255 712911435 876691169 835094378 950967310 691013714 807110465 579114638 909053863 173133752 360067891 76552895 343893018 584874515 767523162 742816161 858647708 479689387 781522343 722703922 993663587 277742712 762620262 732934898 989800372 128602312 696124774 231491319 769225749 676862260 730934057 228820582 902697440 657119775 710536367 225762584 825751626 89131696 409219594 390042109 766310519 676980403 868572344 33823468 153158902 943642960 959481703 978745466 982602903 750499007 917360379 621522354 850600405 90509102 382033118 221158470 442884732 149711263 695381994 972561135 986320604 745736344 943978238 574369806 731248974 652755770 956396719 800964504 935265293 14386534 276334836 461938960 595228902 544670481 728833309 172240191 480301832 302170663 935194655 419899535 758541334 261793770 337273811 905978230 991543593 937977810 962720776 114132728 307348065 118998663 948128582 441477333 447536530 77647700 553161201 720458489 961699770 44926720 635036127 440224324 587884370 241034637 749007980 125461591 417792809 533409522 686676881 392040349 794124224 578656875 983574342 417490986 653410797 449132442 632927683 838858079 854086915 80457296 739034912 596573574 812089536 569640327 840997735 184264319 786059463 726117453 909581402 716170515 785280449 804808363 811626257 311512429 446484255 137940624 450490512 766490922 854279783 678829951 725966736 891949940 920969504 223566721 506443690 766075732 856066195 381487264 746137520 472978475 870557898 586936838 984873669 243434864 403413195 759833613 832137380 155956833 237628379 351613969 628576599 466733428 630303642 66558593 764099522 668895697 990083433 826548010 865833931 514790228 750745969 575767534 690541327 440620927 954701929 50946206 972510903 251271312 413956331 318337164 582581444 911818338 953747698 720508696 811697073 580737584 928075525 302571228 400363152 528758538 941519974 722101121 877858821 229055448 939151688 756093861 881742766 384630342 501059001 546430683 990921099 177204548 746764820 45930208 992927075 559616470 765967299 914670964 966962997 804920089 997428015 49746099 323520449 336867747 651525807 568040328 808619713 874092171 953074735 677333382 997585311 697165682 791128184 270041374 931341999 597731268 786875018 93057439 442046880 134615370 143708021 765801889 986192533 34385790 748003571 357628968 893669780 13584423 49770541 35487436 252452632 132486469 506127039 104660577 121381188 75150332 231361732 827409818 986109703 584570764 821392513 758042394 863329334 507509625 966308287 450696478 788574497 722341602 803133979 123498279 427858325 647900540 887162549 26221308 868737990 893660418 949715333 445942334 757554011 426863512 627401160 605448139 756504048 288991879 521990409 53961570 503414902 800634231 871935939 422533314 783435988 582740785 877446053 349977095 504052278 30854576 498617709 318691344 783545004 152214701 424168512 45363300 277593712 729028716 913465327 697854341 906109191 553147275 657344599 674375288 726296003 491086670 648866677 510029962 634978129 786513230 966305467 804608490 910795613 314557363 592445746 774672189 857576387 459538785 884845736 359790308 480011184 98358011 683953323 816277496 853866753 800503822 865862109 120338418 765167908 578239592 760318310 746248755 909335916 786634459 920902675 940737111 985746194 685505964 819640856 591912000 705761836 266921549 621737564 66088040 193230528 487082866 750590654 63608153 901345675 738415587 995982642 658942672 813444841 599526769 705226182 608652426 690101534 19627399 595912236 721022892 858420236 439962239 999249588 194346344 658326364 223967269 740406259 978571508 979071342 712423107 778672724 595105236 912668364 768006461 775647924 152103178 219178460 618428122 815887527 708751448 853803016 808507700 898506571 588070682 978286278 614814748 768569284 187366893 198167702 782423043 803180167 179744899 477696957 902200105 930679203 550285114 988679485 932702382 961790729 388586898 458224924 39634115 470226519 927374414 945024019 810074268 866710856 608850406 809779548 375596590 459487299 14592247 923812016 781871415 917710083 736129966 912292305 275870107 780773490 613618341 922540309 601097957 619314051 483136682 815438692 681843667 712359369 659778318 812443837 469366201 559668974 96846642 886167438 784279399 815681253 834856706 903444147 878102901 915009315 507350202 829696609 707095734 745051565 499491065 883371511 70579576 356821760 461649741 775367925 884995377 992001144 583339561 886447542 129362764 458306570 130837693 301525402 244160118 759303375 246829296 249499338 21962721 727616672 77252194 879566578 181917762 807040558 980498297 992218312 328439774 486224810 65974549 606262380 421017637 874644291 517462477 973637930 265964188 272956311 247473043 795667506 619864064 697875792 953450776 970544399 489963869 556661079 547685363 899314388 20082308 132301180 230392615 430477317 750310420 975783298 551697915 642098908 129371977 843195828 262219107 959834041 952521057 996112978 977298220 988905525 921743642 995241744 498814426 758419851 556800017 854535231 556095535 585642328 256070974 351767665 985206662 999483658 178309524 807319423 793873014 990800431 886800029 962323999 205304845 522994299 91730170 727391783 119283324 865390005 748939659 966278320 888253761 929280786 706820176 910549343 41564111 102223486 888654721 954133965 458172717 538074579 37597334 778674824 722297650 931965844 807005614 893966307 401832247 636397016 504359351 708542418 369134569 501873665 22262307 175564308 742505976 834393841 411937351 847244442 238187255 377740300 445461593 971469611 933105717 990674453 687449162 707345333 359020335 523549720 297534932 638555772 22749121 774854919 477533493 660631299 581656123 808789843 86458586 734040840 641860612 768338620 653774993 984379255 184091194 254930485 60976432 799685845 106301955 519656195 344577111 804462071 945172788 970712725 72120782 812952825 189663570 582827916 911551419 957321892 761591321 945775000 272614737 901528364 711152591 738243149 522776853 600950745 762557211 842102948 69414849 870990179 918285939 946393308 788117577 892697744 328428504 565219466 247160703 312365269 492933833 955705035 363316611 404395643 915486346 979249190 527843345 720854607 625956563 892640003 705624695 955041912 46792386 266322739 986823713 993427297 208147328 595826530 293109220 914724687 56259080 105396727 672898108 779050268 43960093 510493068 715797923 735877863 863518839 987563225 269056613 448818036 372620914 665389415 325287404 349095911 659558279 879903297 630840710 871423970 834607691 887290413 660693479 960792385 603779232 655787550 551993915 951620348 41968786 762224717 874556571 972707919 243771740 985077069 550190495 733251583 657176010 782601487 130119565 805635872 773958570 815574779 480715032 834104809 442720034 518834716 803430196 875259064 788884938 931822305 361100467 614986466 361024924 925025311 120424587 796805409 989691881 999651865 502734958 546484199 636081814 653505994 333046648 568805752 159564564 850060614 246398866 828566395 714017060 860165070 185837084 523018187 924378954 981779935 494798540 754099805 32182486 144357276 53447672 568885287 155420556 461447573 430976455 967074330 431386757 727865457 994785397 996844173 403024042 967096698 708216225 793361968 274287528 664013510 61203249 140471191 605288466 891657958 837501921 850653309 53666395 911453015 802821261 929612507 765297483 933118688 616335538 717377830 825135982 866524344 262246796 363654653 538599035 643919457 563103273 647000129 999579829 999611789 922910907 942823804 411783176 861965106 638581366 785464814 91254863 681767170 834848863 933446289 581481530 642211540 392030278 583933112 643813018 950219536 691336067 992302891 901173211 962814925 186538418 633234741 496009963 864016955 191228009 231734326 474199391 901784630 604687224 722109518 412296971 907231520 88420501 479499768 788317976 853006776 454035529 834298694 489863635 711216559 830588683 840607716 547737084 729474963 639619710 972082878 198847002 630664703 650319005 939608800 827001445 871505372 368403485 400908584 236792399 908122015 12920551 386661104 652811428 764745336 164698101 560939612 918630552 965456869 19649900 696462315 364527628 707209565 983519481 987472988 927831846 933240544 277590764 638814390 41296251 589896418 985593025 990425123 973079902 984583702 825846521 962595473 570025258 998579034 303593837 511281968 974136256 981490101 926449992 986480461 296862975 982903053 543929009 972635588 207611282 792985945 532045182 736734356 802776726 934947431 694147651 988280986 515134543 528375518 828970817 928026395 236540711 703979594 665128557 733422491 360179864 583251878 93838313 595383027 796978659 848721618 716539495 853866603 581033366 924749982 11719574 47341711 507737868 534089722 43413431 555634562 557971076 891284702 185287222 349328960 280857289 955280669 660380120 988997155 221863387 494257017 793747060 896589479 566277284 830886306 373553351 845157565 98398949 590480667 246689366 970341118 154863406 654686684 639205454 954280176 698619928 941400544 881337131 943995212 396693049 692630911 470502635 492461743 258303583 548174477 50597953 139793641 275833862 306467027 704696828 715987771 599582170 902880169 138416808 795734371 418842965 547907921 583020355 807283159 556784277 808272761 196417900 358009795 882662449 973317581 26143798 981098651 823377460 872689088 513229807 773792786 45078637 724513392 730063629 995384123 225220974 590430273 711698536 922176379 858209973 883244270 355854326 980861532 770367344 829113696 779383816 822045466 217158770 833569156 486092788 733434220 269619977 332779889 270457803 820632222 571441141 893694617 452873813 478748533 21715531 492191209 428449430 564282473 603112486 807378303 299537284 560836985 447344259 756878539 493771746 770945967 983965068 986896983 182583836 679969057 838614318 908802669 942904764 944300354 509053423 672862872 461557700 690590964 219044699 480927398 429362919 814345271 477825223 885593269 691064189 873503439 99838644 402364585 595560898 667173513 148778696 278745234 851019066 977446095 203395486 762383226 336388455 391533177 796440969 865749165 250585548 510581077 188076074 491468759 925052614 957923066 63346246 977388777 329333751 728839837 592409169 631962373 419956412 568093811 380974202 730548942 522490282 983385366 846783634 922654738 801988124 901123005 134342360 661730605 204899099 725422670 609118934 991681389 670366185 741770851 160032290 485620598 356714462 923846554 702515232 900539850 77550864 711089385 350747312 580276700 83770639 613864175 968526398 978698882 609234531 892922415 21218860 784774366 120721288 893257678 22358233 681042420 272227834 686614690 273509376 379759059 631747688 942079354 822369350 931025029 855437855 986201708 749041070 760006180 439257033 747872751 554362186 591313001 254470536 686285748 928608389 930320692 777953616 852043017 625069228 730725861 240775998 318977714 929206330 997203145 996193026 997265870 219856539 857405368 445898512 623837208 144387301 530553192 194505498 644976855 51523706 419283836 973561174 988469118 170119568 434027406 591774941 669884304 578760297 661466876 697526397 887056680 435626574 479410781 444279376 903492069 994212904 997560730 310055324 800851440 22728244 516575684 553254466 585169532 254049341 862506003 555602281 955735292 690577542 736215068 922527500 940999665 995113400 998304706 278553438 988847048 831307106 926610202 734900993 799075213 68964962 521553942 220386097 994447510 247392812 678992473 345814395 361463439 174720960 460215183 523684044 633766349 345517091 997569290 368159114 836868304 120195647 374868131 803480851 922329088 321149101 330958931 635058454 659182529 183511471 574811972 215841323 269137962 66729872 648824392 69772382 916337980 611161326 796558880 192823965 434639018 104651070 164876932 698660482 994593886 871626364 893279224 163429176 293373306 529204447 908487393 754320286 954098549 499660153 800126338 838881772 889924853 116155798 952578222 476197248 495569226 789990128 968646097 797194280 851807977 619369911 729243301 59126046 644849604 575673430 798581479 628061649 735926279 739967924 911144201 443307906 804391593 508923245 690138709 463302003 777738552 97432690 983361659 86730989 778427802 643229413 903232965 459698636 582269933 61724375 266808512 401244486 935141409 81959829 707116149 252024984 759907688 390719662 654902340 750233782 934867656 59802659 704713803 865981996 891346767 481822371 637376578 91392791 207411156 731243281 779415235 621148220 787286173 458097906 709972219 305542649 805106152 281908593 814263530 192183189 349827924 88971987 120260777 140907288 542604881 783963523 996600048 321955360 676262880 627059361 644688952 967572826 972929054 655767726 703245705 321387136 627383308 929568600 978809457 198581610 749864618 942186087 992682273 107002165 355332380 264456309 613462129 895009784 952743066 597947319 979089204 20394652 268552268 743592068 795258323 177413132 425057950 48891530 568077594 544682937 557198393 182266220 675909044 73104573 343993320 413982199 720662739 637011677 789317981 825138136 961432896 587080439 856350252 977226466 978834055 96450876 471312062 937133556 969021826 735613201 781440561 283943429 946598591 879793512 912774858 623556463 813772129 256680353 597441579 332473269 474127963 517570793 557172199 539449387 650792851 736996215 809056273 884158231 917573112 391316345 450576290 302197771 889722324 99601014 845492833 64161287 957105248 22455171 894948012 264070108 990132946 528949154 875155275 100332439 507761162 928427566 980596979 971299497 989732163 753592961 945399402 853329309 881693803 990711128 997557805 970861577 997143315 50244550 344566244 875155379 947916286 40572539 757291218 750863947 887431135 804726502 876222066 449397798 533005816 145142934 257875150 482109817 975933402 855180862 963437638 882956946 937895724 45593152 66593121 814781615 954899830 965983503 979568070 585272346 798731804 403880572 892230591 332780539 489344320 915604419 999160175 537490340 641032701 109589240 153519208 199771488 394740597 337809879 535562759 79418941 772705031 405278422 833346675 517138461 538146452 150785906 263337833 476980282 896545652 271807659 342259291 702974333 905550958 151328884 717325635 687096737 975424123 548929877 877281115 214965652 232886864 740561745 999372234 347397900 527637808 472965968 506220184 956032240 980286505 698191973 754629792 52951816 240929055 138969432 424820528 733732821 801238138 773808753 992626268 729483566 872627673 516872414 586626186 456729800 780719501 446516003 973562503 716991092 978801331 69402064 342114754 877672942 947587803 904553784 934791909 343059121 428074368 812290124 942158529 466294989 949009719 929408102 980306202 519453464 939654111 88083346 665876918 824646498 928497319 540220168 821610067 658746788 876320623 54247956 809011168 180353360 708797419 169107552 178645396 447235122 746095095 280673792 925662982 704567612 809048806 507115275 899904561 243039220 310872121 37324741 630740600 440166659 457206689 692319512 917748575