9387 21
691485512 193991722 336145563 975928074 822591950 506906307 350095303 951034808 132516391 197869180 750027812 374804624 129295055 299512235 348826065 37612206 733405448 776432785 743219050 680658401 979028379 773803532 18227774 942528848 724872816 411017996 112683016 75490148 625711107 40407841 987196700 331973700 139241948 91282095 140916402 510690335 338395932 216047683 155590315 782095040 477932978 693777949 441311895 325530583 316694869 300952945 920732569 888091246 593789862 898376269 517934978 705454658 991552466 757939588 609567825 598536145 825185837 550648498 603619211 641438088 917289561 788313971 235338179 28506852 296894072 259674888 558070541 367140729 504292383 864205698 38536034 540672909 717204902 527729194 572309284 180705832 783329167 134283578 969505289 45220162 560598669 543407145 789282728 395762775 417486752 902317289 156740371 223309773 377675293 693645345 661336012 540244681 6799373 583612805 176559709 684299568 292125071 121959057 682688399 136385628 143048868 135933875 983835344 284135657 967086324 93965418 503229378 297843380 210760580 99780396 600559696 771031424 364121483 756179244 399415175 895820853 958173766 537457370 544547465 230436515 652162974 696153110 957814914 704384093 793172802 567798211 704649076 973246225 145628317 305837952 888969109 782477031 576649155 848647469 304991144 850051117 317912365 453562536 741273498 364444728 953845289 366664194 891695916 468639851 395605780 352804025 974359249 162757272 181535477 890253015 8717506 569847295 476576135 719367700 226235227 408514766 536759910 102532867 199214503 633183821 735013637 949678746 377101126 315249565 704978178 850947281 717675741 963912077 537844827 795743691 295858004 110367512 937199675 980988795 63110643 248094898 883551793 851626455 925202270 411947329 463643906 437105068 213046503 974050457 26677873 448512891 204964254 995512849 306030331 503303643 29708520 458521688 813528474 916675406 209746006 115052792 83705433 873380599 561034425 301695051 661432174 265370389 109905958 848081316 940866936 287724703 109090848 997008482 727695722 389259900 690497001 977460740 755833276 315993622 617613362 599076761 302332193 600256199 649490820 300333152 517295039 198401734 704120617 683325892 475651369 998131563 40349861 194344161 935809958 971162358 320780494 154735961 928692356 809358297 654152753 19727048 473321414 287961255 729556468 822065966 898726138 627916818 70168466 952408539 195431262 853727184 403762423 802919437 797056573 893815948 583769307 554127950 659082423 54806476 853446019 575357934 391383171 557802376 733139749 271241854 12684784 654207708 265164728 560945794 231441771 800424154 796638276 448503084 713382862 340225812 230956014 808770892 539731568 503522447 719675450 103944661 515075168 679147404 749190007 880439751 521626763 282055706 552788744 945854695 679757623 153860277 358835627 941418339 665834820 310077435 87253447 783515661 508579738 192719876 633373944 201278588 44140361 895825472 233659673 638122826 132156737 985310984 680158140 963843959 835431527 133509065 314830985 186356175 783041248 805256200 984995670 537116714 78512307 898589285 711475198 813974525 103952244 689464658 859869798 649773857 638876429 71162340 136024422 74257901 251798799 473476651 596774264 572053906 750310335 429329142 692227017 489455783 906662349 662807481 563209620 710270702 70727761 565991104 143466580 893934912 986557878 838818463 223775250 834316015 482794256 138934505 320491994 831959995 733646496 358447092 999229709 579493309 220655735 305972455 149146625 254086975 742037916 397702125 177686780 604442772 577218315 395925659 915423180 878226928 468090904 714860074 436621801 402461255 63241367 47612736 931948761 662828807 486307163 655927429 380269625 437558747 407138661 501322233 284689274 777638325 193977056 788857841 259737177 110059534 963022905 320549239 826632540 983093846 907703051 279043302 708599758 627266129 46233044 733587174 61638828 45835890 991410598 933937443 761673570 130920380 887118610 130069211 905385959 434816197 404380689 724759406 813200167 823391574 322678694 522017136 894909121 26369540 428405740 161413478 788148238 345665058 821178689 527305839 9853375 83884331 460664840 944601769 85747060 554894646 661093674 217418171 318602533 733389329 624344248 727231556 242409614 300831247 700523916 721507092 314277866 754200939 497301278 322980384 395904052 402655525 538072735 588174753 718198588 201332410 587206850 486635356 434786170 565556999 260095632 8172508 517552681 138242424 61779925 429075018 700512548 588908336 487040942 967897391 266407959 496049923 174683554 345165792 791774964 687959404 314538339 549654912 316248029 274782453 829091755 995094489 289802855 280983325 747908108 581866119 677969360 806316722 381877934 986691233 681809493 658582235 634642027 816561190 870476514 819960458 62566357 161159162 55105544 202780928 501382361 398469286 14233097 237778712 696465324 829032037 37864770 23780087 578474410 705309759 632632216 865420363 912481392 311996973 951430666 898957296 568927225 448427947 339218820 681886971 972566177 838496560 541053104 960750861 514780520 461239448 75442472 937524702 299633611 331034133 878961357 422066338 708938284 385485342 534288163 768799173 674553779 908600204 887014090 218091422 441878168 484654314 494200898 331175298 239389043 479262244 630204806 76970533 429439185 283023414 928618925 229218587 669353842 841998825 179181647 570957332 248877865 862264721 748255148 356663041 195127344 704392415 224937988 78159299 558093188 837661396 577522290 688872755 909733185 306963956 663198619 811279062 984327963 429934399 103886258 357264648 190555190 320711998 570943386 616131555 300621061 763202392 662740209 933202904 613307406 599098010 913581122 520831834 131472902 651554771 684941232 640711225 251443241 984735009 39007635 884446163 4419291 99673726 57265503 820518086 377039313 723638476 369870136 350074434 912300286 487507055 799131659 680591981 33907323 945365258 701164212 956449061 989991430 738924909 258870590 210793787 500016642 614926160 685985834 48818404 638349993 879543170 879992220 840559429 335767210 724061960 171390947 415657867 750678524 370043355 608341668 561562306 362839985 512478044 239049628 983958546 887525040 284112382 727464011 19280471 257067281 703828325 83476667 425139001 255228163 905972481 998695023 978538987 715305913 839618795 166655282 388906672 914282494 855940339 743076608 642120399 597424493 898741476 129549889 370423942 266742642 645367967 260380209 125616492 949364155 524594796 775455337 163611086 554772265 538228279 603994189 565443776 483211285 617560146 87634706 921485389 916671209 853012317 227901281 458044484 396654127 209800046 358901236 510646570 293995050 910221593 801579188 881756996 832466199 456378522 704569155 629059421 766939240 469779988 786648750 859871300 839270595 527233799 880183808 797927251 627493349 303089910 10817316 640697850 579144769 261584012 408075778 749778366 712481334 229057884 401816430 600480277 745240672 563032079 626334432 977633279 879711009 976348082 477450889 820698709 414475634 248081990 508994992 200833682 145663005 440496694 440751341 625135802 551913084 966262376 298874328 168064459 156049635 722409304 749282378 423051001 423453640 524074478 384995074 449925484 281516075 889051874 184772466 202607102 366012438 116146698 590752415 753612603 744029996 618262346 594107706 49451874 562493967 421094367 780731326 896831845 843355795 588953911 528517386 124384867 79312332 607235355 587620703 808848221 326863516 405327661 697732440 789588892 450402993 329444350 591303861 906852158 547142662 867247832 95216254 328730788 398213765 60013692 986495021 280806485 691127062 630333851 671600364 74046290 654727450 462709620 857613976 716952697 255540676 431417163 145907447 481306356 445930907 802489094 234280775 479029593 391376035 960998110 325760373 421032568 928979046 813997188 94391160 843769159 698030692 675415994 73244837 958318563 904817951 450909922 673376732 761883450 948662325 907948944 382564482 994623539 604844952 979950511 333735551 39463267 559790417 587938093 843935222 921589113 366815385 385827746 445542544 844824458 246482988 123297292 421137325 291324977 178168056 731056724 925035557 9890461 254128695 193555759 381677360 357202605 708164122 635700733 747574119 975218049 536363979 781949719 497460800 143553875 705712741 656462105 296168031 254508254 878292984 202814045 628047914 661234174 321302339 726327696 845569633 221593089 293986300 167282445 588965312 757229334 420249032 589505855 393641364 437389559 771563237 618445931 453499893 17325055 557690242 940745609 958454840 321724319 196541974 833683194 398581328 564091594 449449849 291818435 976891574 563386026 4218824 783814684 773704973 945176146 166322477 106875972 402635229 786231679 876644557 911292053 857817610 294844093 816098634 625288457 402424469 79484493 307478612 68120741 300117498 286774326 86495885 163226478 560979459 661350668 449527418 241863779 90834621 520176091 892532930 328371406 313389894 313643088 160264913 437799562 258730529 69935149 795346085 522425653 791068978 208721877 943551720 614631837 321338241 138216965 685740600 624885207 561688530 260664269 59381439 209273480 801623224 429921721 913230701 223657235 224451253 524397609 531961944 100036865 552852916 414588136 522542369 45831799 920282101 912554027 142892577 354853655 686505476 51813273 395647671 416720147 41139679 655333623 243314546 26173682 67058724 195475339 306232405 857115996 753406098 147604005 796144186 787556480 511385377 273874353 377901109 1859872 32443041 256458567 987678864 235801519 487309635 904047386 951243812 177920079 113641565 790498541 300266505 853251963 355034684 912534496 658407693 750960116 425746729 278951725 349737975 631754414 462092496 630125872 479858637 673129769 450506595 818845449 571179942 390400675 427768193 901464728 945552480 994352979 94879679 529140954 463391495 852570342 364382580 241188082 848207737 377759396 140790560 66212985 505831831 290955020 623594340 552041442 317792262 890100327 193908510 971024989 638645577 326857283 68186792 451507821 467662047 79061863 737772333 643284130 390336049 693288298 912318463 985670738 315933789 641551774 859895609 307593273 53176710 188216944 649154221 815277615 679291658 65012056 438109029 537665385 134845897 624111190 259831803 210152990 16617393 892744246 163034798 110901831 870374623 589708934 876594049 255273890 388274588 320566857 607807996 30309903 408550447 522901423 426647153 774177544 718399008 907199891 653389396 343015471 868339529 680053488 615949106 813289550 144384120 676989686 730207671 839580382 945558033 849210809 976751490 21462493 767395378 442076996 474397728 859777267 672671854 946959301 559608730 586907164 729344723 962343377 929369706 795311328 18645262 327910901 661231354 814807861 111060196 325516956 489996023 130378992 798515120 517855234 39062115 336772566 918803511 34418095 248259585 28557192 333459378 648798435 832551765 792894676 478396739 351935317 121671801 764291792 918425984 373436840 685181721 409262475 78692721 711358344 139358564 165508381 982228674 646480685 601910781 634940524 87921686 666160441 149484700 221512294 776285911 210453863 814281510 684719090 569609595 954357592 625819639 594815644 33515226 103026668 874646950 808144280 791408867 347954795 738408454 294126070 757173161 815299394 157492519 641574657 973263301 523919139 351948484 405783166 66144946 676141539 653160329 911468011 932586818 957100161 870469285 856249766 217406667 500330953 830365637 638090597 970347703 420280002 715233760 829335109 81743913 475815297 353385812 761558577 940726090 475038598 730667880 22154705 2036313 328763797 303058191 630909269 965227716 667135743 245717119 753613996 732295641 821174158 207689976 926880428 972758031 408660569 169136279 203624466 206715957 412277981 672944598 24329850 433335947 878612027 314412591 689332197 412870998 835811585 648161306 661031853 829976405 235803702 641445121 875161722 159843029 994153770 965711516 605191750 806581868 756006471 928014461 730212257 307010660 851316422 863549108 83446092 65971033 312980355 821449836 105422207 152941909 3685239 560344413 617811130 474164761 899521845 687191471 796646334 113362591 459512145 728865799 377513794 120002024 318085388 671221707 778467227 157572021 258386787 880503273 32653631 348753702 437246489 126917137 763385140 13363484 253822531 195977822 676296571 116485306 728370844 185475400 487281680 827700204 775360135 126757947 104222340 961952213 716729215 442562875 86736124 73140082 575235176 714987818 45440129 585931819 178439636 825833381 270850650 292898729 145813294 455919861 291689233 719493096 374755433 503053910 365450471 519589282 164565058 720690627 660061857 382471194 233909954 776136609 411852985 490557902 827134105 771772748 160275982 27439905 887973406 502282164 189717726 214380112 112612835 679944331 150016470 962685887 174086539 112644062 344656970 540791149 980840916 721758596 712642523 301184527 582839992 25568260 588636324 811005182 687441894 999364713 711594281 846411450 684808326 888442852 878752304 854348161 372038733 894528981 345109076 414955506 329852160 594459161 529144168 657136710 173828843 694492981 518682660 978254942 916024475 889181630 671699004 801208777 157568580 840672472 747193246 476581065 423179383 832926441 345560515 980314516 284104133 740597475 411772812 984048571 116447267 740902616 251040068 579614901 33142046 499201789 962385077 915977256 609024266 14419915 128413246 651136009 512042514 201623031 892641475 278180519 142583661 939543227 42779915 816248862 7384778 168889520 387029097 959419119 278154821 193198074 890823170 160832485 640766809 135319351 214155546 450202197 979008656 912344389 340047003 232797854 202036827 199328094 173551611 458585752 835964445 137778427 121209996 925828969 649423234 2940022 191835217 968742280 154094383 14561336 196915122 168764194 855088974 982196505 369917761 585339680 212214258 705962943 276695353 378594298 246358357 708018258 419180083 579107010 526821795 217085169 207656452 421557501 143922874 209796758 257907070 460278944 968523010 477410753 404485435 414901545 586693104 400641572 399235717 646376030 155101639 782865418 380718388 357345182 496449351 698174420 389938662 876970955 448968816 197769364 865374694 568640949 463789035 895394592 210591883 9007205 305885554 947328227 74720575 246849001 190843145 298261788 893235209 13834312 146628305 878445164 616158642 771157052 410344486 319375226 200765163 278451798 74200181 774080278 24444788 309379165 716997027 520014824 791542071 202576975 377653896 246321275 998779488 101519415 330640455 493504448 57438764 393760443 985508095 723190056 596737654 494936865 862360820 706946457 440308082 651271887 876877412 245443014 776346900 559893765 18127346 745780504 25431165 202991525 678843573 871199468 338794046 673694214 229816001 736197011 539380213 1302620 481578113 995038482 871535402 766523446 517393012 651581654 937907333 124174474 299925607 379293686 173556203 716248440 190767027 237200143 411481853 675337152 315747884 301721920 108201787 184171209 388041739 730854297 66756177 272949681 76996176 526453876 686306300 696049276 149168286 754119509 133340231 83240986 311197410 568764450 949804662 519590136 163847122 10628062 607040812 512009074 767251553 112149802 114379724 264608341 763762536 521663060 503169237 512259985 1364319 72377185 454494695 804002704 940012962 69904584 428415569 520663552 380978428 521866056 954226418 714618665 328190680 892947557 17044039 411589866 263038884 598115562 739154173 434042924 270845882 275379314 5965868 2563953 105344034 261599216 364643821 919188742 923880099 768646095 430089343 829875180 738904238 427004876 275407928 250112214 96127347 238246235 588224261 718698319 629655865 868433015 278181064 876394983 26094744 794361914 543669398 356210880 943851512 538928512 508920393 706747164 578601931 487658644 627009216 583402743 245217822 334613287 458513792 380641487 361636359 62693922 702172856 152596763 621218815 283257418 900946706 983128880 220862641 560475260 428059590 182959293 454021889 53522696 575703317 636048489 493977243 79552209 52901524 164596885 637113083 39407473 860208367 932404377 203837318 259923568 328552313 543402907 623585810 307547647 232886045 885991252 151783021 489862186 560815944 849348675 684705666 793383965 705378858 402064445 608913504 789690707 229126983 304678075 854567378 695849196 527378640 610868953 612921751 125677472 78764727 976418608 889044383 297525955 908339165 24166685 730482653 55933119 713756199 454712622 906453252 231608405 523597867 176684684 925701790 806615971 57616557 925241327 947532258 160940677 919352861 963658488 724416864 703627234 334646561 67836192 825377482 479101061 531749758 778325239 609591503 591609237 169370462 589662496 306660250 299846903 73694538 252688337 369865331 479996897 220658476 569046684 500278353 551878855 104581339 612560356 613262847 394982155 468089338 969900955 499671740 647953793 273048285 138189592 641425648 521789099 698302471 632132396 280661555 44975003 550277151 318351330 23455716 316916381 681141632 771721887 324800734 149820353 578911610 9693682 290945307 871769238 373164397 508180408 399093614 143216685 309067723 352074587 426679257 878909330 7624464 985175618 577086066 181245673 326642858 852090486 926716809 365400324 371081914 384869922 935711484 529572613 815129387 582921213 897034122 174162667 781924289 892320441 134401172 716466006 260104911 824216943 240380989 486083741 471309750 745547922 173917855 397758964 617298732 220093602 479278635 210026926 295048986 798526057 673261601 439207362 847849571 223008677 83466414 681765874 237979503 250401357 388156641 797850685 599503702 777240501 696803991 861663984 226499029 759077080 801927012 802778499 132895097 624678820 424842400 64254840 432206925 740046219 776627739 324540240 648158724 529364536 338661790 545202459 688218653 839190320 705281238 977522848 886530634 435271334 912127103 816305255 322252230 939112362 545190503 969400788 761226228 198975749 879630787 853120132 10767660 973361618 722651174 585227931 304203044 595919779 78619633 374060741 721151544 385895628 521732364 650535620 545301094 524470878 756842669 265072405 86795432 582601334 930149916 602659693 189145544 848950107 376747822 399657292 513392834 163475224 921890548 594779912 617833721 99276107 604547966 402995456 854026592 266131944 250442435 448821363 437172975 892301375 785957670 432741972 197724083 301066715 783043682 998616790 881708107 348314779 193791192 530896556 818675342 385993277 227344170 493231560 838723153 312347240 9746892 872817798 829092942 81394749 16383237 361875204 688393963 493047232 181783962 696066200 414519748 465919680 709056168 72115817 56312872 660928084 880542108 628805037 505148682 26512753 23382637 868109083 141727740 432863215 456007829 645981888 477728306 51784478 567339407 752558893 800474678 442076572 140233366 314455546 578782779 370993219 383665159 287267009 482721992 673796113 495475090 473482611 505316111 78023093 564648183 68350407 772035225 832971854 80479096 569270719 381920529 879332370 511263819 744643740 958345992 730461647 603633676 532064065 253117922 228593888 396966889 216034669 767285338 116512336 86978689 832162178 876544859 78520441 643045030 784690492 511093086 435278742 108963585 612904776 805856200 350368758 7263375 427628312 925450277 851576474 158806974 277828738 564128683 406121143 193881703 935328786 818443189 527753564 891455962 566989126 725713688 188584639 992149868 719651612 404641667 181928357 158269032 185644802 233150420 607656380 543040337 984899852 61503193 731817988 500940714 114960112 787044243 960918298 367107860 938980662 718386364 542650259 477808383 545143300 896580269 73040230 219768131 782118250 220282376 886947587 878254515 824795997 881783384 120077042 88387000 197351858 442613319 893654657 59658818 486158685 980571551 827628519 82053614 241733957 584055105 439231707 183436442 690960612 275455082 996938600 114533931 624707662 267952857 705054077 264191230 724568624 538898756 953390745 17494873 666119118 770207934 640009511 261597168 157613415 676678483 280582976 328649709 318939347 564031814 363446147 232026316 289603284 220029689 90261108 351133080 465966621 791847849 841077678 78099282 559412590 870246919 975084884 659508868 223302885 243827523 249838716 473074147 718509511 159542057 921011022 970513158 818871188 728856737 269159268 764269943 988935437 357869095 936149977 649866191 730273451 929558966 546516307 383990496 572249729 78479821 213103339 377823680 963017855 278977004 805911620 654737905 570464642 855477153 566876064 30234689 828301109 362600318 844929228 153457957 258613877 676875143 517249253 342679462 917337102 855209680 126710642 515621877 746889239 108904731 845094128 419397578 822304560 557556077 980766674 630852942 385210059 783564098 855685971 397326442 242164212 339500154 339892099 65734690 348880177 560879629 884978229 419675050 273517312 318003852 862532411 743921529 36469917 267435956 293479761 135623515 812874730 728740540 981878 298035159 501496907 181093518 131992839 756310029 617835643 277999135 244432699 216178250 655534383 400591137 970077364 899514928 515796649 555553911 464954346 53778037 500870813 343429889 503576511 11116053 349693319 985389586 19730879 963734966 948652114 178799047 358698846 211011441 177474969 229978457 561327320 956749546 118802055 86373533 621963215 643859517 251291074 111067154 285572615 172283337 570596229 686180083 152611595 71644969 781328943 896078649 323395521 48234147 482159559 477211354 862540112 79560809 661359776 94086567 232654958 158615664 963799367 218828020 567702950 223507473 810025377 779921982 141318183 617253007 680899219 834986356 38659543 13387755 674604687 570090448 480467201 248526858 947618371 623304245 549859080 442691210 828356304 392600397 314907513 43847189 390037913 800401522 885877058 620926438 546785388 215019085 763441617 866597453 853633647 179912225 629574882 276096449 716023123 727556028 193509649 483864522 659062488 938965951 390594319 947361708 525887961 22578526 467301882 236519394 847763025 274256315 711309209 242578897 848624242 302759110 368741506 181060175 939945197 887194557 905028235 679879906 101865459 339328551 190106761 556563645 840270152 502273295 847460379 761850500 769112463 330464505 264000999 791938241 595203528 906816365 466092713 980530272 277309082 818458956 230881692 900934020 910797164 543499519 76325619 955150380 666338635 486409693 781094565 546216674 296421714 179611542 174632174 198598586 265693002 223383766 297024751 19588683 685445690 617787449 694944123 230207595 369347447 308833301 554794597 774917505 142283598 634605678 433112962 141280081 345922619 924765205 945512842 514247557 62799977 540966003 278779808 87331482 846422027 837738350 487104103 304699779 868316051 12226715 289103875 890990025 377352040 110859734 470289875 506949370 100470878 470900230 91283006 841642962 313318781 143111797 561059514 663405113 285528675 901619269 366770670 482963046 174252360 388248307 294878608 67799479 275033125 533280602 43115801 218003454 121446376 880075023 651485436 448580720 760929456 226618022 854419557 467298749 364400939 978638583 228401448 606979390 288318678 516954407 72507843 39371207 703255222 816423268 433928120 945087085 763269238 351340197 895116419 785516378 578596749 20009876 777942227 574172890 930906451 912567221 784709493 199194466 241889520 506211805 971327577 174455593 998287556 496944370 418196371 274325038 48086672 552860012 22621834 124463119 91284090 901580828 836618166 208878665 658825862 622074674 118188883 280360352 897788867 676095835 632501994 648950426 765384181 137914116 942696491 286498763 741377129 16123639 70956239 319757536 683667910 496518484 162711843 371487312 918026012 206494132 757356689 542120289 366831775 884247989 703698390 116780528 667102009 550111595 152925808 15560947 377930782 937539598 418769320 820011171 234160409 142631074 288269927 710805441 952053420 24343627 735376844 958554567 167354905 269687892 569324641 646210443 757474411 40897879 92061085 694612542 486597583 755027946 891620307 761598374 98498973 123266722 118660375 728443646 373466826 305489467 750762616 820537865 926506601 242364525 834889043 970733417 425933881 917230403 450314748 192453336 955687564 882330001 478051570 973367856 988078629 408932508 564286530 292251036 302968152 643956979 384715521 676206327 150750270 501581221 640639727 748647778 51191100 892656030 696224953 456997978 312852635 272770610 677657567 872561434 728041506 461420095 670142785 525438088 100369176 573691027 436985281 612627434 367576824 643694530 551370811 303719500 945602080 913256357 226020586 81208814 291187689 125458234 858635974 168044228 523470032 224374548 384330334 227285831 524389762 240740906 518988944 585658831 789673352 526405012 782564409 22113395 537140398 403630361 446233884 536956512 746966362 992279053 505663595 415962779 456298855 996546616 332785130 472921384 726662041 819849729 232192153 69160953 694873057 723591627 170034934 323123070 61457566 542174694 591990807 376217581 456844524 629752305 777193381 227875860 906297255 258013208 843911892 652597501 6952417 922979329 746424386 595280109 633619089 293012072 782615730 55232273 463859957 489624912 887503750 488629414 133332765 988171246 481847699 542794582 488226028 734195535 61280995 47079649 830529704 861490646 404046422 905117319 71853325 816156401 458969114 923405288 284271387 193939254 711266623 282213711 931975164 221395325 601763351 997647522 544090881 12745854 213103259 703216401 216881827 816699926 77187184 330242400 443873882 998128852 771891989 231890541 664892869 762150966 589142039 359219584 424334052 27326593 929126347 153395070 174287093 294097012 475858096 858551811 398699584 694461784 577470567 536865190 705005197 557393120 666258627 50965871 455017492 377955247 587991928 998583733 50052354 533433414 824026791 497189972 6870701 434068087 429787322 567342389 508678544 225812788 334148582 854568707 313891677 480897095 718611922 5469991 905383079 178665494 851333577 227751949 104907817 305331039 467795246 226469191 769262578 837611762 604895699 14991997 434946700 946411841 293731040 603400776 187134215 553677554 203763591 372698324 886910066 221206421 61521608 874600466 923505423 818793144 894478624 898400305 725585309 131285356 595077145 131294654 396510465 441241699 553600501 308321883 791249538 605178810 800335908 862312589 858670870 396954551 538676880 268182488 517784899 925655953 705156892 705408896 297605486 408805331 283489106 602811376 149411663 383036749 929451116 682958642 386877139 892598804 901176253 62471556 541296627 586935121 678095933 111166866 976746702 314141195 966462426 942884354 126043181 966127113 880675862 228358965 731249851 215322912 583930550 408083622 686472589 353051269 59923642 326157776 949983315 664561556 635541547 898982546 570353113 115324497 796596064 704385689 540093326 316257412 584079311 971816820 994261043 836880131 632786843 399518746 539138530 618158430 345506226 990199417 206654276 912258753 89694700 787205532 752388949 908841014 282120912 964130332 602905653 347408227 17449032 463791858 766712921 924204461 453818003 250822746 531775710 780329973 231836315 87002889 762664031 171676690 243281292 510188201 464191823 565051974 967212951 404085124 967877332 6760704 278911255 720642259 938218268 941140047 634166897 618430741 883993773 604072910 342186614 278370573 662336973 373734614 15544271 7191147 565953430 315913769 486502559 323904193 634595345 221328600 896485642 170893330 501497937 144283611 67043585 85511360 648415234 630478714 835811289 930429877 764420193 317691313 555290260 478058776 244227397 936649893 151163267 873164287 87917470 254838218 920701332 141508145 835047404 641662793 135415047 652631157 950674919 836106660 478326017 887301461 52224433 884924834 552931968 574786317 241134954 407076830 865111360 287624197 151388580 566745314 287609056 788028875 27437463 560888352 749257133 761223962 443340192 961126328 995926611 5047171 581204617 34443740 934652024 432394652 129601856 865660586 226294344 844839794 298870059 878612405 266640057 490738338 409620148 517256104 845510508 791628302 210624994 662479206 735713342 318132082 872289343 477021901 762260133 513945952 384190163 155835795 807826706 298653227 911367053 904207889 496178692 823559920 438134017 550706515 375210461 321268007 504315002 234355419 142566733 811192629 818772055 704044300 378843704 727498686 10116075 528184775 82994249 537024693 44281520 163997966 509435652 634013443 42803011 306636306 676971672 776929680 281760312 929961769 391319759 524832886 59701088 298817064 504287519 421917090 476116274 189612444 855447314 64305588 85786125 684232672 154699749 357693998 533004184 498331638 774736109 947306930 515835895 138495378 422718187 647634570 125641113 517994717 314125864 479358933 857347180 772329767 383035029 389097919 841816815 192709456 781097698 788570819 774387429 227146899 569478305 812493017 691953676 364269663 807374599 9611004 448166901 671842840 860997832 421573539 244555908 814053649 586307782 191215791 649291599 498007789 197081639 343802921 542815 81528408 388243084 238752501 363901637 687158424 619546084 807541925 167911894 513320132 351209365 831951167 577525996 425799668 648052961 137826192 356244784 480506756 141856441 986374270 540094970 391075434 587525912 111968256 186023812 904756992 826089465 318341024 481952535 603637681 327330540 311894987 886607973 993016170 704523200 284856656 21958136 81015861 89575415 111834234 721806812 605875455 433431204 202871260 872125577 795443675 886429645 716975881 541419768 774347667 146574521 683230410 943574286 731848138 2279883 321108313 908030363 738845440 401386799 926534260 995915203 521226310 626863804 486970622 687481654 960406644 449111990 750521467 297611868 4366149 595458464 804584379 657453526 304531900 110475695 588402098 9000640 29169694 540502185 134221132 150827701 668062013 933615494 647459919 603906868 882488885 299276712 827375093 694840540 346497676 274828450 801009088 841676670 430530952 703931140 109693448 517335917 469545159 142760482 650999097 753310668 825988489 771746315 790182045 662583408 969972806 868073327 354331326 892253118 736061634 857693081 662142108 947536524 434618510 669382181 805851308 514955916 468184165 979623040 6897080 287614131 25959218 440902390 497611998 38895136 921866114 518391868 906636764 87028839 949577640 950605871 242806906 159143209 416211633 324080437 692533845 979625389 52766726 195808467 853562133 799459755 491651345 507838878 461085787 24724890 36743928 851653799 810678071 909600369 150923936 922890419 287587882 272984292 60890058 447577729 710415495 701168926 856026543 660835135 863229096 401148676 689662776 661493831 335089789 863522585 345106145 831450244 824130957 672811496 991692529 410082232 27176264 878753420 664020497 910128989 796184075 767387064 994037298 423201135 366456813 359879267 107603269 348021044 393677248 944886977 618282016 108981946 286027856 458820765 848240363 104705050 515121852 861961506 854337348 645859037 750937861 475513491 944140430 700398326 243917609 417372937 544765558 952572071 694655019 955202044 695310660 125979490 360031244 924845069 230509109 809297703 481384286 234864605 74102283 420812204 874829774 59823582 232103637 968828390 492605994 118696721 686770860 217321081 239513382 999722839 728495373 976193579 151320107 228819790 537106229 902206273 592462150 490475778 585729939 817956982 769118198 355544665 749654899 351124044 899933683 529026678 273591043 640825094 957468119 678602596 425732117 668578617 325918386 272897881 840144728 150596974 23450232 710966133 472040320 494234104 967621309 382040525 831641732 689548192 538698289 36548674 366857671 45688745 739791131 307744575 673394268 377123203 345729492 882070137 732013265 103040641 559901581 926551561 533680557 77850236 768642942 465991750 427859311 264560220 862785636 882578624 641421982 648820975 223805775 594519646 250849676 950524557 666200788 117277921 517535220 997572123 108201983 201784692 144843242 447448067 618687265 979113588 277144146 421558581 712110850 463045517 676001477 417597492 950975837 425691257 999447008 101365608 475520365 823059080 540873354 941809594 976564853 742412645 653383568 280012311 136681307 788390481 522255500 328633908 434630759 953922814 151858215 21971299 944737575 797335704 125490539 414024505 2797696 728278177 409828319 273059999 751127292 271393248 788968366 427553762 208830564 936582412 519486703 986009525 17621203 876597741 622019397 167916920 37544624 415756589 716144387 277684690 23418332 627366202 599888868 853006405 4856567 644608214 527278237 614194686 355274698 356003342 757156068 790260871 781294066 766363712 690528507 396519487 101683206 605606799 737622624 410230947 415822111 510372657 164626222 542803725 840433608 309502590 136896763 30187392 260139762 63515590 345675065 476360951 836769291 725625431 911503396 754512338 748572085 392082179 491498473 188858718 586582091 478209601 769697009 572400973 954495560 70844641 339983597 291967224 208569644 73691602 732852536 839868702 955664271 245222186 395540479 697760458 800524133 501727142 487830593 905063252 873165068 524096893 197027730 612940494 123544868 261477927 43625804 71550905 268112059 586053873 25847917 244521820 823861594 181904900 204260403 220861063 933126261 794537338 918000055 57375803 474584360 646919545 159703782 380612212 442147856 435697142 743042551 931597377 74898073 769619363 502145915 635159210 347164815 560164559 137788212 62233841 105870418 309028791 252400094 66737937 79527982 137057551 706453001 189110378 488567559 728794446 667703654 998729050 516832755 468831564 282637008 400489689 881279209 297525786 389732169 303832284 904958143 401069862 331129679 210460578 781375293 201181182 981011541 260783274 137313208 438987226 391393791 397768265 663764619 744010540 226886475 812694115 108988302 73635967 947682542 43064887 650687691 53658909 599958085 468252673 249386890 175524876 614594102 352981839 505388411 244523067 373851494 23100004 999291693 873902404 142601469 473347922 133716301 37216349 434462387 572131397 248749900 580861323 817810481 962087523 344360709 390369268 750381981 451569083 977118700 82969732 332668513 204560418 615802533 430947539 538353047 637188471 154081366 155269224 90091768 979929968 706077054 570255609 630583989 708799859 797181493 426556576 556547246 50022264 527199016 840464863 349766737 904554054 628666695 30435930 67375658 423266730 821243774 465832170 98102953 61829315 26484837 169918710 119131961 483920679 775532243 613240638 789983048 455902250 6650580 506704932 212327137 685381720 574247542 871003595 195794361 390515751 511726065 935172940 356693320 478763918 27875810 553491500 342697645 402360228 83415524 205284699 23383456 843992321 346468200 992945161 747127889 914108987 861304860 886492008 698893923 455772834 550891356 312865893 322459374 915354060 620278078 542114437 224033361 873396682 919782632 612774394 901063462 596036435 53630166 793690636 845371374 179097258 418183658 929963763 868350548 587514362 214126209 990634492 331178266 469076476 549272999 917799672 79906654 600390481 501899449 917028226 949290977 441070280 113995615 822085600 600909644 462008135 170677288 849609655 40792601 18056451 719008911 324479068 477998722 385638363 747770801 392310596 197765090 160877465 61580642 888031423 123080432 936318594 588030578 254271219 270655513 782935925 608118184 955222787 346534172 130747289 576230741 951653522 602393110 229967939 981259897 201075318 518970087 830216724 154760480 143532774 133522344 27603975 605541622 687589241 820200979 831301506 277884777 422442153 878194722 765815810 353835653 561351256 501698588 412183721 139634817 482614777 54820949 308479776 257456202 429228514 875390734 477611619 357887128 953452476 673274531 352340918 645592385 619021202 833035542 415788317 740004614 845050633 462843940 95937021 411814963 625253806 694361939 918525570 994735115 258031011 273096481 858740847 876739245 679178775 407779836 881920906 245061805 555344588 768203690 175580812 939110697 788335991 835622971 915341300 946741068 358583322 177306625 94838006 682479217 646408939 271456685 225007090 97463308 713490537 107597687 828363855 588958873 849456501 994649040 621381370 653611767 665609905 311583851 148587208 521705293 150411580 660420675 837373913 189349187 195676996 333327122 290826723 864403261 54889289 869473001 489941636 10163384 732067459 364629234 130871978 192772688 57891445 578937150 675551103 563906609 290904011 425865159 823104648 354116264 217282720 485827606 995884330 341327417 132264422 297170315 530104558 875284931 459210599 303871241 237804693 195017878 47867757 9883091 215582996 11101524 927955639 625196945 818670096 311447540 656517636 576154043 857788140 764698103 95756981 715848182 515640253 137774099 83076001 476872068 382304982 280350512 602497813 620893990 449011343 245828144 333011260 39967057 117015683 117555941 318065801 589208500 48418797 538013317 25078019 739945521 14213343 74959686 838984579 476698143 840235066 530595413 223967497 359223478 286857654 525389361 399508219 143428951 576621816 290120810 7003294 389687061 742877445 840203215 29004459 881546428 772605214 652320921 547264095 835458612 595790224 211020429 551570891 100273142 89801384 169056479 777948173 68516512 91486215 777957944 122606812 948946028 172399812 907172875 827762229 824879980 291744628 804955424 521285296 13862614 266337644 542221671 452313953 920694030 735774381 213614900 609676783 461402162 64030506 550729897 946020967 719616043 391064380 215493204 519299230 795862827 975627713 387697273 543098082 418787477 768184442 477308299 829660832 760002416 931590304 597713976 73106783 276507616 545911858 49625562 964930062 553729376 974832909 345656529 897672436 394947371 805903352 253925682 903260420 10952917 771579395 844924257 151047561 964072231 59155421 905853214 851662332 789051873 159265580 511738114 402575772 880448740 707194336 765657685 294591317 233765657 895582761 92488318 858474527 898272840 255813002 889277561 654755856 965228976 887320616 473276530 510420455 471716611 328431535 426318561 827890034 625805045 177199677 674007840 198981018 649761028 593882273 479170182 723761861 952701266 215837507 241112623 622503582 219564167 146389530 815977222 838139115 255150925 597388768 494886792 800708932 943809615 677355743 67680533 923045995 939079725 616875255 964378034 283752289 665798058 117231281 717060500 10796702 624581958 364336361 666290523 586015664 323963015 256718374 571882936 628670537 327550518 227731346 168113986 588901264 353868497 795360539 79403206 769720478 547122436 534141625 428687851 696746436 71158008 185044555 208865005 769334143 646795094 260672557 652633679 35676289 476650500 887374552 76767082 59968429 535085768 26751638 539486814 81527284 867584617 438251020 395650557 239036353 599458587 719245539 6050012 470871538 926670358 460849885 679309138 428720356 578142712 893622654 111281877 818451451 190034016 605365909 536449880 960062103 944661218 775669495 80948675 114134752 381110738 593210430 867828684 989273058 393772335 54306080 490407366 162482994 43283327 867533697 161106919 389878470 697599265 42647075 638082379 119915336 794983095 521652142 715934397 48580316 633864801 114402558 971863810 419923564 104647489 180743398 737388414 515275870 786465332 437131967 452985427 659100884 739618588 384974112 252415274 95156555 584916274 301701986 371548042 664625555 466875944 466544905 847640205 491024864 264891768 611282556 323038726 932488871 446059777 844353468 719797684 709061275 574108313 604012395 210868709 594317137 793570615 72520349 494090621 199065681 454878554 131607070 647847408 791774011 2217451 305742871 870127445 393919246 757329962 112092514 319080569 465700576 729524117 40077620 61108202 247260458 145709077 311125654 253861115 505128475 328025924 221590476 109906572 27379889 408421722 655986355 901301537 122022541 653639055 142859581 467857574 514058538 546279153 345296816 189266811 697607320 583093609 808009610 229872751 290440019 423666436 612614352 564562206 218462622 129688728 396826974 221577238 610913543 137462457 456971228 949225925 972327994 752438300 606025228 970484139 158116112 661377450 264435875 430880251 947891250 130167488 103209201 345175226 94560147 784154163 789029242 171658857 620478910 683092848 240108943 684652337 446610422 505674878 803416115 47342729 737304399 910868129 775704734 154642407 544098358 10983963 405449772 659264425 978108926 337731121 88488956 671288420 301019050 572079765 264857411 765403196 551777193 712716161 865681312 503379876 911004900 960047216 437102178 102336060 350275674 407931936 31034113 592762654 57203711 761177352 764017725 439714563 571753288 181122301 165545679 748878850 589772414 772789248 399636068 391578238 300121268 102343903 503796833 889562342 285989680 904413060 517646718 397971764 545166868 58863205 934292581 531170684 70248961 852988304 730237120 193780521 618967694 140812745 147668365 222845816 774094939 482154472 711997880 33419731 399460543 768166153 880019618 607712791 318333262 357143992 869228858 768082437 141708514 476255138 776881142 12323245 894059943 625803289 639882667 438002370 90580141 663537940 629134757 536238980 268320891 264401868 224437927 532538620 909415940 432234874 281978885 43234581 122456619 223542209 303525497 671836829 251875510 836067103 244321790 756700653 135597973 832336543 336874176 107327303 612473278 367789587 513124843 272186343 63228353 352469318 99954451 528952574 664221873 855050825 501651792 304786980 131504361 983443606 734862150 671860350 157711129 532359066 202534180 497203005 498002064 929030231 304888873 589616843 897902045 663013301 295376092 381407711 671459597 185848928 368907389 91803418 715789663 498088557 720521487 199608971 242335413 653788547 285866006 662536192 983787406 140683509 27906931 620817165 403934773 82621194 339604968 773590235 717169668 545571093 726044910 568425883 16692008 314948865 259138585 346850735 445119262 627139335 583001365 395101475 465492600 683764612 314968268 775701761 903377488 691792476 255315863 472239099 69221309 868308784 353235385 461315759 967411842 668178666 551039881 869290003 277514194 523078132 411419952 859284679 595365887 781568733 915921209 972472472 867592454 242603079 500459698 106648271 178957930 353207286 128780490 891969166 328420625 811897292 447446752 695538608 162999387 255364158 607558080 522253030 237667182 285230879 930832714 167235763 540904766 623439608 960533762 846609198 923279367 153451640 609479480 923261946 766635153 576631742 152977788 407630985 497668041 284334748 606000189 952503967 849999619 668337609 194925792 563064385 988178170 527664686 153360052 742941443 637644427 185936584 593607697 400590633 889542442 309766751 323219922 518654711 861689981 614518578 402352094 196271050 566839352 919899872 910487834 479604306 7281375 561456049 253931924 996653514 993971915 963993299 146780830 259004973 151360695 760146248 791618675 538950545 828530710 261457966 218084445 127945372 817498709 959006630 499358781 700256576 328712046 893380966 628977765 466870491 512538456 484115604 9013861 543357851 569541210 375386354 682546435 259718131 445391672 942854132 3083231 237798207 647627076 471771367 992166914 962719702 902634772 582638508 120011565 540492508 262965329 942869892 341988437 593418142 463255613 892134430 3020699 49575104 617685726 401312240 34091801 626412810 714049277 601391010 313556905 535163472 953808292 605411837 964904572 656470557 482051334 748480934 316030629 140319785 815862648 709373070 587870411 747110075 679960557 69321819 499583954 201048736 761888311 818200464 141970513 813862806 545549195 958369543 665182943 543162176 680480215 810095530 193003918 820184870 409132100 670822965 375342570 31271953 778664476 546253399 551031902 718607761 139728124 136164822 228279465 564623809 275300174 966546293 176688446 624372945 448953594 62374163 201161884 13225269 589302476 7876137 456878858 239569816 692234465 44569307 585622867 497755172 447850196 313345117 757038660 979985924 926348192 822745130 796270323 444632112 62579131 136791308 437550477 574499761 445140521 67792335 197158473 85009877 653423446 663964406 918532441 41041794 60792056 538678755 444403913 280005861 779868627 415919090 786954085 69272739 930287869 312364063 984510773 861061074 723408701 524451669 536232083 431569672 719847238 549670201 384725860 989216040 495611266 303155800 811263931 464176107 819201215 705864357 791196400 420006478 878895891 663656057 252357173 527914616 844812740 931480691 699241929 464948557 593322438 162222168 837862053 757401984 47215007 710759258 815341920 439267008 560145349 240859974 56980120 894583088 735684455 44306238 794421609 377342531 245110390 808870317 480055007 89602461 563145170 424470594 651670216 828826457 115242827 475390432 546516366 10862967 924159741 552951436 771862870 984551617 627174205 694795660 259570314 792432694 87698025 183392234 270463956 81182354 390075168 608093120 178148421 865697293 264075365 912761631 676222852 690982994 762661365 817114984 257213050 844050454 299668357 704089413 422733274 295515927 928600969 533993218 859962755 74315414 484768149 157455703 368396894 714166206 853398383 49886064 465750443 942935270 361682190 591820918 63460410 349730504 260241650 816756913 486899458 581954499 117241548 475266925 384160225 233345241 810183504 501324880 973827936 188931531 985140789 548131749 735244356 755898133 630240459 969521813 268512229 562677462 534760131 823455708 489503995 535749598 969508164 465206254 799150976 173670367 970999353 631667727 618563776 947877491 622630835 854409244 180494552 403277421 901479554 972631303 637865304 129727898 387502365 37960470 18077998 389487996 784271024 574288761 146687470 391841077 324740601 71185993 386936368 404589029 364489784 134592216 442358519 530233468 969522093 396905621 137745313 872599187 389648107 270564540 48410465 98547252 328888462 621286213 648579906 944129377 679143165 41592118 688443960 271028385 879709690 286218149 308083591 358622063 439380519 895339195 842623475 202997442 674077850 164452246 713251402 545977815 419299714 505845521 497016983 762408293 890085198 887170770 738234018 990110591 403935462 385266386 390075662 354373547 376653431 982115209 55856086 133004546 836692803 635546140 520550344 587701688 778314703 531359113 847373486 397298145 496517799 45274193 288925702 433310782 689960465 132991849 691613246 232915969 687069861 463457946 657111007 524272118 382141691 891949597 266335553 217197027 541568740 31375148 571088821 996349876 185159298 465421319 659969119 434562960 60248257 746285025 834759898 789869367 759365524 342120205 53427731 810563052 869633866 792778490 344488715 543956664 198530329 647143364 590663706 677379496 67363538 600211118 440756376 890207728 393530150 353088159 463499993 24579305 19676975 767569777 828874523 53739057 708088503 900215493 397025022 311942019 927044909 849919731 542904118 187904535 440642710 61939489 471326026 43395356 72533676 316567025 764205725 162567754 939700978 436251876 83801145 589388661 891761445 270930923 155864632 808502287 944476621 574985568 623547628 715111483 50184233 113482044 63979607 386611336 735267249 235145571 470556477 694187567 276554472 796659386 532767021 842136725 401826246 430362977 758242423 45173712 953996848 625806716 386714965 476592977 757822018 587188404 210551801 60079109 836877822 311238862 86746451 432872672 74270256 977067871 875900342 649898523 698716367 156822523 656362420 483103523 304432572 302009710 374814893 697919759 671369364 471113100 941803316 562822537 434976889 75147199 552138417 914292168 66636726 480292416 750165230 162209329 557263445 591807572 648085659 172578969 659781138 554168901 188409270 705467982 555167573 667602712 847342478 290814612 394429888 576855606 160347209 838150235 698929069 959708797 248216394 182160746 49213250 682665004 482364033 594378054 825362339 799234404 328258166 727147913 408740577 127860007 627807415 43311149 277041627 961957391 814735233 158573433 501443141 670874106 21780046 667051811 472490258 385749835 97751862 326028617 538472639 667874805 478521636 911565792 812374768 498240453 276388113 639187120 626144394 318490716 204904935 529993723 836973177 226488962 656832066 701857076 158968984 236173598 883380186 217488759 397287033 101199611 736711981 539539369 573837247 32307620 635280595 155240803 868737282 647474168 832100372 179204549 897290000 710861235 447389904 999353819 886415305 854961788 748882979 237038813 373088870 154390654 618129566 622291998 928083549 766322880 584811756 515523227 87399057 309914538 530121561 498096295 100351780 42032516 458459633 498116270 660931966 102899598 957882995 24605036 987102141 68054033 313285432 964189129 982196225 174353929 877691397 156451135 20347011 412509702 315419580 568175656 263206697 992556639 303967750 28550897 172434184 540485576 969476329 159887925 41461642 990942034 442705592 789765238 83324200 86524638 682823687 499315493 975158956 44855330 33539392 401430753 172838579 105385993 700884642 226298642 60613856 99946379 609339642 238327617 419539955 38723239 332688037 169551254 300304159 773049536 71156339 990734134 674568647 369105975 316772639 904507590 660744176 380070395 967339218 702359580 694767503 65585769 213128687 587401107 532497155 535918822 366168431 941535186 836456236 942763022 414422204 163413309 799527478 538922735 851438793 162088287 510497126 98529907 43651222 508288212 688189159 141326865 261890767 936871139 678696543 787725196 835685131 76108680 890402358 607476969 354822089 799251218 997013101 354504011 825625382 576412300 195201178 596785215 584111679 190676063 992951699 423394194 349889651 126109114 271647446 871294258 150507657 243026884 745611533 552713977 324156700 312604067 340465049 868318823 188124613 162603567 102471642 300067856 129605540 904620279 873291322 437740510 460711453 868152036 522932112 555150904 706516581 511248601 23051013 333551003 500584605 832882133 5128776 514602859 625078675 14297899 712254255 440426254 111501766 41278941 644973579 172086473 172849956 169923392 593182000 392413922 716943789 620472654 305903556 601805915 570186583 761861730 189883973 390671282 17880320 337232427 521978746 456300358 366556801 300936332 550009005 12066793 920798334 251848977 999246743 131118009 261716137 843869872 439795933 516453752 849150307 98722759 116144702 792498576 86781621 397402956 57659820 802349086 795587218 867294731 988765674 395270680 379923157 744262189 442219796 862641105 400314556 512233555 28674853 474358039 706174686 796989299 573770767 507366739 757369801 406570311 58858985 246486587 519990312 879584531 498601596 975742258 972410788 801933088 116055065 542663046 727417776 72973908 308662991 830136015 18326471 104955033 294858482 301814442 45085455 476865257 409051101 734857987 540529568 361727625 520936693 718799914 874729258 620307250 629159570 593298455 624154250 394116738 806300715 902295725 187931786 836634744 396196330 294498069 790250797 867002876 641534598 60020009 805954874 148166831 777398878 285294962 805884717 219482980 84499649 578668992 941853396 854097457 552896983 434195500 436433040 957663946 541950135 17403944 196495569 420276505 861772825 355622838 995306984 71835606 933700527 233417925 177842936 901811828 703860097 36055653 92018020 860228190 512686548 75690834 68733985 807902715 863067881 647814239 76394923 290515949 694276620 423858899 420436983 751624901 413045116 356259275 656191935 499486181 390191174 90712403 626300932 579953146 424057602 937446301 327000537 641804678 85794656 830764040 725716338 768033455 942454839 55429452 135761623 483955260 187886405 555214645 257819724 211589528 746681293 994480953 537351496 482840981 761879899 43902534 231294156 462395311 380992127 60466231 44435559 348320563 991638462 177921950 192700818 889438892 675086123 841580866 340379324 263245963 548581237 702283770 709144338 535960063 8883071 421788248 383659461 111523766 147720796 440689689 20259588 471604202 775764902 104058857 350932258 749381119 386774778 21420433 566522914 394678969 604519256 120925463 358428710 579133691 196916813 228726962 605042986 685757123 958505819 597360263 576556990 718249633 907563384 602635862 303744823 644803885 698135758 244163550 750859816 12588816 404415648 558796523 342599356 471735791 399943735 294248623 120105932 594065533 801983624 906608783 24724883 633433443 595447486 954932602 106348984 762090479 360849384 337037783 871725804 56160777 700472053 538533450 341826527 439500230 403792456 11851396 300981560 749316788 780523249 441837557 846177344 625440135 960846068 745186757 730120407 337447966 663632011 890481708 660368994 588529371 451685101 892277562 74223579 768247512 863278290 647129114 402556762 973080657 728196402 286969034 429930764 462647236 688356107 25088831 479354427 235449146 734236309 963461594 8095118 821184295 54455001 516723019 686496022 733425645 300467272 469071242 216169486 892184471 983556876 357585126 405377232 791263089 939096393 215564769 609295357 932704364 613929507 189949568 196771863 819044257 866418987 826153282 905885191 26969249 585073212 133847266 475886401 364893702 181324915 539417865 52152339 911149440 895792619 876802810 909541784 917880022 534371849 79265780 900093951 133697433 242903089 919389654 63953452 287084672 131830157 5071515 588277823 810500006 700823463 121605178 617108594 88953397 662046592 695936661 150478240 242691003 617194692 229491238 218609134 370451404 935913387 266560988 691370726 579486587 78635103 785441288 57655832 17076659 816409347 836082956 641253796 747696118 783015372 559251450 474885131 252148189 173557751 443630592 914706661 576393530 646549122 763783220 537671875 521450751 961845870 333877577 754714720 581086429 515512132 345895158 351234241 865699197 64645974 975299947 604807636 129116088 412934193 950188263 263303089 510425226 701356430 515376440 739991860 16985935 295039732 798053979 527843380 646514583 200217103 61835065 407092466 50456303 260914719 938276187 733242177 717033331 694864599 237948672 576440612 606177884 645136788 123675694 809666779 204234160 380281958 414287396 219230405 260690998 543751388 979127611 331784307 25247986 304472128 599622097 516091394 15541896 632380833 984222915 887760621 312567747 43110075 673144956 361842831 589530337 196715701 915546700 998200731 183767271 629859835 782484067 825690200 995406540 852199269 914443495 633216618 652134360 395141591 926848147 770502308 108457489 898749180 242220116 6473338 232557035 365352180 216941323 279359144 69122404 734662374 570867678 824439410 568262009 10109329 582547633 850576173 728244373 607749865 313308107 294712666 281888808 745289927 143917799 787567224 907179663 19551234 843338750 217598441 904564687 365568817 730052653 311310922 902547815 353091696 163607021 359720064 468335603 592773489 295383839 540660551 818965286 267864037 582961066 878197511 992975210 669514431 425405143 786074334 80926057 977327251 889732867 976327008 595004967 379607698 252134887 814096292 193415261 188559390 835272981 437754046 98250406 877304301 93288637 661882560 158591260 921818038 676997687 971863706 180443454 896518147 167528488 192946951 413453042 535241643 482985509 616142167 928403955 149527388 584770133 234571985 162055827 691157278 904357505 93743754 725159287 363526889 442107083 358304533 749728480 202819352 880888249 868175896 170488658 273525105 884645321 400364028 787060778 594529338 113452250 86130841 292954144 425760607 996846941 651574236 555846951 28565493 279511988 952953185 43547825 37584044 441796686 710166995 520265232 460755104 246620210 846006355 88471615 492535489 507057477 113331178 839960306 473586852 196382675 597378284 607922798 317536108 177978512 884285792 526100818 915646465 449998131 694459877 530548077 409648477 600296480 575933362 378101703 744965577 414361162 106266917 34911736 736403369 702762406 715084381 191992788 833854122 52395312 112582664 606183068 138438074 824743142 170543749 827976401 173468104 711791737 605971097 106060542 981503967 713299345 280034443 488342861 977194197 61290668 349350961 195345931 629167586 635846459 715119359 418954895 212792662 389990447 299778154 701232646 837421639 336619117 150359272 788686306 312041925 76883462 270971021 676559473 115820029 524306785 855164088 549993534 796248484 706134561 105560739 122523190 954884991 969583129 603478992 932421627 668896026 11367652 619692498 620310717 921732490 791926706 60484572 553518180 269793103 414651646 130509023 453111022 175030387 249301782 585480531 545148054 597140819 287183665 931704453 505304328 172362570 15589078 861332605 906643863 517731894 100048386 911961663 401728722 805862544 927830765 861234582 1716998 554783148 715004805 737497423 518698095 837860977 219071161 709380750 991740457 887776262 458398796 577305152 202579224 673840017 64011855 446663882 927609228 924055006 94953657 532410433 993730738 160268413 679493639 435528036 431199138 12759600 905878694 418239056 114817607 223466970 12120047 610715645 296142896 247718481 379303199 73394062 111317849 882752564 224055955 80134285 286707953 444058748 163749712 631767616 255588504 97262858 583925092 587808805 618969996 32352873 898964464 713489598 108251128 546674192 828479569 223143399 917562884 840825173 481817714 959493008 125065878 483340437 926453951 804573805 45361967 576795668 299186559 986128554 830010547 430306730 461979367 632786232 334408362 649289406 317027395 211233462 138888598 587666608 970714405 392920476 947043288 736038250 915286666 312097913 462638288 886620249 286605167 762395684 365613695 244628315 25462984 744584868 730069232 122873338 693394158 974041280 123597655 813818292 738833690 767054126 767774674 792510848 625923759 878806986 857614563 499301540 97921817 165777476 401378364 670936954 323206580 797426533 713052018 82278343 306787137 246836520 826934278 736231763 282645771 889183031 168324454 221378087 547803988 673523037 756290428 772964667 591266356 702581785 101119831 606472454 462345859 347103886 106327301 89241666 288918155 163064777 72926897 448978675 160181404 748675249 353223116 487879168 196322700 932642397 369484345 657555114 500702264 437577699 128013970 982373373 755449805 575238734 73605390 503078527 499877937 567395877 335712533 192544025 752951817 272484953 297026208 574079495 608924079 47929123 840275450 286682571 604796590 343963039 360043358 677713964 299907017 378783151 297642071 332378594 369713295 523695068 235474627 33234808 558638183 962358700 168281087 894251566 592035143 24887236 606122520 67197944 249045637 360101807 222122873 70851773 57760206 198867047 782189818 437625817 161541968 268153479 978923146 676752071 21197489 352620207 227493351 38729379 784939100 460810972 881092233 266672310 442206779 652853809 862643810 440866935 891516955 3229527 890215856 285560022 236995206 245579930 674915354 407302902 762221369 840591483 720353259 678914092 924043483 86282258 952059154 320565250 785525224 897206093 29815735 897086603 847860158 957291052 934685578 122868383 533776048 892934909 599525656 623759385 419270980 727019993 890296207 757759307 457796288 213614154 527908687 392010756 630193969 617868207 581190670 174469274 715415506 672190496 175937131 738328647 13081411 483252556 778731544 347053639 325783970 9852697 993305655 452092844 138453638 395452561 502895746 842564602 826106588 722293384 114753080 228455502 816394609 401499411 376666650 55578347 308350406 885444699 80396798 447559583 909156371 96059303 402038243 659976047 958694439 522172780 562870144 410711982 612390870 589553936 778032057 136676723 696385211 135233975 855929206 541855689 239112448 747765624 95721774 349168746 727402365 393493486 722792508 287821853 719104003 521557509 203478217 339635806 812443701 773786933 299958313 672229888 465258300 203744705 939421595 661254668 302456309 777277553 922644936 260741424 38122416 689382206 590991236 138536639 762182299 952995642 842970716 604145554 244781989 675249978 751694829 34646285 770542027 605011314 755079046 693643131 137117924 858015744 269945712 543743516 105051911 198062732 861463548 576369689 855909902 818681055 805964064 406289182 379496433 559695767 400307213 926905172 646777510 971040863 316661826 812902553 645022713 142290737 845984080 529812180 34496420 124736914 319302685 526647417 784793392 502875496 823490298 770078069 730071734 988796211 652215601 858857733 305507400 289179932 696544609 182114783 330650645 911609370 869340581 482828988 200798754 65480352 518705356 885161233 609267681 337998778 18455474 598981425 213565490 755243681 430730580 269499454 416497657 929414903 137936440 281885134 984633338 713552692 440427913 35104397 968939045 674761691 253699123 45845199 807322960 233651082 396909781 989930648 757226573 82799525 972136202 907233593 1392573 574938347 835390416 996125658 802410484 18498793 455637706 250857930 27366743 313964880 143042670 986910014 296597766 103040167 340294629 25360788 913585871 525940165 786005044 835105493 86214807 844100251 736178592 577996613 563962484 910531241 467262519 454712318 277728547 460690445 71484772 286263464 37508574 731823783 662955691 671913164 471019473 332437995 356880116 73656694 480507873 375242618 740746067 347989301 489260735 537144100 854695843 963473553 609089932 344887633 901170149 806272181 475332045 993419133 652760267 417787744 507781611 450476296 595659972 490554016 567343760 557757085 472869056 920705370 633519563 326357186 534714632 151310203 443275597 848607785 696859241 583589179 891155473 850571436 689953300 4496141 451730835 147963325 425849227 926673457 149086847 691135582 269387622 837121946 539225500 609433490 818689583 513905765 966467412 829140461 510809066 918929582 598792885 227525400 623639701 215959032 359964287 44176082 936541367 78228087 986090653 448276823 126819416 690681606 167421180 954813661 233118099 683664083 721226589 330707427 431921973 43524019 764282021 429707387 671342157 354671056 849255230 577144541 265808214 662349451 44773503 73293596 426659774 99485469 611588577 682640883 330170287 843075313 850701743 517632452 7361287 308728301 124592618 727130641 727543385 316484336 502809121 868262343 885558631 326958585 589035398 36790392 888099191 777300878 239400986 657738219 751125278 117567472 777355087 795130280 496959782 281552150 861576443 871981728 945385259 987010186 813451963 157240518 31600931 511522174 715932771 194864521 697919361 39104904 914228258 211211461 597335856 290223452 939701940 33830553 99359450 230290457 832713380 270891041 346815295 328204914 342471455 411784704 787732863 611997118 351677835 467989381 707888133 918781366 30857483 322146720 21395315 356734223 502382474 272808941 277497035 364459464 215430498 273060270 368986397 580194501 943821607 275076222 337875393 899063621 512129440 799337712 37110261 370441604 564257316 433143283 964929002 362602319 872423868 91317239 75753504 800962347 15777663 29237604 992459748 424736547 399314611 168804764 110655507 894783848 842857722 621847693 827400776 474692723 198438370 736041943 610096498 58192932 58225804 904117144 841712695 836484627 660077257 181037750 514929254 558536873 188068497 494522679 809736958 658761440 760987487 443019138 870749106 438978462 492697191 464145990 323275242 740224450 311544936 207721373 442149823 81233527 437368600 940526881 997134909 569554143 227584584 612199974 206185966 951648199 503508712 102356909 594403770 738446487 389176472 727993925 168372044 492990636 746883404 986012791 482701311 713040837 166344245 77814814 553947396 660955241 946011220 599495078 947619459 829518914 962116760 960980956 488258097 12089444 596131115 964479623 703423048 692100254 553699049 574406627 970943865 839465301 697545044 840924859 118880592 752047720 914307614 728875463 449950751 811215155 861122976 258367993 679536473 319732382 488834652 401437973 635832473 804021599 94484502 10060450 566558655 685310622 986260970 650447995 501820627 559060655 417974555 900587071 511633268 786585433 877347659 458111235 722948401 775659079 290373564 36867730 380418555 828711921 132358860 687701741 411365359 458837313 587078342 761982307 489866241 934259565 103255444 891500313 896226403 848309495 450943324 203470051 235898311 490980860 950071705 708611602 369307040 662557586 569182758 715004072 774295008 260850161 267641043 660677377 62294687 81909438 337545429 240464581 222141946 318138848 597107670 924967715 397563030 174969106 871655154 183408862 759428525 636152319 286150769 804134644 611475768 861457611 99644512 29567404 667748044 207578031 402743556 130468205 652845966 149110691 244161770 830274130 978449376 532083475 51517788 538642108 35104648 651247197 107097004 336331908 795803433 149460332 191065911 48388321 442283046 805472240 578098313 950594764 323659946 160440995 633041423 132659805 119968458 413736414 35426460 711519580 290096185 249000948 979596787 930780957 359394606 555954250 715947216 35399201 642283988 631724233 74033501 267160117 997827739 673047620 561250215 611756696 682559572 697431228 59249719 671487161 170436879 395896132 273582034 697978356 378256727 646988084 259747615 184273424 111890606 739654425 229329571 522334469 627421943 749176247 992207627 66318825 726673187 748294488 163826695 971419655 241595522 544721040 241658255 646668252 912237821 23849226 967127027 230770997 547519161 9145070 472202871 874914462 522916223 630927472 82398549 613157910 176669364 588364947 368553497 119697630 461335493 687648779 738426159 32200903 625156315 185247387 476460515 392414975 484438152 903674638 135513346 987783987 681728830 898363192 164079053 907663091 554000560 628896508 18440383 316622029 739708259 435981091 143557291 454337768 553588880 853525942 232588929 379299402 39554618 25745948 661424159 379307857 794049967 532362238 38249746 982706235 842404051 520303083 874930195 525684278 708229893 356721241 504292245 417622974 899476560 304321538 760259306 634589773 25544172 618537133 787347268 599071972 34405347 263235801 812780581 324757268 110033115 211671350 81534504 137374425 826023474 375708878 579639826 66245798 89680849 431599468 367764913 160172684 762978841 19050166 179655271 617601863 689999972 554560903 914990527 297919674 561667758 526704348 20364326 949896410 212576662 349116024 591063052 326967287 739899308 643841531 433966057 639432630 690291452 42162503 161262626 107605547 653550603 772825407 601234608 673201598 698228331 514390114 363919943 705679665 594125034 482869082 152811427 951207072 84918656 107546307 859234106 873046206 709274727 971372114 106456602 880628194 196082580 739230823 764785321 426033297 465891375 299111951 802537154 169304814 676089039 757631822 942731012 316629326 21197430 139596796 766258612 295453104 10846940 127075681 447934400 315117407 990468759 365727376 196330406 342314866 841668406 933214485 246467359 781886828 457267777 875894565 277539904 490853738 423350500 279739738 860431976 917724009 286959663 946782088 370997004 16873156 846901697 742598969 425510459 794164717 978222837 312495310 657410313 374063949 160861999 320687581 886704632 798213257 323469326 434024520 466770326 357837106 14214945 330014693 384532654 633949900 259999221 865139101 709743252 81936754 672001435 832410413 22865587 173088681 251851844 964944797 210470890 539109771 365086750 667109224 589253123 615146543 159702976 772921931 539181060 764744992 41063564 602397629 78057851 516372916 902545187 852473329 673878629 789323820 160809757 545370052 488710834 720892048 636057238 599551171 20145991 109815035 277280254 333307601 422911746 560352217 605125504 829233259 621271278 148190099 83473465 709771407 311108468 262573347 203238914 540821334 355351814 431429571 178364081 559404829 966149339 599364500 541130559 993433199 940686565 872773273 82783821 565347965 156635997 625869441 105426496 264147452 531195811 71043769 432162230 914090463 700103641 51807112 884906329 35817417 291680184 783561636 403361453 651739865 298508898 845034608 176567328 767799937 754738485 285114894 100929244 823482472 382940265 937517518 55096869 801517942 488360448 730805177 889894108 277172370 36690939 872637638 805448986 892766437 735348867 722326004 881411035 833903648 482375315 535542784 289269686 903697308 42689936 998688309 278561570 743946566 367050220 477698289 746292184 737309943 377384381 767502095 761877611 394201260 852895447 540303467 761195767 127107600 229368541 70899300 197116870 339624476 700772999 623798726 395964444 803668689 467071866 389698812 239946403 337599795 844875568 903649002 637624037 376935839 289325612 750346624 723275008 311515988 353787683 785738656 737968427 733881373 390801252 222421670 39399560 725107967 605592768 322207287 99885733 542042436 738592308 812292243 379570557 944315932 696954841 557106572 690202273 596797208 470289112 563987927 175339280 143640181 919992848 809336209 810497547 156413974 103963719 158537799 228294594 42491924 334937179 859623476 606023048 770005529 734735848 848085682 518837506 73705996 705639756 67396069 524066514 684089860 685262725 433985267 270788729 382216369 787901847 245153837 239267818 98648945 35710119 301723649 344827755 633908051 376064287 933176733 566038160 308553282 307500604 28458676 551399337 134862093 715184833 617361904 605236704 917421517 543343471 710842075 896926393 173810720 778747669 737640286 826846210 768852185 81731919 539842176 921981509 452562458 599595144 171062300 920238713 539097205 703500478 701089894 597927412 7790536 10164448 580046773 603357099 292517009 343805106 937209834 269906351 126900810 482648324 989544713 981852019 700395184 605417207 961866480 610773005 394602589 293565043 482616380 101439025 434197438 431067355 513931327 499587133 523526311 600643081 197874443 598806940 984969338 82246658 201212130 250320714 507105898 332462055 125735560 340340228 492205113 405476623 275457623 287339312 665512948 894833481 619650394 370810092 68646528 945678672 567025264 700624231 944407801 140054804 464635329 693947929 490537067 113054940 929267498 918153085 234729376 832371612 467476590 190710530 79713408 5181201 616164465 740862203 499637754 186086204 566561570 883762244 512287221 713528987 14396214 696802170 946506183 230303011 362844050 185584303 56374756 63257426 145724657 551512787 254350525 397420256 624198686 540272373 598261395 90969819 684401260 95874953 962844843 824972532 461860436 334620269 258734796 321248976 509971811 73233951 357370509 243483266 180852896 104081137 111552690 716056822 389244775 226176683 256844872 203834377 250372799 986721518 558754011 679395028 806055838 850898510 178314185 294550184 195422422 472979167 774563433 740875553 882607957 621809330 693659252 868509257 473804693 877643229 968004161 350996209 822459043 531769575 953344372 331215178 311308106 739348356 77163490 939871885 504477405 792207618 296014864 847591723 253499724 422860938 469372933 716099851 792480262 375613020 292385652 300317988 646806149 857702890 829883636 275973898 587764359 115936016 214615228 279400606 151372687 200918452 540785893 644082497 378200535 777742068 829062312 30174232 340077066 608465585 169252694 275849056 964156478 733530417 670399650 734389857 195070003 815634074 461609639 457534147 519687921 762916255 106975804 385434302 435588175 124551621 202715296 966289939 481914980 752989592 358620552 537115473 193011229 786359218 926025508 494910461 351936567 727092479 526749250 466223480 354453280 998023870 267433619 771587579 426257199 43136726 3343121 267905300 990081456 508883440 103391741 102592869 94802983 100819201 933090238 894754401 257197577 666073432 502280472 606675839 971770789 869403509 542980781 240884013 517744638 688386892 710557453 68285055 629392097 674090469 896930988 671945637 67159723 911176014 366719504 456759474 977214546 23219332 688773308 329990945 858180424 431057299 128439689 997504899 98017553 134934239 973512916 805576235 415440772 555855539 780140939 813238809 56687723 595542483 238485853 236616373 356049011 576486542 32838518 164659604 791868659 681811147 53232232 163405087 810413731 665355085 233469149 332650851 337963455 199291351 485822480 84673403 405547186 96281927 579793608 960907482 765176214 813507132 493708858 890184497 432508677 571619020 987675943 759135020 25004418 447131105 990317120 91795990 780125958 379732927 362776894 928285109 950507760 461823748 294087808 648873562 898965395 243351985 465308730 628737701 254617992 708414003 260711026 641249836 404935662 912716645 772323780 846706172 633864485 752516539 124854154 508370525 884539053 45996996 630370299 489578689 662298186 165136100 72849572 72230491 218781611 395883216 219270203 110382091 515470610 275098484 791284590 240019225 586131963 644196329 5837176 292518502 231582485 484359051 84684804 263016704 379412719 500171441 881635532 862878913 891153420 72533459 801142284 324385497 161682377 615816568 700842982 980520808 54729628 477586165 995717720 298977901 711905385 33594252 444028401 840348570 336205221 783224410 91694641 162213320 758506322 302090336 664109066 330084978 21470932 241333050 195927579 261888143 121194727 738376402 469955068 723308747 423734497 644230941 109116617 488863322 709409167 809314225 596048520 466741505 964155300 209129733 491650762 209008657 813864744 397916899 328397856 583139937 709822095 985864464 768622058 583993180 14081186 96495057 454079936 682053068 183906258 304149097 442193035 661503363 130626493 795319598 738152125 36052702 362389744 121804466 770803609 613907104 807089298 943822476 44182357 248956770 662190994 776325042 973510614 80046175 979493334 457365464 980519888 304384218 852085958 62781093 752797318 678789854 809455445 980648726 974244826 433921978 813564037 56905183 349507399 226036757 928820167 206838344 313012753 335989508 853113790 898513776 937052501 704061148 739277443 630961343 607720111 118343683 989231701 16387733 895447446 291777870 142532622 294484484 115110240 26084184 213779675 506327008 903879203 593663711 129902535 604899856 473563693 914229375 248194933 505115573 164845431 472730922 484901361 670077683 391756398 173154466 382927022 932348149 583983993 43856098 920503373 411755099 409566820 197740641 719191591 832047160 680133040 559997498 530920081 123403286 480654825 890610567 293184258 488517991 425927879 978250575 853621681 994965773 373135808 290618251 167427159 306517208 286076448 359899764 392184398 699644079 573533035 285563708 166657437 8300978 73136118 493876516 645218107 244042939 800069558 634505201 770551168 660088032 115595271 263116792 674809146 76100837 542772277 335885704 704361143 406093918 664057596 808827352 464642082 794172084 924082273 17239036 69080093 163352586 891237961 269192562 211969027 645212487 677425434 700486478 500763734 828263583 680578984 880875276 778908682 634824663 821803145 245372679 638983423 113480400 410646348 933145933 886358245 931971741 836005112 147138222 725548380 899910679 371266772 830158607 271568844 335268753 976953149 847010607 739479627 417581471 996177020 841432472 167454417 346410571 420317998 189310985 910724789 923422061 59182323 979509609 794991953 672687762 662385104 133509766 625553110 732878366 436231019 171112361 916591652 798696036 520214910 545922829 881083407 678232281 868587424 833563679 80378186 643004696 332528749 449641464 57348939 546474570 961573353 862995903 766532544 591042024 656067941 515196596 30364270 335733203 370978164 859614590 608014578 805356044 347739373 482296087 523744755 39503812 278657313 427010957 390708022 228566384 344261593 893920311 240041368 890596749 73815648 490498220 840525592 265870996 985714673 516356684 62802183 271848429 271831543 849255365 976733829 131630064 84520955 721401016 695041468 453867756 42027693 675330114 299152757 531972670 111451644 160081806 961218511 299585967 496411248 136749643 141166784 268964844 876090895 256336430 413279018 311442377 6583054 21994115 271529195 254944162 997371850 911969175 622316181 579384580 499386081 297112067 464901077 179437534 962218646 31128953 58062842 449213079 361467514 818816597 755261795 562704648 834834166 76609003 895647775 415399204 192896976 222249186 240359095 281437327 929604602 160948051 58869214 609098065 948689884 853504051 440727279 272900164 888610186 661211862 565464158 253534151 471746844 811652495 41276370 925070226 503476315 156305352 580365925 368932594 803713801 286206137 317411098 541926777 179312944 28648805 222087371 590893599 354376276 388241327 145056777 290420415 74359360 116145896 525562874 878397354 229389075 748851740 191817642 346134051 118829696 715325802 631379630 656816810 289920151 653670721 243463043 223433303 150857544 823022900 915813753 583658471 272542352 351259900 773989686 919371572 816553845 888293474 654438739 395039477 12526321 971291659 905030543 689744579 9402006 505078726 497012706 750133147 985715500 507552818 842080712 358794481 167639747 128116150 80644142 546024184 418171724 143014593 384750182 254705641 347804576 636952564 371009213 389471767 221059701 930096250 762487720 351532203 432772180 133427307 351055338 413283798 931291586 397674516 905048986 233701211 371026107 218107533 863812394 286067965 260384959 653850508 100666405 604456380 559268417 985585350 755404610 595084403 605944604 193104156 489495239 324174168 123959952 576021064 355225353 503164075 7365775 403236405 536685981 37240768 466442389 355384129 595751991 750308276 522621690 944627147 322472771 30892695 4364748 273598037 40463734 644081990 363059346 371319835 443522489 932168385 432652910 822013035 540307766 226173332 375941640 15291058 18279521 470636813 184597185 217773228 272310564 73799214 239911795 885451989 979253171 492853843 176708301 992038386 757441184 313424516 759043162 182324989 879265116 877245502 736473305 126475379 409575591 599435244 179432547 514864307 368800776 28918857 608584838 813032904 960314954 836672916 370988254 578968640 752173681 310140723 551324737 724664238 188803715 273183678 872395034 188732262 797526191 429630374 764282712 294476282 529468426 777612683 336394141 909988642 772752444 799044444 993113546 378806252 539303260 532895621 25789624 55760845 186430173 161933176 510512903 389956370 792702138 474442960 643856800 848870206 612402239 260152700 283187473 55810393 129346062 395756808 465800374 534937162 245892254 422927814 696884374 323949606 143155948 967153102 950512174 424459407 713366039 785320446 964272142 807988598 847563162 570248057 586560351 15165594 516570829 784642923 674874209 282114481 650663629 724109580 501532916 794925515 47622105 651184351 481815607 805987595 530259251 384113860 444404225 650119023 980478919 335807585 33736759 813502319 156374690 821103517 615650714 46639282 82113967 292320858 915901916 160493940 753384976 43916381 242785667 516351829 756243373 573933140 166109541 126333505 884126648 253059796 136308424 579902637 804472230 226222255 272218978 208193625 433427447 666310307 714639074 696426596 594376792 525484838 219336145 264266493 936183974 947401092 445938754 953365853 409475809 260573957 52759001 535062717 105730925 164639175 480720261 951943138 358780303 196425228 990898843 435982520 996088623 432618682 861783801 736406103 608803881 137122205 213308733 485363242 25510362 597508805 66132789 331886666 376933458 524312213 903246360 629545376 58721715 810973879 497670936 283621040 785186378 341101327 327350718 618359294 801016291 924151478 165678288 867166224 264637403 807080438 181757531 623623026 108665708 130274136 703522353 676334920 131298225 893472735 291546301 804906232 362802700 715423006 722733559 564353021 11100194 936532327 405617347 507010758 786904258 223603650 816191815 698283891 556247551 226580616 803842460 468402563 717346234 819147075 840601525 235052638 349912335 589755660 955731385 569723509 458650946 847328578 396297799 756641690 218668225 147342944 974406615 781135293 41927541 29933003 997544678 33335371 280101802 274906590 911852521 541783966 574259013 279949472 517818862 88950878 208930584 778428547 280858120 190012848 870644715 497861944 431453291 683226279 124287477 230739127 66587445 849026436 206392050 855705112 991373453 420666302 426904862 143385022 722675995 122485888 177483301 400008499 181632986 128761192 567835696 259049152 932243533 953452574 622623945 449512253 136059374 793335551 120809655 318669518 584979678 600146955 761392142 193602232 316111157 870163527 927238365 675186814 832932221 417853195 74069971 515477505 338894816 261919095 554457963 179679983 692206270 665248724 309640356 740009199 478742878 629992690 493490087 85353785 128812092 837431963 637576067 578063304 20762192 918721159 612590976 382126614 740007991 362428126 999180088 715078615 634157301 572288252 771754624 30727231 878352713 673308367 80744677 415000097 687633569 797431186 536775936 510767901 366311084 769165895 915936989 80503367 841958317 124458038 249884122 615428012 355208029 401490874 711992101 592965074 910983848 547617060 423309141 377057991 196098294 693619365 971490158 329712341 120885847 530431442 122335629 338026826 539810859 11660253 220937260 28132856 308464148 384225364 786167481 623163245 143075716 334883973 670174442 366298292 5995061 885681997 802286168 331297196 280448442 957491015 349010853 553545473 526739122 847987174 58589711 955493629 157126718 278379999 822132845 886213335 403042692 617554376 931828170 941160992 332149502 985847301 246408990 57379629 539274021 52387912 422811023 37575123 631779023 685968299 61781077 28309362 424947170 638901831 679692615 29628944 366535020 659472502 598124994 772155129 131435765 482331008 364941086 62384550 549905481 228181200 679719519 21774820 354584375 947552836 236299015 103786542 357028385 916524122 940560081 458917660 561061255 216463913 270408239 101471642 844675052 243819710 527864148 282145160 105801758 13161725 207812699 544251516 312910399 94895349 622895369 518504177 119947317 453658725 830066171 924232382 49871806 289590795 973475283 812105352 313186881 837176096 738475842 282141824 946921074 846482326 87257370 817721674 268246495 5635619 719236910 970200296 939039343 324043871 97309411 27123313 633445068 506314839 666205009 23433595 560230064 220252744 871129258 75062296 780221643 429268837 688407875 345199585 809002156 607562461 640394744 332049862 136764061 840675572 33589959 256406140 923138549 345106674 729511640 832844590 773705904 847620038 921108033 574682952 782590282 163974287 445154201 3491233 286764683 452704571 468315563 125288266 43473330 628731844 200396778 352809454 337954058 335652150 599488397 604022848 610569152 801681910 421351852 183716654 643838220 404933073 116872766 148908859 903416301 7637771 284148393 929343007 736460644 736117598 37591336 585044898 217132748 970504626 268742592 137364546 576999917 668161133 170605272 653966212 239544315 897865387 87724413 9889215 488792483 964568324 346533855 756966814 865244619 974973601 973221802 603817594 443858866 678938555 575047446 437523916 95660043 134919132 27225769 36687582 583282395 967775454 160257301 878876601 146544506 713093018 594593986 72941242 493829754 877422924 298595760 488317964 567207056 777067290 482390180 911566528 969895507 122934369 865306162 498760203 250173671 948381339 267222503 530050160 570283503 972801471 573031921 710197998 415140833 298269308 336286668 713136319 693538812 311102400 534099348 885761520 968253210 341924297 903816325 341430901 850125050 317450101 74805217 492343457 445825706 487603032 723108628 374520825 953290669 600211235 789025160 991362344 152030317 215694 844887024 932386550 606549030 58987530 994681411 694125459 223075048 857043683 450531649 591585904 211574191 978140939 750981325 559601575 339991051 1456579 458982548 568793991 808297450 623901312 118373793 992795151 22624932 343769321 90766888 344744991 57115832 537386255 432633809 925870001 189234787 379938778 317072043 380782393 500832143 511428097 99450463 277717819 649223794 215794937 391886827 652170305 63020118 632269329 94174178 567238740 398838004 287531234 90854362 325052701 280932693 168264751 168722060 905921542 34282505 932347384 782743132 65068243 300944976 678826342 845707522 448631876 226172884 990895732 398046864 908487386 138799559 68007646 697846837 519239089 739496005 556641997 642915426 587001156 187874887 213511514 285841302 987701806 87040411 93869366 141712559 47762859 681696013 891302590 991327723 920053112 506577358 621622201 384370445 39737574 40208172 472446009 99995153 622073458 960133446 585173005 150228920 329377724 338148736 188850863 512069466 996943920 493080647 420501707 456803389 984754500 809183863 964610896 508408441 839665170 182910977 669311113 960994376 646819732 442883264 44072899 754011424 65908580 579970183 748950616 666737192 349397214 932128673 791812877 169411437 230796306 406866358 845557038 905103071 698933509 284724158 174594638 700328032 122971247 387342565 263308034 755731070 683439753 401023036 81216102 615184413 955199775 41427797 415996760 600671828 520299071 479280883 108038360 517085295 651748829 179349693 389062090 305990366 972052927 358347081 978295841 255761849 591424892 565695885 266456327 618494368 667909852 540530855 540573770 693248897 165071519 581551717 777306431 78514543 655507114 666380487 316614477 992116251 30286980 43360570 245014277 616834126 495900497 910949040 397906664 723530554 373179557 956821441 48633690 56790997 627971969 18798860 794593164 44259211 861988783 256546623 683670314 111541660 325685306 598636960 9845871 480478610 482500648 699254874 370985749 777353375 890674428 131307050 161681409 119423407 690667945 920084566 118482446 896867807 8142176 192689694 538870746 62464467 139837545 115920804 830839728 214548482 983391440 951972743 727065488 41983295 96012619 245358670 509217202 810308849 802972197 403890180 342620901 213472525 909317361 450134842 738900887 425384869 884689044 13356357 513792992 187574303 291185035 257115441 264199689 484620025 584940186 670357113 52834730 914360567 937749794 119929135 336824929 833874072 667300291 584196707 606709828 617683158 738364479 749212666 211737663 295946742 224565554 296911527 378153558 492933815 400801059 230580838 84717381 194212726 406525587 689936838 888601852 808546626 817648206 97392579 56659123 298883926 483865150 114117534 354613074 137406582 912670990 331545565 271327616 689464311 715044957 837368184 871764846 355242046 676861219 600856634 732479938 963525059 627125621 325370428 72864200 153811533 697283718 876906395 580231590 698787097 260627210 644474137 953868200 479800452 546391892 897773586 268487338 376569502 344581535 612134092 142008844 675240670 711827617 123766946 337885793 307121459 282139437 430000677 41387110 551236739 557864352 318763616 556453399 198919048 120012119 114558111 599782435 901271793 463046829 811787545 689323007 368783647 544897735 184916971 800731694 528439958 911600676 752937424 988493160 60607268 99284731 928576812 484691534 874415500 255932955 303415906 843117006 205076604 192877673 36590064 930879601 287920638 937920604 552728007 987080384 443303200 670054213 399094904 984452995 993376916 664174796 899992779 16571802 175895227 439855674 839168158 412234091 330410745 8728088 857598080 955421716 165619812 502561971 28378425 355935704 874530446 189599064 869653449 45141829 647950464 606389515 822402729 677487575 731613567 639683139 899038832 768114920 814334164 355157967 962554489 415542819 948214912 990963271 834085289 489162927 295915762 47339512 442861195 518945603 391888160 169205570 967349950 391775997 996274637 720995758 99447823 372847285 836180260 538422622 609669721 909639313 294461228 986647547 165041864 548881556 806428352 906337507 256651600 536904638 194027087 809988515 966229613 773340751 115079921 622389345 997213967 32523600 944835624 630608997 385530912 465159540 143689541 431479506 911817159 606059167 804032755 894745923 824259328 961860212 97457067 600287929 525218646 635066302 914938048 547972649 474336845 641016933 429592779 774916991 452962253 263113748 771117607 172093463 616559389 479097109 144367637 775683036 672316191 321881488 207388785 636092869 846121231 274150441 600563098 808260851 91067542 415237620 372181149 4168747 66478255 641398120 563081614 199121614 289819181 116595059 478247747 620448616 714329190 98113405 982074919 874905416 357103791 584371039 328600104 69930019 70890575 116812472 196381122 580113770 348619664 484348549 53494963 217790870 658187472 91317653 917138492 476556966 675658026 648151691 862973719 297399075 77060430 673864480 614970803 786038357 777539967 925252775 631267198 383107803 31697680 154493071 484092531 842381119 119884297 645516612 752495638 32958269 55372501 261836318 45120674 72458478 620776166 266815687 503780043 479359328 706403791 802128258 931754812 962842837 934996310 306383174 84596088 670592435 365568026 553259892 861279959 357749942 126268612 668050004 461915260 139377703 590936342 415749626 510334367 266826692 945187977 307407141 871596806 743286446 599116002 848748124 864918937 34414783 86532206 194771099 582944886 675909540 834962851 424213856 542340084 728576737 245781650 96696949 377808093 545079415 993899949 384253705 381147294 219633266 777436654 17815509 273453449 450512793 463843876 99064385 656875796 986053374 766072475 110724102 335685429 979558048 180632258 449430271 723924020 615764416 466692360 610410980 90528598 745415972 646562573 303767448 80529126 735760920 337996449 392987423 910341017 966366624 869737633 282840732 596278206 295661494 737350091 894497596 454362017 149315685 639688254 791828613 178021357 495116827 450663000 572938653 981629317 717186000 718258171 754490721 723027753 580888532 994223041 165882073 202469460 97958622 868957180 290523797 485942371 352143458 672409683 633769487 986656111 236552958 298845832 570066128 592865888 151307684 259859654 603095897 181605349 483341174 139479050 888162354 762043054 208242434 414904597 3005640 491777466 783358995 584638435 816248438 908111042 246410193 789342043 705347438 19567762 431536004 381646224 595343073 721527895 659182592 605479571 825141694 407853764 78014496 641383674 276578729 129731681 826015313 115942570 50138298 628654822 795539506 834784221 989199208 823434623 977469992 497203493 842755089 131576350 716490050 897988787 656311319 411844904 329626895 469416646 431999775 404369091 29553800 410580731 726841060 310453473 761049304 42976914 83119759 39500353 456720159 568566782 120393067 363134240 657181280 622349248 809169835 754756779 859793215 428879957 136500322 920120710 727983784 474377497 513383871 534342983 845552794 246056085 493342364 676723446 409948532 319604227 167648936 482448163 44775353 381769544 17604302 157663555 147389796 841700926 18290951 55719646 970641621 624821038 966884027 917984401 643010717 235772245 715809653 116314153 572753170 435368073 254090005 201211544 853789757 737108776 626218337 960275511 442960545 873200069 846777237 127174170 156816595 130793990 463077245 75416318 416610168 687593749 952044304 14937211 775162013 750651366 227231438 309996679 104209816 239332849 625488592 567361502 579541582 33182169 37614293 230576108 612764462 696564740 511278603 774602837 294294001 374872377 880402735 686560256 619262669 204915462 170188781 276129678 362040263 317991186 785597036 358495782 167051106 182110783 455986324 406260791 939819701 815118612 504370504 297690248 9309899 487155877 499604627 119297312 263803388 465235202 5401026 996757482 960586809 748964781 78379463 571959119 370371514 86223139 10865606 703153032 40792279 57627352 357265807 952256693 996905366 242245026 740824952 733914060 447224413 769120208 370441156 657012144 179594953 521650498 630840694 679330532 115682810 223008324 301721507 277466957 891470152 522201925 832178450 375071313 938088317 557916165 15985556 78952099 778598368 938238106 289235412 541276708 132537856 808024535 547927035 234484549 634040327 700052715 432470700 908615870 801720353 734871356 336844520 442018817 480115355 52478596 208878436 310192628 383368208 306427758 521137033 29079907 921235416 978854068 296434651 610804434 806816901 983504206 393109794 685784146 516684414 594901806 339250482 947748258 744852529 257856414 80199479 118286811 778573939 442101689 799267063 128426810 268571285 584089871 379368593 749171491 614835066 765601017 787886106 781670745 123011028 641742243 967603726 23399163 51183296 361959905 93851968 753853003 828192769 587530764 808978801 99283472 439298885 345450399 59291188 575714567 136603444 316476847 841437424 953591730 644427648 500404469 929043268 944155002 267053172 460677976 972703318 752123964 178860065 953502100 577878756 656737078 760839807 150003185 428516557 266444940 932134766 565344547 405241589 800738892 553817797 613176779 501488497 825382791 535419469 251706429 79854188 643252421 727923941 282461369 843657538 576802679 369770059 247275261 576096617 88145729 894575513 780265484 921551463 429615549 502199553 74101222 612753024 731396634 244425111 6864479 384224246 112560761 33151861 505116259 130316679 430728299 962081759 445828102 194474163 290730791 682975954 88561855 655402100 466344739 965331410 360753374 617760708 472147356 596798553 109427762 786419993 789456993 281163414 886229045 430343235 400148872 692721780 641223185 110194930 145004372 535172428 755920936 829633324 530755357 452624471 66760480 304769003 817728217 489184972 16675753 645795911 141974177 463124727 910986005 828219896 402527834 855999727 853266880 724055902 700845151 262239669 559608896 503659810 595196073 704819443 548218398