24618 41445 742697137202356192
27985916 976931433 157638036 915467079 616489499 254506048 661329257 544194874 148611636 763385050 916622646 448695485 873381629 452156753 743606351 803893586 432123703 64507101 479855792 9545266 762210541 209318923 968124995 332621715 301332660 451788805 224392729 897552354 353636587 747470 684093358 419142408 694001402 883388292 279859239 232121255 378414228 205763486 131477396 77646940 69769462 702219310 96882736 604600572 105013799 66268190 784118174 830066136 213391416 330002548 254508075 748122875 469193348 131651983 836039184 242668904 802786030 554014313 877061807 821070430 944766247 626560469 231369683 357927574 405843430 670261183 903101682 15603585 45561904 667319409 178528876 28024459 863256720 527850954 670104778 659658333 655937629 722862214 856934913 750685716 153918200 511171963 664855215 432166541 270804236 789402327 666747738 414192538 117676495 981060965 720370102 473120588 703082045 863534023 658561501 768828201 493306465 509216186 774851990 498687348 165019790 699196759 471028112 264133737 709685919 465781837 442694309 250199423 955245373 642980650 917335834 197199526 252840215 836645521 974993883 38101385 886253096 85686403 332705217 867031755 937842934 308156824 743059661 339329355 641952719 715033668 34373484 54821217 427439115 642740244 817032626 328885792 399988047 880180464 72574113 985881236 611488454 517589593 658693985 732295939 411354727 607481001 795500167 286306862 277146676 348921431 4099920 970018958 330844022 140011314 494675684 451165593 351324675 908144035 596820885 240002300 171397498 75445741 201682975 500906975 676599428 821466990 795523303 225715238 60558866 13910493 660356414 948216749 890991267 367870092 354121885 439555465 416103292 52158884 49398760 113314635 555596271 638403949 288213165 698350141 394891415 816109445 741426276 310128804 187921048 948150822 561004974 97503998 825527521 633618786 611841431 699919683 578050411 680974440 369345749 985236006 585130616 868322494 366973192 488227923 214753238 32706950 907338234 605001648 583282204 678720187 97933023 889997469 239394282 114245235 34763667 950404918 192403242 832653340 876494304 859390093 271703123 127790528 944992439 115686898 279272354 932416323 614573427 639411757 167722080 256618401 203322140 363813056 687414817 622104626 417384351 946208039 42000897 637273064 510055192 85352985 391552998 720667789 806039817 427476166 175122883 525442568 138446242 6696472 348862672 911837078 531143929 126318068 504677588 949026578 19833937 478801528 772502366 395608111 454757717 820513596 898231045 282822586 410069851 540103827 659554476 301706458 29408418 850845384 622671554 728729682 13356950 996287843 878168699 740101051 231798793 256688228 388150042 969784524 470563961 88605572 216466217 202313876 548975951 204969336 245007805 718526652 32327707 810762543 390910388 390368455 593138394 258272529 62409975 52520274 470807346 235107391 842651066 694280534 67931058 101743064 702338489 45476195 812607765 610500143 580690811 21571301 544095101 119618071 571787664 974070624 527699897 476408857 353927124 581353397 641747073 774350266 735285932 822732637 667916214 732667576 560110149 389667754 421009317 349914187 422522329 395183882 970742850 880758374 730498795 8929349 372856943 1032436 810016391 85166524 49377588 864995613 673847429 395174570 881879302 699217024 675321541 852184676 482512642 934533753 111175794 527694746 23824944 987304282 214339393 104949141 690029250 981973939 258801328 957263225 215981908 153646475 334991689 723600258 923987499 563052454 637236190 155343432 730059896 329146559 33062604 358519293 73414036 39562445 112893754 39786411 298123331 738158655 164412505 530197112 262122483 881487169 835970211 199465699 979202555 250669303 206371101 79475206 162173150 411648191 274320023 468325588 154582408 439735665 381189864 783143257 867862157 871639199 924530228 765472767 728331118 398207959 630762024 481811653 97630165 672559582 186627898 320397447 300079317 592722420 275815403 309298747 761386541 378751764 8680966 992553519 419198852 513753394 954026464 945255758 791620523 45391997 73454999 734892634 972366304 149865628 435746901 690331440 255527175 395291635 962621837 350974473 173466352 596546269 764859450 814461621 679591318 814191856 539560996 948006879 997138524 659252798 709619996 419969614 542031695 36559504 931202620 478504991 530746472 918263978 342590249 711961614 477278921 451526028 140024659 851317932 11846653 588233133 35443505 116199847 23552314 871671359 734503816 324198151 87492767 595661936 7770274 662787180 967123576 872456356 818256793 808740435 559063671 622598590 171472779 772176208 49762554 672489557 620931300 833556307 116632650 726359041 999742617 880329957 566835159 467917453 611664233 986722921 962375550 761976131 974257948 233793373 359280837 879922726 482484165 195483544 160346651 747946289 480232706 223167115 780346395 59023258 749921080 442744962 998904519 784729363 256670425 727753186 14594254 543021317 208541599 371672682 887881416 635005908 972170192 219117172 196202102 627011104 291623290 563890738 853912581 372884992 457058229 783494899 926050633 706081862 598979558 929716317 65841924 698505663 947879672 420856754 197370398 885167730 426057378 627980045 464231659 378631902 606349989 977682084 81858666 832874302 123098637 735030277 876230018 779280582 209094253 193334618 335981637 467611876 288498469 520462503 710360879 370771585 886501533 763141896 680199270 474288960 981944201 686178806 385238776 520985787 49955364 5837440 749854753 968962507 218576759 551408788 901121156 534242750 484631697 196429365 6374767 58078624 428896717 428629187 916857370 289793397 892014097 982008888 816429286 801955194 467536395 601355879 892462751 273972585 239458164 72677949 747157947 536674739 76092494 643849986 603323802 160137925 95714855 247981462 784601030 403241030 359106902 440170934 134706994 425346133 679691834 387969334 574589309 492117196 845832320 278562117 601154094 411772545 668389979 978653102 667311094 563264130 854077899 91852307 989683699 299916630 248980441 798036786 741845737 257705024 925896150 970766370 938654856 55216253 272738465 377509780 510053547 181277314 808473568 528870676 628748949 407023936 734037827 418931782 507612723 249995106 250981830 134513195 401285982 672826508 498332397 29499484 639479064 83296923 90065927 730762315 334625483 103157480 387916653 444155014 574787471 573325191 985037249 862262773 961275235 648001154 405740850 142397209 412053105 545234208 203212468 48914765 761050188 633557282 220315466 257878534 568433970 302743042 933003582 745556500 771133771 454202419 825087332 669815521 684747242 717172326 860151388 467546542 873135817 707310273 517364687 713207514 695000398 48497703 942154671 827074844 714093003 514104692 993367929 271491782 184553143 604448960 191535475 657766146 805003767 789643929 728517104 907905302 93234713 242485579 868724361 848686497 5329301 475290137 204265827 934815709 929641996 354946178 648373357 908996317 756229003 232607615 740191904 865588942 514599366 20188865 900512575 24379959 359147871 471405557 960913686 472797498 823225630 604114433 646257085 701475027 572966199 430587974 244150484 472141333 79089289 79484893 612598086 274126706 490624475 659161820 256116360 632061937 513443103 158589328 688742360 724968055 899345073 969227202 921520000 810371841 934667415 214028788 679269394 285744614 867150783 719706275 410501547 697209622 677367621 159792516 441638193 552868191 313517996 313175752 753934231 713876388 165194274 749832282 265588502 240022566 798956478 947374365 782327411 613587901 218078915 408381488 75566654 884382494 332090844 924292651 38855694 792067604 194169184 798493281 411563463 38267080 563648653 544307742 287255766 368567034 473531085 963341288 923689328 483529543 832619254 325114048 404247513 930207843 381232259 914065247 379623833 106363486 463294174 890056571 954588358 220704225 350536344 959917825 304656190 649320303 76500140 400849754 676282347 49244838 945906113 884892328 975876095 236347773 881761639 65115911 294221879 519418758 287662422 584701390 464282650 104351018 196758196 15290062 790083897 174337777 51093837 903477135 427609198 845712057 223391962 471322775 501368094 812612348 341943869 656403620 708056185 964597261 536624833 13611502 644636854 143125336 311592283 550739816 316539482 697842854 289860589 794306046 974695791 307826009 217345664 140232662 716254926 174315434 822541447 961827729 146572632 415835631 358426656 308052872 983333686 63540696 798690643 894225169 84562718 892208559 684141395 885763001 813808526 180926358 634171834 501963400 88297489 755334346 409984462 695647554 315977335 543742691 519826880 296624547 664734750 50767123 260618218 595630240 83233581 235912548 920959502 990124970 576994261 313019901 843237531 83132907 766287248 347770459 876694505 5825928 300446820 283311257 2026361 411216607 47099935 238330538 786455351 567412680 689203097 287430043 280357562 446207702 923360247 637440212 21466752 335414421 807256036 500132181 664694068 469592267 33418455 645900539 207723754 765901240 743172177 155007930 464052319 919001943 776445726 703005922 371185723 634493597 689118353 612370523 111314000 768170167 920765385 337404394 900642522 841541709 225815793 164302444 825905086 151018691 983983737 211743000 357769677 953593716 834571872 416421567 575269376 421979383 269235563 843519245 332535994 608374364 327517292 273673159 686025995 787058285 151754109 375596555 158630890 41268463 379544388 270495125 409884535 711020000 402991151 317592054 668447297 950707896 237733815 338119645 157891195 477863850 507055518 956755024 648845638 252478178 967048498 48643569 439405547 82304453 200585866 188645947 899388704 78103094 903974853 189597891 661146176 146922957 303597648 747577977 541670549 90160415 323244062 110362342 17569936 127740667 111651055 278807918 743190796 575061417 297151371 387823757 764042384 104046122 374770438 717617947 862562443 800798589 889478652 619208074 474279576 782430165 222132691 251782948 869541306 671232997 746936829 258059599 276493214 191549462 782636853 282923722 561217501 458706893 387743423 902596335 684447032 153379496 946164650 283234545 321998044 311601599 495175695 671690525 827778462 896965349 329373264 253600794 881489214 68915173 37313627 330561066 552368037 443737543 217362663 939716201 319924776 477315082 441180340 25665035 676039364 134099945 731020236 341719455 299726178 277014936 462423750 651165264 385811730 802413446 254652927 236579616 618511697 748190619 737320673 183758380 833850181 792673912 609998109 245804525 209691389 360052923 75911154 173598323 862803123 488119354 219645286 419806377 813046283 96283461 227926921 317214102 557247827 253670886 511930807 618506647 449780419 335373601 131299796 463657896 353921980 910726198 289760143 28491930 983122954 166389724 355533217 811009115 688186148 150230918 646337293 585248051 328549224 711000735 425315423 27623683 631817569 397109711 300066031 502136965 218591491 832048693 685510173 204930193 352782571 307878572 870664340 872170836 29001633 62632200 565927304 335424920 148494551 11031896 455576570 687011328 978356392 821635363 17655280 700717642 469440732 532415149 262753727 3579021 667707936 773705776 466312003 990980730 808134480 538591525 667104035 438983325 257106095 488285051 530756623 660337563 486370091 10424540 710086147 474178419 712348059 451581932 593250691 520985279 173761538 292107659 393244895 137471986 43913419 543713808 575738734 379872920 539117068 893080717 746684116 28602010 429640389 919875600 13307453 781183354 160406048 959955165 940496801 990219153 461617328 212896694 560661760 725135189 761558964 502359829 789743525 176055447 522989138 750718574 202478949 932135870 296039134 984384880 782486495 992008975 912146450 700195650 884443066 128620006 42516565 831133127 618652139 279418876 810442487 54855900 927504110 34735264 765478768 393101719 920619530 612448768 742336678 965766023 568182928 867420767 486600229 978707448 426827546 421335902 748447078 448302894 549735630 637326645 940107531 548691878 978664601 404044792 896108574 389790554 829905525 852095188 246112599 415201019 547095718 252564816 424807509 377624375 531190 203871375 14767841 604464626 192648190 655394954 294874672 693518222 492337246 309772120 459099679 863185957 405966850 695510632 427568247 462993611 113548124 304892355 259123752 855682766 57377454 38351180 697837711 815161079 465767743 484680193 947435698 530936009 352409250 517180729 64855680 522707390 575971316 216801765 573526035 691147407 952358173 178556369 644985071 881555562 275315723 226004193 543960386 560541243 307714556 260024406 940885284 893878758 882312370 620401161 572597206 27712392 158127550 747239852 290039556 823145147 844033975 870189070 500224517 614620112 459805058 230215765 177008919 427807508 634635145 9509699 503889573 259427853 434251014 386143347 682488962 782981820 752944951 102322074 541363501 980397275 55658152 874699720 406524173 740104990 619675246 530502310 724389300 759656563 672565608 709882296 859118878 727485251 735827326 637126042 978984688 655857329 74873060 236016452 948859323 359048663 997670741 785654088 483783224 781833997 206097241 673245456 721014923 946602788 619434881 116892706 929449857 629677221 686671272 355697502 932736468 679461652 140804145 707656251 939106147 865133616 969672525 815106575 722193532 136553778 548793396 653676870 818108180 275789323 423501416 156467880 649171467 464121512 973220087 278321301 146538603 710191151 505998775 469259337 306931879 156088385 554129034 228692250 456982494 217727544 992719513 747856311 466734358 52165223 698072475 622464872 155177091 425807199 85133069 814959954 306209983 223738150 16157048 798479794 553630225 666589311 619732399 360354591 577744297 282842150 336796688 455324106 324720351 38860307 697286080 435372734 863818873 772898996 783651313 735373602 928890851 939085364 698232094 289772915 283511414 700381625 289028683 748765389 901649587 13200543 804682823 73202209 646674311 932159935 707893483 437391229 177858439 746432172 70422105 966956361 922359346 229568242 315771967 8204166 909702964 748083544 178125588 668416782 769184671 969728796 850491224 510283481 421939505 199792955 773868757 460432180 381749650 833079720 361082850 593851145 846467988 544605329 403122844 404386075 388542067 36638111 340531756 494429000 421423381 877009716 544739846 821501383 336920905 446106540 220625701 530794090 966775049 802208926 871747922 650764251 963606457 463095322 289562716 151837919 161336679 371168747 356514655 341616536 278084619 719643348 887706111 273027772 79500998 439438804 261181867 703419617 180328228 385998692 630674652 663010739 131941468 254789301 863318101 75825977 492959884 71188211 227788898 990964501 402863615 418371718 732082203 105054658 263737960 978552398 609730208 419923414 202887718 431835877 474686043 4625215 463950720 286050782 185269827 704573064 217683432 98158857 960436501 866673170 410976058 667125166 255675035 674021725 269449979 198061519 420679911 676254782 391359388 937675112 362280853 507338280 732511157 801451440 804269838 415096165 416844620 275301463 962015682 416084572 873244942 799000776 374757738 818523850 152464786 344261478 554258510 3737867 958977179 592136400 633758842 226676560 26768980 530596638 920096520 514517735 304584851 703825187 45906267 325773175 724265496 942003115 747036767 745789507 813316557 293822140 129887180 484423524 677966853 581964502 274700642 820541201 616800190 513034805 397685292 316905177 107746273 394557963 975805887 464012005 743488638 429185992 57291129 260285240 794936339 551862868 545899972 966726384 719664324 620422993 959296850 424835460 816597409 773087835 969316960 105537029 364326372 461696073 273944053 773427807 628166706 479804011 270660385 566727319 393072087 654854603 246553664 281900556 897449484 459863150 369135671 867592375 539199283 655077010 617121203 457476717 596087830 636853743 215454318 637156889 942641453 415107832 708285547 292420356 332566487 642192409 163035959 701745167 380215197 628646136 897548584 297046261 395785588 388136885 783021215 778135948 397889273 893940779 419275079 441682690 296888244 458501935 145818965 417007905 889114711 569423310 441107144 196649357 930886142 445120144 227110056 913131266 416213871 278961849 968265800 34603672 78054489 392458628 947716741 373321473 185451670 435212648 354881798 84828103 125563754 222563157 859040124 12390544 457832131 21636597 334746337 8911451 88640121 629139181 489876666 375886018 172517773 556260891 917896791 216089912 615082347 381545175 205208591 818117194 703427881 376763700 468029063 531584736 790531272 839111485 18727913 436007290 551938159 751679034 875311918 436001140 549025205 812663274 597979991 701478980 231457494 104097225 255379117 329348793 726307322 250409033 94851590 522795579 199942771 467379738 435942401 660789775 664554492 523761507 188727366 935187602 246690812 937664776 158546120 484554875 265840323 89671652 769496324 306403355 572621514 3649550 138594626 794807965 224087029 770908182 416715728 969257288 61187281 950131270 151361612 488021178 982804439 770199522 200843992 822825516 184666281 792237674 126758245 421558962 148437842 259329237 478021355 998198394 885013896 812007126 876509868 434423306 798989291 182072856 44223862 957147523 607615301 491944835 775988447 682052578 775145929 584577142 580658825 634437691 740434005 919541772 200386909 168515838 143115698 115902554 579169489 585774388 578488784 860736940 980929060 765684673 715998477 186859981 305051038 318637217 572421485 759124285 341599187 71953452 834525664 664510586 33293022 306911315 713786240 400550714 767159208 917304290 228270802 370255789 92369696 718129086 82505474 714487741 948321153 39424038 151452969 622054990 619035537 610992116 597829000 535356032 901330910 877688795 68250828 980445418 457392129 786180520 576058698 860508382 583733212 778706818 724956225 144754602 646730461 266198315 182384412 148213202 531916091 498543934 99972783 497009753 576128309 339944561 549351543 161531895 614066776 10966226 758890972 125388385 836676791 228898060 203156337 948813701 363952178 337297825 128925744 770822861 786737074 844739630 495660223 107783257 462553192 327729836 870202031 815837767 283903251 686463146 693177273 151060973 303082296 212658838 724933377 91037466 688764521 622870771 270384213 488315738 467690369 350501794 448546669 699864369 301367780 28292891 13376298 668091740 382309569 856571826 166960856 152082453 987852881 72475348 512805229 446409293 249624855 162602057 375915722 31661810 208555807 192969073 809217271 359274536 998511937 57507977 688629608 351139985 311179356 201084389 149006396 587908231 908788381 435765045 883386746 501879134 627612344 757857474 632130643 161165477 955328299 208542895 344462437 88682339 610471807 230832698 910009588 235821915 587425672 648207610 986774065 239806026 939252898 881049120 625327221 988896550 900911347 853990328 928564611 376893790 96935086 349812711 164415947 805648414 799492940 579240492 535753635 568496521 383900882 315360416 922607246 319191551 680371471 500118840 701436023 755157335 416200412 110082815 537440500 840074275 243064668 820787038 248184453 214784240 394906427 109113686 17541587 375242629 409552881 46610114 820025075 676726305 254397182 719647640 73274019 344254 451773229 404405030 638562185 823006802 818485202 965898582 445992825 161786379 672123918 901337580 993510573 437929104 400134151 204510660 367339788 621491012 254603314 533334550 816571237 251861892 650914955 787791796 129112243 807073253 571039193 757175880 345028440 301667193 917028589 71336856 65155171 230259976 14601185 97424068 990862028 560802905 499905370 433466244 589485236 556338536 296811975 824947052 871534248 371181999 319283873 992056105 665085149 468113247 110724011 924306370 626287218 570458277 742341682 321995737 814814898 863058664 592469068 971397354 550555217 326243334 103827482 271993481 719333036 202605980 706579207 505815973 550869259 548262973 272274696 611287497 98069985 276933303 557572059 590202455 885543944 996838227 303438922 193343949 120677382 293000980 611807591 307900673 81856332 978967284 47579087 511771239 49447283 196309803 549125353 639212871 308116863 905475690 588491814 657412361 262148382 624708889 987905600 27464299 364978663 456726175 935656572 115351238 45324957 90867864 34832874 524938574 509412972 34462750 854597281 239545937 585702440 210291458 177570565 673578101 668022162 617495825 715286275 82723323 981585044 791076177 766659409 114244096 68528770 215614787 158657200 197537720 898529112 769285664 704197420 588091827 744637696 453467166 147189592 307100442 259822731 33529258 805199251 865655537 339685748 973008045 41670983 705187668 97184995 199240649 154292262 188937915 603956453 983862171 712483182 595218232 343653302 785620472 417379620 631117237 350544633 806790961 158394714 715128632 563709691 156799313 623399274 780118048 733392885 318930267 197800761 101197159 20482889 415142542 700835447 900194271 607045314 210695075 805494748 500558199 657413078 675351051 671783530 787156085 49334501 481469235 368159407 855878332 386751608 683794369 763303937 846392069 413602948 434609877 297533377 814938150 621953959 830970699 212403355 351053904 474110055 738903798 934351810 70238282 343842424 748781028 639987766 213936825 606917620 561754014 25562623 464871258 971176098 678890598 887416176 83759683 756970289 66049656 410757223 637190951 798633595 854393163 352106889 628993169 867651781 402325711 858587528 686221093 400814843 701798063 972314718 386728164 630898678 93715342 349018769 117907558 911177655 364304459 594346095 705400351 403544747 519755070 618874193 285481884 956915430 889157498 979964121 792547525 102855530 603945995 462139445 718787866 425591135 326573879 40452956 987170552 510634330 153888703 373591629 777683155 627961496 359103004 17946709 738743931 520043585 177861060 299794759 167533657 501684903 757045860 483207875 91186352 72502406 829806373 849738097 741920478 729288771 925151720 235672133 781496474 765088047 712967820 341487034 225541429 832268995 382533669 13907225 541301979 918798819 960726596 544412081 31828433 1657373 423014451 430341661 840502198 21761769 704710711 8805251 598953667 422991592 659196622 480928977 726709517 901383974 564551152 300649472 301589440 129835609 713485904 698241875 874713699 727617569 460761242 698398870 513895960 362885192 167853748 704894560 996419290 600925698 52826367 653167443 911295166 469492523 170181012 959716185 948831028 544135565 365473160 873875174 931866182 353716249 730089002 833580090 958458325 527696938 526220354 164838046 539833569 563631303 978649938 154045347 695402175 750752224 57496278 25654888 250327650 99127694 321768325 297923795 272661908 213903188 624516751 11536596 406075 594958690 268027102 584144295 154874263 668454862 916371543 555205392 129453952 123106779 468114200 960235166 205732265 246427444 762135225 531627754 672439010 148439854 269326221 156845271 717658191 525333515 681317856 205770449 796546227 569988148 641668407 918480400 472154538 2197884 766165909 165016532 427326696 201124961 464162994 681246887 532396924 199695692 494098243 219666848 89884433 856032205 196658231 879077276 611702569 789771745 233174518 648172677 921543778 881666350 251529634 67168397 838503347 992813635 578153047 819412849 114177965 834480603 99402348 473067959 959819707 168378392 105020592 490400242 238365028 810201545 201710000 705805819 695745926 486082982 427671789 817070135 195258778 604451216 244694056 143947989 483314421 840863188 382549656 424535822 703528450 604435558 208185904 296745061 66998154 120177192 711125724 836493799 171741678 71172130 624710593 874185066 759835753 661713097 544298114 839539919 551455824 707892026 837706871 362139457 841274963 504900221 179910645 201009780 536697787 663921348 986877323 905509865 51353516 277728939 727651648 558418471 855660642 75220599 969587672 566095361 814177397 868631897 271115278 123970004 801950230 417834666 963431385 540277447 902863953 985939758 101150120 169896458 756683339 178166867 930396072 866446361 550631556 973630320 620502778 404447737 720667667 439096584 469534975 440675959 497337326 400401414 181240462 728016237 518541345 45320961 808042298 518430974 576071443 308619639 440583310 326528727 776128711 333724947 973362514 714038638 330414614 266947304 409466053 535170372 173154807 143307445 80636386 7028260 420543160 374827041 803493533 224782947 253532996 231240189 185233701 486965280 101872732 344132999 233912609 220137603 887226848 776381347 563193077 877139199 342572550 398160929 1975036 46349457 950390942 237592828 624745676 892386048 740944470 831788439 833289335 101882909 214192113 531167231 839935942 875377922 418448272 976191533 247819646 159345493 73317355 793759043 725061788 964537987 977266070 376483532 988674970 200567559 677517375 215971838 14449066 148489634 753719275 566610168 563511799 480722594 334099518 650242054 999587561 184611613 366254002 270403290 132100447 352947764 159989468 441065426 221566452 621710931 575480236 545480503 423662652 751918189 794237098 457546361 874458117 373748545 452169276 835012469 805378201 114935449 977181149 200624561 828010488 289285768 597367653 307925916 816205856 844877993 297733701 342706128 122886214 702507876 793551049 235104338 644209180 411956010 448514390 61132750 224824075 527649206 257812395 530802909 820042103 605738315 315969569 717328192 130881024 172572666 914083053 884072739 133647037 575306459 665614683 906732125 835974784 459212624 459826962 267815340 290908694 480607303 651073364 949812732 898754438 801847158 427365948 62794654 64190287 77489823 445219839 231533970 179145132 106361035 501476910 990728383 553731537 270312848 905707248 360838967 83993388 219282509 522041930 287763830 365735591 25204587 984342360 444134818 461144034 219744155 842018194 722592457 86329467 918668060 41547274 520960551 258387783 312287475 301003946 997388895 539730328 950282802 669860217 491907775 437624950 819339060 487612884 626414207 466291688 550073564 239265718 201078271 47743530 273323483 817347826 934956046 576133878 88169961 246439029 845053215 285893309 430141705 931300231 928218259 802119660 850533575 121087752 175793140 341514282 114422138 772489396 27984949 327872918 636791684 602421857 950167797 925036555 970377870 850991934 705621434 496697948 203858639 749552404 179193144 655750554 744940100 230092678 781501578 783802443 194438134 700423506 529706613 334699442 606715705 41148302 365129897 441555724 449545961 910654190 702357249 262849742 721072300 431601402 832819903 575123946 248831540 933972826 330628563 542474504 635292796 598403340 342427667 657183183 641858824 403519401 155413634 515159579 140386599 532684453 810245258 584145222 970100530 358612110 969466179 17743713 716462540 732107338 885637292 905118329 426951969 842265691 370871534 546405332 74055721 439912476 907203998 823267635 978869219 290566914 805215994 158510608 640183452 238883805 84166440 531574495 72754984 195170326 616865660 365668430 183274533 65645297 575153584 901076614 362654012 212398794 224708906 916829801 269911649 347053657 416199227 244561620 365926672 89565680 345923421 226760156 322603920 793729721 423190642 753253394 647040049 331404794 399758345 798637505 400088207 933872210 641055386 443741740 11071182 229463803 752996806 911678674 173237981 123420936 328323994 157028524 139301301 508264613 243027402 969793899 572343449 359399004 235048184 865358012 29579862 818276428 349808620 47080325 858678914 978615665 225022682 498406183 514989245 325940449 296200353 881750715 520253940 342195979 884774408 882945623 231706523 255923447 620836097 763862600 299886832 861177738 42783208 344018519 341292605 946555585 15571138 840264966 923382804 204005618 140951168 952284882 546810002 218850832 329092155 965251952 737225374 915587814 821290103 675816209 327239976 80524888 208082018 466011552 332358764 615277735 894835475 461604864 706868527 608890539 426582221 523418960 159566846 559421720 208310843 13101608 561753715 301347259 998706099 509194715 12755057 746580668 492286582 884810165 504357221 714064348 100558315 504588860 924428165 3930550 178732777 103522417 162625298 161866495 301240043 827677966 537891223 886216135 313066331 715378630 9148201 197827767 641222346 883860105 33094566 389404242 970909235 118187711 631797240 579372598 886583869 707815562 740626257 611202138 536159351 154770951 433582703 824534095 696511132 374377611 36965591 755037825 13064143 402321895 739811354 428605301 480481757 71910821 936978708 12134666 663173247 923173962 131781930 813268410 771952791 403045012 938292105 964356567 436535151 177010876 683150444 48378576 789734399 132176819 672037972 153102443 868020262 172309605 173455183 914344970 401274861 794291962 587321395 4617192 668566217 186216466 906045409 511396955 422439128 537827846 466836100 320639249 837578272 222597676 351432913 915476564 571121620 518421009 724907335 48476232 717245841 409227966 998252398 554148906 842896026 981476852 243279129 254938512 800631073 793001842 279822757 440340909 851168128 792790060 177472314 294427787 369063289 734951315 104405510 269992016 86480763 136116945 565650823 671168124 254502366 584911883 208807359 713145639 131169315 359659935 600411775 648455237 791793718 490268005 680959135 593982691 437768110 475031024 127515969 828571753 417451273 807051212 143073043 459203031 251559666 791165119 934546315 412523273 589608829 406440201 848305707 9164789 456297319 128824485 539070396 741743082 424569688 401489544 367603092 879823057 4766498 903165919 908179154 25651309 386146049 891074387 355324318 970793884 325192410 811280453 933255788 665498005 730921854 490450963 73884983 557739817 630418405 608548691 413375687 607991300 351828085 775788821 108978669 918537194 892852795 430884388 464381124 524418556 399025199 739494466 562054127 260133875 884484209 216551280 492928991 182685537 965061007 186557733 171121676 974223604 887755711 835942292 487950393 893505460 966734367 35499753 39376306 501356610 779916793 869037706 72005262 469026329 850722307 897290839 528085231 68788431 377099672 667484139 590820414 615865682 761534466 532514267 954749553 143068460 582912434 287364851 747579207 936551872 122774915 552545662 787869065 360519053 817662972 697833597 390549576 164934504 343748748 204325100 844438563 695601603 165372622 722341633 521113215 788541930 336113092 179296110 348503247 184036675 83402526 652517532 207671243 57429643 1906290 65750512 824541882 552048413 204422274 68183816 106658474 316409899 43322491 38904572 853614004 774453252 401323314 20410783 705856059 5701967 536558183 498256572 765522987 250793036 508687363 473641307 782059579 924544535 574707547 737271035 733817645 867558886 371654764 10964183 955769611 483435080 519875871 663262500 366130793 583671397 250993796 914791502 82547623 444841794 980028952 979944000 160475182 898461948 428992769 711035290 69423024 733514761 924151118 358421242 804211049 439732348 783833401 426798646 202996066 10353984 516342374 594446238 545533354 140143449 28144419 36595516 26650525 681406248 993622440 203969557 374138655 987539365 670528342 579368806 381898207 12399525 776768505 466922473 403399318 583428883 118935816 946685712 599368775 950544952 902046945 103347270 463278975 289068276 868008975 105723443 501714323 305253380 925307014 25153014 477491174 346808892 177903843 110451306 27905826 214388684 704812974 962470755 836531836 212981629 493932185 735217392 524344050 189673971 865155519 31644824 821016206 590702826 92525288 217252511 172791713 978589306 988679361 29457216 113793034 657756756 999091238 437672433 3016303 713919748 741143386 767454372 377893249 311384367 757345099 315478786 937003834 498115284 410509008 999337903 32594463 105554573 237074924 701277067 724890751 232823500 244756234 121913581 245530035 655166240 688954432 128435431 150251358 157632367 844138126 732443783 894623917 652388667 845208350 316211729 360301974 900785375 612126339 36183111 661296666 590096081 768958460 104854435 610741636 7170271 201725615 472938905 712451497 127541620 856874224 237782488 992668711 138266321 318553465 153082247 207933864 903732310 538489009 411079306 611580190 162075064 667686888 568187579 313571078 944197706 424158358 838675763 999102119 797485110 611968929 967342464 643509585 155144131 93283989 401936622 802262433 351469198 514470123 333049793 997917881 735451858 868898117 472424054 620512649 20958370 353199789 966251271 696632331 372847915 242122715 441974821 544589952 729012213 213559406 470743678 435752118 686112 533405743 824760822 192312131 902291881 998294099 373767407 684910792 280332964 563054775 774236035 494471472 667497089 427806500 59998918 224944880 246873929 470448266 872040966 402645574 759361759 780966982 463663629 63272060 974815809 775571293 925155419 690332965 839713989 636133312 202578030 50627932 22007135 318113673 718413563 297562377 707796951 146799674 276070707 464407581 9447957 269519874 128507905 503155154 323066711 979585273 13670729 142382062 654333302 129165920 441975080 362806270 376668199 359826915 598156600 558632605 189074485 914563800 521703882 735641260 398262473 32463232 797819691 214038169 763211428 73615427 245556450 745906586 654230881 780733685 892333293 921111792 87007926 114369557 902865161 334874407 560661425 431436298 708424681 467808082 235656700 274275430 593142907 972619344 95146779 224802597 922011944 350609420 388944810 243014124 138373395 200497334 349835425 376259404 896783190 142033420 503701138 851037182 467292746 771284118 336671463 420498981 257855165 430455011 685524774 76208273 914559291 452253902 226227246 606273016 174835527 433160381 656704377 52188733 118657696 579550429 754957914 420523947 358947967 990128745 649581374 45684280 300770517 85760739 418021612 909104324 538347919 169068375 599430087 461412953 756633043 202083740 964013320 19495274 475854146 286158227 385896966 212395286 755996470 354607208 941512047 838803043 67613699 48544206 755511438 549004677 151965751 543249733 388459653 868292886 855331291 263504213 508818322 453228381 336602033 757593298 436045387 403357577 152131702 262580759 769099491 384626421 55603231 867085901 498459237 124714596 668402461 907159203 841471477 341675331 616225179 311970196 66886676 957126891 95062204 970010150 826462682 728928221 923749343 281994535 142410811 388471558 325945821 835275376 612641093 641806587 867788871 201622564 14105950 231224635 695478442 627538415 808084615 55622514 97297356 261317192 461357469 315458738 246640365 835021745 231700372 383849145 585888009 748157940 462045372 817090863 432441363 909273445 435246078 734277350 644814905 193832484 885348894 214619418 389490468 272081753 108829432 740468401 483545398 542423672 996311236 60388730 729917643 567885949 752067923 832028015 417659258 310157614 292412241 491903476 49046356 38705758 160231811 906903831 246939681 29845285 837117960 582685904 192162983 590296362 842159514 214452800 345022436 245577179 384910540 330363635 988568657 334114737 765692234 787699744 300209951 826679151 239282462 253378021 42712443 184415586 612740071 558075021 703244747 573229215 647612961 3718603 871287023 802083401 351633505 968700414 651819395 732952266 330555544 998504813 630105369 959623446 415350605 652238218 932210049 648625134 399769829 618592817 10774019 500121368 726135005 470920423 137713313 870699689 349059339 916843549 358375767 151927869 314182370 816577643 204716893 751879739 992473772 94467543 949095521 392146195 716482255 445757198 524877774 846995073 420737291 874044071 463118857 750153929 663572920 76542053 885213104 506630138 671884554 604694131 709295835 317535021 883771470 548143783 829563997 151217605 525914924 239988161 788700930 464484015 545239268 199461547 537670352 587626913 969938835 941422520 979460168 461207644 692181869 560455142 44424611 200319466 528777218 320829982 203309590 224992226 120429435 740084336 610701584 27094946 157566427 63193946 254028665 458734993 559483456 620545792 672509683 964377188 368977441 153293938 423087386 455633495 427226767 206094570 293251269 250711153 296806774 981033229 79778628 209461699 855124698 63910951 423409057 42951847 382305820 412756849 321969121 954161154 917422389 40560460 517711938 80240771 596925431 137988741 805310077 505276388 710399825 22868881 216563970 278937638 500572809 656474063 19378752 77181654 194787457 781603019 397216732 905982028 565869300 362640247 531468790 433539305 718956471 616384881 544669802 901412950 785275386 525574721 227952650 456090825 151250823 722805401 597216230 467018304 85029375 279284117 976225414 450433477 243906594 447821307 874887979 525801130 729764613 342453114 945575187 498740684 212726106 654707692 199223988 459615954 187457710 883393173 880514302 607040365 428764324 490112355 280606875 243595415 130798652 779767853 255572272 783985622 383871760 837548022 808123547 857230455 937001619 899600426 847666740 369017557 510981970 281877469 14876686 511400849 599189044 703544592 245405748 449694937 420576188 229686253 558696942 153555363 217874755 657164296 27943164 158600432 219252288 865425822 30589143 279417611 236411265 701302999 35785204 830236361 644854385 433407748 944352002 968738505 590366290 945768419 74732072 236661939 236434306 901638360 889301066 891240570 494434999 716369460 179699267 403481500 592502340 104764528 266673194 311540318 580912468 580722543 757828239 21166866 137482028 76139457 160929212 11732818 19390058 352285148 888060150 507926852 884059722 224514403 749896634 605686997 19343325 615873121 520271618 165540608 292208465 215794316 767244416 671643911 828195118 310513284 106882527 337085365 684024213 336553747 239304199 968878756 793922433 904804460 137729111 31255922 346100231 950793069 728252394 655470348 727084951 771986655 891393237 738504421 168859962 884422834 710653284 590124093 108197331 561034052 456870242 978326876 659189088 582232216 528167759 644950229 69878841 650259873 267418025 882248390 332726349 756798326 740318246 965345812 109566569 321034909 962406646 513559985 994249074 259680322 711049731 565094872 816140199 147352958 758475313 521887052 84917730 454849682 10019488 10907806 687166677 113269803 132677095 958598502 724231247 729251485 619069273 247922567 573857911 563398442 215758913 883320941 413403917 269884730 720430887 921821775 913848493 94379938 563644170 20293999 793986573 123809247 540307109 535703894 531953467 635544409 428925868 42311707 964217569 509493923 353789965 566965147 208244099 737123511 884583218 762626239 558705342 765995067 803497787 921695419 105690248 376673472 224161350 567985738 705771124 286260735 331829673 467938549 41641196 595463964 436776755 629187147 678256247 145188837 526057584 878656808 459858162 24274450 889300452 514203375 538703065 148875396 403539532 397781202 206167165 429044871 361702370 378200838 767871820 862858001 81121688 879118353 759170317 322817539 275134041 643143678 600923427 926620516 738588236 381197221 422304200 98205355 224289298 538291174 792577873 305622004 269079557 790388971 999208301 218780999 463005561 724382059 247322215 686373333 444311037 238571491 862933602 808591164 683670680 846075357 809276057 23370432 942391054 705511210 253042854 759773330 116123417 114251049 511669178 520781066 664222642 140393984 318456798 527333870 185138247 33673695 876192570 823799211 837603844 270833218 998846796 90251416 378335501 752356653 897882158 296197176 408618943 54399599 499603922 184498294 204421108 584488673 742020935 304899816 869689405 620359078 84341747 424150542 654564135 871037803 190700760 195639441 199159929 73089445 15964113 602893958 699814514 735099351 627734739 778773163 461242637 373302987 603665198 885286310 492486462 698359254 986965196 725718347 787204147 350297622 909047150 419384276 579418773 583870901 555772916 379852584 38279622 576937765 542872979 799504918 162993443 136629347 135721246 974460824 81879873 804413493 324606015 533602323 312210226 505044334 520476348 843602579 609853887 895663143 784697780 43512337 503687852 293745925 802661089 327213230 732804600 659473528 250344406 236627703 576816924 939788791 65944896 632926497 998010953 584947014 36205095 22927435 504843692 280515505 797722411 621459392 39898796 451162960 582545353 72546356 51866920 430222403 379433364 841110276 858987706 332300277 152609662 928306552 948409336 893186139 264441615 305969667 851979183 474178356 829190570 832213374 403575337 993491271 615177164 290472562 536744550 311265706 266631758 657296461 126615907 208993527 777689504 910344361 949720920 302376086 109615374 442311306 849823475 814885367 761757692 13301662 539170464 298878934 246983467 735473532 287782850 263359352 540579316 209476839 582071288 903171562 966004617 814407947 702443611 387072839 68622392 834489020 934739644 933840880 727679657 35112891 609451752 506175955 390784797 608920050 741463525 969061286 851363503 573493428 21084468 463408682 23676052 905161728 632163342 430152042 560488796 421094333 820523689 101881339 197985328 93505277 597001074 896869436 233778196 819438395 793793618 790120853 239974180 745951647 296823276 29058489 750976984 372347958 768940762 28336613 209920065 171940156 610708724 641082400 305601867 547526228 122232970 487630459 264389115 683714507 345751463 177192016 216459952 389731290 180991310 32163205 86042724 692295651 238388926 62017992 868739050 716694961 796052656 939882961 16980271 83680954 146865813 874175652 455689338 183007582 520421338 339199694 161195949 978565670 806457125 233941926 283122563 380006151 38076311 272695435 131248850 290494111 255328777 159635497 890703817 824877940 575630417 445857717 823521072 348350266 749830268 257056814 774170540 490824203 598861843 553741724 277303545 800217518 747214168 363244115 722399536 163470034 379129479 152969262 540737537 266026577 823464727 842790869 164546551 745615472 851995384 787783161 930656185 650711067 178859477 810225813 443955524 698424363 782161489 59100205 167723315 817678497 29279563 322505999 826454009 687739370 517024539 413750934 339814692 641949722 689334484 773767780 809985689 112698931 819851138 275266981 49195484 72798557 825253227 779318864 146352455 707288109 927385424 71910502 768808783 48455136 891895210 338766643 12944324 719594398 55723503 76215434 327623438 594657721 368973772 359588363 186726259 429066989 608273002 720875102 271003726 328116639 906294699 218400887 793726295 69438752 936537963 607543506 431587807 466545897 457193665 287659701 185502738 149998046 2243389 902824818 799605300 134218125 16779305 264511908 197452775 327155566 988045258 682760815 630926177 310158882 170225822 922582210 436776632 688899253 659774622 309619861 257258775 535221725 160292474 60218925 994091527 359509306 527394529 485210965 912142505 225402518 72392120 199768741 133319928 351830308 446645088 281233084 246462218 625876163 700073458 531435911 338716237 830961978 417420932 841277306 363941579 300227451 979001442 238764755 689814120 546788577 791141975 963927771 79782432 191819891 436650468 884375334 930287948 465214497 764217989 287119056 286314203 468515844 917248241 152458175 336257691 377166239 868253272 543719397 292053103 285400354 968246692 209881213 350576535 608067235 68162234 267386699 852542957 375930725 324162488 53897182 720406308 963370258 268534326 974157519 69340681 323799298 536718471 632647937 46962628 250932596 680086263 682623201 27587861 490016466 646215948 29833636 288982425 893833967 734738118 317977741 919570179 945618505 217015264 965474854 637456997 756694345 592174351 934408067 715052391 268588927 99911487 611360645 539471756 736816360 705954011 687008786 485596018 276932906 868310276 120661343 936421903 179392724 427058902 935482152 168814070 925336737 667716264 282691060 111694482 751367859 597772618 537886803 102635880 15922137 75692870 3843105 136197463 339730123 669001761 211181506 615159768 663777642 24781720 445740902 129149503 132548099 482019045 453051972 594418938 157299850 911524346 973049312 852394703 899949025 301899459 601728838 13190175 105138960 984677477 95500878 195745319 568648844 832124547 793812184 355429948 676026738 936380533 699747855 917287692 578988746 379962000 559290280 601353697 412529862 702821219 589215009 571641822 251328514 267038965 725850372 694462273 324770499 777411082 436330531 115066018 694367290 525994333 477662427 139798576 517287360 993375973 522990163 577843960 270054425 885945106 844292028 827017759 781267123 909381134 386100112 506539556 441054949 299839741 667939028 370008097 204913970 809389887 393688663 262618889 597149317 535370667 280423411 165032681 293134197 444283348 460868553 119191592 856677248 684086085 302924166 15992008 459576401 306720966 466780578 481053092 593331963 403633046 838370462 442098098 984122173 137189040 175702083 909256513 7583933 605493256 43542247 624327993 295922255 13211597 424960168 808291935 629025582 59422630 693881520 141278352 24200255 688858615 537781361 7805442 287128914 268791067 258574057 909608072 233028706 909000872 133231069 554382541 122359506 981771952 404481310 729804181 255738031 112588540 249130953 580519169 903183858 64433745 53538176 44042185 78946749 192983468 334498740 928854657 620017051 743271303 735406812 821696726 771506370 381248276 844099004 268695760 615555409 96671102 468523169 341887504 675692436 466741037 820482721 852403472 298408253 604217088 796027102 679208039 964590250 747317138 861555137 169383428 141991460 68936823 337681472 244007536 783115035 257066365 254738202 518035982 436273516 151996398 504539159 618844764 539158685 633559498 51120458 757239601 231687965 222966543 355331665 313417727 537381766 83108595 713378193 9384719 69131229 228774693 109603708 673495753 293385934 670649105 475669964 328945899 183079666 422978331 316082375 524182479 672031754 789808608 759660154 225280935 671508546 185830266 898664448 555651522 348476273 582457530 83539642 591678918 893832277 743699566 429143958 954175733 749319129 900791962 307822667 173784938 751656017 426191808 720341656 556153179 558533306 614800410 949069194 369477718 458032124 437284060 850344628 387353734 470180905 455078772 850708342 136050156 249121213 536504524 107206200 700484520 20351198 808701060 871382957 441482543 167809690 927866938 257455123 331941780 108838957 615598275 743737455 218473153 970448442 477003121 999001043 181369020 572883983 331999565 287927450 295740645 153157859 334752859 953248168 568193844 443623705 455255770 912166828 442805629 284364157 567561859 964701791 606459053 491533955 827682759 135428547 825223179 373463436 914922260 764213606 522131578 983263266 524729358 993132447 788879795 178056504 610932439 75351757 163478925 542266477 868627273 529680541 232870199 157742407 47593528 785457474 681969273 711988858 592412850 27372732 38764793 307212065 804527424 737015828 890155377 697095681 471374116 564339355 434270459 520210634 797327771 818074928 210047559 889984343 482144026 797990265 705822945 709645546 374673043 782519078 334044782 851164531 884000942 96366386 543458796 752938696 508335890 476603683 293447927 355463659 16182683 985994823 975945472 715150409 490947491 652712183 716050070 111704823 474449211 931133910 966442655 440882165 552065648 606752528 900730268 814308716 830162568 580760989 480144106 30549233 759136580 932790909 981131262 722962114 287198238 204042235 620641702 584051973 210679178 146026731 649893196 25584397 438517302 841053677 295208499 585292439 158327883 8268458 956950202 987994886 884782251 722494228 416628118 427102380 828908595 350980775 496288537 43904003 111762168 551504300 553054831 322060525 918620043 426702451 975333597 55262713 841084983 703698581 870433027 214817695 499817023 416906809 804131353 633810304 53070626 269846350 521893170 151201704 561425881 260829899 983869053 610338254 469016085 265847796 572472961 92195472 58854787 91876757 69392222 561891002 565822729 354229062 591053328 89407101 997882376 92484775 344624557 618168505 921701274 954148515 955614371 704617013 161838546 66791086 740355581 55637731 686760704 30864393 460528797 90531615 94612716 313979130 332108928 996067054 333741081 251794966 207293951 256410433 678757121 553960313 934953738 350034737 614431068 761024522 204053100 801702210 146964826 146536122 350741260 358343842 711537894 116756931 668177703 202604648 480024291 832859626 399350681 467787479 932093040 166757822 11730707 821292698 122234918 540514009 701818211 30316039 795288918 13879580 892507825 746629726 40374093 659322868 452173502 575674121 930671761 817270169 181620772 139495644 595853346 743108171 671222170 269255507 395281084 736308117 64074031 229271000 654989329 653960076 427303308 954476284 654628369 625992207 355202869 587848634 981965860 875611654 554098118 55090873 799267948 356594852 802253111 296590216 281352966 366613670 95535385 559342562 367696199 658329491 530105816 151670506 712161536 17247484 723379705 730567277 8480699 366033339 173176667 580533284 608874493 672998197 465181815 944706289 205073028 112166554 230859170 371151902 92301193 158607393 921213512 890586275 506000893 910402126 653788208 481338975 138697420 951179566 411800252 878164827 780433951 801557399 567487015 313401100 754532499 402712170 195464390 57119632 890671748 613590995 607293002 275986669 358107975 629401733 368550138 167663702 130649705 941958911 807343867 63544679 986856691 600893131 898078601 116416358 835635367 75520956 416529981 376646786 505268545 310535981 320511558 375587093 723645368 752312646 284022194 831219428 850554748 148176440 155437220 740481627 384985527 179105149 647121564 955087315 30537358 284447003 288525749 139649229 314199135 812417759 160277471 709292853 921487106 670249380 700053547 47810722 980592906 99370123 571452925 287301522 714256131 953372226 888174169 240740016 938062515 734583360 599574296 386490896 776457306 152846340 366180401 56609391 416980468 694983258 461972723 170011765 131310707 442001048 358078279 809513460 906023175 42679770 314554096 754635047 621081176 133548108 618655436 387060214 655026119 653154910 247582737 875265838 730736307 602935310 202811282 648706507 250085296 162386468 158494458 216242736 222528462 849867119 870545422 29820267 133315034 177852938 299087341 29425779 835461014 713184411 493150288 509812587 846758656 353997712 735457996 858736350 318654355 329375842 578225164 562396930 808911230 670760147 88585497 711934200 976436464 176311345 431127188 741288967 170074958 94940818 781813240 790429414 22726264 506164248 560927962 877837552 384995337 131647533 750738986 955569007 284599446 914107077 653760370 660922579 251395308 211560352 219644435 992420858 830935891 425936774 514574476 850443624 170899151 589767051 293678004 619231373 404621403 803079754 44450813 370391812 478940206 946614572 456988849 852911055 66451191 192396192 698858806 64569502 110930723 439048290 327324748 859279623 382888979 582945462 853545802 548417996 567206248 700103595 81565030 890960410 662918713 61631833 623814892 258399942 825535577 263334949 326256259 534092176 996819347 812946426 735879278 996762209 872440047 295744400 136212934 942883470 340823020 644177319 625970114 721120276 843843014 256148041 349733104 810533595 166726319 74493453 574441595 929343478 816374551 648270672 934555493 988068063 31546085 631514491 890061772 259707068 68334781 967189058 527350822 853392799 887349050 504552673 940502662 199343551 414529074 93453150 827014103 13054657 472238071 935489996 294197533 432154355 953802898 298075524 12267193 115626637 113142536 398499947 624906659 179054832 634992790 530516528 972844207 215554536 144038390 622425484 784178635 567093996 219288218 823929218 390156092 162930266 526734829 914895518 71548646 506299581 81558167 561273912 893952899 705748489 942422967 995299248 878903784 635133147 791455272 489220016 370595909 387301819 425199038 645271407 76820835 795128923 131917448 958670826 682663909 956836566 483475469 822694187 168475017 169301748 838362769 175714180 499265126 793788258 153101391 396284114 539477550 477047036 104354493 718968764 479523691 317948933 37111757 86852850 789122242 564640107 495196968 858305136 461096501 694920197 673699187 405726394 606011994 229722582 905994123 164053024 35455399 128824137 581474762 517254137 374704040 551785588 413300034 458485737 177673796 102907479 703484158 980899612 228934397 792028700 188014917 944322954 176065070 762921558 157682904 403309875 655414861 194170436 996642353 652085602 494968104 785017612 516817604 898197996 693308201 768216834 242741824 160109167 442046100 890102496 463240652 876527509 968741061 513720077 878433612 608611920 313863029 233354457 602099867 399516445 687101940 709480380 525947087 37491523 518897261 566069916 761484666 69258771 251310886 239134981 635948516 361402407 651794879 124728944 918875732 643605668 157670512 484138366 58589510 940170874 536474445 488790332 269813428 286153632 408791939 491062879 289617744 336565338 549096602 403109511 73370565 266879093 288430002 165815165 147962 652071559 443032264 56067190 944405584 988316465 606874096 714877775 848279777 123754590 41889945 512761296 368841409 544876163 549097678 381958892 34362687 843995103 408633457 384620029 192951074 107595194 700178560 540558345 616237549 338701223 762907730 249312001 131837725 691931331 765337304 753721087 657210727 731923701 719891934 979199877 875551229 892162094 186630985 501061826 49179079 31585192 818859608 377182413 752236716 698987817 909009636 351330538 21485768 217488959 992272545 240446658 996522933 521046914 550157917 636508076 481594820 537864150 560569150 427011561 636437314 634710440 403752966 121345505 86899126 625502766 742057040 516722536 122437919 504877738 37096913 504617213 762797367 142043045 148039577 238224135 239339188 899327541 516798290 132961560 598404740 759734585 379667581 313002284 466831118 356017817 369575353 307906792 410105717 496809608 294354430 869127389 163742421 24484548 434686427 605784515 339919238 956778450 890009277 543295936 790016086 913242692 433448490 828304289 847354321 399237108 347611903 405525021 807962490 232534856 741275319 242039575 503082768 798941806 261523109 56113882 287650252 603941535 115460918 362533724 806234527 548917597 47618865 653873533 500856438 198673334 539732216 760101959 602147192 268562304 859433415 232703021 192731715 702521501 320443633 73680974 47675956 394287158 169263912 124192176 694411678 613930498 548674996 292272263 538550031 574015869 611104696 164589933 7494800 99701555 904391537 89989289 9085667 176283124 33054584 279714154 398352581 194762271 22167549 260011787 728628779 733208281 51993099 999545422 731654022 537439572 813183689 566085283 722672385 355160587 661727413 332982112 464089023 915616258 737874152 268437767 417038111 727969800 524482646 294109829 683642362 311953397 471315213 906019439 646071777 521942510 319394674 79860804 953273953 167448990 129642377 941064624 942728256 357187453 984659500 477434308 805084863 905161226 143682128 695193153 889080023 626885906 798305349 662192844 737901694 701287656 923917556 821872696 235062241 754231212 783473952 220894657 774152873 390346375 491778727 192868429 941735736 185493739 16727489 516742571 821779434 442009556 279436861 897935829 649211991 922805003 630846152 638982703 357647501 386302047 476108839 100150983 800769623 930063596 477283449 745560981 111551098 569534038 406035064 126864826 303312884 374270476 173668022 680527554 441802558 260536967 631372514 677188579 379256713 469795466 426136834 155625790 877596162 458181729 294606008 584809755 86768911 31048484 593449088 433906990 973710736 590512626 85128429 49983446 558389281 676206392 607037937 23288666 938359892 703577066 103785491 389081900 544230394 991371974 611009976 817386792 210567768 78530454 947725404 721195731 681233267 612946027 802080216 551964317 771533127 533768932 134885787 445923617 202032393 751283047 113423859 535038050 655987818 909791844 805448003 31326990 366524628 740936599 830994764 159314876 694845100 219775812 668140646 699018799 339152016 537006459 769789637 413129362 940766873 213541715 738305974 568091323 261880215 418754608 703672545 602013034 58677849 690479870 401511814 749537160 678341348 815416181 989967810 664200043 270347193 8674133 727854537 894808590 663300369 156320169 821159211 612572763 317261346 276487686 278363152 838339170 58374233 942745034 302548606 275185825 834671262 814489439 35741071 147904315 981448341 577525111 928715965 523501891 563044825 443825743 785894680 925082608 9899329 560986862 668864140 935620584 69294109 419447908 30275358 40178295 206023032 300221709 269489709 154363094 985591125 64408525 565003698 503538022 695358962 265715540 570430850 45454580 424383754 111858009 37200008 969267189 767679244 39150560 545848334 82799560 577760871 245187702 937122546 568651769 314582208 239742321 138630386 662604153 447631927 609540914 381793763 555223529 856174248 554679652 62496499 714929870 362245349 655797308 666415084 594584283 125862398 982220728 838921842 40971564 749101179 210689250 543293761 530188423 279160733 552109836 481705329 408588955 414787747 982839060 155962804 145089346 505939968 576955039 194898836 596455360 885733031 771603806 899418807 339963395 677790018 169481806 361420317 24283618 736478067 256711921 848430430 552995424 284694299 481150616 873586157 383865065 650696593 71936922 681740377 660631185 769848552 171309211 969226633 409377113 194356012 422439368 745418749 656403307 257186722 709784087 236462866 406485595 501297165 808869002 772573243 953541222 85137893 894247274 568409162 593524147 473768351 89305485 283299495 448836502 647578602 374102929 643714709 834560970 834310382 24733985 466567281 313911220 808841100 940729901 340980468 99597733 70280354 681763379 804833390 646289942 47627334 18278778 521439755 827871978 104774920 172615763 550161679 712125617 209770290 582365785 172667931 34269153 788513289 903698351 456426087 573024797 447762699 985849926 785574664 811844464 462732592 721453846 189218857 646007696 229187114 476517729 770863699 522769693 838838183 716317173 747444647 310309088 113776779 794312808 568247583 58265359 484711481 685049436 8125395 331900037 922492361 230199482 957442608 146857484 35449168 745862392 789468992 675645332 680096029 419132501 429506534 577451898 950579447 289553177 518052384 570672580 765633890 929602008 737128005 115943266 575723737 195914925 597878343 489797996 621496082 323186304 906119408 194524263 411269695 576150595 603509030 516796290 733930569 987254830 900329768 764255187 213670421 968363272 467755984 953324956 81350848 935233887 845988816 665511818 504515812 499573963 735869687 572326897 762627539 857660209 332240235 297288211 256910040 150515196 644450542 912274776 673531003 138661731 166116892 339560597 593534907 330588072 901137832 959649095 15884627 86378581 867833764 454227158 747883255 119435134 716517047 853314516 817559190 172349699 235144550 362790205 699971991 524176332 283437389 818033079 518667293 718992653 429367909 57790673 318848581 239607682 28548158 504353349 975999333 969952945 675809091 98639671 598752076 147504172 58496506 997646197 536199558 442290894 338886723 636436151 272395927 980016123 111352470 400199134 640369981 395933410 691807047 934228534 644372399 379333564 613246403 886105269 174861026 791868684 926782418 757263163 554783680 456728286 473685717 13659602 796288625 746915849 849086214 532649966 98505620 691844463 755795644 949053356 218904964 924130106 573421990 124260115 282144149 385106462 191542797 170125655 921253717 510903963 189138452 805276179 946662349 566693434 909068537 88763020 528023744 775281869 187537491 191564019 415315944 589192113 970469203 970359712 773194302 561280268 392547333 305275993 819655984 882181905 207587470 460960651 686551530 789246776 551094381 51544973 12264592 777749896 859321787 65168866 512206207 976420816 734929005 198179957 70882961 41510119 206130574 840317148 328612439 460710385 425263752 906306454 90543967 621683098 431157849 892918607 194705773 420623194 878128863 877075481 111780035 604456113 414092815 895648435 708127579 277009002 910343479 847148995 878438953 669967321 951076929 341718813 789677147 563727391 443133169 585250043 956570778 496840546 989480483 621658436 979412553 9352215 267297040 507144903 689571522 943882298 322727559 108236926 808830622 783651986 358871606 437451982 53055723 595380719 268400096 561662147 254575733 267587693 870611621 865154902 96831231 548124849 498862655 174165672 187234953 539600168 497563201 556919110 589792393 781391692 144903512 10613604 537819443 101667552 782307979 831205412 455002804 973776689 469602429 721120974 196963952 103496277 260550311 836836375 892880457 9385069 737816224 401237852 419972568 364841188 899720535 452738021 709161395 540029871 984859220 191195172 33332904 21591180 209182460 128210677 813890302 620962885 756672460 958656734 113465272 826322924 221726107 240869710 430022610 700857886 508422362 490839007 486869892 325400642 537734356 494625685 891341180 973982665 448847600 505733150 659860006 358729069 441977324 931765009 346293477 404585075 703741217 6401841 960524120 96019947 565900739 456369065 173710488 917362156 971918368 87679824 5247606 418982106 431141598 314410980 821195455 854243490 247637567 297202000 114342009 469866490 287705437 3325671 414965029 575130019 402066288 189084328 568774141 530175400 529131781 191139450 355670836 561568414 881636166 50237807 456612155 849695972 811332406 360268546 989616120 378784226 442475251 444486234 584269838 826842955 643629812 573877127 148599833 205068381 249357643 112703170 35055088 62628125 34487010 150014382 980092388 137142684 576605887 596561051 20733949 577707831 400848705 330570687 895955777 990222800 712713570 924589693 456680687 663947032 535638517 502268576 226636221 391406023 579801318 549975454 931999519 38936287 136479359 133617111 888464513 109340398 706645151 531796436 104712841 347579210 542146050 236128650 320074840 278030164 63444862 774390679 973063367 2087864 373041985 502630529 173604780 48354729 2620950 731338236 77811988 925081127 662776991 291395106 875430024 222309690 901240473 161988282 500477002 416633653 223900701 682528371 64314518 419027958 584487130 636155431 817636579 709284386 869312350 178694683 448163106 123954795 576578636 446398779 882332411 287314123 629864357 21634656 584889620 47403976 956733953 754974091 350382667 609549232 376605652 275877160 599457017 954275803 465498795 472661326 526235695 17853934 241793134 126490876 784986361 826284820 359328926 246374235 593589151 614972228 704698261 10669824 508751585 600855168 36218314 807427880 983701816 325855761 777559308 141748475 301599770 664422350 445092292 315634891 241657140 585915220 370028085 70361940 653975471 727184204 653892541 810333947 938096493 249718953 657124883 415666449 915541066 165088233 541558408 935396111 328276829 517088337 751916360 630786521 704146998 154553652 952881304 225483005 920558112 782470442 549905431 855771122 519944030 43880282 220364287 395301723 351752303 493412530 324812898 363307076 978608971 480067371 613289071 623961953 534799525 495191816 982724012 699359827 961393960 905892885 637771579 611265764 543166652 942085865 739219735 680887879 685219265 352343078 13535574 898277979 98353232 942373814 259706726 225585383 934853503 300709901 918627665 111582941 28295323 982975851 574637819 238377880 394809964 294872857 833451872 430350879 387149942 974154408 757936600 290190434 664732724 456582967 743232853 409501817 829241949 91919020 710995873 888651754 330000417 709974775 148948643 929228002 932726890 965917524 606598552 725754232 651053341 913246087 884524123 398070510 353522776 834345759 947592863 406830833 597570995 955701941 838320433 827122390 961489793 473160492 863759160 523300061 710351374 238708976 272371063 302142320 700279008 496474937 812515719 529655906 333719543 73526086 869986591 428020273 755690254 811253668 65340238 413616454 448943834 78099815 503225788 449571121 389166664 75909997 584925679 233257455 379181504 54024096 372051585 404616486 730265702 534552114 152110188 502311781 216694101 236025567 771712064 876458342 120888548 560907312 274476905 773047630 59637219 507326645 24999787 536965609 949336284 425815112 602556711 138270192 454864724 309261646 993890326 20949828 238801673 101122038 625584010 565366834 344114483 797760889 167806961 524828846 47914948 143350106 529192979 879523738 929262250 588427430 308025937 652111870 900086026 474557746 211995622 52544591 174202500 914373857 722223655 813665706 788825715 573396701 420936644 587218711 237718315 828306139 357855238 935558856 586125115 90774106 521571857 373697881 734701227 981753313 42730017 418387215 338631228 72071749 519310030 231652635 514533548 136654306 491940938 757507798 939361777 195535327 276592031 38257412 441468027 980678509 344541171 350688531 233748596 425223942 615035845 870088282 650751233 687972783 88694319 493974364 887532415 766731832 477165603 871164164 495145160 475585144 677344688 391696873 549314670 430748819 5877053 69537673 870040572 745427510 56436938 444076431 899444282 581616599 686951731 199408910 631439975 123719159 684824430 532969925 258683262 842221665 716091337 372668250 719755635 804205418 259543855 837887137 692937333 375589169 862112866 623769813 621674028 853960926 259729727 74346203 564588281 478229988 957716991 7721603 850129722 736755520 540370034 309697480 774149765 834531513 333086019 931992076 15693033 991391264 132214585 259850591 415047730 647081615 365080177 507627447 584953124 154228139 240623526 800604215 161867453 740315876 416819564 829621354 407108980 493978802 355981678 876097413 443794558 207529943 593010101 78845866 86207237 571235489 391443425 274948386 643690865 422441510 921505391 240420256 943162529 731722119 76137459 576768386 400206640 375275311 132985949 104328976 581801650 588865555 553420854 11303357 779353846 330457842 42542561 295783779 764723523 875210132 263254748 593210249 349192092 151926797 574332158 626407070 391237630 908883960 680544184 40557372 747396511 917035453 449595222 273677160 2448430 290176461 565846589 810749902 583991575 787929058 100533804 363449607 395820222 644587074 308240765 942659284 765146048 252846331 765769314 164948321 642070583 157013797 258589738 617093765 885313780 706156069 79280763 643185918 774854853 981228262 295778455 532395959 703505326 78487327 779616409 268862724 195759665 620692626 54528183 494124514 403143816 388807752 1976959 31594297 84717031 928506327 957534747 283772187 596996029 525701278 365930895 276060676 583389425 276972293 721071607 629434905 14292774 468282816 973739212 862634603 321123833 399279370 144381213 191933491 408108607 794913772 958132952 265638933 519635274 566830453 748880896 786631519 329599523 12438016 78024693 725377864 992406734 371303027 873469617 576155187 628295051 312407420 333689351 357473515 651340816 156484308 254949092 469254631 659375826 575891581 342209168 788095621 771811899 879269382 156405227 325646416 498010610 249358275 434107058 182263355 768673304 81159191 379514041 363049957 618578567 851259563 117267247 303164116 159429651 245019574 129809375 558110140 684346314 189525301 643188843 365800375 32276533 463630385 142090641 614342541 872353943 622897150 761176680 100930795 130957354 861031287 833498529 154665389 653644647 173730885 710884552 709083925 682018620 568371223 75004801 463584019 425039445 959462377 667268813 830982525 881063509 541692223 465515589 566686037 899720987 262523752 326570843 28195336 496008704 22668477 293586589 514797739 859877653 162733025 881345267 358688574 159336039 275845888 281146078 151448042 911504189 5315345 789281209 576425028 762221909 20384022 637945081 13262474 841530412 800096601 261066606 614178018 268171829 878995119 355504258 641247391 806622750 616605622 986589046 324857725 329118224 333832727 454619305 882610914 424080621 393392582 54648018 586800925 837638546 571941439 196952643 959197865 64901652 307707337 442574374 278824296 42474244 3548340 150324673 306627561 782874797 514880668 58731443 65484964 153070674 546313637 715497270 46623034 532668275 454214590 665405789 26106807 701400326 546470368 542096981 982342610 314674367 952639310 712577701 809752105 477164618 190318805 638729327 135656839 675339917 829478922 188585647 938811424 388520169 209907856 543859320 443876049 902831736 241801041 369520188 146056290 562944333 742946242 847069954 287869637 528827321 224600353 528724399 989059158 38678402 712425912 769756736 624164634 896822571 458509849 902134540 240174594 57291056 174980705 225717251 824185383 60260168 232954743 215545331 432992781 930321827 297609803 238445503 303050978 747455532 649075481 94052264 245520829 924512198 551942309 477319814 108943073 390209424 735032191 387717901 119764729 654776867 997726014 65565451 620164699 568692944 653651398 232316582 23711815 26202852 234858628 401025439 575062567 639230693 31686062 375949459 162506446 565615571 374448005 473940534 6994875 617596522 714718612 478231704 553036373 361408093 720857072 406001250 615095597 286091162 721241719 404935703 196621121 805333898 404707859 635440981 526789429 218650190 504947190 125577235 712604313 38702597 573761245 860105187 662919976 84174339 465137231 83871534 530493445 438957593 413212125 772580988 525326077 269198289 182997601 581716907 793696201 743011761 809366337 410447157 454361931 956739189 305504170 62516077 52228813 434186326 245599703 978939327 979958599 588648007 563054153 251135476 6719640 291829044 495607566 63033197 706398409 641523523 493466364 374276710 529738063 428025108 160292084 774151986 394249800 217563395 308666657 885932418 162336186 665086562 312370232 746040224 323728600 593352897 245820600 313489326 621796670 785417512 335652905 184301801 15459378 27075417 903933534 45107433 419744227 997139216 380285620 99344608 332449451 493129028 87482194 709269208 937155151 653474149 644351081 277729016 201862971 509886109 782166900 648126653 29129159 405287185 504423030 619160642 647230839 290962207 463975232 480014202 70837300 676479136 94247594 555851122 296426902 579843108 225120726 479387026 180567579 625262650 130924914 874536666 838101614 12957863 10483956 859110695 338676387 485199276 180513245 532168813 134188407 49033026 567184633 270835707 805675410 181509214 453696923 394263484 965450438 380545071 105124579 60072818 984963918 556522845 433333497 912871419 86870802 626558282 820327504 976846990 812928735 387907410 340101350 321769468 985743281 896232460 648511872 442053105 228154347 262872712 778934512 997879858 816385179 337523088 886789457 922355677 245736632 684460777 524063046 993837742 612926565 500412561 769314112 246453814 913743405 17182720 149670071 812143908 77307974 599136104 146715501 3295870 583738320 788745975 825914544 395763942 409771541 205447186 551379607 486355927 343718344 480499865 778774849 267097830 442625096 717022247 520698907 969404163 29229788 855970641 887925528 963958199 138465781 328667876 699036152 11912294 478466673 373124904 86460292 776850828 933227732 727867681 944036557 443272705 975978638 562115018 538556530 631370295 913004858 714707802 490175448 763956600 450690010 796720769 362143345 933289770 54549022 9961897 799768312 612588556 804077980 472707127 349563057 866026872 186455830 549217224 216908971 439178913 991249849 436985206 703886591 172243412 144758362 931548947 947816464 676564408 896218296 573028459 655511498 898918031 957617855 450099331 749955812 666969973 340109249 489411806 405530144 19337629 121058748 460367540 376518536 338716569 662570648 886895674 131155888 686933137 450690920 961222623 465578744 861166984 771226534 575441290 25544393 937935003 366710392 808874975 129685716 531064387 436387311 807777657 952349784 201332368 900615749 406500398 27779419 86171245 640202524 755749456 190876141 348072161 198286019 708788200 798949226 866227785 196085106 424963579 890992566 872630177 317137546 238950343 811439744 768045498 393433559 577474052 597269121 803658370 487962320 55305764 849181372 217898561 393648595 696880533 405835709 370805464 810548587 729032955 758472412 337136385 39900044 47881080 25235321 690485140 118833874 763937254 432383039 593671358 569598920 665404442 828498019 953495369 197013020 512227360 689157347 579490264 379737581 434987395 52057032 91534889 593003776 452887171 510235494 52514387 487360515 710612318 796491161 191692295 918185938 643570570 659016456 390111697 614990512 616055542 600457827 690113622 482487691 107850062 361317798 182587797 911228730 717119798 254031190 781809704 354625472 67611019 611206080 106360449 82777480 592582311 120792638 200505903 25363112 546752924 350293107 137702168 80591904 871547765 895545740 912107710 826794266 675778682 559962495 887218557 831919145 896194410 19972173 667397064 463943819 5354688 803362625 749363057 648638313 122549232 591551535 243663583 880027924 17650344 213148856 171633239 748612679 153372177 617846147 276114229 43572073 997629454 989166979 341307698 764287433 192884346 227854645 964221341 740079842 707332203 29585888 988550820 232107415 669250419 491026132 607259274 353161589 239014107 251897517 722675440 775127541 448234727 611339920 103626254 930756536 353442327 428048234 511585784 162117579 705820769 37902646 472203739 445975267 167273594 894635573 323861822 603260064 46446348 824615476 30458180 848502475 790848510 704170443 484962790 768308889 752097713 776530331 3315515 345836519 203396671 35919757 631376562 171044477 604108476 492850199 560950356 585553742 944191607 162283383 139353092 784878004 260883511 476102391 615495872 584859829 258036607 683712041 448576479 39357506 609359820 97685547 972215378 231438964 877312979 394464482 428966373 474686160 851311814 347139648 68186236 545718146 28309390 487624575 855057752 917255842 614612495 240997988 848915026 561629043 519790696 650516607 749499164 498428321 419068978 168450664 613199493 593936000 996144574 130795265 588501939 348136018 802342233 374838968 39713640 327782783 588902538 500250819 8971071 663147483 84801872 735254115 260962541 963505125 556396901 952166947 39456130 495368708 284854143 748326169 545704103 772728778 793829516 962252321 712112608 512637747 324835571 629417766 238777801 216639460 940520407 200264795 940939610 981532270 578416725 832762747 392221989 430987657 357162690 44567310 987575444 825193307 746785775 711134117 374070061 905194673 838849639 414948635 382795728 259295810 945432493 667987411 163272180 801070577 769695617 261220350 312638703 11104777 744848153 827405524 151267117 956857472 701838953 53945815 239459702 433029174 503036765 687705621 624650794 981371445 614248220 280129381 510349957 686861552 63451461 474421670 598768605 873134981 535938866 409152517 658383585 664029949 999662905 373548085 913410265 675132297 894395879 815324086 48406762 468922820 230796613 964182288 343213905 977207285 188151317 407224087 903131301 938492747 470121236 171336742 917561110 451710241 867902519 430156646 455323570 228617785 431195119 172604422 958883741 614285315 233541735 715131009 596534101 519749589 909210818 252647389 541938166 842716209 656678495 192826088 932413041 453022724 701041687 17552251 375946964 631274979 702749563 267836856 754188679 310525773 568928792 413690702 528426635 359570925 951377076 457275057 742896314 700450519 252049552 999213156 552342796 660843976 520156325 299639856 843967438 292828777 818823913 425993836 264028138 839597962 183991689 10400565 956980771 61128808 158037038 989534644 422654039 381408745 462983994 300339549 53602493 23076828 435149578 321183532 813674279 515589179 569414451 844193511 322641983 179795562 707697094 971168864 548547786 285184631 883637389 942237874 222284010 849775194 284589134 390151553 14554965 401856820 365083141 428119100 370362529 357158033 856076843 287306588 71814266 875770279 696554483 326348708 798203623 187185303 24455817 937339744 854693258 889891753 376650323 97078696 447136478 294609553 897329714 620613532 189103993 20969390 444975295 334740903 527142729 731946823 165079440 811031741 269007577 603268814 97831538 774053278 766419082 548280351 528885422 990144019 265653724 620801727 595314245 740909102 54167204 461813534 888345398 845285772 527257173 411831255 163172021 84466835 137295673 508988653 5225075 598480310 698647479 204186894 736988122 943910062 571535244 204181201 256287055 651992512 924376851 8240121 707499376 655488251 821062271 843253937 220288086 335738744 178072862 730238159 619983058 672647322 322606229 832467219 910101936 762506062 15380520 697276518 668765432 802534217 196567536 586605853 773423914 853144142 378897444 313710134 342517375 445722983 6738515 218042520 656033325 524193321 701784230 506015316 76520865 439874546 995902240 234416103 551650755 340785452 497710303 229618551 166448183 330162825 565351770 799605268 199125657 536216646 882314146 312572662 301988797 777206634 248949155 84751555 55337718 689179398 688741730 278305479 155421006 318015860 53366334 465655867 398215880 391005593 867015216 487644544 794080675 809178660 93247757 592307043 489353111 181924559 539899328 707455577 713270039 372862875 594580370 490705345 588345486 145241109 41848676 862255911 75610020 885849237 227195121 923145084 600648825 539777915 485086735 350705760 679432934 118919282 823451628 915633499 813385664 724255151 426985554 644860701 464197654 915055409 464029925 899835587 874123888 945051136 178345057 29125906 963505680 873581423 42174942 261684667 511294514 27941979 465872910 627747992 315069261 136369771 611724923 184925931 146952272 728965968 995309259 583877283 38557672 294700548 103398397 640411543 701028279 451699724 828500395 648176330 297068443 427549880 146644808 337179048 48494831 605916256 844928353 730663237 703339458 248536486 835897566 42994594 401679395 979475640 823119423 803240681 396791639 676242060 146082016 804396206 288941854 925021219 222845495 477842221 270724851 692228552 727964435 69192336 336494922 144083536 937260764 540900392 300479698 142444634 939376855 982433713 765389235 135341454 575795041 114161296 50652878 400504287 635235121 292428054 329648385 497113291 939137176 168349115 8993890 248089239 125482177 853325413 10929537 811625365 70959347 510992801 216993448 898071903 60028364 406789094 393438492 72507931 598862981 937193687 784606299 52623286 20923442 118493311 344572253 732677931 793700097 103532692 994654164 672810427 133795191 162918326 91397486 226693172 550955448 322422958 630360847 532018221 359858366 860736946 529738266 65758533 928886686 280377757 618081703 805123688 969502920 756340025 497816523 585079052 619378501 841281142 930417365 246552173 857191929 151912369 487915660 673644247 817568992 613104880 385699188 581752538 975193170 928609570 335270920 862545045 952883776 736452962 556823038 832219373 959019894 298596914 475834760 658636500 704539353 577829058 903469199 394836612 687836328 493030952 52484600 352365251 83286461 977860774 648120544 164718111 359858379 107118313 503564769 224784433 895440287 436450629 938259021 944368347 662638176 768883452 834181999 788054411 952819408 605869430 665476559 24231544 612438922 900914568 905480300 733502945 379837252 485879471 413636097 715486547 130780684 883420243 589555778 464207585 657573517 821997318 943924510 670514795 273959241 366979012 474849276 510820570 796053469 397524275 15465728 240642911 909806658 758071010 258067524 633991353 65119239 171122827 38759713 798404718 619735962 566960978 748278118 619951118 362413438 222119685 222236829 191144564 92982676 918867803 916254538 532898566 770534484 202724151 544454189 10139890 289068562 661366245 850146684 988233329 123135035 478040153 77476396 666781702 419446935 938354292 584068391 984531901 631646342 596775488 47373973 939722862 402235973 202587441 32264981 707883257 399111208 215600995 850431234 757148040 415803871 92954848 24139184 441618642 352230835 523283161 341020845 970026836 633052103 280986346 838290691 209499799 337453913 3939928 199604338 178416751 171055104 11565396 850841272 406590520 815257837 760826422 978293450 28713497 585354284 744634564 180142106 725987394 205401057 322780011 910762448 242061359 608479117 940631682 125062675 146689508 546806601 699543948 86272831 229551920 209537799 159267443 52594478 79214316 602363350 36926159 985795697 293281339 159629596 716779295 685410710 417737161 535777243 462729229 876878433 298468622 844969966 855453100 816836884 386186634 794901323 525555386 6562217 340667400 282351424 756958688 488159508 717145053 352844727 618791663 623265411 537980967 73626228 880027682 536796831 285768464 191000659 463086944 356806859 935785226 868421260 341557624 579698785 262671889 908878833 471465828 648147962 495774446 364546092 506435465 280934052 709497457 63673091 906405107 900306219 430027444 432694166 831562907 140236114 804426844 435785117 420495010 820659481 863273432 572306604 71585173 520484854 723717282 181399920 836604328 851972126 749856891 775918320 773762045 129874363 567412912 160285646 794502620 139700788 683972441 215018374 291023866 603754858 215291542 800739756 501371316 446090999 832234962 2286895 322327122 40587630 337346818 826959770 191382598 982346656 130410980 143687247 720004716 340419027 770511170 422814156 495559498 230047498 688401454 639003367 419030607 337803842 978011461 844934675 436989205 760687024 607478254 985692315 797560480 521917957 706860442 462728164 276770974 427690924 345232131 574876333 737432230 876971528 750975343 813518415 726252411 975253688 956303339 42141182 676732488 411156181 173087378 611453448 277672420 624180784 16932805 689975058 675527181 970703510 237675889 356314464 15322798 422450445 988994126 927843340 833490714 720573718 432124701 350633547 179305296 434615787 891595239 896642733 580289335 858911680 210600258 269507675 422432225 68681987 6604172 901248089 943290057 820595101 682766895 265158851 943057686 710915632 79067870 330456593 645255384 274229080 720865492 271339605 252191816 873144045 374069273 587187321 455864585 134840125 47494334 957892995 701131627 887501395 2722845 297974226 456847780 563312949 760847900 183112800 447708951 671561503 849547880 611628543 385071503 615081674 889945532 851040926 949530242 797445033 847230745 21466755 361222223 8608040 13803789 195258769 985209730 978461677 948270830 125776513 867501069 887592729 986999838 767897129 938324622 540185989 622569286 461012666 143463310 595411719 16126876 959184123 527155389 336529324 694278175 887718801 247807033 206867709 761148119 406507577 277074885 850596156 993591320 607112969 451370516 837321894 249188285 31281076 734947325 384292528 793383022 395347653 907195845 511886667 657922268 787137760 34757723 932555809 579096322 199592966 126045844 718746583 2798435 654457039 165219445 931416907 236333136 333691823 409394279 732204758 117814049 170291763 671896194 726362505 538612088 699013699 131713476 657519729 7964291 617062239 624761689 328708564 391468089 23816676 456053202 656977010 898729113 743061062 34401903 630725831 862022896 289986645 309762648 717752389 751024401 721843322 694446557 391223964 943045788 904857848 560657339 77290228 453322809 669964077 73693271 667632943 6272732 418408656 680674050 222729513 351602944 375843634 320550197 361038329 986439662 892599935 548440532 675684143 383126261 212354812 851944045 252430358 16769201 152998472 983381623 102669553 71480389 569171100 973091477 250030143 269244578 101554189 758237651 338722808 103941568 474150855 471418597 41631951 951426530 304171345 324585836 918668144 295666900 539040205 873825074 535367105 626157870 175727414 475888490 523019810 952284559 933213601 123512307 630583470 222822372 229522558 106038420 427325562 941041312 624736727 640003135 332030675 851589635 468889485 698676815 334762113 742330710 456083104 612649419 594581768 97769515 520031845 215421603 32306659 129591198 588957647 600529135 425264073 398293400 18807464 375827509 59196394 446346760 992304854 68288674 162189617 739580970 588144025 510127693 907498881 596236226 572524745 186970744 309741304 791989855 300801049 995855056 274206001 58658970 226813529 173962922 750524539 62321494 366766765 746761798 222989093 209250047 793737176 945131534 28407476 895358669 692552054 502486485 59518248 227000320 317589307 187917849 788202045 99132707 188542518 988686146 133769893 482575178 511083538 686871779 815710544 348549973 463319121 845624566 215749797 190911277 121053585 778011426 454345672 842522372 239576777 98796022 953224148 348973207 473902218 513772588 123660576 882411629 924873791 971464681 956896380 479987990 717117295 804599801 678137970 151757422 22609144 370315029 997588615 385594585 798194771 966120222 488297593 598240902 240902869 795339872 346313088 190803631 200810217 637160658 828760974 903397077 851401560 610710867 13963921 979809285 618576515 683242220 183161262 293342743 310900645 31316497 34554501 284752619 248399379 517431777 398023793 158602668 312392829 760139108 677318599 134857743 272946732 555546314 95367955 193303954 759363140 771175088 830949472 348716735 2674945 431433051 862391918 861776488 370852603 467970044 980316667 728875754 116699747 224745452 49286397 989643116 503681605 33114607 84257764 957550878 465624518 428278131 904220378 723661948 986034534 783987151 180532484 441606283 76369980 741654406 867574207 488146456 439388478 461622659 730748901 190866686 715237496 383985756 770212104 374078302 545426001 116811666 566680243 989261029 865337548 80766668 849686958 485757963 159976130 240068897 702133560 329519952 502415146 361823820 415714892 744171648 358767698 429009399 68160223 488348653 187992868 767347955 385763101 414676921 269038692 456963195 883559601 432516875 637499887 822312311 664367099 937199446 386507259 111748532 895121241 521148823 810550875 146042670 27898465 692858773 850988474 563060551 982231330 68016929 577794268 260702223 162619752 392230229 884304866 165295484 461897207 148024279 307415428 960694961 242295245 962846740 446863958 136153400 383272290 644097159 380323845 457623625 554196456 770204657 628154521 685900803 100353676 269306016 895351731 831486128 223045045 419958698 370841038 574163971 59929154 96076848 513927039 851832410 445798094 45680286 573942453 808266237 471811821 46855143 924380155 144074847 337831534 941573323 441457588 104208730 343870616 516638482 685269340 555499125 483538287 977902799 67495115 366726687 917119213 128946079 249629554 498290930 925715531 450242538 176305053 586789106 284028727 182426142 839486897 482424526 234933533 354013689 975198061 270076187 245863009 718052797 727082794 823882142 103147424 723436923 688735005 781178496 52935924 642304075 436448913 170145689 71044911 863003023 648774448 832970663 950348572 617306677 86206521 687038357 967116994 103120372 604209608 649688503 572075170 857551499 808526866 723119370 694640374 455869190 508888744 384414838 417910002 341149947 672929201 799057421 673356805 320085959 42037042 315051083 324058902 559351763 261153351 17135957 846871496 398901202 722479208 681710652 157167544 531879426 324863143 561526329 328526780 455095656 141914350 217720304 161775395 884782358 84056387 711901871 550763769 587490663 384570630 981429165 358873409 495365951 921323567 36308813 437765179 812451660 495702162 248236634 942366109 540882761 289601308 111640395 254957532 430436664 388269333 44498814 528697186 819112101 872165725 406549629 923839958 750502375 922296240 516070718 117634393 737741664 704124900 368949596 147745733 379991738 171646248 515400289 754085870 269153833 8517 42354430 800195298 14514605 899324894 378571854 462328106 101903950 558440369 881973016 156848137 728395616 775875540 836709644 155902137 911377855 161206011 294460931 877765555 985057041 806135470 601567552 696341989 249724169 610450581 887343795 428893691 816941215 47361966 952332338 842469784 963924826 91499410 79233215 765058715 603347080 590263733 845592007 444864093 367400066 191173285 631787103 231170287 799717355 376047944 479054983 880578654 914678511 248613920 442931816 45106161 336998022 314348168 172299159 736737639 322916784 274414581 100606545 939586618 168190647 562780471 550317759 239214304 958269042 661390263 493684785 219012102 145563518 143230649 885542500 81373141 774261125 219942041 981659838 448901424 666545272 15121935 772197774 12075761 73582550 157172589 173535566 458212144 725716453 526670301 29269475 29030014 901296885 455199909 728085465 180018467 158894242 16487524 718573481 468346981 647968528 575530068 986620148 804531651 921784367 707145608 372085190 424746547 428877558 695224876 814342102 978494313 433500329 210887882 937268162 271677201 950576660 671771521 717164117 478305298 6607055 280304973 806249923 433828298 655818874 522466628 197812457 92964694 120796160 982016469 879832719 741041865 92005077 782488584 317235879 13482609 661952058 926243522 304895373 579299863 978325621 216485888 120450374 153237565 224692763 901830680 929982659 801344351 40060744 796433661 429987613 702639412 994811619 426771322 605211352 489909741 6953437 197235315 321468706 21456242 814382704 560364585 364712210 302363817 138400609 758771572 52526315 497052336 645247295 812703496 520513368 575879712 785147812 52349106 845873839 623966282 461233265 665239706 345659952 846202491 125995283 118428801 892265285 587714873 556955074 944006402 725489857 474572165 997207742 168843474 911080995 469739032 360450450 653187585 952843474 641416360 191415379 190600504 620524895 234567970 244924640 544305914 745955016 293121775 243934752 68576997 197172657 170587185 569621833 480407280 953812394 409637636 97539861 261467820 835429998 624225983 884600076 36006533 892098847 44473138 11232958 177290496 699313037 267110376 835007752 497412604 496306542 687656804 522462540 415294963 31263652 528947301 858970811 727612215 428494204 458266915 671749516 736091959 953344491 144551569 870967875 814250937 288679633 345162139 992218349 718560287 442542647 159659623 799811168 925040804 617692050 375749525 822121341 816155550 828193023 933809025 144423535 559179451 167367303 498826109 384174059 74499653 511597402 210847513 126901360 717839968 516080405 327611741 784929670 40193097 18674430 55389195 552646912 896938902 477214020 424522463 533845564 191683962 695166017 613979856 612451679 931777535 570141626 783082318 678716571 88205643 42597915 509281156 409647466 76805342 850141628 663426453 412379602 911472336 651358752 893752288 190717344 615628053 2765107 898006077 392386991 85976762 968530569 917598015 36189984 599090471 974152356 403271537 301401761 854222684 160020012 828076187 604043688 843189557 513824565 441399037 14834103 960727720 230881406 585512592 750294423 418951428 41646 506350153 529491102 899833394 649891223 50151767 878630379 977462261 463793013 837901922 401405862 218234667 317857838 490310348 675747395 169367307 240944272 470389233 327897533 765130854 462936983 59729000 303482077 230341351 160254886 390970177 981967985 754138197 649170379 309071686 766707351 91812814 720957693 680950332 971747314 406550284 776686431 191381537 374511345 452016033 786102652 984713325 507110156 36253755 948042634 710728019 742205960 539128802 604273833 773561086 763599664 950816055 871613987 377314006 16016539 794519989 250895531 907724986 719893099 461026546 906017184 69833286 788267017 80029660 796222025 458955788 710297452 277824509 598402327 682794204 845639761 703516856 677124328 144264957 766421889 392523916 108992064 133172595 692072464 932054606 581341839 825936185 93383321 16428144 146561904 949161606 581266565 474340926 464209893 129094666 648564547 783378206 187382174 322466351 177159054 465586125 29945905 849278554 520555180 908752294 115980384 175568937 732899243 392695259 728591704 473739956 512519332 81758395 426209262 690559437 733173754 810634989 317710817 647633730 480956825 2750641 65178909 161808919 569645625 578938147 213983476 499576271 99144345 796226425 145702756 856740770 347173574 560299586 451760213 183582149 370210644 235887782 254931674 515206823 729913505 490701738 421197421 604648495 487030806 287257451 532657204 697089281 350916967 913248351 808100416 980648376 333081552 74997401 861060811 217197099 285702487 700204804 428540791 346934953 245476367 902848676 718643347 569374014 412080464 470559706 14058071 646727918 830933249 902486942 557057572 997304055 420109521 989122245 144035782 465281041 619879799 566469434 99867828 928723374 768615414 337524038 180656460 472466236 269062365 451939529 693914649 853594463 375296897 429825664 522843919 835675962 505602882 621868351 55754954 293460389 452014797 403594550 479993812 778057333 927596374 339875630 169606110 742532024 203953115 595407819 373035268 703849208 796535398 462093513 584217867 267710069 853002057 216995392 234487972 155125357 499893345 321952737 113790120 572578390 105146452 800514104 370315099 406240287 145200597 440089578 762286507 711709044 621558493 913208566 873139823 346446585 559085041 986853366 171296170 789930892 142174560 160793436 940246471 297998212 491059844 525231287 885563100 438451702 919163646 206310381 766932969 802608620 683336187 824044672 886011416 741471150 756308339 829267659 264458236 8447995 592551782 49514308 829677267 276937550 94865183 580783033 428683206 504721179 919312499 687803029 957296422 16568080 642196736 625438745 285263278 366238807 578615152 782838693 316245957 418002128 291445941 263258862 575320762 468583001 424256332 188140359 12271624 310154247 252853372 565795034 202904209 447370092 430271382 648720366 831986661 621920721 653783348 526541344 138665850 137973626 297281147 487033259 118965746 225626855 717518427 951995554 734234714 796974607 974468811 515551282 474930023 839375780 459774479 100024291 70853304 695622739 444183540 641614549 262170649 9087491 630595856 537175813 52935356 968158483 987855876 630547079 995518591 987792285 261259451 543611595 782948138 863029943 465027498 48662490 666352560 177464239 847919376 809740183 71174507 335386444 751191605 938076928 389384545 907693841 256787628 507764075 855306115 763186299 336012178 347933644 429710826 69068863 712395982 749659115 521048603 547757967 207835217 517776816 212436546 183978324 194273621 244348505 797969015 817644914 602505120 532987839 907249149 658050569 4814527 769149335 82500224 830946991 230725453 183183532 827564884 684562360 725282347 533296167 527515322 160994673 622162375 938453705 629433629 561532254 652137815 519354925 665347662 976347009 550544413 474784265 208230605 256519060 88246434 605147499 401033473 57297482 996380156 528796157 336245884 633477268 925357322 98185027 802563386 343819992 22567348 211601881 302637280 235988025 989768749 188823735 318757374 593941460 899830835 81600111 113409871 474212862 23929931 396525163 893658870 882635144 57400071 815762993 848726465 332218109 824648257 294209184 515491943 797314016 131159647 684406578 759111883 492173297 606538127 914007866 559318328 131366502 388142857 566503205 873891748 491694900 987043410 307361210 413922543 553313861 531196021 561737564 803664931 750385344 226064201 571079492 7179187 406811718 245194928 824212681 747057853 193640496 286531027 664009369 981573194 228080852 723557480 906396159 24641675 88147647 902807534 259099165 725500955 199940602 291860717 74980145 155599681 78423879 981838393 659578833 364916012 642963299 675010094 308056112 73837879 283390019 96953330 67799897 291915812 374013016 334113463 994751088 444966243 446781901 569657592 421412342 717852234 80687557 522488248 700880131 596691803 658798496 752388040 369645707 141291395 755620916 241762048 988555932 270615382 272573205 120470915 74755996 945346646 405643727 846710013 972311436 696877099 78433576 841307621 93157705 757199338 906332769 55481021 173861831 92008784 69773427 356520783 292101974 199869958 620435284 62708719 661999839 526834908 240630577 600233149 411572518 444816143 354292659 944752354 999147527 964607877 664239932 418383311 151393210 126682124 430969385 100438659 62331920 803623073 140234767 798761156 727148981 559681189 710701311 26576994 98247022 298819111 618141380 244144249 327257946 116839710 509020705 155601581 141241907 71518382 834650133 45015661 800828044 749174880 51319576 561148978 34966545 131454315 871312477 367952574 111750860 224959472 611333392 399562848 996034652 681446967 829824407 346014764 860732221 211034612 958682835 266362181 557349380 985573254 429656925 886331925 53300386 942703412 522591947 263563665 82793886 734694512 754365674 484818551 871700317 638125333 368811267 257551504 72579419 537808555 381807896 933494768 6812529 347943839 574272805 271957555 164203279 830676109 188549729 888193984 833503872 318693752 608313468 246771975 292129322 508443406 49315040 488467396 895237581 824607718 362032115 171344955 491219905 439582659 591798865 205000827 829146170 164370640 70560787 976075678 127673477 639629027 258240524 6385925 544530506 190452412 203914504 11265949 916787401 688737604 26200333 978451742 803863071 188624080 128063131 785437512 71041664 389132894 377764845 660888358 45686140 476107988 21888056 947425868 737819964 745076294 831012585 6632987 208685507 355411758 517603049 626799354 605151279 908665267 579617753 461004699 588183031 973605093 337495384 358476862 684359212 339716092 979485242 595941862 94665402 346342302 651675088 251926951 286380965 83164951 677871396 421594074 694106702 577184160 479463483 911009636 144977070 610385306 535037779 346263285 756494999 579790802 960851492 883289668 463673592 987702973 232354081 521048405 253293847 12897722 796975797 819856309 66774486 306213972 45555336 271514042 481361136 589602175 899252410 869845957 480173626 982610648 134784804 771907969 178054884 798426088 793701531 202849059 491900600 200691551 626090542 753671849 963797335 832471130 459410533 238176541 513853312 694902686 872225410 579187153 169700939 631159516 805588417 526820770 140456551 598998509 436577433 270104120 89993058 391370774 420902394 269946689 170033375 323509571 216148110 502060474 874452958 676571980 804001786 200782120 231017465 410983732 6598172 184577752 764140195 415562855 856470604 555612965 363079273 422111737 139591324 714696368 632635954 303690219 728317210 748733863 762257537 459221095 342766859 194211072 156338351 61520129 123951 154912188 876183091 12561397 396801 851137575 237316059 476214125 426227446 388471572 631031570 294719162 652082618 199845154 923247386 663208344 540413048 155401211 926650961 343105900 233945617 656761746 128948077 579569287 526036833 477461346 967806657 167256929 405448830 425923507 895353720 987323872 792830970 164688086 860764887 44714129 330804254 841660005 51707772 808713707 64906799 852967046 515532963 934526353 776555435 439380775 288641885 516933518 276167050 634127168 880510424 924053912 828078974 648979478 675517084 222960207 18209589 636848756 214433226 901595772 306314132 468500977 970554973 612334164 181542395 816719406 267014506 225234613 375550853 417313815 161368929 123691109 638306886 940503839 10234699 111674200 770453133 562792070 982372363 120305128 179255329 715257492 807433631 750246428 300280710 985340380 657699935 108126435 964549943 219620476 215873594 995337560 241166571 919656281 887939581 698652669 179932881 842285925 607973005 542174722 367871189 85233371 440576553 709453436 374407131 93401215 131152811 115836336 578972929 334993631 351836101 128754759 802268382 864111510 888310342 959052953 352848071 894244998 726866261 150054373 958259206 124382491 306384562 616787348 655976227 862777740 319455993 931073147 401434909 169601563 536198880 947120663 439316143 598544465 575932533 973803472 756205965 763237957 139033186 592856120 896497574 697093588 480134443 463703115 24624225 450181095 903797357 579830959 650520546 870584754 563596830 206933747 47983684 84099568 76066257 787402961 332335837 380505130 640577008 888217965 524727679 687604719 453670146 685549717 854251443 865061915 832060132 394826240 920365565 152167442 865635858 588540049 422368541 876033795 443846365 702151060 794434378 84524839 952778931 566541309 557920118 180503808 963305819 326150061 369153678 852225181 777838136 884094126 447034041 532053714 174002052 408132724 487330454 110126722 28638612 644852507 136513664 464959447 41814551 498378925 198545355 875494789 935808344 330965595 427032581 836988940 170251642 507283905 473451064 506635509 49159608 989487652 869049892 450856978 402314668 211778484 580867463 192116927 599324807 425400524 87226198 536491813 396932178 583456559 585394947 648617843 30523189 985749323 363474871 516604709 573622958 103158647 373768086 838492223 281856727 346510133 999463168 301942417 926874018 723781234 967224267 427482866 592738846 117572803 191088268 799237253 483898801 849829544 295586765 156490233 29982045 728739019 760676181 281320643 8735997 690658111 721458533 573884003 76274310 680658626 60041719 156638630 269794632 393775613 978686463 524241888 958499117 701865152 601323691 880824879 946934774 252445513 725440677 828019901 236937347 652147580 937155405 35142652 957289481 622096937 959157761 716409321 9532763 150397002 266832726 517735243 141170211 660728388 609610845 345506546 626993703 304580387 227192801 950010 728343174 429088736 995973541 41968647 370621178 390998684 794430377 120902281 890343190 52188132 771978595 203939319 127902087 41036780 592063752 65456149 176591189 434792406 130077378 689354288 425321248 632886506 415493112 619802717 100266084 60317149 650772107 841021120 461993143 863226892 350389781 769292993 980288264 207814335 454502186 681297493 140130016 486105192 715148440 728978749 347959714 26641379 798570664 24534080 976135627 646930870 800667740 845767281 415436852 179261264 270709425 958832749 462392653 424979019 876105180 428336539 372647010 531613611 353059982 832205163 83906263 905166622 108226354 145715866 310884205 90316347 651953451 429330538 69554557 698344901 644647449 410103276 836101689 892284647 407799570 886389559 792211951 150216824 2942442 113890991 110704967 813235766 356849261 846471233 537205890 556824076 210913186 77791395 423834299 806554445 542638343 410628246 465940263 122704376 790218713 692187685 888033878 782188532 104642123 178036709 860729713 385142867 891789515 967733 329359228 514971792 399366466 991758973 777850515 609736146 441194066 733999216 860433198 573964841 598963863 763466571 386704734 973882318 223130089 859652373 320792591 237768804 760050326 592661471 124429894 9590843 211616937 630013188 716004962 879494537 540614952 473098343 261211485 291483569 606451535 692385721 104671754 459056254 661700055 727451057 785426518 212483429 950086707 93062996 986536584 415373000 32241615 385552685 299943554 17249072 87926097 755935891 803428607 901591184 209171418 335648487 698203349 886210950 254645316 908407508 409754163 980184731 498089570 33523600 157695457 316402559 101918788 783437335 304956036 488657488 853294450 607430773 747832280 38710993 711748142 627798778 918752758 346899381 706576565 123896708 141701262 203941331 598239356 672041147 251744811 849035120 389831028 765921102 866188148 139763579 917926727 280192312 700987494 60078281 101093019 902340863 612538780 368693087 638767180 545783025 991604617 507336614 318352051 343798886 116213179 132887990 641823459 574756611 788172311 5269645 855941608 445976051 115362849 999243095 250642440 828725549 900988979 931228325 988086787 901576371 340675266 13161399 805822549 982079438 358394782 567024565 223801456 167854676 362039087 316212463 421477380 919129572 946661819 555973666 283561017 483948327 416910493 191297459 861596913 874260238 805979021 854203123 716785160 207342616 784959964 155227483 397829269 682733450 114386358 788490703 970811944 377103030 764522847 555448285 865634316 704992823 116646008 51115260 803325572 306945841 734025530 220841935 173895183 590744211 772703672 112867681 997976229 206091350 495085342 970825321 152515321 250793660 857666293 934480517 965191095 840012180 291114590 981972352 858959045 824420210 209998164 69332621 871039107 871877369 749542381 23295371 592453388 112625682 503302039 960932929 402132341 594104628 831655516 648217504 908594955 475720348 233048096 21637894 278923927 598250899 759438815 814077815 265830298 791161773 385166578 970327268 315556243 936333318 823748168 540172133 400182070 208344196 619041711 431516288 524382644 129070874 130495242 984107106 69681655 706388224 405127065 191736610 52086244 881089533 92840758 212653058 354170265 855170464 345542548 824395439 436682414 724721280 11937664 672138878 813480310 81296256 867543074 88669103 929197628 74692879 294719034 242651819 880758408 771053665 438183781 587277127 226413657 4892857 132819798 509095425 24824171 866182817 407426335 237615935 858980464 129410350 205369960 160064149 543154776 62654270 470803636 372902909 475778443 530325179 101913761 707195166 546920746 283286486 514898213 550781063 647333459 314580046 835452627 628561650 43546972 236483241 712682774 976346244 189245205 541657975 342137715 210928649 820368904 626546836 386651849 561380922 949692858 126789221 229976209 826345720 496689641 15181591 980809247 534220943 631376845 921870308 793380321 240045302 458687321 75060815 575288477 260861707 299588216 113356132 613229748 987552730 346642002 686359291 407099235 100046804 614621318 548284660 359688191 799489561 177021551 342693498 849054006 881329072 349022818 313037634 696014930 564904140 96934635 532437706 703043702 392488454 668419605 825982364 351414752 111917479 553318049 749191818 246092583 137257693 346352971 439805937 569624189 150473986 547699721 744849656 765945580 25058522 571044685 858436816 646124954 735752147 479067456 459190259 282479878 233431364 958546695 617707878 391973450 980043696 910867456 903117305 270088793 54671362 649785091 715958147 788728128 345363152 18892706 262470696 908690790 402825114 634946411 367387541 731142349 601120778 529482530 23259712 697407568 778452276 227219978 829748906 763052261 867306708 903973147 764360862 237648091 934579348 893161034 73029233 759061786 643817285 548008389 30372929 442578535 513006626 102939446 14206776 196930719 488685074 635270909 738819785 725350904 473853157 683810168 92200431 837767749 678570644 189764157 285167218 757887536 640773250 909736796 155818019 815108224 509691583 763832479 76937244 93845331 367059265 499787978 721535490 418454370 736532778 886067421 787467589 432496961 776530439 489429839 330227804 524357277 556802317 919338322 916061708 837689214 866653276 51732 895697567 964451204 138847294 427094009 800054063 677117228 39945830 706728419 972618970 853980426 479113010 297138284 202548748 42358542 742415082 951295272 840710074 563307457 356483841 215728102 18685091 718224774 243689809 2073581 306189455 130064347 466742625 946255681 205694865 847772311 446907296 514068957 203256647 430998828 174441640 282807031 449762326 253896163 343227005 715147841 577172592 802790180 997740494 179486500 349440527 767885485 571440432 894986244 75604793 837387480 783462504 817681281 516616700 852397527 323703199 795903409 229641072 43956473 373442733 494018921 792794874 494360036 305444432 569054067 525117829 323460058 149752691 239010775 956416712 449364726 376376938 16901396 371481220 419230574 529302066 754853220 185064901 145351376 2846131 531833341 917849118 735440198 193350399 285704781 722011887 610263252 785138322 309080891 241775264 127973527 261076113 363578475 44917221 738937861 467295757 149455735 988218105 433455665 188768831 599143224 4010725 417355525 859706827 719962364 888900792 645012103 593315327 553763279 43377869 468257303 2117650 91191220 9786378 763915693 856174183 482950379 50192157 934547229 230475209 256046891 412106175 489792852 348829358 411246822 937778162 129737113 839706743 899035785 628515652 637287119 346867371 319475130 195395596 165826735 214752321 414546074 835919017 851231504 574389460 309367043 586361032 93596449 285322222 484081609 841695900 641953450 307390528 133697530 135714341 255327057 997028069 57574944 946045548 93931984 868057252 974191995 852448451 379859265 9996589 323038024 302077446 481618516 278262872 379056639 366472158 641373333 834695019 441474190 348037626 511337385 519066707 310869921 701354838 376808590 460375783 344560347 284686198 815753440 925194793 337875484 793841065 627503120 436643206 450149562 566531656 508761773 687778323 92438217 368990197 176692637 828627408 166669398 713248479 93841761 97843430 183898789 300247034 267210582 556218602 999222648 218884169 782069489 234133529 434605128 340876310 783181056 588375196 752978315 363165237 771713773 730084291 544329710 61301062 625612283 246201163 113144219 914211058 500353673 323599514 163869554 368341803 349285196 827810303 920453712 184348014 789532822 72652788 984301644 942294529 602623891 55639646 904377847 55992119 313430920 861483465 185240473 375583401 853615381 222503598 399911033 703447676 148200817 928342190 739564563 455672479 212624306 988122069 256425312 494968331 250496516 767114714 957808660 677785091 409087214 789578587 745784793 412905299 546458259 277564195 199268758 874892691 485882860 289064294 445826731 806453347 701658640 276600577 345338420 330977966 22634349 99590844 500653124 805095401 718388494 613758089 186980649 271260498 804013525 982249668 416788140 691816755 885086655 380417394 895286095 934282270 218453797 912289156 771858318 479903792 495359991 518532115 58826529 330841680 342304512 798342051 727683126 217389422 388000551 957703522 501876408 500006342 469736617 85695079 123133837 131359772 708190818 773077749 978301393 240328448 437614851 264974775 850695709 923109385 759861338 893384963 437353412 970306843 772194959 849699353 216090130 810919843 602383714 348690531 998414733 527580631 540108144 423528116 521904438 840139256 619594093 553486987 97654726 851279761 136787817 334147919 705082611 752243895 957397005 295561617 811154090 837193032 486308829 654896207 700930132 682982446 632883317 286827053 424031251 789333147 740368845 864731835 282966019 418395980 417240438 13378996 650333051 908256712 745860060 976793146 144733259 894837664 950914436 794375197 560487934 354615726 580948557 921172755 950104855 646379351 89434288 262790654 937825365 410459083 86626562 741384235 129695216 581522753 732814511 593398415 233112283 218081854 246886270 54378762 159638018 778493644 790965969 999756197 467641739 319428 846229219 495179221 946630167 619211271 779591689 80665527 304971775 593605054 144754164 339500372 520883864 529162655 850798827 168906204 741198705 513542185 145715987 137575148 610977170 531121380 565704104 171297738 390042813 117410723 726032963 720926373 503135406 956694979 853592595 397983703 490616924 463983979 453861158 64938788 265469751 334800588 12598175 659309307 796217450 651647840 745844990 56479665 162507288 987633453 929431902 476830410 136437920 628277249 690179759 599028786 401477082 437513908 537865730 247803773 175134809 921035371 947153595 510313773 761740456 654800849 795106270 852553194 603448463 797249629 906641220 209790920 401786958 153920912 930104548 38278534 584690142 422088758 573783053 96498123 318161461 63284642 194048680 860280425 221419647 703863028 480231544 24752540 282887015 765387348 341988954 448091465 307942478 750836789 871860103 183699009 541896336 899286677 498510031 19053437 407575748 969092665 465864670 750591329 70843386 395011571 855499897 100148987 461007612 852418013 617886655 501249858 304358287 890329757 350034793 443247193 523468721 950446753 37273356 747376331 476846810 400937826 207541587 777386190 910379837 988653730 422226247 468315010 791823109 324588975 506608521 512551985 491122074 892715168 623203732 139428750 477975772 122598292 748314365 549538552 598412388 114387448 340013236 309484982 193044167 217574847 649778754 365529657 65061076 577452713 738093323 5180255 994410195 345446270 21353867 158131628 300990405 72589138 69321882 692163216 768837288 798263489 902657194 332662694 430199218 204648241 242458373 633777136 525335955 870346260 260270865 150140190 901682357 16097317 547002254 914916038 722671741 515430056 478592467 516564906 612132489 441256620 802593046 646167799 885818865 777220170 419925923 707797378 166486663 708378084 339511841 825215754 111702553 771988329 897893587 820279163 967277484 893836173 378950354 339457575 128046784 518099219 85140821 482123532 8077456 198405636 679685866 521489938 418856784 916198647 425468092 517120075 492195695 224391753 828862925 64318772 936836308 748114788 747532346 93232112 499670563 607015417 15586428 845435025 416645623 689262407 676855459 576993616 92257319 861020500 321171867 712829394 302011138 332561456 266900584 9909859 683765909 732089143 370849643 507386683 993022945 909449805 923158428 748775870 628955175 725058337 464167887 559054261 770352158 565363308 320047090 300563095 191649592 408620849 58330698 511435973 454110947 694573564 163207867 712964807 119984068 548510245 796211199 925012625 474862843 669672716 857290987 987743426 530489699 723631964 55503791 607098337 272712400 212331593 294899988 860095904 18828624 991207636 174051773 770359835 990371949 933494531 202492776 745729303 194748519 592471339 894200364 736723269 200098172 694229288 746130363 742303102 848827170 191862177 72339615 918682630 168915273 514160454 637871997 678782922 312014746 233647123 203064407 776557476 66715324 154980492 685627843 152015764 648890252 394851073 347422263 792924166 367907426 214972617 125997887 620072720 857348688 841743752 725182146 891349938 359867491 674974314 663259202 502899478 45314786 110314855 509045274 542782415 105949836 914127999 257623744 10827547 931729884 266437373 804174850 616023587 27663942 275381942 82405450 704759096 255623032 935402313 366714844 886714645 769766044 926648157 408996884 964653089 758760850 749644263 126432939 510971819 23036472 26717028 174730481 351982894 467212708 139024152 902686993 515993484 707349861 825298007 972256593 395066965 349717703 599611834 316271441 556472063 347904013 828229735 772376393 608278572 131462583 591698251 718182733 769411817 686036924 92834400 756143754 325936619 957519054 268436970 751209608 975499985 732097946 460805555 115380327 903134567 167603719 422886484 512050724 212320991 496801908 150531181 942166483 238156567 761997052 832325610 888509155 687341015 357933747 148016958 211877727 94376977 73142503 534276776 688079657 224623393 413997665 227071858 620389695 27235341 329642660 298901806 987186936 9733316 339160362 154458362 448041285 727493984 602252460 232546491 334027250 743495525 578655320 265068642 283967716 513381633 224199962 893635884 801678682 690062412 165855957 762825947 20166445 710728839 187552169 501431552 202150417 114481503 347052332 145045042 214837460 265273384 603989427 147714902 1476764 97855779 423592840 4610774 945970731 967323322 671789106 70442988 220232988 150790849 673420722 32016854 839451940 342708661 161112514 852193568 247735635 741057022 920999702 37390559 815461203 5345582 985992348 722614770 543588005 569439552 341452989 410572353 97550824 496038364 353649819 251519488 944017940 847196559 71257939 560911082 915405240 188529941 913360186 322077575 476207681 194031761 956554018 33308776 209865525 87908049 155090835 778245480 339250033 547627148 317872148 748851946 658584176 556059045 304445025 173301535 214298501 649482855 414617012 727846207 576218908 188998856 940235774 172340428 155075071 590814120 222180652 354815188 196990093 725556753 408199268 388353838 516069379 788738166 832059207 98368953 860438964 382520821 874019118 351682465 588763218 420209559 591993455 786240156 846893349 776177037 313543064 617323559 396368720 212664946 315751600 960102091 321518352 262596749 299112570 993616219 314468606 440405773 658203058 36485685 864299850 334520653 934799951 158550142 658836735 74970127 911291586 669821800 226899780 70292674 916144947 656324974 799306391 270677694 755174600 704455572 273638417 855161989 614876384 40029353 956981926 745576194 842658385 714464390 966642787 194370250 679784623 463783245 35105200 681357151 914294662 509021356 871621774 182197353 984120220 498564378 542276568 242763005 409566770 302716695 316612739 852184 215819330 415496301 519723743 904313763 66874815 445524851 289609685 908894766 835691226 11878470 270309928 30236598 215233336 693173263 30762422 252543264 485287230 925823042 183725238 706720829 260114760 260221402 843540730 258352391 167119595 893144736 901970732 844039392 713325112 490829923 576544786 860511191 560293114 430402623 309925323 601953251 561501172 283132888 278447377 280777767 582917669 5817501 910959222 98014255 22809093 807426823 185108393 957535023 965190855 540613593 125306032 965982024 676779927 885106015 280957741 783143108 104254171 472168625 15975835 778264407 506694516 466062063 203270800 955959646 220448251 778115715 585873402 556495137 518192646 745522276 896790628 960672786 267379042 52008783 639849008 183133708 400530264 610634510 293103835 72742039 100114922 427157939 123576382 232482336 540513556 291971290 41464776 55808323 650199053 151743724 999329735 882069507 371726469 233161817 859622046 221102349 599194599 259676890 912015886 218757883 107050646 611925687 835414127 170360204 715470641 113885180 214328821 325207790 896928720 864434115 684799981 779432183 90829126 96616815 127972863 136027749 93764703 624498156 246697323 549847586 3062561 330188530 459392590 355785347 360355340 329273409 403109084 662923910 889381724 272300260 488107684 764801809 629412931 527761520 415282641 580833336 335717937 718844995 948861030 589160565 430579726 105185991 720597374 258147311 725068156 646697134 755737235 67628469 138581527 245828661 749838517 507346690 412162742 446663267 567621584 170250872 174845097 896250952 394148329 708414823 338423546 641248832 596592223 417751301 474047406 311029552 746016555 161912756 964484355 657826757 243041826 572175937 953774257 360419257 177834543 323303712 707165995 160353551 425740444 381055411 771885277 456771924 565189703 431485826 184126829 386015966 525318894 434667394 100173051 975980558 675427942 997304144 930243938 253489807 496542685 556952181 812747639 216119958 770355485 554488737 514830407 281186850 343927242 932830705 327148634 819947067 500027040 893329450 622269684 497575988 880873655 363790333 598802256 105146090 145328321 887027523 532946405 117180420 106410056 101320513 173865379 625557299 291773170 133092834 623608116 533665137 784498111 508538113 552693821 338051651 114920007 873507230 459537564 678315769 729516029 328510757 72161705 503425002 336144752 777953453 315614583 663279035 698866055 656042036 32951313 768209558 270384834 157563877 52561599 833867124 771805310 625455955 98865984 165225814 748251694 661613757 687200527 258302085 644310180 40619594 664845473 804045783 861482312 887606604 278323875 744005611 601029469 970837375 447367997 665051753 888446784 783399496 710827859 386148676 725871018 807798264 810835392 810546169 886582507 906872583 42438811 398096080 747952687 972433243 649660531 172366871 223432890 855136641 256957332 302717292 695552301 620335088 160470338 219873521 523437248 562467403 25153787 784014999 744176264 101117597 960087479 157942614 551860912 152807580 934086441 788963440 145519041 432314600 337251068 844074163 438651356 134077002 949342744 441037749 727301115 525940471 47111132 171202840 623590198 558574541 607946595 94802885 907795962 444814738 821250753 650748210 18716497 926720058 956009029 296193182 633141278 864771615 427682743 999050321 147406431 909975880 303937944 671787743 976588907 499011236 617209958 747587683 651948596 237603150 896817111 574776262 201970820 692547016 17712666 920178167 25470529 426516801 542442779 383704881 526527402 902134481 246541758 585372218 670293400 807147194 332486945 519625632 970589888 967338406 96418780 2212604 198889710 473559021 480379713 91228720 283451977 695383758 930274462 496981162 822763155 855927730 307511927 934027937 377157224 495436142 549940174 867635796 528853115 214831999 800938845 770363728 866233566 393857869 874746072 288550824 922607672 458302826 129338414 32943420 119695630 599431378 199350982 783950581 851844860 115222059 748073668 997275652 294490107 539344644 404314179 70378792 469454747 469569303 369466521 560309222 245165127 687618952 392123288 731219409 200448645 491851301 843030729 494335425 221322805 674799781 642281136 524431645 605338063 850058731 172883469 631507731 864616871 185180483 30062871 955638748 618973482 192326049 528109248 281300987 752559136 327235814 68207606 102322556 322586090 284698908 102461149 808154935 346123970 69461431 370175511 689394699 805267711 813299923 813032958 82375717 1559632 683919994 312657894 518567993 144178430 917970397 80318814 159748293 951664428 432897176 255227757 600307026 966527512 86123504 185695702 976541108 490100569 812070933 759043670 988285767 175446048 757623650 354668514 509567025 746438777 446950298 649180140 733600933 136551561 284423466 162768285 493426204 556440015 765155948 675741465 687250587 975926884 738670815 445514944 121933297 157482045 310767217 927408232 670973175 392306789 270458039 418475174 774841552 974470213 442682417 639048708 170905128 911772382 482230153 395742281 505942135 696390667 155382482 847216566 403078461 714068930 464873162 136388677 757474629 950201681 550216730 267380458 925350371 822459554 915736722 882944724 958532152 335862649 411997808 335652010 411025514 927755954 116718999 72566735 400914670 580618118 333985498 421789088 347609024 767913668 968698160 617815218 543846311 455899161 493153534 646073366 879643508 849891659 298035027 381181591 572715841 450628983 890540837 438439417 94842803 217085016 85380758 417383481 240827705 455116673 302232115 164201681 804455756 763787167 519404080 229819890 870335919 450146233 656554415 169069513 382115247 822517874 912456696 248890812 902525794 681189187 179989952 497954732 113066217 852340163 28651620 988366643 58824111 941379297 595552044 165492453 843906473 805698597 72807562 280251792 12736149 825443572 994589530 743432061 410139965 226140107 780840994 734983598 120290995 572135809 691172432 824839456 685836180 916345479 103125888 55414792 926997831 641103912 291867318 558341400 553161533 911203787 637799837 114513080 642989104 757655598 624253392 766209614 983294821 645886122 63088655 570249081 97571820 925618803 906529670 836085071 494442460 468921303 220866828 200933284 241278874 712181116 604439647 107674692 720884496 638568868 745373546 704280118 163469559 395349865 692949376 87118584 8752655 56359939 33705632 606178759 817021028 758443519 174869681 482799830 5262473 532112007 87816900 792319635 763387101 541560478 494359639 686563559 892677322 790053474 340014734 691541108 320799746 957442122 531875706 543554007 375386051 8037480 361764691 459306213 91812882 449427878 238292927 52644847 418239745 239365898 478370059 998321408 906715114 767114483 354223470 44708635 809064115 706461787 457877067 307604863 685128969 426017813 260626284 181900516 633804199 450524173 527035977 156617405 897789838 785697421 175231809 972309110 412325708 873475444 566680286 245331126 469405239 227159422 636254483 629216411 262279601 280094593 484990078 87037186 742411363 329180587 353922984 801258429 789413251 364385479 133428801 420234461 685227024 920191863 396087910 779862503 783747090 877682552 522258909 993590560 848418780 327412963 358856533 383276740 83408204 61231463 871324073 564409928 184794887 55915922 11619611 691242909 386254783 414811143 298744474 809041006 420894574 506543815 494472446 271609694 437159066 889917546 660066377 668430668 611464081 67858276 513913573 175567504 212368812 817798978 78482666 334278717 657709709 558244844 736900950 978611551 182834530 377394403 48261973 316839996 918283298 955886721 768695672 549259669 987891916 844726589 281034495 514232803 571093677 94957286 289307409 771752604 458557336 247008229 210762753 346285933 589991213 501143165 473097352 942972798 401458708 556751372 203863823 724613299 92395841 866552393 663413476 850843368 357977903 328975493 85485953 658680626 35440423 329655020 123629002 348520226 369754744 592665539 318034253 587801090 172401085 253535401 729712513 281209879 729593372 771606488 430965001 139475423 388511875 198740322 846243056 776297298 633755883 487855222 52320237 811752227 486783383 369350810 696395166 846806014 728926803 742251760 726989774 321648585 530671030 346605427 346750896 338523876 780064866 35736632 699282723 104301931 791819329 483667120 723591150 781153392 946508743 303355106 840962818 656758595 640744244 985655475 919014845 342190764 735479761 956309279 637421347 607779885 998078255 257092478 544648997 80455490 357255789 825543874 344806363 268994210 656574833 306720437 533442763 185062781 403742763 724409661 366013985 65990333 753667031 310426522 406676471 449145927 161707065 792599460 329597324 800164409 512037088 235004175 723822734 904928299 386543717 438868648 837204050 509244016 766539691 124615574 248315160 839661395 875292446 595707036 693277513 477362780 553030646 814306643 84142778 740879243 492990835 29598066 226107881 23827609 140437023 536938504 123854140 869289019 852697873 787988157 161560135 437884256 563407654 730439959 234138372 119900784 656923208 677165488 705462042 917648524 243042473 27050370 850267928 717512403 465808902 676753693 42233784 573155736 902849765 997253101 378255647 669935534 775864281 206175094 625152025 646111134 30218939 364407449 197820255 382800109 221713904 345913551 891778770 455456089 690350503 556039018 580995262 14714906 13550361 312569560 701552922 851870499 899315145 719703521 527009988 499592799 174547140 292245222 245746376 937912054 790370272 862200098 146525591 378425479 230948606 654911978 56461905 538865774 155961673 283799022 443919357 914388221 904230517 391030903 993462477 784562884 743808515 353797801 361716573 357488074 581363834 186641600 830170099 178102483 703671981 194005844 226997694 764032154 602407673 410782359 215396376 832242453 890625669 537831315 609171397 663078070 471896705 307254638 519990322 228371878 369393513 761769639 886901945 82023690 902886466 62057560 501554138 916182592 790242265 977229171 39230081 360370720 780741128 557576711 21579076 209532988 334640370 437355131 94929315 230747682 212769860 888826063 685841736 336471702 621333108 925695967 116933447 523238107 417485315 623106721 771134812 281729001 792376508 610130275 557859121 264121269 249374964 881945872 230024599 343284846 5793994 95727722 773013961 952257979 179169126 597782350 968957614 536700416 829097531 168447989 83777046 365326743 930356806 615501871 733208570 65193497 745960270 115905703 347887549 140355477 485805860 120144420 433567599 518894037 881238242 663424195 486432518 765729181 708854318 628159807 3685796 256795629 550325365 381681196 731866326 278409020 429735986 328225077 251255249 158429372 181042214 973363299 320396469 793726363 785632415 11326294 165923787 505994813 139681971 490131595 408198344 204618116 444876163 257187478 737875466 807465482 138754939 763246439 284808151 972257636 654779790 787203975 88425891 897229662 197426299 883066201 695340872 994933058 681036812 554626651 402303053 649261331 783568980 961880164 446625057 190511820 467037934 897558757 272616542 624117667 340546626 479649834 281037832 317377354 705427137 59097240 898544845 715599146 514053670 173925870 320481605 995709351 698819252 548350086 675880241 74618721 413243004 525041810 354533054 13735023 213233814 146419041 974994369 918669219 172178020 77338265 787767033 938882506 37624532 387737980 891690321 593993451 775139228 932493861 892007709 289228165 393493118 307851466 307035994 144312787 313979523 164243705 119696624 81265929 349731650 204006108 51770865 304943765 367112215 633861751 782534361 501348192 58643310 979032806 109264845 68524813 794788343 629640098 243776478 11446070 398484977 140806074 719718981 470114996 580681313 840988 669323174 950926549 517489241 30569931 154847567 46612133 705359412 703840039 278314615 108980264 896140501 317219626 768354689 372172699 808745709 771025831 395882296 440177848 643000884 955475339 71795730 890417648 484114093 53520414 490813807 331444144 78374884 862094400 640655065 80297375 303957040 526307246 318100804 273173980 44634611 691275324 226249292 369005633 210211542 813162777 136186747 153938852 499511568 84456464 535051138 551237907 191017118 537029315 935182204 783169301 868901513 670907376 320604720 238562029 941062181 151786158 350210894 348082136 366092878 767129006 457161902 700382795 42414250 838529148 326382486 559047479 656390891 936295612 787761138 626979655 645255180 180107119 25853340 39854622 630776721 252505645 539947411 514682268 467379401 439473259 42785093 477017367 907493901 878245556 866453447 60631204 113784832 332255217 245144857 583582285 297226446 51804323 469533028 845139801 294407023 415023653 355651133 191309193 499106018 146449388 428267489 887116375 55738228 292504776 544315001 609466934 637327865 858251810 820467541 238895063 1710863 729885502 648269874 99135328 190856287 72971896 840827510 925612468 442529245 633536648 775765616 278489519 534427397 794806720 302607514 717976937 239428638 292366154 948498137 162666352 260713336 326099052 281054137 61844496 52275887 970477509 955307954 305314956 689808359 782896271 309425256 234277987 981960463 888058845 145779684 601780366 474624288 422961628 295962078 23829182 73951069 915960083 63717108 617463968 765043347 113306020 755622897 86127898 421355608 602600587 305170697 775699341 457150028 684776155 692405017 778032402 197606236 36960518 330846953 56365503 859274492 151640083 29656683 917965793 397710442 280576231 857011707 78363457 439816176 439838079 479427998 889661025 268443680 612790834 469543493 419708862 684507927 290370288 355937545 791303437 523031996 319234695 752691310 112183423 7926527 119114714 783728545 44213758 591014684 339888426 456889788 599150192 367171800 527480655 705974015 580724465 593840832 118412029 449360918 324760090 851043950 704897538 252644695 503927614 274362309 747382404 382606850 294033833 770078770 378313284 737879937 974003681 227809259 636442591 172277927 173894375 841546033 694374409 183352051 471939444 777307535 444493010 512914379 918996798 237435162 201001699 77841859 29718066 834193840 789677759 722429910 993911225 451732539 573535748 983953577 36123637 842986989 804694697 730071500 374404866 867032964 588004927 992568058 124463671 668351109 10713394 557268309 199241572 295037569 549309959 534488237 861863956 919597652 89722525 702130872 892426954 867725667 639287150 178773080 374851653 888309979 288227021 409944794 441490109 852284663 598741030 86061875 358441253 990594104 862858562 588525891 38648937 37653164 241345922 934606099 642536111 379237673 785380130 609798168 897397400 782573200 966055541 400806511 771965053 101088012 897794860 494700065 383779252 874136402 841168273 180260958 636207050 893892577 600561094 723198147 743630791 161144897 10529544 693915798 975338863 127387717 143433455 700431366 91659902 421988171 642879149 681413997 778743785 483874680 42675276 159593615 4850465 693871358 649728499 628489178 226192720 688203607 352834847 583724966 412084379 64277128 577715691 413798260 920048992 852479585 999820874 131190577 6820215 523837370 423794505 64384625 439720819 261335989 841912400 958662582 441993696 521825536 404739167 594144680 326649988 872088849 675915603 54043227 125352863 971749738 184345376 128352910 312128812 320152276 990468885 618301672 124238368 181877925 626296093 68899131 88086440 511422972 571824378 904759747 1854572 964711169 796410762 78097509 841628624 577017896 840593412 481191410 207566639 387231596 79715641 39828323 597735712 72554901 772813525 626631452 913998515 249076596 608079004 8394795 646569138 736281892 762493871 404837255 649655010 821195081 583743431 789922643 515061569 840045649 150893686 36741146 458735431 706258871 985767531 928889874 257492263 832065341 846788268 200248411 411765517 841845295 31015387 269091903 66388574 753910948 474721138 454657137 240690429 68158654 283072777 212262992 566063234 91420646 711785357 235240226 123080066 239331347 138759304 146843995 639080140 534627073 268828510 116395478 884193960 846122876 880649867 123623191 25880599 911976084 463858919 625537169 542208023 990678760 108188388 119624667 232627422 501602269 572882380 437116411 189144860 228373734 520338693 374090909 305880891 789326523 821526862 802376026 897408672 873312931 46810625 825845492 312967913 125097900 227605585 418827414 636114734 227870703 436440715 210109205 563955521 407111119 425009494 406215219 240760560 716344632 139896052 339294169 821694784 854771425 981645441 159611225 695881137 36370828 782129456 411845812 355291006 965026115 657046419 395016655 245239003 165280410 167128786 531927485 793219127 729870833 586386416 939767290 975089018 683902129 238842122 826570668 570986821 989211788 414477465 540392162 679483958 941530302 2647213 21824982 256230947 31201616 308421681 231115309 85000540 240691793 716215852 878773811 317527019 84235037 384303867 314425888 561078484 103599512 134288282 512057175 327641431 921727857 346369242 205018532 605323307 578185569 136476329 165410427 463293635 5652587 696395087 115406398 205529226 15332124 177517229 73565557 340426792 267391689 793382781 694004756 579207356 598713045 412418711 343807674 888071969 134562282 806796840 474169326 71249195 81123645 280793849 588760930 207502057 981521356 143515568 810887986 407191522 754884001 119976456 590832419 855471194 819874062 547689497 13934054 853955723 7429103 167258004 887714900 280023022 348634349 117967621 293107377 220619378 83572920 296867089 658725866 172070849 522843466 984459703 854290137 94772863 726066984 642104209 586936702 985710476 2609313 524466449 62115909 57910591 169896206 810049478 417092932 5809322 359007250 272975766 443584379 696973530 498390234 989819395 466481171 399534614 609001820 398739305 404938658 800206109 213452697 445836859 401758051 117937258 493595868 822160459 738435200 196413297 641336058 631633408 885145418 488361441 166330769 255940511 534080636 771557089 808670539 402024068 324478077 372014164 752219418 101682280 155435676 279254039 520202107 924251290 695720020 108090176 382410165 766381896 794324103 910952798 759633688 741017269 289282245 683449277 267159105 759328897 111611524 440096929 888535122 163818215 868716646 382044807 831445051 221396984 68893560 188416873 122881014 146449122 74357359 136393720 999528900 886202156 159458026 459264225 62220147 979438073 742545589 816040459 215545753 621453122 309606146 656826325 606146775 536995614 175405999 939057754 486702872 773723900 969547908 453150382 666359505 519599845 721847411 647354399 299439680 927558332 486660824 604834166 631365295 469677951 398424249 730767414 486700977 465503365 54448645 343447513 328437857 828087487 625622230 286829336 679354023 541420025 882333360 260542753 747591796 82938391 847435713 856988384 613744386 369861722 787180577 162021944 263345175 920159899 264480017 124423497 483292992 201689228 690584126 73242538 493807384 777986812 800295164 406020525 76998784 14152977 498128268 188496287 562439142 474849165 312603224 577636102 184637056 583793163 5007668 819914723 120234383 661079616 233879709 680964592 567008671 369842492 891212539 940805089 998157763 432252072 362888160 192596132 694690523 23898632 646896455 428111010 525573839 701608952 837560024 352906493 224231378 782921072 174392608 871307474 146706849 446927106 738078427 514696310 928289476 26163736 501263404 142116539 722387914 272557112 871878625 158446633 601000078 916021314 701348529 864659015 209932662 257581997 514450047 489739473 330043055 219213775 405676950 702716673 426654068 135141652 940636652 401829576 555843399 506483780 953445473 368318995 346301748 205574591 10906111 959723528 51244818 997376705 654487353 688118344 410179266 603496096 353756461 135345709 342191472 802881547 355712228 308247562 400207567 793840202 814344334 291742832 594505311 878243458 724881097 133316453 406080168 883293936 629364185 204585388 121463422 773811754 152444142 231557633 298277948 289325155 497617763 775062620 606485771 170939558 765057018 357310251 406221850 403894808 591920162 619005081 717236708 692646711 139414835 439967180 485158255 319151391 910538671 248332320 546158985 997351617 507313280 925046894 872833035 559902251 295773246 278751817 538747672 98796485 540684392 953563453 586103900 369581968 203526823 923112977 858516046 2632294 634866192 785582595 824447856 581676863 491289184 813791760 630994828 512610920 754066752 517954091 558277878 496244427 985481600 305876098 26193870 681860907 231917149 994200254 817195324 732548454 613285052 549854017 61373108 906866611 895899246 636043367 280978226 862592995 705704300 314810311 997006460 63491746 185501467 32107377 740163173 291814581 926692231 8041264 118980613 280200252 973596840 947066311 21422339 339885550 499656609 506396725 798674125 411491937 675238398 583695090 613056988 589805889 809314035 477781809 668461811 853200021 432380065 494061598 19639903 815782399 281229650 864680991 52494645 857632250 766731450 150611477 305500312 697823516 33784118 228136602 335352050 499617107 391546126 661436225 385967415 470449962 721099188 800483290 108997672 369276162 454867715 326612909 48634763 27178587 741155970 809636028 903063925 305950986 102911137 385427203 950100866 719109762 205862905 798277049 302327321 846638861 499230862 464519310 493693866 2206994 888529677 504706285 435314673 434557518 170210832 853413689 517378866 161122076 790211414 829801489 15515004 830310831 744811277 664544141 585471464 366247765 370234122 27406464 184313817 974425523 218743309 297629110 82649148 417694733 69629184 554541877 141991111 934830204 715557430 374514557 275471675 828697399 564091566 730606282 579611298 706499021 574995278 690935886 246776467 233302119 190600234 636891001 919435884 514839816 204965308 255733043 508086420 944000206 26074155 364973342 275697600 674539312 486001286 315841750 826202156 784044351 636872712 409986866 318650079 322134247 181685587 973772162 853162730 610865709 841126327 400381136 424116391 274024048 335263850 451330849 279933691 288880553 176575950 243772595 526985878 996523437 370707120 723722046 197970735 780074343 314783620 171499317 531752138 983286304 879887276 666723076 826882804 949678777 471804592 6322769 661085186 863641837 200906629 814916924 796485208 787029137 969018824 329114016 743700382 326761174 571503873 939887186 160228362 759220611 438855651 436993631 985749914 432513085 327252360 468097615 834828632 948628928 669642422 275298662 572494998 79444772 626928414 311685855 952916017 745589019 280857753 973950257 102550480 603481391 942242923 162571596 731841828 252058374 847181954 966692314 712514855 381379999 922148534 159432320 990308703 92176532 915833864 231823132 401432345 308797784 439335396 510977286 31750320 131177080 869031777 848358993 623447237 350664412 645081213 623492872 668092294 608083204 982259043 190917235 146557417 909381196 123671462 196674129 308849903 730581034 844969861 891666462 798790371 759374701 253280039 149578828 372382362 542327165 614234078 518165387 848491187 800816543 469590886 301663234 251209942 706358320 915950884 983151253 827379446 4662247 142206824 491955231 681846929 368371477 742805677 586964663 737042412 42628325 579086038 312541420 918189401 469596318 371268721 115791627 164052594 101476062 477748725 781877845 571647325 683773662 438522117 696272459 719899656 651292594 142607788 214002148 739038571 760219528 8120736 788921043 624184523 157104357 630979968 614495939 181332210 928902125 696050712 106830492 28842362 429637530 608962970 742469565 210477057 422085377 856889573 318250305 724918644 756630162 950259903 111492413 545385798 966344022 611216156 353469949 82388663 255393329 73717846 348093260 107420687 200020767 840302708 18139562 29552097 955228792 978166885 11227541 926893131 697040941 109307716 626448067 79566386 550911242 762523539 455456100 268548744 267664884 185027201 983195490 737387400 493535018 449106726 323667361 955078645 757387142 521814980 922531137 914055776 931374523 41915141 353427673 221485665 927130006 760363841 672962491 214225371 646212414 14673847 613428533 943845946 352471669 882117072 135081931 374745013 117025238 189085793 960242815 763649678 813657111 681117415 764067339 113753166 256822086 194263242 192149028 23981836 214718990 740875420 103285430 461181093 53121777 601015641 814438700 239751170 419573132 369508263 397651878 2394711 561527767 486982420 40516674 780567647 100320100 568712541 552311381 472320419 940333214 265278883 524039089 832063410 201570825 505705397 484263903 818809192 370684806 14944586 446331748 338559529 159158669 604785477 521678589 202643236 414118514 202147569 374700772 626423954 924443554 578240325 637379082 791043829 398250725 254187039 689655133 213011035 968923035 297164170 673877761 464597915 715883009 484429049 849855384 236507029 297694315 113047179 850584956 201757299 964761737 27610695 433580545 914482412 149118116 284001631 605196470 721421693 542802143 329388399 146513570 515363248 42025592 74242492 768750984 139407702 305778950 219028086 246311205 273284046 216528314 726387704 295618671 791994174 843480224 77681669 568419541 64464342 387149276 908133130 459107715 62113042 367358191 564978529 132731548 381832950 976144370 200823433 145588864 179933521 759581399 159402096 631197958 99375356 955794605 540818091 612259008 46483738 535095514 662689210 14669883 939168856 443989600 549129799 440039742 104577067 562250522 989932645 983226888 952778774 422205182 452431570 383808659 28243683 873678170 155085367 601214421 197013991 413729816 550558820 76450556 263771200 241594108 162188694 219744431 769185816 632768226 897518515 529733713 712007137 317065474 473743243 538085695 489233816 856928302 717651478 218353166 148802564 520598544 481435577 156089808 102728181 10614382 461001603 775319373 30393223 679339624 704531049 152538700 797141854 322303926 118887056 560422601 565975018 979622380 238503553 542689342 255148194 334230967 490033268 410056924 110502730 348332574 461175176 815084240 123882798 907424707 571979014 738048384 809609830 612104226 390348707 639451341 971989778 572862159 276910780 211000401 442931869 288181945 570865049 678594208 73850620 175311723 421511340 836749448 910024174 579582535 897670865 135636562 627084346 832587723 502334605 539365632 195397366 717884621 359090001 570686863 639468220 762342336 585545910 845999668 90481908 152671727 998497216 184940961 98481422 955767487 194127389 7081534 312054726 172588270 715016549 996395378 244701281 41642968 147540569 622962393 797306860 461619886 401095205 953872780 434419842 563923391 942664607 275294559 932778116 398155184 38880392 966763548 634069984 925504197 79545544 5224650 675499340 644190232 647566259 815777514 750217097 400139998 721256776 470892981 298647202 908234151 394428270 915264353 111785772 637560220 850732854 671302235 782011782 250847169 975406110 239532684 965660440 104492594 617061706 664322198 665858965 670459239 923313867 114165014 622486074 983594866 949058265 829570017 916865294 622890813 932902170 329162568 195431970 901522894 826926043 510918486 158088400 851665284 549515603 730372878 459873022 430318425 559875812 936373679 458891866 583629343 768635995 728510450 46178716 803320773 376356141 619402568 207417801 25474193 480797114 245041438 572309867 764111461 164463244 256123418 513630684 608834557 139150230 466526044 143128698 112392748 981541750 747635136 304616433 179462948 80642741 749631769 263112566 778897836 268386563 452828533 178245128 1711209 70829181 94688861 436822447 865883928 768435945 495201811 43908799 884328911 214401782 615525075 753393427 317554241 528377727 943026708 908598611 462177529 460349126 734920646 454967344 563770523 942968250 313912724 36014501 723916584 622872883 4692513 291602486 803594552 69169459 741568076 631077425 973702463 559982116 151645805 603148529 665449162 254430238 568161687 26185752 440405953 763318815 738987222 993953490 963224996 3291986 482490992 647161110 697602256 708761675 514069798 93719781 409326521 269289031 459451761 514133899 752553007 819998830 719157959 42640603 18845339 670509330 64420053 151072373 689103168 553464559 196028100 643027714 41954684 39271019 316082805 194361203 208913158 247789781 481326535 843763783 676278063 227701159 955817422 886356163 459823139 706486725 270572059 444609081 297864231 568710333 5068280 866130244 523837658 69853190 334066090 28291336 855950453 71222851 455606703 443404916 790913805 757348991 664445439 411784065 517767117 904104305 783776077 340561009 888200767 309622967 982003269 585821970 452519810 644356124 737920205 22378491 92382098 935611091 829688133 174959052 97910404 873190587 871883721 290695791 688337864 329594778 99550571 127313499 389222248 985487460 737873787 980035021 27382085 192052340 777903809 448226318 856197727 741198543 946931903 690132658 150140427 815289701 632656113 432613589 885052732 658230353 694182414 24972381 150744508 424172822 539904326 791822140 665577841 640758241 301580675 766485677 559180699 240272076 306486954 126957172 878222866 153049366 657073369 690930720 972629641 228280941 82027944 923750986 24401871 712135206 897216362 359025621 299798795 100343425 815321707 944011566 401993469 122935783 513088048 525536138 182529346 203707437 626746044 920046124 461521806 175769553 198259143 516515230 979700976 550596921 84315654 486530292 320135955 161381369 548412520 631667471 540639097 230575627 852946773 155362773 799276736 666045718 773413359 693404027 792623583 871900073 202312018 283106237 846062439 110398590 229744597 20533538 283158211 804660665 5954631 118650938 762827130 146666025 4084021 245582561 766303850 217474179 656721952 794909563 57461516 487216812 235500745 704091192 972295349 62000877 754187367 612569167 151037392 917176638 360419053 762358084 893431078 286058621 477178438 643828771 770980632 954138037 471969690 887362756 178517217 943444826 230181001 976080647 2252758 979938953 187051628 193027095 134347943 971166794 585742744 742528937 117446813 281116879 29156508 463049531 719588059 67779252 861047679 614102871 465342368 329681471 650921733 820966607 530668929 169382558 803847145 699386880 605788848 915827501 712880162 708958225 471395897 117953712 822120991 176425523 52354369 502708882 853004 489083104 529299016 87786542 618067213 426201885 876200549 921431556 899647616 80121785 269286030 684601600 975141693 677165198 681543375 635479480 549017302 976785341 2785167 37641644 774833881 860630260 483872464 123952262 787912203 561965224 344895854 28204377 86596012 321481053 241208924 322447332 671580855 856251611 701226476 497012174 688336160 996702584 908291333 525673961 522879254 829089618 231929964 478421360 424534080 366837139 794782206 893781834 137607938 179646381 34134513 963647303 392806327 783165086 558597144 808530783 908862453 209741355 991684382 129742584 552694222 851059749 91724743 866885151 543624459 542717865 993403956 869062347 914499697 91556953 995470109 356311582 370607869 891572134 297860374 948629925 418135337 87087623 13755340 436475541 923064359 654117440 203769671 216741134 487543074 564781214 29458216 706257241 122229378 280638007 21749737 981295915 310328614 451151917 29662242 317450466 242342825 36593897 284452287 926316740 749286303 323156833 655008076 369731141 960532182 111170644 197488428 553114431 997152920 223578506 733814491 550381368 946923237 533395734 133701169 357880994 809648571 960544918 645050015 913710100 206582863 821426287 360398961 175173011 289898579 650717459 27360780 54037453 668643120 878145596 273107247 181161818 500037962 129080880 326714931 116381179 180536129 196432636 5078861 677172189 519580460 318444987 848307144 342870740 139555293 682317775 6493518 126715298 476064801 490049059 567488798 118717743 427446271 398824049 415205716 266499536 297788406 712147575 222954533 68485762 568773697 20389186 792837409 928610861 842863124 908822117 250403954 406408419 775068381 36244288 411243545 283834144 868272518 297386555 918801718 74996489 580919727 325160970 296078142 853410735 751563510 650932456 297430852 388109899 16248880 462575581 396944178 94167937 615917230 1559034 516717838 936086175 294873467 20571546 491681336 185793244 656954011 841037217 483652264 65262235 119300683 14193854 10841138 432863911 750359621 527775914 344149443 212937078 756389626 600866663 447829155 399886440 543898839 916236931 102136754 116099335 135889283 917982293 651275948 711646791 745215773 716776252 408493927 901021124 622350719 991387365 173158674 118673672 125728639 371660675 676904310 160712900 511395371 961280278 45102134 844535827 44454922 164680871 387058704 167494076 154583135 673142663 140632090 849353583 234940519 293422229 865994503 95017220 771326615 557452151 756952162 376744897 218117089 258311645 484147152 673206162 675171565 531451074 443035728 694925904 705007970 541321644 462953851 105323773 751798556 257335785 444202181 350164228 633584501 124687314 690024636 952726395 490117246 710747658 744227910 315061857 994518084 411900093 263466469 526892514 838794765 894172899 409844468 723228048 334568858 99626364 111600360 784663977 412940389 640295635 638597777 468816982 25527009 200265148 127426392 909762791 56254399 40358103 431627393 70603033 440171301 334078413 185231976 426577490 646047222 715497104 916852165 165613793 387315983 871367836 583319274 977515840 202102917 899105850 102729985 335312723 265658601 889436602 504351056 235936681 77653126 217004725 331763830 550822583 548889247 443402579 245846957 422281250 717124787 845833088 593928200 381461491 568928699 950243382 314831283 768954338 86213480 563485880 750356280 634327181 38104423 780145106 75347638 947141311 243815582 222950172 551875369 302167724 885209198 686917686 632709031 403916593 688995312 165557771 989684895 914729238 622766394 943410703 843954969 327661133 955465369 262350723 218670074 901257522 257558486 804721838 125915967 310715850 198022515 170924066 984074558 183681286 605837293 986835966 594049002 438518783 484089 558402344 157102606 945983801 959949512 611835537 104497806 196166625 914031429 117700211 425958315 146777361 682418515 677669779 982871613 590596873 30001169 48709760 717833464 785425525 818000919 8384724 102507433 404561835 299933368 342753904 54362232 259217387 788972352 45986497 298993446 588533919 474190389 937368575 180034126 276373146 187272344 82696298 992006309 667616603 743058211 466053005 835960379 537563208 788194697 630824829 537902009 292163061 646065594 314011161 462375330 222377821 134957854 842134601 255327124 333788453 656199639 971557184 434171782 571958493 397411841 633448891 329310473 889372736 144772340 744097089 897207945 81122928 704406142 295360355 538913419 19048253 872474154 269797627 691197678 69729885 316885629 873110382 681340972 366590130 856154165 633189356 748182167 528128393 66096011 775984812 581306782 506697175 430196079 12634674 711143687 180348796 107977424 399886475 632027700 305475201 784756691 778361485 249326432 881724507 544590105 245991705 538696417 655556391 162419963 699424347 928215653 390938350 304359119 960480006 97767990 981038304 766776354 51069337 233302648 841738394 688465405 255138718 147268200 334538082 432746017 114000104 163471260 730563943 643231309 824755922 972128071 629446915 147620725 954110852 62088051 481573882 905438474 549008175 453194310 339982010 212253750 404383053 827819840 360680859 774228766 474143716 620294777 641835550 260713504 911282370 255287269 400495152 412087060 86271679 698490513 166282597 185341069 590773503 330083300 721265215 14524183 237698095 646476513 28592998 72487544 817840582 800810337 786887918 635927792 556367171 884340059 42951574 65777274 477036914 483955742 613872645 993944075 14330793 255514003 713383437 228348112 82167556 110460285 379895786 959956849 729258927 681451706 430721921 597739346 540488730 799449729 865100195 174079438 979470915 214039971 754475849 177592700 750631666 655761355 88490199 386717548 480207094 615216320 768271195 983835752 741299306 184059808 187432396 783944245 38627316 309579301 106865229 327512273 973908482 93547489 780535145 335722932 9990157 588240770 7598422 104173841 244054487 276375056 642331956 84264212 355623598 372293676 112385101 58303267 883850408 560937809 969272660 662150942 787585511 521158933 579002280 533316256 897142741 448224870 771651215 465910333 464435302 916543182 702815357 713687236 495760730 416523696 429815884 926252157 115690873 925139339 933345411 781828202 301464023 724450100 931013778 861765511 1332495 485797661 593697297 344021514 749596810 235027602 614534150 729768101 953658295 286539512 251338269 655400897 941723474 837006095 68099055 883044035 428296351 962793519 221135934 586911049 567539885 235504011 884719669 572422251 156420500 643579250 826378409 794883068 363054521 970879627 347677532 481164743 644729095 258700054 563249206 240059092 738957366 746372655 449395852 694968482 447038470 898339084 626459740 18720364 91911809 44746300 268244364 439384167 536964158 662772967 329184047 724853503 29467546 916459026 26397377 686818335 584082942 865657306 775649640 675471463 174152478 161156789 30197043 662490229 687689270 872763062 837093980 666567199 80492365 286144712 463382664 452633525 790813299 289807855 194435075 178671425 206102788 911284876 661205765 415738824 102250724 709912983 844346097 964266631 793234882 493945829 883173267 377797688 683195479 703383905 732867679 392990797 800684454 5725780 129792951 737405489 564300859 347643550 744608803 25401996 959152494 928173308 602512279 610472573 378511007 855947330 811018930 776994527 424649848 318158496 279370235 973670790 511029808 213530847 505048356 912355457 100975812 654726562 766181961 209908567 988325950 461979816 867536687 337145420 652048112 76695558 763154055 975379867 332264119 147663214 935761194 528647866 417258554 299006828 678606172 762793371 641998377 165639845 953513994 999891431 79248512 952724248 594949646 937914434 256180163 205669215 653372775 664517004 746306626 814986732 544547460 920835100 203069780 529854030 351986040 242720516 854892701 43891307 155315012 89452370 901131081 767080389 602683665 462093642 534356304 152666295 623618933 437881774 574053554 927046071 724185003 248606456 373220026 889878163 132527325 80332444 143975229 362039734 647902555 21359689 972874713 854108513 609502691 481988390 247271736 131231988 176115929 876971287 123301452 383206948 641418637 243401206 90190738 847027780 429218682 335460060 705189969 661453182 632978306 556846423 24098266 261116441 238608181 921064115 251045063 963368370 442439177 919588148 314549309 720297092 485399712 843758423 927167788 617084578 199209479 416750358 794490251 495970617 760909555 877851426 746540446 256751057 499630339 2904105 724354866 84304266 571685891 319652879 583268573 667183201 794648868 647413046 592492352 545798250 969174599 77245368 256943174 862200085 558372145 508491433 711182948 881024106 873561301 61452119 481814489 384136271 126589583 727824012 548729325 555767231 981600613 322471368 61158963 993948689 864095558 342021769 748462536 455946296 240471116 227732356 39838355 138992639 827611643 350150634 593708165 73319243 903929473 933322406 244186328 171650395 614839798 27508636 230863186 144422920 745816475 777500393 586032001 743342855 229853980 714347559 863929341 679875363 657735632 2572711 899332010 468298117 305749493 876454838 483386101 345479406 163847670 826457050 836515604 116868345 560498599 584884244 43948873 685972828 276107141 83897886 117760029 196480293 194887672 361427116 860257958 728555518 848769170 826965676 626960835 690044266 419334990 11397255 804745564 978503688 402564564 295418208 439326628 47216845 849895601 705288273 847216217 791523404 293015201 500511667 124552704 373357039 260692935 486501460 208165163 314470716 65319153 610108096 182499252 104311058 350169814 799745658 348494337 683303147 341281113 794824513 129239616 759106586 216820421 700495438 71483306 755547916 351651088 493426066 109166017 410563208 526203162 737572090 840877971 292783345 158287340 210404780 52013814 959766400 346992636 291528009 826221516 34404748 909903973 245442859 438093630 708986307 838761009 589171110 104584963 389331312 874006416 481325896 322502295 5393845 830938400 763011610 214452358 277102287 893332261 266567902 751578016 793876311 82966735 223968336 88316996 140940669 911960440 471178856 720487831 230558285 100223461 325834644 629100747 801724139 876789122 551565312 368100955 504055256 377002920 230035663 846172491 594611756 937876185 160709984 346601578 199231195 552840703 115422347 446749584 395708915 357478834 688684004 874526946 427644378 75137905 239167221 705887755 993874577 547628773 412669573 55666051 690609397 821298979 793370068 558977993 390266362 428000744 714669534 620983978 205327344 530448604 70902934 640606841 191099328 228876498 669572650 281071958 946895918 998586116 511121475 611027562 911749398 85291096 60305731 211231527 74825904 280671903 569439622 202964105 527554253 231928274 835723427 244849753 711766553 359018838 573521579 563137126 960235865 511786295 79465318 167079884 933412524 572898669 472497562 644753967 644817100 20566811 183283269 351926526 310388812 429575629 994097120 560437426 351270104 907377847 615969692 699763214 906476666 321187322 216827558 843419486 17611985 702147552 68554084 928788410 892534361 624034333 356715702 720720961 787313063 940762894 310479160 295625568 899926700 496276731 19426428 578800139 12453359 308385621 660254802 148453632 31039957 399796218 695367682 301433865 787080154 998351982 277064078 599927095 275559383 955750178 822471410 722273833 867785532 777154735 590232933 621931845 437553748 90353433 235616408 821447419 878514565 227922701 473864179 462516999 568257679 911775013 523000796 864761773 525022666 587029280 946400497 550042365 242603882 74682668 364166474 723845134 827258044 305268510 572083642 800899140 955254632 465245110 524446477 573457547 247910574 74009566 50412361 693587099 734749355 420571625 632303854 855043636 773537683 484739798 17258552 760597601 953738998 985234827 305946201 201145015 244038397 426597404 750659777 681970836 879939499 151554307 958215256 125190754 497187870 580515943 415769280 731944659 365698509 396074839 22925205 697401380 602848201 519576334 928147374 491629916 975615486 118693422 510219355 353673611 802455664 203015687 159433382 95456525 838575744 995943374 916349588 799298246 125215271 234975720 683997795 441890150 729935159 954238751 88363467 128085156 342477983 39764456 270170431 314150020 827423653 499134885 902239019 972703379 333339947 365936094 909783861 936257831 148387052 921334152 947698045 560111777 268574909 582566464 774567903 977864876 485916622 180949902 825380141 309458301 337565161 885881893 408708215 943185682 677708975 254912799 554701892 160186485 72449247 66818370 35937240 485109497 224455569 822640191 833047150 110385529 644271476 458932719 890129021 72528797 502624278 506960790 703559925 527103765 474360602 892525858 955674240 633229534 890110848 553498731 433258179 406230138 74241762 537667698 72482204 280009018 657431731 752498339 430777443 727505781 702903680 738323477 944708907 276366287 196815408 152229574 503847935 193669749 480644934 464266465 420315687 706976861 926155803 854022137 642472803 962019977 661227046 701189709 317289772 355411266 254491701 344744452 92755447 630347102 135791539 649655920 240251507 446161787 823279074 520522061 923226823 348790084 894921504 375930880 672384471 661619369 12038179 136863961 428078206 574069544 118465854 54013523 846732499 286817544 281694620 402364497 713554278 483423898 165691522 987473761 758285953 458217849 787199118 17050106 701265769 180313032 48702204 414910910 511072155 30151544 870469853 590132410 293511697 107296641 720635999 385486499 477590653 688324389 579379722 990826521 738752138 129069362 358092287 940867046 146292000 218934590 727361849 926801469 22088606 725361899 261321933 102218237 209957151 192729378 668042539 276122092 901228984 313284953 200244572 162607102 711863221 411787471 119672899 281287821 345830625 477542348 625036766 56780704 794994108 440312548 790079109 682818598 152768196 795532338 586125351 579343162 652349871 716013727 849399697 939337054 247634093 678217498 80861608 537162689 105435560 909472734 11322027 693757819 113079172 451197361 711694708 404767950 395359585 596368161 940406965 8505444 388704214 106588102 172982845 862444181 989997109 356725125 864123443 364766879 866403276 95166409 596283479 44186606 683810591 174208202 188857669 902071635 686299953 943430343 104530866 629761103 476907194 223332685 712388015 898276423 63707503 773497455 332368355 732985806 834466622 469956109 136372947 156861920 130006929 107272975 852157980 945474850 218464392 421883049 120977844 892104997 407467073 545369495 637050158 55984034 393609234 691233631 490977012 541373374 262621130 928440211 765410189 831027013 43514101 18518798 680508630 320716271 252137495 428643636 23968074 555197599 213262317 787141428 356117309 172098208 936465073 241346375 823916570 324809961 797646677 805481968 624263081 366105432 946953924 372029243 537239373 747417080 120992549 73818111 792371520 575470652 420518681 420407070 399707607 413294147 959443194 146104514 477007553 725355028 660802588 895071135 302273609 606373089 22312462 743057974 387299985 143226437 704654807 686718477 937673431 996821384 972583739 327914233 898325682 745225431 613162996 237109846 278120788 125234318 720042235 665760330 194889414 951115888 956878782 434287368 797982000 433370346 665539945 398181896 966548496 733175381 954806816 608848210 341447552 582928947 703488064 256800434 33842546 248540271 191229347 590054658 942962421 146979999 682097370 707653989 214750575 768951619 990683762 796503687 329666530 865944325 558309938 361471968 108629545 674292728 298544729 163547888 509056569 330405082 922640610 294205570 295362402 291446868 45032640 290682858 79437198 638421046 635901220 722623561 674351230 629356221 338351284 482639301 597149970 215132623 955732179 204874963 217866879 63497275 166729438 476505967 834385304 782992636 466087274 324142688 842101255 220656756 39355273 538479734 562759570 42619315 527685636 261309901 962321240 954124718 910407839 980698890 862573843 345997450 560250201 24685210 614787670 102438608 872593835 702742007 498993614 700933816 606759878 319638244 774901891 693172065 366994903 249879214 793139989 289896980 109775173 482336619 959652608 173636998 391800814 353835836 634705882 590042900 140889455 244616588 831124114 622365190 798329435 790638160 743580337 824628430 403028864 56475974 733437338 534870600 385046823 554991928 450719690 585028345 268695635 865090360 608951322 350365266 659641342 5208035 707934970 80365036 615374433 643226784 379538358 96842443 996367402 848919264 966162354 410963613 931877828 153079133 808561071 857996026 847546517 47642460 871053062 389336739 699298361 854493165 157100265 500059844 16763338 288719655 177169830 831163955 435170073 424843630 627668453 993460913 795057139 771506863 955820519 237783589 923712350 455676320 87253703 590580710 487604955 720808706 534034362 199781872 359476131 584202464 299836240 669153834 764106732 303832527 376718002 113786280 690089507 839958574 725504227 82189797 316133937 942849381 678154754 513979910 570940600 862667047 315561092 913371163 466705493 104830130 285769851 524785759 848919773 614537227 755820243 359129717 793303713 417831236 679596689 597105835 750130092 269201335 487377428 663534392 662451969 257358153 491719766 599443326 803853279 799050666 728433706 222262090 824231167 696715666 794024829 540838929 844812754 553369091 462134934 208971827 596281797 55503243 647017815 747104314 229754750 172858752 598251643 562909721 332606494 914239811 208504024 99841646 939934334 334866816 918512796 918315970 410313332 998265706 462430354 193556933 363312653 755160065 555217244 74891924 793051858 149054797 959871671 705120757 540823813 743431585 603831484 760311959 821811938 321591003 466218779 554059605 986506208 685247904 829878879 935530097 572561903 348294306 204596015 464538842 993072314 8360923 463019912 970795880 100344548 447247313 707475461 181122076 607206732 825671890 862323993 734975843 64255562 365636663 291057234 590868818 138031857 361350050 776339349 369232104 145493581 474877505 721111654 510391120 117369508 444829706 628449567 524118302 786731191 157363455 50140725 372288399 54526207 843752041 851161464 534872011 577831666 19038239 734229328 20249636 594267197 530714046 808952835 483221846 712911881 233504239 649638124 447787975 404957752 711578533 851911107 892040902 473694886 292630366 827127257 932963789 389653610 812435039 594879834 604723136 348473620 390226427 186232970 556615725 385258478 963956426 327915274 594794123 886033213 182356467 483927827 703387517 583127423 98348644 557186744 974782990 334865069 124833302 689291557 306572532 127987575 193805644 168224739 941515216 674175116 600695762 240049683 520834665 355671505 438564927 804417968 428735990 663330215 992603957 389661392 84606547 160761895 56391326 224968929 562522951 136238694 382936302 408517613 929492934 460776371 276709477 511414744 819604779 143409366 318888524 264088478 580711035 370553681 108298804 822837912 771990950 685615776 642853180 265116085 161147079 335969146 448040266 63493315 874138977 755703055 793680462 792055717 204962721 749307977 337204612 231177627 178875808 728117517 48864432 374004351 682713248 830445945 589552481 681479684 171400268 935393061 918741040 276294903 339909114 34538596 535400448 4136576 779719658 714860418 908780349 269127519 175425157 207965189 677849375 45165873 660670368 525646317 786430181 589480873 784829369 401357045 172193564 255693273 331549494 161098706 277325016 118814569 9488810 181315952 195774711 319429084 488552722 635549754 462817635 835299792 521343761 735683921 285410382 420402235 605419066 229774289 956470133 755963312 94655812 821019665 867002718 192329114 846124628 808808673 946253468 726013822 499446329 16885963 159965448 702255162 403921832 13912404 242536711 831364426 462620806 145659449 247326408 643087359 218673948 107654324 448808324 85901512 667311458 456058551 193352382 143187563 380265526 798319150 856423299 899952457 378846371 758780478 259323817 862883487 83627293 193718922 157656849 145756610 996669633 834112106 776890085 805582176 656715927 163089459 659765980 931941571 752664785 137291892 471018100 775991566 194563595 29152564 801564724 257342591 835557003 766335287 632497905 302798253 693831551 61898040 623514887 710192842 222918723 852094766 43902365 216436960 584419738 249614217 908067300 892570901 933047026 919109235 703327318 549757928 66634147 219196688 724519928 453149299 94155822 319841472 115681178 594413481 792030591 194409050 282595603 262839191 80298028 949262705 572844167 358989476 960381365 10788752 646191011 69571282 448671684 986477439 836694749 461840124 102828396 233832573 480039606 778248728 238441580 922248069 698089721 58782837 420519531 820584587 561429499 9875195 787003 250403262 135892955 4372079 15889175 337436357 307092417 740398254 898328550 787842564 736472864 369126894 812757112 334482390 571263221 628149250 580721349 380993489 665789703 35021204 908773427 933609479 478072103 895257963 91168974 691262017 241411695 341182373 890721936 455654212 553992836 722288379 379529880 981050381 884773078 451578881 845867124 906146582 324872157 236189284 738596185 120641425 454384731 135433260 397945191 239669929 128174750 991239929 700872935 645571782 359685052 926288200 677154702 77817031 367681750 770226605 789811130 604751687 928617559 420922904 303036337 82384346 682193204 221139218 785519334 299887182 397810732 673972990 88572726 702265837 373247751 769838938 691372580 605934263 843632601 414470653 200542754 230161066 456931901 378764889 594037194 690425084 612320411 223107255 618455326 509058908 351347044 456145791 418390221 37080886 331303506 611016303 208679791 475075822 345706411 376644577 252153029 888979745 352075645 858020359 415699196 575818729 986967265 954605104 79857128 778145815 119477561 300675586 342156875 486252665 65611123 835105471 92434701 258886419 406684997 402073730 795448451 799312487 851163761 177945985 624858538 439023279 896654336 724202826 100329322 321660703 696313736 78796295 399931861 714466085 367300712 770502076 530473831 110164907 690146056 867362694 758796869 545579601 877008924 609618139 878134144 527976117 83042271 463398094 870125649 784928684 790975322 370560841 199640924 29213832 569862044 704537170 366039534 301528657 874082560 791952201 922716993 947440398 678569068 881960486 71694261 182913275 304429198 807179965 871045142 8779730 646569759 465318395 955935450 213787652 674233890 504603943 591311201 540305919 770031907 915222820 562222901 326342503 321717881 609633707 168082249 149469790 373803654 988426899 990808892 894773950 107664627 136014603 458813077 466554715 144752119 623459547 214205958 323005763 82136975 488021928 146394282 659100415 561005764 759181359 742150472 781656017 432628458 660214151 792133520 851332854 269544668 746089057 545178970 429720291 198091843 196183113 760733676 177672842 237327566 318041315 574284082 428300947 102046073 952674608 847885573 137764005 852672968 349514953 909216871 920128156 96570122 352425760 185632451 329713618 798250392 313410756 134798127 440297048 546076693 991269019 320827818 258158651 685199533 846445350 623272032 269796545 381531735 465798082 164540643 337734571 544164373 280863204 877555569 167061107 834392625 636406874 885137970 506194317 148651392 340949134 322767481 865052071 227460256 884024771 45085184 691338986 783310650 347150936 301435950 384574520 133251906 515308290 314449234 812907118 968323636 122944531 600471014 661229473 55829591 685772471 956389838 972344418 735241211 451527731 590812056 83645180 611873468 450675495 241855932 488186034 505615038 146761930 741450715 674550531 975631344 188451890 791379458 567732968 358999371 585865611 79325157 939521042 120262674 521060188 495669286 868647470 353241362 550200264 966235533 189589538 121471968 128729032 905263695 533346127 726767647 552085107 128332617 196306639 562351801 133686327 81786691 999858869 889337123 856530975 507475503 463091025 765655707 61930253 918491240 481593451 368931691 720438014 802159606 24995461 615596581 58446923 44444103 43701276 574626534 812202212 589943541 58402021 573715605 185131412 118525955 762870545 672452642 652523330 769250337 671859851 967390665 130568235 353521254 585266742 44429903 568974635 157290259 515350321 975727169 499645171 779445972 733502485 267978041 52642641 982047743 617670707 123747610 854948973 29081044 8816855 116830033 770230279 136645053 306680970 793021460 942556860 651470477 26060873 647117732 966087488 962712003 324057809 657360268 711552419 931351237 672487892 319535585 317484686 790745639 111997250 767053953 67653764 246432995 681416323 731553878 927952163 411693984 50952121 849430674 495647330 942202350 653119745 50606578 53741523 200107909 230776240 972771325 319982560 323308427 684058007 539142212 375581967 262479308 9884224 290283937 228187455 367357442 292844080 936817530 710206697 708588300 692828197 868405500 34263138 220013624 259113560 227728994 192788246 45764731 510036922 84985901 663107788 112296884 260950327 903189099 811268326 523706351 413820663 772385778 304709535 903781022 796941210 97513379 358917964 239278559 474798969 566390185 898960798 989404090 642435050 477061817 237085404 755330402 444001914 620705618 459709227 999473265 415152178 254795516 787682759 168526894 817146068 318221706 544673865 508357832 16531484 790668889 952178144 65750169 550178049 301903761 452345498 918669669 991064819 421670752 846467226 520022938 314930972 687513924 13613408 179964304 463527841 760877375 116107526 303611080 612491488 878250786 464541567 825988399 285203121 4441541 284295641 921567833 764104103 295545930 20450681 115216071 340273230 137640799 225610595 274533156 796150892 61716090 493191024 31273857 572884545 134265628 193237911 65858718 108939209 780070417 456865575 753951522 169732598 802541740 548446729 676079839 388972536 759022093 251585536 394370065 150212727 641428572 66937321 253974173 778640084 879963660 652180733 325166932 159411310 156451099 719613964 403507503 369437144 992602190 621541058 201567378 685922341 26706551 295864548 248978058 770756127 607314353 994758033 812483601 924072841 789043871 998805634 721131847 859591265 130633138 840811852 780003000 925477922 892270178 112653466 86614682 776925947 315851889 20284789 671468557 815484699 493853998 943027838 393522267 274572263 417036973 681394480 983390263 206379839 219182352 33528096 226248448 205926078 271397827 216794942 439715324 874054393 874462905 334776595 35407263 599977660 98746290 189141507 39393987 525928530 888550775 667098762 773239791 68425404 774734617 607363456 923427987 178385654 872739127 150842711 431064647 693964087 232878390 440759641 938722321 758711854 424694920 302919404 503598493 100707400 946031592 963676367 200696964 37129958 869248666 838509660 992588680 894800297 401956269 124699334 280761811 659893672 583199546 551358554 629707837 773445814 812663204 440682431 524246149 251405470 892363991 395270456 138202260 34595432 531154314 325189086 949117887 441847699 128597119 299692264 253228036 704120154 49546688 210762468 664429897 243746290 837475809 88696573 641493153 450710471 613590850 87365685 715388296 34917060 888090444 283219113 868347684 462459786 550294961 862149330 482200964 784154805 555669421 697528000 850987234 573423131 143396169 194586975 149937890 163899918 179292308 563150771 498740690 532762263 130244330 616996381 893373418 216301755 592012335 1678741 215664267 992890807 972953106 910341359 717597058 343375941 22599500 357696025 930813507 892658135 763070688 890074456 429239088 58164696 674442586 229136016 519636177 724552944 758296082 702896763 388582170 212550206 797626984 643733998 670901930 903011997 916894983 701762329 250990600 47080929 190918436 290495173 784012518 149516825 402047933 715647381 732453728 363675340 220737243 150844743 358496571 113756222 889775826 354844146 153994024 870022314 296664446 795925320 677724160 849377670 972429702 265254866 960709639 402424516 422707611 372694584 135120426 913555981 85157302 217772153 519533379 253178374 429669471 287777580 496252241 924044 263835618 369910471 663783618 336417529 486825881 94914773 172761516 625223518 8305959 61297472 11764493 571336137 656351161 702593927 555305487 489927294 23141189 277659142 498938183 337775167 934234060 560395571 227247603 734524806 226050713 377564380 178592058 921875399 882233216 915719019 578150253 20488881 695700002 166922020 98613578 863952747 91950374 546829155 712286517 72710617 954121087 694889441 700599422 366353877 69645738 763450350 636468896 811804280 803934958 949509557 657164413 811826513 994927259 101249916 635148708 473349545 581562189 38303971 774985101 595418567 940364841 906297890 197709530 857824807 514499612 321014093 811861142 481413827 401871137 874533777 460955510 950844493 333601657 621383798 840534300 256344432 637207793 692820252 68998992 638149651 367850529 414136704 702722887 227551895 483543978 717139382 426150623 737090326 177857909 558819117 244171230 31252132 112060920 793020912 134638391 774014607 721553265 770808801 800430150 186051489 561561898 126092798 706902545 307119962 698922165 176788382 575899271 198083896 189946160 34650546 218098626 644992496 595986560 778802182 497246534 51179188 886945431 565743231 404579137 868508268 520286895 466701916 516427723 412575999 206764685 749634422 301925925 45553289 592765377 832814465 678759931 233260196 837808867 167938379 728568996 305563041 998653141 682248186 217753182 788601293 245638661 406118480 489948564 640542383 308065705 473775080 412345882 165251142 739204354 44895351 43623533 925923916 391775387 982787341 320563445 397453175 160556938 763309908 790045507 347679924 445507243 840435917 867869013 904461421 830485481 850576919 231769295 90842562 575711095 905498154 750608450 28595152 288109840 212035477 646881895 680771823 195113788 464811973 390236514 753217517 283719820 494236735 64852480 656021334 548516571 746932707 132445947 487462573 703662220 434877481 946765363 678279089 789680592 130128485 324349428 221103003 242472415 392165123 24827444 866619996 633090619 476097741 296569299 603206113 171506674 866681890 256209370 412659536 822391003 439753791 343978687 401278026 722731221 49213559 770420125 59808297 231749389 414732156 683061118 826961217 23913270 659919510 247575186 336352288 879398608 43845351 479565175 172248783 822392419 160444079 533150321 722070544 413122755 243768964 369198768 498635936 737306187 829471383 698443150 683371124 344611364 929941491 645072 866302973 421986173 19209663 471265506 571582822 763346129 898735737 211731485 197002706 328882982 866250042 526813187 517880480 782022986 271097078 121335166 524161193 728163606 576273850 860395814 558916478 4802732 780176366 597293178 632047276 56111547 445272979 187914019 698428153 79293623 401229700 692110902 39916454 589834787 195978934 62385520 743824300 975564744 290943353 318784121 647600897 826090493 433112758 781748260 88133074 555110623 895767856 456581547 876373448 947516311 228125381 305991668 638111045 199528345 999160748 703296720 624018085 506625505 541457335 630565944 537565055 773437493 355887504 809930640 359139300 47798375 890182141 862673126 187612060 194927506 492314909 630407730 790314349 839736666 395145130 728114325 802796117 158243118 726191670 777812379 366651085 234225543 421969008 294703227 853739526 603872040 331852382 654530899 853502765 546442845 437476770 696473710 230871720 675744830 740353719 977640832 881737559 940475883 337662003 778551526 878263254 838971855 484391428 246460135 544168887 450820830 839802037 342296823 160048330 803750360 782846120 439224561 886531159 96653958 380052314 210140762 4250720 46910202 231120548 103574947 714846946 91196113 340268021 595610981 541064978 954612337 131423643 248260004 294264481 590398541 651694073 343196429 919715065 811767838 277806288 77286457 915815039 340683305 246376568 37613802 675849169 348581501 897102629 738386763 375532295 566985779 582366756 221965618 782001908 332570798 824468765 715531615 377095268 284661979 590120784 209046716 300639581 829031535 365982938 681451932 482647648 1773869 836451823 151103742 902063014 847811103 342001182 931102152 541547621 667410650 918754706 908589582 840635913 496858812 492314189 700489802 795886461 688640047 332628333 966708899 229564514 401636325 875931241 497142312 120773204 487356443 913801810 688676884 221320234 542557144 182381844 461258505 690660148 41119789 569999540 40962646 735919229 837564276 838093457 305245491 790983176 700956306 717246116 78753282 593995795 185656374 154012866 2139021 897752665 878384666 670029782 681928268 769872201 744002111 712161065 970476958 222016850 81972274 126498204 790064396 264284185 641004619 294193386 223417739 669831102 57680106 278695657 976507064 94236701 843311034 667079367 910806555 423491592 55451376 857035342 333203558 888553103 791386763 785731874 696925877 137529402 378418579 680991231 303184334 816102474 912065883 72174077 122795872 440671230 348449472 542149070 357758789 65841097 306842985 746344188 568166081 585946270 827770119 264793901 373039554 148824870 471325844 860796257 780621344 24431366 857840534 265278256 209030364 437834268 804454746 340929549 774276962 941938624 25605691 264114823 168483017 78649349 713266906 548876677 164969231 244509431 118096229 708460423 247384671 283621851 797112530 476445674 884167244 605317236 353487906 726686753 769860885 821827642 110459808 967955710 98591969 3930018 266808353 848297449 431508226 608193883 287748676 669601317 835384627 862626701 687673777 669186063 351540444 983152409 125323355 506526304 104345162 332661981 672693184 985122664 664163833 339000047 474632741 971984467 477542348 878789599 806373852 915059301 277984336 452262903 217764991 155343423 618531327 11345020 439771700 972128537 109139064 101222635 350403816 702378504 712994249 458735678 556925846 949905719 362526631 328856103 217837951 313837359 208887986 133028946 20248433 429254672 132385204 877692836 440785155 99440343 924795104 647217536 239576532 304449177 691183381 258181886 238079184 311755716 795915033 962596915 933762413 486648674 53173984 197059950 210471143 819358294 464076484 238563446 986780554 522406046 157676236 546418639 440010214 57538705 604967399 345224179 690987034 169718305 853575983 667130523 473397515 164077592 557747497 713044982 232712107 593565020 172253953 467433966 54389300 775218220 421926352 536656744 493236588 884862305 633319895 472132993 52452833 858166192 283895747 342750931 242177324 713565925 852902889 640627376 195374383 806291751 60497800 259691619 134162265 84140600 168063500 325731444 759628766 244711603 404826182 484841954 490505473 564623694 188025782 350245736 276878411 483550744 141992900 708527802 251573202 627201977 466723584 69649863 987609461 670119606 653630567 403915766 266140701 516651691 208932510 415136106 784903419 991690129 629355830 658814528 557041870 787196664 722665960 853068750 208587548 403929419 106465753 633959907 811169653 313178896 189532372 933828107 831048884 815997991 668401812 449636042 774000703 818513160 323319289 123057373 751275332 846059527 603569231 567669374 382803964 387218065 800105101 68312735 148745450 624796270 125309585 141236779 914599450 730567935 131772518 104027978 627354212 340485246 640441727 253480091 886690472 272197442 815696379 402911352 510037264 913052410 590858209 206651960 587134547 515099631 467945059 930951014 127390958 462994500 148232988 37768460 553805930 751163191 74446676 416403181 218707099 434074207 89956152 10988739 210466525 215258861 40412964 730612615 412852567 452723437 664594651 131096743 217046073 965612164 107014858 485560143 243736319 904116529 905841994 799005603 347613101 98389261 649976285 280564736 842942994 951323661 819617902 717878848 580184839 161054012 839212691 394683124 582482351 735058435 369012428 872742057 930648246 389193571 83250626 415294246 413389716 549652791 946509707 259452074 264137673 280737141 527802082 751346992 237088 440266603 300429425 110649260 478381550 293104387 764443144 577424716 532790353 45383681 902933988 658884281 843335539 333177665 672346603 974290261 415459270 34771452 798021868 906079869 787612487 550801153 248711650 25758919 349594300 70204925 628733231 202343234 832493816 664957622 762344930 936229050 588466196 262004297 570384627 366825714 189158069 332505713 89249924 995062249 107367242 628897473 135473439 119067416 20083533 622867942 229727484 321780400 29164671 601220327 81964345 985229022 945583661 744764519 564784930 199643913 52950127 928921567 265642344 221285136 637099365 931660518 811640683 188821133 58498170 387412075 128085107 886769174 388170147 539316726 461732080 140442233 89984158 440194796 472718271 892487677 921484853 302364106 959060325 691925925 955759482 407150439 364291411 659936365 118277899 421511220 849183010 466212493 422509132 123503996 69146582 749351091 738259633 73152166 687190813 864016715 643324659 35810416 687027855 419152312 371435096 485762611 670823661 815384985 340436461 160727843 297376099 432359943 789482957 970680206 486890695 152285395 105932889 304472602 310439129 455756234 175709566 838097160 301818243 267449330 933471220 376597365 112556057 419139788 559344764 33517206 863644311 268131218 141911327 600712953 49726183 829330039 910963 515815880 906807322 305000940 572860630 409166854 763439020 877000663 116193714 578606033 635814082 321053915 587870394 791980448 348824428 169408916 155381033 465592709 769650149 624547801 466815751 60081770 255022544 759347707 173484133 29444437 217917818 541327874 832414365 784165029 364760861 795210996 37871509 645599060 46601240 218879503 484203258 690783796 600358969 611824652 165553543 791948084 63461109 744765020 467065917 967045787 351756972 886971500 194868650 222967881 995306472 681223394 434109220 672117498 827708572 424379615 368692237 314733956 84510054 782014268 865714446 656244245 535423695 438081999 117154141 24692088 758900871 460522661 194569721 588672590 211780267 547395911 650325738 233990231 82582273 775272951 335444612 96964521 163938360 10562289 123223202 65033716 188881195 357330348 798989292 513850310 476955164 375481369 859314963 207729090 294724090 112082912 812936722 416924137 883888541 482704807 738186092 68304595 28013830 281474636 685656434 444458740 312716450 318740520 669906300 794574809 421223557 665357900 754433324 29605226 984573873 61331396 403279792 473704232 835678030 766599896 298308863 960294253 662364145 421200968 407574808 365991088 454713559 859986573 297532744 645920960 777314600 412618013 514550626 716939782 257428278 244663205 366808838 423944389 794253757 753743694 22386908 772461147 942709027 638313978 27986392 697038463 327845558 539146629 744832629 42104962 24941554 184739078 95664124 799207056 116193723 785925133 585101756 563885806 148690844 993934820 498431569 630458171 645663504 737114320 878397662 859701169 382896311 268805455 431427156 355778658 737721757 190640474 917369515 657669757 445666424 611079586 434974758 83048328 141621993 636779219 961286801 955357861 475060407 544676565 766250116 252127695 306109721 450956296 611494558 627169051 910022634 973917829 559389900 350958074 505441012 539218274 132885377 565403763 145260328 696370156 873692926 263587435 188332514 546824427 77347977 842001118 86096935 497854435 489031607 31452964 996688359 540467279 320937379 933607983 497355069 451289830 210025014 697023945 185715628 738932440 76001631 995373016 775824737 407634703 938567258 314454940 600520309 631398256 323589355 779073773 388610602 624599065 574175393 657705855 790097963 425656994 663463445 1791519 86336462 835387230 684121642 139121140 725414739 698705049 809853772 164983233 114604835 666927065 434922163 761565471 960622867 751859486 758826911 14556613 302426528 751200803 140023963 763018434 372167475 166741917 644590267 680894398 180423004 209757817 746138336 219996734 394730009 580345631 456653040 32669919 307554573 596760243 843191584 668913816 632760523 246256208 669120300 372070906 643322890 11722317 436055451 231598705 132374767 839746938 759043325 113660289 372823624 832722529 953403182 570364427 840228557 376251015 543912082 869525384 292531295 639992233 250656600 576377674 175093067 895043842 102406330 71889343 140158342 935607937 725979705 639825327 834017263 61374485 850326242 644775291 723478417 168118499 748049037 387486814 901832928 55895691 716240154 365930413 793725177 36058728 502170548 257672728 26083044 718051022 785001488 598486248 403291347 125097036 550831020 966643521 421437794 529728234 723887890 512850783 243289814 996068713 522204436 236535770 499637856 251642503 2721807 429286628 782728025 912368186 322669354 987079559 488553605 264356082 605125525 281501929 530461522 276570329 897194444 633574281 164572952 954775316 634192596 550096513 342264920 43149056 825261434 630961859 782822398 835841399 31946649 221546590 578880672 619413003 656498514 969528249 295340990 504586311 752671826 323348180 596506370 447165683 577765649 635878027 968273279 721678158 976688655 690083284 210707700 598779987 640891160 790454013 376801544 435262454 215580287 243376369 507584141 834692710 2028643 533855346 806722750 948824906 584592366 356972381 168539266 108872966 33258642 897307627 358266281 344004085 480130380 239002092 136029739 293811630 691059683 897973259 128059758 306932288 162181672 387628815 646006654 84405111 569680181 222220053 747315285 308812823 77738160 130134744 805944082 394699549 20337158 698796779 515270979 557851907 435039154 657546492 942531101 667596539 235142773 524622097 593427904 618340400 956259485 9769675 120922229 766370570 801774912 675934887 93116401 263813736 985285504 611903801 408615569 305479397 697634758 575280241 85707422 40914965 416238344 692019416 220396424 783939015 838203909 311444689 395668268 374910274 712442501 465424858 15737104 980662409 100477595 263229898 819127715 50408857 996453860 919093778 137265536 738126248 557284040 867315454 646158505 618750053 888584117 211374835 860803021 88735036 756336233 299826608 216740740 282893969 328012582 902301583 258250127 508785409 958256125 87310018 664066587 143083174 798939142 389914264 404280572 893841489 164822691 861376695 278609140 682903760 104051906 38845025 313674987 455828519 638258202 397671345 253805877 110339288 456137322 36488925 988318929 615078173 270294206 777805683 685531815 469664298 836747436 40829341 504622279 429713262 995914641 159791455 794015661 337401808 821579222 634218965 383511937 289005811 834270766 33820280 602655569 54141556 27777239 456838743 814083671 583860520 550640854 576007520 140632887 687224417 867993917 752658326 984295230 477365032 736376423 862050393 302791078 342510465 388052792 6755235 80062671 576879020 20117599 426067783 986507141 176071519 881266580 534031922 85704766 734337294 380862172 539921324 52570202 186125606 972722626 269226645 804952931 164395851 502183581 461243562 280229964 390150047 806536655 177379775 72104628 334480892 591595266 364674819 89927202 683712310 360170602 98158657 137685319 2197083 189220359 21234971 787226433 472641012 497309409 887226959 827228372 593765699 607977036 906991860 907969968 51422085 922390308 962961851 778798512 897854255 96577295 68601391 68912151 196704563 117157824 6673911 357935314 737346618 532556847 697061393 971084730 997420520 689371619 385711638 131199953 326247452 325748266 464814459 645401730 113713199 512840541 700871883 748353250 823087666 3710495 415062255 991862003 975122994 304863388 651257448 22530782 800627061 748022220 377906321 689255478 515085756 478315695 930225887 248789305 703230593 373354383 690813474 841698319 3474488 468581699 143174083 56926219 414315407 638841960 945297158 112638695 670306991 263915688 515715655 506120202 495562362 667407348 475621438 769562563 301106125 10773963 824007485 992881292 755579069 698879091 808648814 436937801 454038491 881654844 586581783 451854728 937577842 559882434 734353367 514760385 929986757 986665 544579560 407342997 682491732 4728929 529849437 644836369 853793813 140325473 451114339 9729001 352704188 545063789 982080385 930192831 679586037 110002769 798445785 21031515 733415334 398908069 250059879 707281394 186392112 517262857 460829502 262275936 5721005 565764456 986684880 470374256 402230320 533405750 651593508 893897233 311746570 835966388 638450207 180275103 743487233 279171112 323355838 584411170 989789080 838916135 177591639 76218503 889209419 73550285 942830045 753496554 364957393 996183041 345826587 750301902 132452698 711237556 362013173 897343073 611128785 317862176 971438252 600378299 672025369 861353226 167118360 583367964 55159377 275367425 619293421 852727603 36417042 924032927 215063289 175562835 226091949 441473477 200377954 569100733 812249199 317831648 352091881 173495515 428924638 929271336 866516267 892652160 893960186 622856925 892605916 83062314 918433407 941330314 296281356 37666114 526141471 287403076 716045668 898387033 445900491 826695914 906183527 923192938 886627816 262196836 513752755 401352220 279781787 719840741 40356671 860670719 417054208 598952490 459811996 607736011 192440940 345912506 638386486 872128678 189894832 550102309 220205458 368696412 977589334 11349064 778220431 970786726 620305379 455007621 754696615 642403686 896482838 789400077 442621484 434328807 282921765 499466775 240429197 746241311 950072324 324485671 327535248 261273069 206506399 30266954 599458199 647682397 482658332 205365590 156616670 566017249 113954331 125698604 587610040 288273559 269632504 294345975 360135894 638003847 903042821 548422765 313539970 788770788 267167954 381399306 847551965 762932296 764707431 885477977 881981735 236599545 485166470 418958380 43309301 175557161 779793899 362241505 140838010 488898095 501414029 518792093 692413888 211187408 905621212 959714194 430628590 265748602 237719554 420405050 577678721 820635525 574951972 196502683 267057044 873665394 846286752 246053250 893609242 206655533 478481999 713261258 428645152 223473997 237670081 907075476 784380686 692324688 427665797 407132814 699950052 680796385 457348704 592994606 550338943 239318548 255021458 205816566 117666771 27110310 856920855 259545263 424658991 381925951 573483489 385122223 414289534 399143345 440863520 617811221 966258306 76780088 390290812 140653321 907595033 768440761 153283159 129124351 300278650 738294533 612178701 253394418 299470454 216137493 278201909 225677739 437307833 560945229 280154335 264810489 400848135 697395130 125409749 74171127 597210497 328411222 457719004 346728779 295776480 627907649 420134386 802888035 688838326 599414791 928311439 792532151 926057906 501623262 510499557 581139212 544337114 424883430 321144098 442015661 856316112 85914217 824647339 490233521 310538510 709893402 220042080 446476858 126294316 550624343 849455836 244478385 125150231 292371817 152034228 8539405 447879001 759865537 604527797 829473803 295158358 71467834 353408039 747100532 58996106 573444443 650105614 860950620 981705677 7105684 58042469 523277150 99064209 570492541 528093283 938466787 987359776 564571676 592515000 430043994 730368224 380010781 197811918 247127678 461194896 578202393 578772746 177746069 292705930 322036434 397987849 266239661 163476481 733291890 154129637 657192671 674314562 812817361 148979056 142135182 996232436 487730606 859393910 646987942 959932249 328012530 162753020 368125151 485249933 694051058 842992261 722123512 585010883 280967595 972020809 285067006 559976333 924701446 20396413 781290885 939510547 908750355 136661136 115614443 102550103 245916751 867179881 178322585 155806585 292865760 698644652 501577795 538564335 302989269 909937908 733209381 622425802 559819624 494056471 209192261 809941493 915989309 390114407 643918518 427774327 70955938 230778349 596503760 611352493 386702031 587420078 406976890 64005011 625715749 429641960 391482979 718616570 949726065 907401810 328538690 492072144 657000487 169180001 693593627 218547805 565554344 733780863 535755386 642385026 77091198 98102100 803844791 886967801 241750173 552236031 234555953 79633306 758011554 831173723 203658133 63003537 877642261 390968892 100106263 425401002 158256808 80338353 103527093 182238088 541074039 126351938 741807993 143558119 397137223 389928496 211963061 428851679 590779849 106116537 233592902 672112417 937271510 902434899 858202834 931350585 914369201 903021549 361744652 664336844 745392202 208753715 130670829 295064025 826204791 547859913 935403258 205430522 587856187 151764876 190829442 342424481 216550145 295417302 165630431 570538333 245230047 922270649 500412338 371910676 746870997 567893568 804305448 351909192 150273805 140998579 209859897 686097237 98555674 109133009 522746085 509034670 482918971 990998549 648967287 540357412 72533399 642921715 985169860 206385441 998426495 649360665 410631274 345308391 943363249 765244848 222331155 866124755 559122833 573922459 925843633 792997790 177495407 216345525 791529921 521776023 848430533 644315156 251080586 542930412 607188856 437142346 465199965 717274848 762688020 462903968 291262420 87271443 602380050 530173018 305106964 925983168 441022740 180472 667005709 781339639 328153893 790010480 670386358 234606569 215212538 117546871 1686355 141914906 909329717 930783415 136001201 948210350 880542878 724461079 851278694 221662878 511552874 713781752 70121491 914682113 563017590 481382516 839548067 826011462 808264843 825954463 560121227 431886198 944974233 801169864 89961738 648568692 219936253 944668854 109296232 254999102 469823165 453665516 786188600 625066283 626571208 362509799 547919511 976784684 234688824 938509916 486820972 672714253 46128785 970615677 710831272 566838194 888972289 928109106 769565317 358152028 720233888 384327778 22882761 87440612 400570543 652002345 989383169 471288316 573705434 887840545 997843912 164517747 940673912 934200731 613676543 704979055 406009543 640652772 331902740 921867186 939223346 124824963 881274429 419409110 330982029 294398071 291787964 191444883 933051732 504991354 274123034 129126134 26211825 410954306 442698861 443451049 476869621 211058365 495514516 305426480 84191580 104841298 39967351 125072423 960345035 98066468 726874953 406740870 161240019 845134160 216934856 853947103 330638381 8407083 979508857 510134684 487235837 698995078 323027950 820742467 297227536 709233132 590898689 509089971 128982816 283102432 694944536 538857830 180863756 863523362 506807649 45274799 999826210 964850408 526538260 260043003 178492760 431068966 949487798 14645010 996222604 411578056 668891218 777786708 421047752 496070389 496879807 527327997 385751937 774098763 185495519 954036579 331927765 429420839 755710683 175257397 941551819 793754332 701836649 809767355 405072276 872950008 603600648 851817498 495353806 321661316 812298305 780754575 38764988 893075778 494555109 24981936 740559505 914242287 142535763 468015536 60672932 369088640 496002224 888760730 768696251 4805734 868405806 72017042 914936898 944620748 225972552 131826457 424920210 845904085 910347009 333709896 969761581 333712352 635540010 780720401 46426877 558866630 446956699 201548674 997244058 946590488 315773047 57884675 658959747 583079523 967478634 283845269 770440545 712230765 799060972 906167314 165218121 876405623 145770108 307188082 966416632 346688378 436840679 26856706 900392982 193275244 799078272 689029036 263861621 20136314 488461927 824628275 845080145 790267213 413578437 636403829 756295568 225313095 264977931 995947689 331124993 398138309 524925240 579468448 872768670 937592924 572048914 763009798 603636683 178076445 420639337 238024352 408361110 893011922 940108121 361788814 636995319 967620416 145495686 797291655 205159439 235839078 993962335 666863137 521193322 811733434 926370909 726503944 751685183 835907696 326794818 445403715 274668716 827096500 899604829 633185396 378324220 896758252 135159490 200631062 710822115 191959033 903068564 97435327 561574077 639502964 702975549 478023517 135227092 593215731 541154738 304142203 965501593 458956611 150712497 773362554 369878504 450671276 21211907 168628442 126791238 48337202 779954364 488711024 950711332 776011473 99382136 542363311 305030171 462998206 582355870 140114145 450675246 254229162 886334366 328373357 99031821 253046271 930203444 963565840 895034702 688894754 928979108 676829989 989666484 322464433 341732861 769384159 970581354 544176837 994518105 436558220 598974790 426113583 308491545 190852305 844246280 566773691 841933098 559683058 296148890 557640049 977795140 593426696 655348559 951636433 658484775 176070218 950768421 941031188 581095902 121904967 755984901 52519024 479665917 19162664 776986112 363138898 852249317 620248816 798240657 466798242 783091709 812854973 370594527 425568260 816194808 519054598 809071353 325102867 383805971 124970716 935456538 654760614 20519508 299523115 949687268 979117069 293996238 484452600 224167078 833333843 941054426 497589410 76875416 612652923 819000413 978687266 583476764 697186756 539141895 977232972 53070844 260006630 448110991 12424462 880964784 24972628 209765881 101058734 428879255 194290041 632876498 472377870 539990586 319980797 764604784 367702249 554755982 182756864 374977332 128024340 983136048 431807067 372590793 657329600 102202024 653841635 527267428 226826420 812910248 742913191 721275907 619320212 744984652 181732399 74182320 431755551 276492890 122164925 944594877 641450090 367393921 431171981 857105928 114388008 658038939 751243542 87480118 663864291 573457388 686078023 544277752 81474881 8179810 959190989 114131530 253607233 799420373 854831434 179232433 277254525 369817414 758591644 610402682 800666984 778492961 11872541 510707456 771797391 345451900 192223455 465571300 868148954 557943640 144350702 626850900 139786697 305024477 152869264 261019462 179922360 514221727 136905093 423816635 940366365 772699613 670843208 654036991 129297863 5693886 245173581 115858661 441556510 994140052 373279299 889267980 907554407 510390554 85015122 562070046 983879423 623174584 679888475 606948878 649941149 451235771 216390972 310680663 643508114 924347295 754115851 289767233 587945225 577311559 567237208 118050589 23813705 224838976 200703853 180278661 20855792 475836932 783738255 624307359 476086583 373426994 897436220 608997465 972852530 314697432 527342700 815548331 545720847 830215339 987533777 748666330 411712595 14583627 658267673 42608049 140389410 621695874 258482216 536189639 193411190 232671107 376846177 251232957 558094948 198017580 608870620 38744191 938389084 564837446 807410350 948202880 172683623 427845058 675445030 968848640 180283497 863519995 722083851 779601223 113956702 368094712 893881825 410324200 954067102 911964584 449536803 943960577 855885338 343349029 185788295 488480631 144742558 358061300 53129535 163043900 556599567 664533569 219655732 642621067 10235820 154609701 691629899 622581032 186085199 499882721 906397601 917942946 540612267 962038562 888012240 63167633 796314509 69684029 831737642 118630618 376469020 653676145 682101498 543539432 809524250 752322090 161258440 120285938 759034402 144948025 822150803 340919098 647533290 752534302 946872854 747133770 237773440 566027073 486421509 852110134 155898767 377465394 829482063 504550110 480195736 67916526 599058011 858560810 513005883 907890714 904102988 184945998 75156845 543252295 70084671 438995973 104049345 101977646 298204554 156626136 183763874 442799603 984720381 1711446 445958292 118549604 713476897 434175579 739583352 433774393 960706941 206463819 744697030 904335699 702864334 147521877 34872530 206054910 936239179 928161970 714299657 897359409 68586473 57289188 861151027 521541066 548029330 26200826 254201008 421381844 432949614 404933832 719573437 306810050 255213084 716625457 340894894 39710643 889003511 471331679 670999347 529575854 430940243 532057350 547048341 903066597 646726334 242953126 918553591 581325299 258490433 993990856 409355671 907644191 450058399 197984318 111743500 275347353 745440147 528576356 841554567 295591354 694844435 315257955 89170196 988550469 290254737 351043946 50929623 650782890 894283061 481585141 849784913 721333311 732431654 284736520 743839899 256445319 42689984 864442739 960178855 409038445 883590877 506939661 117826948 838102663 664192782 57166841 856806040 719713877 667010273 674565350 325603557 607872640 963922970 247350089 652475462 286567709 624938747 192851619 898136753 436726506 990266750 473857470 148944756 707549325 860649111 303754225 694566521 665747418 359599988 767836761 922462596 404227339 582168254 583415584 60419953 782454791 932997592 165630648 83855736 846927773 176886812 465067806 679082603 645768392 559850019 214436633 679356916 153263594 376176891 213522297 63514073 164284946 411736944 606482010 686043450 191665720 591155525 694543968 203362767 786280574 466402426 740102651 880171307 756653934 685194373 648865442 513097726 262355776 907227034 65471513 583555916 617293586 380984806 693702061 317847480 365534768 379688141 948661620 879260350 296091979 177342513 755564943 301782002 919223747 503001004 60093289 209924675 426893536 305984465 700539126 764423996 620715282 242727281 934370807 850782271 805166390 480146642 313479987 780180426 370180561 308648695 708378557 16233651 568219732 169931485 164156978 610622829 390574168 63255225 274643449 591915331 798680801 907914556 704806019 168266650 740006301 656736465 520375946 113993520 872852516 776057051 759723347 205032289 434156343 429801209 747805166 743047006 919382018 315557956 226399858 601955189 987466587 368683661 650432835 150190670 719234306 807542689 474608206 134661674 807128289 850920070 95903817 572084260 840960076 104530621 499096053 499669873 139593023 171972992 716136797 61483681 499593636 325521666 746665238 666822365 376983692 384680884 759315839 722122537 292975475 182252412 65831936 613090209 346115454 416513789 934959180 973342909 959092925 673151187 256844704 640680590 60349291 818936021 462980100 337475585 105083691 281251668 688883078 254920729 231209034 325425240 318211460 142390582 998842114 633685735 925954016 660446290 898794162 195320896 7018059 59539007 289586984 761475865 599417724 450072300 17325529 83692774 482189944 589182623 781536549 685344019 470852554 611838266 405384597 710943302 436404425 482489209 966561055 620452256 735237846 561846319 514298462 719307258 779968157 647795598 273094107 47525162 310905681 377137757 581923657 495745341 279590897 365843265 750796994 468097468 380068488 78639607 264371725 822277353 56402790 825028757 827347417 750009600 346028649 109739726 659797248 867724153 527290937 578473772 412605895 783051842 924073349 727281238 411043610 966633734 304684104 372709449 143470546 949516906 851027720 677919649 752513520 635275596 696921107 725809871 239672801 877993477 660423361 275953505 525889465 354764710 882081975 364277567 48315002 197698876 819415328 69259753 182759756 947439885 784552947 610034620 893931716 879242201 782657330 780349228 622738975 286620188 55511590 97002505 70583429 175522632 365529766 19136700 1809992 29476621 437954638 396816264 467674148 576383635 887040970 924959691 124559999 782844348 529782794 60371772 247718567 276041316 535592845 28762924 444659736 33681826 280612248 989703111 15849909 897206022 820054909 294485842 591815436 686595035 354623959 94410604 453010325 809188964 950507466 862339662 256936945 383544608 778787397 602458125 170243884 346667015 664498497 87180756 399007740 882387404 448006912 534163757 789105665 730756890 291006289 861285687 862642949 822193113 582388424 85308910 158295612 391747689 260382728 971323239 594059138 869622499 539535610 173959954 646960801 234887773 918545429 918819065 779977354 488649764 844550550 584570621 424573593 955560704 163037894 950209566 736005587 537977973 513496377 937800113 479123496 912927742 654604811 741044905 638005683 993074770 297946402 412945104 422043127 660907169 286640753 583903244 457259297 691867094 160674608 623959453 288784714 671108051 928189222 2626395 268186036 912695993 695016930 174111993 67747338 402873888 740316155 715427654 701686178 359162968 334351956 868826473 217618619 920504752 834970460 937817634 998857665 699939245 790552647 393850638 551163526 66634831 630315608 10477537 597760904 398255441 305074713 613850026 343191344 196215656 129710751 477638676 964336398 85538689 916132040 508367521 925702432 947453956 426559102 461212655 809592073 270818837 755205106 699972853 945925467 527283407 903762659 544901700 695165648 609558665 154902999 195988807 401458058 558273043 78480222 817296261 453869144 9864695 361220948 190097372 15006194 251033018 533128222 228623301 707292217 179337498 202231273 630385812 732502906 816666959 15055855 208952503 411079594 418276427 598954419 837866740 342088104 125026300 255727169 270549933 104409727 392591751 783009137 408903197 428816547 842801804 882841891 259336601 947597617 353421926 544385154 303306961 420396337 608179561 657360707 321243406 560053461 186309668 190637796 4539251 436807865 915602079 822765039 748662335 33788706 839714203 316475702 233373703 751893313 234021846 22486806 25911549 416663663 146116934 532278966 550478893 568402288 915784795 353387335 82810556 691575218 193575231 103236419 35886378 52343437 776808727 134536623 933272718 958170753 970600256 842236251 827085278 598926973 157298836 512135198 659876646 731753236 911576741 466462748 588410061 884778439 266910974 517554434 91200725 245899840 979942503 67164998 634164762 219621266 16414751 894955881 688373135 783352188 552155425 279275830 151378310 891374501 777083234 648023298 107924710 811054302 291875598 768162539 826082932 795131493 516559824 489027099 454007821 779776286 602550792 599166469 374944743 32367321 137088532 552280996 386896341 150640017 457282442 125087424 762280066 562553001 579136121 422588714 881729714 962666030 426548909 850523644 746431110 107323417 571205354 351661275 420912310 812867980 777426478 931638071 192700886 937955346 338403569 999986567 82811283 236481249 623330405 968005264 682893813 792930841 69911479 89290396 935563933 610203651 856659278 745929925 217714181 259935828 189376521 387490857 446223557 446350697 52540035 230973236 972536521 177526155 837206096 359384795 237166237 966774314 21009727 213207517 825158308 453255459 977979031 825820162 630075482 301610492 277992027 685609821 291022743 797830948 398433928 766849420 674102220 189453110 159651924 83528436 947340101 738266676 80735086 493440007 748905063 920863437 822068034 185795711 147706609 961057177 723495476 619643554 222946620 574568025 56081121 210415742 110975869 693836602 923944291 341277483 254186239 213893648 691267212 347515918 592348524 665491357 924699943 81298962 706390019 458622665 3588411 668238574 169153760 941686760 135082825 903303779 397405240 555489785 652949899 731409789 54522267 352699363 646685493 21251023 455763763 867667385 84421558 143134905 580295937 728220660 805583861 271824547 464546341 697151165 605757845 730628161 910368276 608910626 631192627 672875982 273493473 186616413 75526308 463750739 520117110 835059985 759004218 417414367 116938457 74637454 675620862 54589389 367179626 229211659 351718900 365648899 36591905 267681257 199968348 91859503 873207762 725718772 247513324 224329738 357533802 788186530 555048985 816501142 602757168 515342163 192556109 714307169 864921607 488087953 317050159 34074306 565454760 382849871 371470560 100762393 133982954 831979564 204775226 33280272 971312892 650370991 729207057 289940701 595612583 958721673 595223411 210871423 618058894 891110872 452488425 555989759 691277935 465704544 825663158 728351151 604847712 41380305 145378836 732405611 221905172 439674374 425885564 682379228 590591510 73972290 884458972 100947121 296350475 125815410 724906976 712570598 50951410 590039663 646048555 447578111 63895396 61425467 873445788 20694859 899910101 3293761 805511308 560407331 214941395 721270422 849892364 472106537 891492676 172681788 561642025 606113932 643517354 75759452 533959722 128147776 330168160 623094665 363030477 985608008 513286107 472597761 584238735 289732846 315018731 301946348 584471267 134853894 410910969 584520093 279980919 907876913 176437321 807407566 782419060 72362005 905975863 678060518 595960508 411453607 816641403 555340340 125179180 188716899 829732454 798545202 325243353 257725071 830708261 224555204 204889429 557429374 367629819 681486200 902754792 655651529 435676296 600084934 86619352 325677973 643462406 747014991 489975716 571018449 33889415 38044192 542006594 876619638 867564346 748366829 90196326 807243463 889684902 814800728 919536572 92943760 230409195 225645353 390291243 337245545 127733509 480912788 746301713 137412082 808021002 527462776 382801547 325705238 803818857 718846876 636662188 707449674 580788778 484370930 690650818 551366860 248900402 928045270 8392086 850737382 594429566 260255822 34446506 81856554 215134308 681070920 563111546 526121653 513615063 718200544 725596861 817343342 853313186 726842265 534977956 376045381 658698409 156936865 559469335 616250998 913258285 80993039 300246524 252980677 419397382 723309862 958264177 728487874 82481384 242187665 984604687 704171524 397013152 58209959 329821991 241938031 111758422 14242214 207694342 981954160 862709195 525012472 358179122 482881085 430878617 332418675 250473900 943698455 374902392 420771474 796267053 938190217 990509685 232281023 121291883 223295656 228195897 50463883 809127507 276053842 949022794 489574897 10711886 458912369 819972675 87677080 107122046 966725943 382116892 319364624 580282623 463965793 224947558 191728145 689988904 440474998 649701005 209827265 833422793 266544135 226895382 54896876 41152621 322580206 889142752 368629579 366373271 257254288 309421669 495093184 370407430 177030429 686252535 442636182 95894514 173596108 941538821 828713410 929320014 824624162 900885589 322051622 812365318 966599209 406922313 941262539 98462016 649736378 19172892 638865700 551846044 854266550 828113444 634836815 812483702 210810950 833979919 970573652 895223328 861171744 388329511 260932710 699372330 973302467 690722960 76324895 559318684 883846071 384892551 759342533 908532792 800148687 821192098 44737417 943702970 724952936 95916308 17525701 403488281 884503465 139383015 134078523 815903429 389630915 219084609 593842522 103217896 783092016 67861922 515502970 32640167 29696502 390144546 492407836 8353376 940771299 402969269 963801900 952557036 649904591 938782824 854655553 222988763 516592863 523365538 617682905 135383740 671844798 32850022 223052959 568819796 695922659 301477261 324419239 439068900 585187535 671032846 212749998 720509541 800529742 792217400 580861276 712491980 741388979 57204980 912404099 985564744 144424990 262441221 959010399 645343361 809331127 155892809 722131157 926293465 817133553 760333815 91965110 803388332 455780042 511418080 578101499 566368913 586621191 607635119 761705992 69108632 985338746 648605995 835238634 753551243 467129405 509137266 258472091 161538095 105583094 372268861 446957370 25269634 769271059 205398049 40015190 161892092 440657677 278148809 30759714 778879696 426114470 600281150 894577599 314700073 682814508 374999841 833359479 513975151 385427126 247910637 301413373 21936001 405513059 400538935 124103087 614370555 851195808 573653232 995842262 514437231 140948832 167305119 878153699 42951853 766027363 32985256 470246833 256485372 275997553 465624202 372417223 441045344 948569502 898712090 351657620 804128212 555269510 858144714 545200307 365926287 152867983 86693606 555222567 580101953 202976299 285065427 600031901 654728532 170271509 580181073 541743534 13008173 35878545 114960568 497372188 700276841 88731054 357538619 188778769 727574562 251246213 110139433 566167397 831140394 30376312 396057129 405482199 458779213 389047414 627851643 483770704 727205264 679340595 440680251 16695845 214941046 603853170 472733855 399009107 233209655 268956733 197783094 281867459 983921928 614826792 271893800 455753093 87022424 463879315 824750714 37028630 146499598 332144615 136401481 977082524 588650958 414198997 89634571 514689062 748778291 700755612 25395923 79966702 383656980 852575554 219937932 501843352 770649792 556408535 307150138 602670962 985252675 782657207 854524222 777287092 359222945 673944774 663122320 251814335 320774168 389490355 71958276 703638880 594836064 330894647 768531848 129755659 989249259 566126421 749673314 708349473 215129895 921393561 437907059 208256044 665566648 82818395 132443512 192771104 98071488 625341947 764726597 911421594 410199065 319750692 661539338 684841506 72438424 779977994 84992656 922452586 753333577 548338606 30075770 576443790 907801015 574127638 95361158 763853651 227322402 2548375 909761996 386087018 982535880 478271757 891582203 505685419 497785119 356565023 513678496 692216156 726347542 542637181 496423776 360821354 151047769 541048867 734705466 890737068 184030092 900181909 167309512 513304357 872845196 305885987 853330044 624152384 55694515 114589220 913711589 319660563 483710995 125215804 994580713 348116638 937806519 825440408 680640778 31387147 229791975 376499501 884813475 427619053 363461474 132668926 931593770 330272899 166233251 962710613 785398125 482832372 898250270 432101895 551040215 55918993 359775617 608077491 219620521 710281240 858309110 363776768 43846211 351795692 734974813 274924003 726507866 91974240 654317460 593325017 387105601 298836715 638439344 892941351 948548642 963035763 892297539 808892446 708013124 453521540 738446742 117730394 779993412 298137751 528373485 683059712 395840349 687620430 872369096 582387197 969119394 989523891 893108253 41728587 381173312 363884158 322261153 279957294 284164031 695758158 744197630 553697904 937965631 972949996 805396508 172575402 596594621 963704717 305283930 583236220 886991437 626655246 308584402 565013970 326721375 628685624 107185818 32421151 852039419 484142075 894204672 932224674 23119111 36609460 558762955 626846629 480369789 490948969 114216574 856639930 502856375 298560777 548757142 155345407 393187493 938559150 63474376 989809753 327561747 392174556 429517894 296377017 239753446 638633665 670395897 729606236 958174301 714870133 897029061 660793604 34651217 629129529 198391241 999193666 814210679 41028537 935948702 783467693 331633050 339286604 125496213 570791722 260373219 710517040 291291132 634949667 740982547 333080272 939527255 838128850 608086981 911489279 756922024 782967925 19410607 371140668 646471849 649871256 597927135 125538030 909225741 126191952 237982719 939071655 576193733 555580540 528651154 344383843 135238199 165332228 196909111 921716935 374231174 569464604 274827491 926307684 725398223 554329215 95197737 573498867 447645031 54692277 13898611 584705176 935340319 266652495 602361415 159067168 39825538 192454440 650440068 832911173 143189779 425793955 51923108 518116838 542035602 358704881 802956538 337203281 456698421 213370954 166425331 855623803 103208944 299331376 342281558 465161540 438213552 525289137 844228741 3893174 298469529 212243108 289130428 952296516 728788557 815336 465053263 168659469 622103077 40269994 217833709 280454679 1364599 117671837 602845921 493685398 844665296 427968321 729980749 568969764 206527545 914051614 60375662 745860872 990986868 232329991 603334877 41566322 69146942 74900570 614381770 409992634 633264268 424261948 468624705 172550054 380715727 906663135 558968166 222227362 228950066 498083774 16014778 101893895 686294488 429176029 910705493 736742998 947167520 542785803 876769067 714776188 622622947 185526817 341358922 546159118 620658354 191376449 132135448 137040523 513013786 777470745 917656982 823908767 291909601 321604896 415028385 393251932 471892808 19863254 882524205 534457472 931789640 327812101 490595978 505824179 779548631 538886916 13267617 525177543 479450914 712240112 444213046 142936312 363179218 298904050 351634469 69114156 293637449 648554110 966678950 718225714 607517412 593085583 489844618 454851332 843513144 360603118 144999037 40251910 201647702 767447146 607103300 983405126 343870472 582657311 356781054 968434620 661454100 838574513 170517349 631275401 791247990 499236239 428554763 786056505 29655207 509719858 364826527 466524675 36459226 694921053 265980456 60763141 26416699 797936220 720095558 953565578 290763568 591278919 192524149 13113926 631785626 839510334 195137354 684193941 152469266 627480747 133701814 533831873 530897454 833637509 314669120 355313723 310525883 677489545 125649997 467839199 940615426 512281473 962311769 968889906 325759493 890290303 357628989 666770085 159614144 222759455 36398953 24047313 161479274 932373706 113422888 437905593 429789875 500074736 924218080 894311181 771806469 288307786 290740049 565442659 204310981 168774432 578094547 355659902 201860497 17645950 10375834 607156105 540285058 591099518 344559859 366434138 561559913 971894659 958156934 993133233 954423058 285525881 4854419 983633528 629119877 272121880 778689335 405401858 233932610 196892960 100766374 464744781 256761474 138228124 813429872 275847746 905964155 177036065 894649022 213619697 627004570 676483341 711897491 718628568 938362312 841200586 745111565 15018779 798340006 361818122 51336611 618830282 232014291 867196426 939387750 376290847 188177187 649955025 541164354 63963839 839612647 46087535 851928891 854284534 869242921 590481472 512393394 511256061 155754734 694815273 406409120 488527926 625240436 845272023 765107159 495954027 995053427 857594116 997036614 115523348 94872414 533311924 865482803 458536848 827483552 255605617 605953664 437122920 594131425 881753236 163935464 538297745 243205697 885979517 382997312 31461800 614910105 450772439 442445496 987944757 463916990 264031703 796325146 762638058 313009855 663453564 884690951 818135011 504979492 537167822 426953278 207330534 716298543 823670304 833775831 435596706 524785436 971577167 66280577 3571697 606558818 548943618 907241673 148043031 910428657 493053674 636064085 632501506 797559923 154007041 176198434 985669002 431753613 619082700 169108939 49858992 666424092 623934363 721772739 856839392 633598075 912692677 33195159 51884592 902380985 921736943 58383918 30445985 773864677 912191299 187208202 575951707 838023492 523649466 836126599 662101746 556034710 961566549 873221145 809101989 862798934 166178397 989137551 589307035 28814073 304298408 121990740 625444390 254409003 595904469 98131114 79683841 997995287 992308876 793729007 379034259 414187422 635658688 53326553 344887084 85430684 823254254 649171387 100682565 461853991 16467550 929117632 1787074 680851665 651724894 208134188 81695792 414396131 528053900 931582368 404931593 230773410 125561610 916741461 677796332 646480780 1374153 275270237 104736231 637575833 467821505 22617318 863914927 75092347 809972276 449404280 395395556 468117472 531370480 871695412 527434064 803658413 639651467 370883093 733700646 820221250 429274535 185408560 309792068 380102842 625016877 510373109 394335091 233412905 630890387 434645357 609158307 195531998 615260952 503118971 605956402 323612064 585885956 54929949 579010340 924650995 594487787 86189226 10395497 181423186 37158888 495142932 254528795 873064563 186214884 298227493 523035839 877134472 552740558 124076739 822949249 480180346 268787937 264220973 235195514 790326574 671063779 82107709 181770219 709762498 978214754 702999973 24047745 282348237 301700087 80988724 408280721 472985508 803140228 890731792 166429018 699606929 363552887 185018876 60821575 560165660 540426247 533626257 895129132 307473220 580458355 214663301 899778694 384868036 638784072 84970217 543892670 492358992 409200793 239978852 647043940 420539607 654151750 867271803 495931765 563228352 761898552 913305547 267454870 595022639 446140832 834938186 655921496 89893951 86262589 147676299 275649652 419365190 819595924 192089080 143197710 71632918 147920696 469862424 51606004 387701304 715226625 706403016 669773278 585353264 124452950 269264003 770527917 853713086 47186789 898133404 78026669 740226073 24145767 321956737 399227348 595286835 774346463 944371191 401576707 910915321 334763481 926269538 409786690 214949778 543319853 581693180 605330437 327672221 143482810 347586586 631702891 563665781 210023341 863021931 64764795 697997934 709156282 162090810 199630695 476214806 432669791 616715689 278393034 329713527 149479717 862459382 866743531 432436305 504460256 650697144 996173306 677458530 526661612 864559648 244119632 14897311 362255728 903770426 223098288 603407994 67292316 772373291 604262026 187397916 146539756 611722098 410198324 117156009 404054116 334478377 722614577 886374785 956932819 330952514 995656300 826608506 100200722 182592972 39143035 285185833 515646020 329483053 992926174 234429720 215993621 991672423 647936318 458872078 292823805 214378837 584516272 591926604 180701052 222659052 635929842 199930316 159943517 91119484 151161514 689488770 38825460 312635887 74937260 143779228 63395938 601739526 934480946 372841668 430501581 438636961 443209763 600806490 256171434 676677365 762024526 987575227 841834741 69746133 58152878 728583039 348140405 323873771 419456165 347712692 619868667 743968509 380220994 369515558 198166177 899642410 46257533 680627096 743273996 824531756 614403191 137882378 558524587 524055446 914708413 685870066 316709879 827183637 581473156 837084805 932114355 623400881 321286891 417463021 534489388 362905354 780655421 312389777 15785592 172277660 3032878 431287634 649795512 784083709 196576283 643959498 991505495 701283868 46566221 120819597 709321290 330356866 481151284 283561065 937080143 940776850 773651117 256140711 20667440 251220937 188718653 443105865 654369791 752277504 661443413 610376524 773034841 271010471 530465678 66725093 772065189 439088906 765429228 523755461 979569748 267171469 115776029 15791703 814525472 588697073 173441977 430074878 482272334 85541006 147096961 851382874 709972974 907501465 460030113 772214913 331611415 438047069 371349487 703574087 301576750 218317443 357071659 711357816 706198301 106095948 395252799 627054874 227220637 742615251 516099199 860316334 478366063 791636557 571734503 73982830 187428252 941805642 216919649 909719950 665636282 886416371 846853374 830159228 891992615 667814987 612749114 639492385 526164557 883818353 395152954 331305247 582839263 761140698 731658766 984097810 889667608 956517272 897716977 679982034 32500992 207673239 937808518 675554477 49815208 373950684 208952602 370244782 28504682 524484550 56649446 247239387 170282540 590680911 480819532 636466800 295836059 109762634 125835799 531044902 20897650 285192868 300184765 68480368 982679730 789846180 492571038 704857018 71193577 954593836 241197891 838431658 754439277 386456567 429325217 562456673 244887968 696146651 926534998 722409145 817472043 118179078 511619304 308006021 266129220 723929923 514845707 487368149 353148906 187399732 640670425 105724465 918421541 273196950 3017497 884202459 587471432 837000066 69892986 76445456 763161649 978276264 502286550 325393733 863950981 88131219 482788722 821363819 918804982 71625962 657090106 820028460 958605950 170929834 127574535 305302829 912572579 415389806 974385882 152795725 937550003 829438121 642182944 854650338 921845255 514570473 97586413 972945152 277977665 243916563 840645443 155215027 346695311 623135915 522787658 469855041 600133352 227468299 813903255 774620522 220914507 41780136 741045607 487151530 855273221 899735889 463098850 373840755 403808745 847242097 101096282 142445173 382044055 431525963 449951883 143724504 557348023 617150779 68703194 190657406 750649405 988627448 968754328 252612419 143098020 455488982 720818750 451480126 93976885 523457790 41738672 441306111 471321407 246215093 607705724 871766993 124894045 122394524 947897370 344711159 232778421 283681004 620180779 90956528 925805621 300668855 221077691 763578036 950877654 192874284 767122304 853828086 766583771 128095953 869188890 114276194 487144464 808349640 207763795 171277534 726515980 370603020 907728735 242434762 584864113 20945843 862951194 260922689 734413097 64210987 365114958 610925400 574009000 788024190 301406188 856002652 679691310 330324368 472537423 772702486 303580420 543441245 313091455 548065543 563372220 150663742 96199273 516454830 124301938 802784546 226897449 331098046 141275151 123636183 738012225 13516394 652090242 571052608 263690465 865308828 478529543 679670685 441832479 502025783 699016034 101341128 941204286 443764058 27901730 824076404 386489833 829936541 733956576 514895470 406544758 255201106 872289407 656812766 842785828 93717191 609801067 707507332 946818655 674516353 24468444 153886972 320082425 81478528 336940306 180584444 62936432 608084096 404930456 471132307 730973485 318883123 566779010 5917802 391059136 271756425 488872624 337728260 472649254 844991721 102417419 73395967 508365061 522293111 405389509 269847377 712265196 963923278 993360027 537297037 366559638 161912517 10565139 711949342 131099173 315570860 842867648 260393353 173850728 961359245 125522299 371881900 451511575 150072557 42018217 674888707 854091283 779823242 177875065 218620895 602657193 128124316 914379044 564657071 523051981 403656214 491182381 203131449 926605153 852475363 255845793 627792862 169957741 799714859 353483350 722154459 292045926 458651277 443762989 134348676 705166697 201507940 793121105 197623178 72464254 932964357 110936182 566957364 660587223 189574140 173555229 893122470 625074704 151926356 680594125 917245214 282415982 211448270 961318233 49580083 149891106 19720486 18032158 758390039 773043077 70598738 249685571 411208404 158725723 522698692 379345144 309902992 988361234 668586405 204262073 864348874 928109057 42849050 914420363 952064668 264411307 408771457 657014587 186227449 371201276 121674162 158075555 387332590 759502216 592446783 681642727 527192546 460372432 11220406 271542193 933197015 188134270 984708059 589139322 108757416 479821221 22256368 173144770 83751243 678091268 50196976 498312020 221343759 452850242 910891213 692851077 775297244 758898992 520722358 364895092 886758007 962229260 5793365 750278217 276680381 627532730 620984586 967878007 703530468 679577610 719901235 120677883 599514559 123126519 531628390 252119452 720190200 659851748 919276211 907148331 826639446 875701982 865898980 678561986 463921143 23685598 604902845 914887431 211108500 547489286 730774846 401792615 644027073 500580577 505661662 604371805 319227435 398582181 342211023 744202922 926324954 873356913 17392447 300421788 324171886 844901265 724144018 179169865 763491684 952564407 901684138 660084946 434075728 334284353 964013089 415960739 453245730 249233016 570747019 493208751 210485347 642158284 317675703 162973621 481139318 502770458 62040044 443262335 186132697 591969512 409840174 134970400 661923171 564326053 13301111 396048691 203858309 866975467 207418624 180332832 933109643 780310463 359036536 958994008 635172826 880096205 654645576 652233878 974122033 407336878 571276247 197656605 542742250 85712675 841962178 36895486 930202167 893929048 28778528 343863889 207181159 581799204 939375302 908531064 69989920 492545093 812260222 332574561 980964772 763270311 976972880 195456962 223353870 924490907 929759675 835999325 836169108 605636385 965685241 605260859 226334660 442960160 69571136 226881779 232794824 661862058 432137214 561952225 12111524 899618363 189414938 335091057 280686708 920301049 410012215 95243859 817920433 741416690 974846450 791492806 885755243 636041314 924667425 81652175 967785357 25488108 151026707 863719040 363813917 321877982 576443604 6497588 267510907 227495024 187393639 883381966 463821983 924702467 215792908 298252799 9078876 477599843 38514298 700608127 183259298 138743046 164643 510313553 416993973 967109196 157956980 470713089 114892153 290071487 442268435 908928742 719548583 359213138 264746017 485232738 21385750 259250596 66187384 467531039 354031861 518177084 815366892 622930769 734568204 117210571 823245451 342531832 576904704 849226863 706759647 466928412 128321166 580938732 656366120 327432465 510049741 212232178 989625507 444878259 195825774 203990620 238364104 92260520 969500157 78288492 149668997 567190434 52993566 744864786 387185030 377412508 562190802 753170724 295976046 106609178 152556210 879466661 573332253 522075755 665675312 201258495 665227497 818316008 517638875 244010058 870560230 480427572 762243993 735671173 178143264 67138171 88325867 608885210 841828062 949119669 412572718 448301787 50623967 294793185 481382103 943344329 220872861 618339404 621196212 21594569 611255694 838595786 645549103 50477359 801010527 672457721 437924235 105986741 845343801 81495938 32467494 443389889 44655871 894553433 147152568 518559396 441034891 980339450 813026192 990873560 447288565 721646764 401748443 944450367 834143950 995835583 393493726 533364584 541965918 929473231 74623801 695993035 320154860 751713536 762671139 905394953 113130484 455357249 849239730 95081519 885712495 442987660 200008466 515825137 356622352 292999713 115239882 846526705 451699843 632767696 399380221 375878135 852825263 73247278 268582820 676015927 829100018 675261915 49516758 168513424 623237481 169693380 989969665 348201929 913222951 245561437 410347312 751177684 325483386 105039332 749240901 138396685 386684459 80612771 340902973 345247354 780436412 21064236 515018097 321319945 808991401 410527644 375073745 750174166 659837610 464407770 477005864 528131172 286985197 40852182 141400925 380327137 662827613 185557452 354131373 320881764 569419487 57923713 942299124 337585968 388276370 265688962 155234531 931199472 130892812 45567593 523093576 377998587 135745185 496754969 638066251 803476367 763385757 4228351 154858156 834994454 47374726 588354129 430665736 711076454 709367645 840653648 9539347 259623674 368346075 90557319 51635165 858583612 698133686 544462091 470422799 574033085 102708187 895985082 499101484 74176376 18820787 611390590 94047186 511385876 332051296 121508489 422420216 900219681 561295358 983128217 344888880 340079447 125579748 95994931 268564964 221934812 928921314 331803880 411317402 719963004 205814915 252010388 378160689 791434992 335569738 327393180 435579682 116617754 983246326 961897005 176405954 338888261 402861759 979998594 250844541 333898342 684790424 824115740 107041306 173794911 934949485 47408137 936693499 755537465 71197284 949553183 544435291 424700775 869606173 781329215 792088719 707976711 106333940 903626644 13563208 365146145 683820859 251660755 925938893 906679015 754483586 29788795 704476995 215732214 202070225 240103700 71273446 339541137 884063978 555282801 489366095 375000298 954615689 506733296 225478573 855240027 771399077 535800758 295566862 277906342 628384942 942432245 665432981 605960250 204855759 513159463 711434690 605694831 634336043 384999761 694051503 341671110 112559905 305330243 291032655 189120555 820064137 546512597 737050544 3313461 516879094 97971241 995932727 445359714 771338227 829066989 786638056 688066141 677947976 505003671 546146716 443726138 738792501 772749993 456676938 14881718 995394483 585318892 667195457 984593529 241536951 557950902 533871977 93689685 483914608 831531814 583769480 137272966 468197766 84635748 738691448 483115505 866623323 330189284 350682227 115597927 335918667 96570785 765781833 575648993 41644269 62452323 784580006 161957314 521326673 419302651 492735823 911647770 215711041 523773828 983417187 653346016 835533186 337631394 432445339 175725620 838608658 520191171 393934731 373366436 324271465 128596322 796300769 426552422 641467066 379940417 796901283 102678168 249287984 109021868 202111859 607009412 862072883 89637562 705376460 530642144 368791971 182078093 279733571 343307527 763973913 974358926 229767112 190741059 323334442 518108596 959799268 120615685 514534053 249072827 232975099 659295784 345536978 57639791 546743177 102555699 238063538 421529824 967167078 651858069 687649603 889354157 278600708 291694313 607363259 6066491 653399981 213049394 330719434 824760061 275384519 560284701 296828890 600531371 430549009 469353027 144358224 282257548 186602213 843393381 670311626 210096302 562845814 918784688 375506784 657309738 375628561 108084985 588882148 863584611 246681437 122018304 760759588 304021573 687477149 431403950 242950437 451820424 986501866 804842328 316683879 712089579 711426171 324549883 345443877 595835771 236356318 77056128 641618067 467143371 259882814 279945975 205083680 296278075 810441373 182676445 132995763 639246644 594315544 814231640 753947376 819580776 978920232 252266103 194002802 646046740 759214301 912262260 906966032 770117438 756058915 240000499 624304409 564617464 657135358 368632130 204713113 426289309 749133519 145934489 160882068 786817041 556223374 679079769 534931784 897575683 973810191 928063822 251213933 464581677 549608511 244572143 264782965 469640335 237459558 404915098 510636750 429161145 731059813 146863834 84909596 169911807 798673143 721629091 44718978 200996292 829777649 557880978 910170072 295465138 10570883 161200175 744008947 357334014 471173238 401397292 182371041 812307110 852538733 821936292 961363756 862162100 815757094 944073567 390371348 795213434 668941240 534176010 69773271 68696532 450075349 208893057 150426603 747243883 510033670 359650311 336425023 48912879 437651187 518736010 448452223 56135514 204159642 56517857 668984143 865390129 813249685 274560271 618225037 249157315 908330327 125767039 439436688 625651817 224386156 323931719 76237421 566141126 538091966 837628519 542016302 907494663 101373132 169796873 711497243 659822882 790706162 699011776 154717683 432945944 574378405 311156427 671016241 616676404 623628214 607652432 754964809 909638219 8621708 75425187 760055785 921412347 233493612 55388030 693713467 665272046 742013106 133281864 470044191 242336022 221561623 141069649 833918835 658250736 62471915 488521233 606401868 9244867 523454041 170044270 530735420 964308192 496936359 136657652 305218700 95777505 516832373 60421660 507380608 615607787 960223483 937206664 638002328 186725613 892315981 182631490 463151563 391003617 271220888 977813762 36712907 702096136 949623396 224206183 995460421 221001264 952794065 849313594 569045024 609208815 750797532 974835120 25889467 958932198 57538969 43812518 336775473 98618624 316087159 608629733 529725077 72604850 255383681 335002205 361954872 29199419 754939033 819238763 283934432 993837795 579322557 518289429 53206544 706539581 566426692 321287242 765250885 637894502 989151263 443825700 537143605 951267397 363016218 980722983 332099855 434402507 888343578 342893953 393317311 140253746 222420830 878369098 455715624 661881920 237879743 989566403 993555818 672414338 689674993 172422296 47769627 777078163 766976450 140474656 58467216 963488852 249922904 10438041 193651731 927933747 391147125 172353134 894614827 167908198 101931188 924300146 871621337 298531374 512072650 44961572 351087319 699055639 909169863 964189163 811887577 312229428 351067477 761771353 53667533 408822117 928137973 590395754 693703708 643753874 840945222 43763651 978737384 196970222 558733888 215422197 823036494 340547894 81271154 615974841 949156515 262459634 600294217 162628658 366467257 195861681 850240330 369828144 644001560 383476302 686443605 617744745 132568903 313459247 323460066 953709760 580200706 683778689 231267140 610302336 99731330 325559935 213523178 984099231 235148475 361527211 505723803 730032125 428955799 218887441 333368247 830672804 482338877 102984328 374958715 931402503 612012366 256737265 597929274 674978629 198385443 825271416 233271974 900192612 247535634 958027728 388541958 688468888 415109800 838391673 799136383 82554491 644516078 421861371 661326926 577797716 220428711 307612714 875801098 294346323 384099725 429431393 678895076 392460240 138379928 708604361 24363751 104515473 165347641 765510033 610826810 204344066 132584856 902680116 103665755 586040188 785277659 569719480 209205347 972685696 934182497 139393515 419722054 252721147 680582400 530790822 655464721 990309250 933228620 163035148 904420908 166501268 15690705 524083401 607290008 584311261 954722389 371363412 725094192 151163759 732851481 443125551 785650409 490483720 914434327 533547300 377490963 330981712 763973186 736644231 612250519 745269273 510071498 452012920 762484792 591586207 415037527 333374752 181061076 434907848 342676299 172127472 520138914 29690723 113096707 751361511 980137588 350224746 510001684 542963658 299136500 747244097 41359247 731557996 273406952 867070454 803491391 714935525 170361967 965853825 938919143 310614748 864208963 151390467 632634502 454922176 134327286 959062280 835825556 425965064 846953783 514584007 249953604 946965111 840299020 852812638 164921026 869367132 961048599 686056984 806009460 323830731 660797907 767787432 374791483 540621031 524557270 427935853 684984752 937747226 563599886 787921582 862249833 157842776 485610758 658920925 25851443 874490466 843152160 970023894 321515863 4776958 711310809 779413534 893658839 54564417 594142474 946525478 171306671 506101959 930954274 956269446 891184150 846461431 820764527 692194628 169871036 660371521 333017428 153523981 591815692 185733473 221759378 754731896 821875305 39386011 447040641 547622984 323386994 11953918 330813525 887287720 766941247 644160675 376197211 124869486 839935651 997167085 702781499 151934042 253501034 98146249 40992565 240392534 32336794 996258285 571568486 526694069 943301811 264853530 181495554 937653109 847716336 259051867 673973656 393886847 199112838 741097284 749376339 653866979 90811874 459969846 888061493 700830239 173471469 597367191 84125532 502766935 262056265 719671580 639110719 768677019 264516754 417974273 324926959 509754149 776759711 268140365 112392792 544394650 473587648 530664465 418733951 798255430 399657983 670913703 404744387 979641698 782359649 307717620 26964509 376767055 806609700 179871400 963530082 602350810 651201536 253559418 873560957 723548024 41231720 662906222 199633335 194415496 275246536 693187857 668190449 980035734 746958533 689021368 899277542 916608916 462683778 383765959 497212268 368364064 84459223 110407910 987116977 54387138 480629914 392544587 739567999 504924972 320003799 546260724 2131578 717621626 247773209 499516139 734150494 696223090 660163489 373422210 110452035 22178499 577933995 727599254 805892315 775573831 296528302 830255822 276017072 32229442 15728538 464917723 239194472 234821538 816656153 61436343 441257219 830238527 852427728 596899560 700293657 686791194 882492317 337718203 693106205 430621599 329816536 523510923 263357854 621206244 418265747 756150777 428879747 602343914 581667804 450044979 816339532 853707992 144531192 724024879 361956694 773146437 619436455 490456814 271556628 748267885 77842276 384468667 804872536 47594872 454340772 518736491 499309194 797702328 154872339 186256029 247034605 522118888 2392028 977631993 166300894 694481775 97966304 890358642 177983254 482332829 950465531 690860422 852628965 396776683 126955843 934461306 500075127 378436669 538431306 46214048 774134800 858459936 946578009 848932242 405243217 311270925 304456117 927370102 493736818 167175334 74035932 603358522 27659655 591647478 316655302 950919126 35836350 506602163 648673062 495245967 623371933 230486141 573262759 964722735 618913349 200690462 913121585 35417168 988945843 172709065 738592035 419296912 197536764 310291036 574859928 593776604 432589197 335087776 162484132 373466535 474436979 744301445 771189398 637857585 793567886 345146729 181391157 135516354 152569565 575337039 110451717 814371565 622497975 67611434 399565185 10836944 615173646 703490833 684149088 558138960 244203948 675619978 91533265 190362463 606629494 807149249 809538240 108406584 499604142 749008591 489785105 327553182 777092394 971394293 48098786 11866146 901803168 854324192 195943883 394948444 372572892 234503652 333323294 47426095 395796485 735981635 882700840 74649095 178498525 444652645 922353264 594744603 775833855 100708639 142249973 437875117 574387233 169346542 959920498 422313286 425503570 273753146 650479259 904421373 81345338 270644374 448885087 221790639 396859486 356722172 966611749 413327685 667759194 31115538 284714001 809461747 727815975 106848105 991508542 979288180 736208469 631677114 588584194 184516689 191541327 125576233 68271663 916481305 400556955 673513348 365029198 561529768 971595289 42620035 392938211 945216866 596376641 919340551 444247982 88162678 734253159 603885404 652074470 543601693 570463224 493909880 558071421 121787865 183754940 787543612 943352416 880542392 452065812 770911664 110250934 179275153 286193722 870762824 642172190 958082372 310197637 571452195 402012915 23505404 6840228 830261064 810087561 662075501 559870688 684694248 875735918 624881943 968730460 773580193 951748780 750154115 65201750 992462007 420678147 669557122 104429925 984112731 665725745 535425651 547115450 149856998 205769515 688349308 110649185 435897371 271997283 9127373 288573567 251236458 920916226 268892642 449585299 606273065 50408492 387655871 189565366 488379611 827747137 613081651 509539293 818648171 364600343 944625431 602787347 660660847 729387843 198893710 766392769 881164135 438201167 35379525 765339624 174593020 415139842 684314289 449487971 725886019 626697629 161470549 564937000 664999674 673767450 528979195 667153285 972394183 224080493 224979960 644182884 21842814 536025028 202584682 88917641 910481241 431729353 824026747 860488144 842812479 334344412 363728029 569504370 563179775 344310619 398359757 985633086 873860243 786633947 32692690 801036769 874909536 580973165 132801148 745334305 246967410 218092764 543554279 303163675 625031362 700084716 611891639 662757002 163256433 318337946 907817820 824315905 586231820 816886624 168082765 374628909 375280584 463462255 748190542 444637717 743494340 250572276 238840491 698069084 601429067 100422229 679273852 162803835 11673361 624752755 548542945 539455497 185545331 732035560 883027269 941277685 35523513 578247496 244090269 586502087 187968342 869006177 24193704 861105892 799477795 215748220 772928814 932794825 867716777 187083675 177671746 369290573 73895510 282404283 835423361 782873057 912656068 876522257 199020882 286955728 564474103 768188494 646078501 233529729 91505821 59261917 560584630 687192754 549985101 446050081 642534730 478934972 661865930 241482170 155280878 516829651 45658432 209934014 832739773 426904901 859125891 509065217 590786840 260602040 805886804 620336975 498409965 602916461 39602589 555562415 461925106 535728513 615698097 300262559 18614504 927342377 584558223 822880092 443113434 759398899 837799710 91479577 444432989 526244105 754052464 655304516 751748304 662012782 146324736 359097030 519781019 313132352 5772534 267793729 915449201 911641846 690908511 670482258 237069455 938525858