2094 752643045 664353897 652597013 10241198 30161724 605293733 543450353 14755723 929875881 159475814 568892112 101769697 957966078 117029837 498404423 400869246 518590469 104736729 635442293 740638159 189571961 11154023 66580228 320887269 175329307 573811598 221889293 558741034 622436798 378415771 727432175 200536318 535307244 547733862 762892905 857129622 476410638 366704953 454951883 192297584 807290290 558189190 517972233 93788548 362778485 872039799 973441784 577016935 217403291 328635239 132548592 842481470 363556036 488044167 431308003 623742176 925497976 293376023 404079927 104023003 250536299 574552309 2538999 320902242 380820566 52020145 858602853 705859703 486223842 275086469 34827804 111550002 531719376 6081165 547592633 462989320 721405979 652948236 920828400 596255500 666185379 539781483 365072173 292395002 199195555 810081654 981394305 726850120 482771212 992482065 591236956 59793741 163280394 476452212 877183852 273011743 707411176 682856724 272108605 36621130 940205388 25731296 380623801 914159993 595316326 510880415 747368176 30268748 12354081 588881897 389430157 963983284 371005052 884881509 186866002 584433469 644487024 922876234 862106332 683773834 732734773 420895343 788271380 972602361 286385432 134018455 561815389 950293401 411098405 589551210 512620470 794466576 634535225 110693348 476503017 342757697 238613315 513971663 497464016 503169772 620345155 522965800 522075686 827427076 69353373 607421241 205877715 578036380 615357648 564597669 596224723 402036607 525528299 144640967 883124685 410377284 540071113 136284270 590975621 428953530 697330536 808899273 61924370 781262633 109202848 551367774 779952952 283599179 204982695 36938774 144248940 420149201 690376732 842247371 652354368 968995010 148752171 82848129 63713529 381670602 469282074 618941627 520977522 777756484 645299980 685664033 401193708 266141353 610160889 101096324 424603461 382123116 215391933 76398001 238708414 202336353 140751359 716718028 152361514 473454310 672967513 383176431 217692997 889320712 206741665 360323275 659703105 955980229 704770884 454587236 340751601 668847325 475198179 676171981 87107386 469627256 204021873 870492396 702656194 616350149 281100923 461101809 998617668 168213644 441158685 163824846 941980689 733815607 974910052 258135093 506868256 769667698 660375843 471737992 914262867 960412308 262257708 173993474 972133724 901444294 898105552 978164236 872391801 739143842 301526864 309649613 575237002 896191168 991291505 791129711 359585446 554438780 356251746 344481785 745703508 540336032 790323900 803374597 452791610 380365218 638042303 210454681 37802429 613618881 268435066 463005794 426332377 141195620 648041022 664421407 44447999 666424052 43531528 832649711 466220728 698680751 178238311 740799874 656816215 6682697 745534178 410538076 144160539 274969998 219702249 418063679 654406823 658502026 625621876 695427884 420930396 704849238 357222252 104517358 432541105 964051953 991260883 759069070 332609321 230364550 325555661 57542811 570081787 292508232 117000657 773300841 943092077 36153312 132752486 113857642 412294812 140160623 634468869 415468816 166407848 637693273 264543177 363309212 41818428 984611609 46397170 131301459 967702689 210089890 266731845 923000780 710812811 964570820 326077494 818482754 554961390 658378104 249080875 670871620 460402312 876077163 415172695 667620772 494459954 74599157 256750486 188054427 104541885 191053356 621297531 667428896 199735355 278843928 573381320 630370986 975132936 503412959 866449578 195957538 27749156 127581306 992329219 131970750 772929679 437742961 188406781 607822113 766466095 721449061 494111699 534183123 140151804 483996773 937361658 132332718 761624599 612642159 452586359 480656797 103705588 243226625 687084924 95622955 310305039 828702473 448181586 496577581 806981112 834810355 541783644 460599610 952347786 427940984 403818700 431140840 703314403 226086882 145832820 712307390 953300574 633380486 976340685 763261758 23009824 913031225 769628447 984896671 128613114 208192007 458598070 270479397 660330362 997723091 34207266 424069901 336381252 153377757 155636720 620624735 89062429 578239913 56808065 501410548 687848418 677585036 98782951 433970643 249458799 93742655 542814538 63634112 895483736 279902806 155117764 846490151 713524868 558284898 192869649 331834882 842232589 384410001 578652946 186112115 911770584 300863659 930951434 418458485 196374309 422437394 220993815 144807776 734516573 865434723 607152563 871546625 841581865 193268662 767894465 877433154 416108017 351407567 926538228 378079527 527952699 153843144 414362933 844049078 733537818 821547511 163590584 114243676 343029594 663042217 595755886 127912210 585004536 720521660 457224907 618221025 520425203 376493380 890177080 923538048 725235221 681269158 240351390 952164145 236699866 452474570 97303334 652425600 469260031 611621844 296317659 235255915 47715446 186367728 551001945 679008554 678377022 970004269 522131525 45333197 928983448 226694734 594516479 563733320 968685641 832146802 570157673 44541444 499544647 919673602 933466559 462972686 965893584 966343581 151376210 544733654 647270868 254414351 958311905 560614349 266421445 879131634 747528132 858011822 568153113 112503634 700449390 39146473 620629377 846015413 922371763 947941446 180551799 363553401 871690770 594682878 270248522 964653001 179271456 792502957 549593499 446815446 845610593 436953149 949465235 823910459 199236106 278342165 29899980 84074876 541603636 613550675 10936616 488338830 997343756 346502921 703182376 439366272 675675127 257122470 740648661 217873634 335149174 125656598 832612843 264367306 832932256 792726938 561976440 537259024 927767007 886920418 813843910 601408792 275799200 540719448 712752771 687247197 608543025 123625019 537925685 981566684 890193311 172060923 559259271 143867974 813849584 801229235 264390113 893193530 824301605 280808734 887697522 65030123 506681385 555428416 790333757 442219824 475029041 495116699 230247205 13980425 309483683 759777682 658962473 52850345 724508485 826236700 619136513 475146950 281791210 750712394 203578968 240011623 256575193 769708163 268776385 763496140 838808702 391569124 321350134 787991575 849469917 479528786 443799934 21665491 822884961 987937848 926418708 541506979 548478953 796345358 748796894 223538277 637962316 17048459 850341733 489140094 782095873 396606692 288352000 229054941 526617346 626100937 731594203 530740068 310266074 454763236 3804634 581157923 877956094 913746681 555457180 195460058 506865645 173190761 871798577 936640331 57138559 918008048 169473245 564345502 905482463 679043994 430199927 24720489 799878441 917397259 664167839 66214293 300242169 458136639 575913320 432201742 234679381 211382993 625800600 139294667 722490348 724775525 163708185 250685963 49607667 874760102 137016370 544107937 69503356 48573559 185483976 246534956 957607717 477230543 263228372 363374522 11517342 73613688 55865789 114504869 961992713 13495798 927611543 892412304 964654608 383575634 222540607 388002982 382345226 323946958 930378950 904184281 669138220 901577527 51901252 745249405 811781089 480292405 666154183 758012855 23704345 836232211 676340938 333673765 9204623 347652752 789382598 729535019 114285497 443264909 229643754 84250944 511123420 871565076 556096099 125693510 568936715 100761214 498024246 909337473 97697239 757187156 164082846 299476155 735447502 119713538 602303343 33919830 50801223 383021639 120262086 807027282 890135971 719353034 941979633 914269167 479814739 492399504 353730876 242917588 408229841 538493337 827902928 130023313 807119221 836931035 393923902 245609607 506934518 662964383 313695972 664606776 327692959 531745728 198830237 149469125 763816672 167225380 45834721 49486340 796626374 226776454 182099457 761515698 372721292 870700155 153014761 141945058 184887145 834768526 51090688 883824327 349325988 223532759 170722956 922235719 6987399 722669113 996753295 553924961 725687348 266677375 237561791 799159670 459472854 153374354 365186374 849669502 706472731 394111403 969011065 667750972 533892501 295977412 682984660 72762517 634005270 474279556 380828649 204741170 24716599 605783117 498397888 383072410 479921700 409114463 782058683 776591473 961019770 850163954 661953496 432253025 934063024 249684140 475551165 113807119 483693219 798993247 530916124 85539224 898629997 276174771 394860860 214206957 635991335 170651477 42904643 692620677 86367822 46431650 175629091 198654365 296348844 320289795 835774883 40979978 468753577 271684066 715091757 998579676 945413731 912610677 74701990 190232507 135593580 727489246 163087276 393521911 141947716 942915652 510421716 196015001 71716722 325729155 551278008 364071148 406435148 291881972 199400280 165264995 60762750 249023772 575301000 735575028 669862550 707353721 912537031 98517415 336186882 542472609 887142039 787346427 96031610 980407370 971715040 436473494 555758961 306989647 479428027 800602567 245716830 966097318 696170492 658200582 750495079 55900886 83244010 362491786 490115279 933022577 510422595 786881534 162879113 142662745 764972718 441175487 282321076 833616902 231944970 337442265 195651536 201863714 34039871 139167347 416531741 115944774 957853377 652353995 750097377 506514062 77750528 24926917 122170210 372097843 680025626 439816029 173043203 500958468 153454467 853128362 875305448 282708653 822846075 38827583 55856075 889182156 99107109 837473120 38209590 337039584 488683984 164938524 824950523 561931286 783741409 254331679 143944637 8102018 609273916 573334434 674470712 56057071 35378381 541792175 951929069 505505946 874082716 130059638 754481320 541574600 266427241 788124213 142472691 424637218 42476209 254071988 780482966 211547416 376905981 7342342 873852023 259812716 567646265 875095586 392459262 968960991 854798643 512757951 997229898 30197709 267953577 21240542 199316805 480205749 700958465 409074412 554070459 358159156 377481244 960090407 643256755 818752441 430506589 642385920 124022763 352045153 933919971 52794496 610822488 592447969 216805883 547990227 326907434 783238046 52657648 191823597 85541797 179284103 724734564 195048114 990739464 294488015 306294402 886755502 443683589 774620448 357482082 254579852 641789509 416053873 874908489 106458231 802073071 957657429 313649846 356068397 339236773 506227979 767100626 777973200 596016610 392658810 705650613 574334054 385907691 661898034 293772648 895459813 266604488 797425958 632284266 451217361 55953943 745016601 822244426 792051187 779639680 321629850 845161805 943977487 725787319 597340895 425774083 950028443 275152256 45837791 591112616 724427992 141638986 11637721 880676073 896435813 721252111 811407383 403561869 969626405 123502738 431467124 540907410 595248729 528663509 966115507 508171844 89309403 211689862 182649372 897672045 184853421 986318847 187924692 937752765 242871365 758047861 789357765 792887020 611502423 79640831 739127816 262228581 686161960 788591196 918420558 195526714 689377724 298360928 660763106 877306615 73759361 292498402 134699903 436222562 258774250 367863407 169851474 192568098 294184517 681217797 195368020 259481180 206710709 496034299 203040447 862734426 378295141 339457488 421354979 629256712 644102642 226515953 239342899 939396436 239841836 322487064 249053854 963113094 82481333 356896360 395712559 851582048 452457406 837732001 918632425 351615259 891232634 28449304 466597813 593791312 920862550 456260210 24404186 344467695 89422544 406367527 288433342 33585142 90734174 990430086 686529912 924748086 771384537 445709332 122642994 258336653 305177442 151351266 884299693 815366330 261679955 58812002 855855999 301608409 861171665 902825567 834141842 396501021 199419375 60445865 301123075 81376050 401032389 694453652 527011051 871096337 255307910 801068363 479532252 488976861 929753603 110241797 799338326 849204072 703117063 271141298 715580246 642600402 787924764 54953453 908298463 425950988 528365661 267419494 479251209 231202439 569240167 821332365 572938644 328524644 942394022 157394115 317178722 504218323 766846340 66107763 344304680 63269661 869871494 430069489 893876565 659486824 739139433 568447949 312479073 13887459 381917361 542150299 507621282 538386752 520079688 189876505 402005479 238933348 104963712 894607730 155831911 423169517 393760186 442715806 818851248 170086538 549821597 438342282 452722369 237154140 415596823 80725480 764496595 357151709 130533892 159129731 977000880 463900029 331609859 282659551 254217832 375937251 611712081 848969069 355782621 868403518 948066574 354469268 30601209 9469305 959201050 867298166 392465291 353710684 952099069 797876122 21394171 93176698 703466419 426840246 76225474 735170701 983814635 817776147 903081745 764331916 958404146 543625650 596899561 310485143 474196063 651469088 145332873 455825092 980479152 563959571 299582248 198374235 888642221 944074951 685961803 430911721 310275416 195397088 181324439 706274675 790534056 181727077 122841852 798047056 502949045 877752865 900753794 288613016 309089206 191613522 319579440 316278679 644639838 342567052 176845510 406345734 997701522 782768863 911112574 350927166 442546979 290531790 86740897 529554854 502945855 591936558 482080112 418931928 39560311 118914194 606848317 750101069 448300514 965440572 921004774 905915685 622258638 466677274 655796548 802870743 77716903 604383003 177041787 813985544 348261864 491079281 8189022 535180869 948547908 796557309 532708739 784446035 765151799 743229514 525662408 908918017 674922333 555462240 488172187 429633361 302435754 882238416 412883707 438185002 873053915 131716990 888421225 418005783 81904908 176921390 383916815 809836194 858624543 479627924 689819018 746337792 949127053 547305410 351177142 580669994 184256559 757666564 382440364 702542113 654006511 822513940 78765548 598027297 465216287 225779775 733639896 536653463 338770310 867607879 316736378 181166812 909576707 686166502 937456559 672587095 860346263 889819217 45970703 773780116 260702636 300872275 304689661 592849650 938767477 355475280 389252987 733382968 173040868 576815631 548117434 60299754 235212076 315207190 468355210 651084090 622831857 219505927 203951035 912628507 375327497 392191367 9958904 32156880 738213025 565135208 82516759 249534175 96027859 204415327 844587169 165717967 162688590 921191173 609717337 170953449 830822548 807199921 55774970 301234660 71748880 6938338 188038209 463782730 646680031 758530978 141445574 256235116 358073507 303431490 222209623 986487761 17989831 875485280 173698545 960933543 716612165 56980983 257850852 193803493 695072270 383433346 214034399 926215375 728152432 278728258 148694170 204229240 584614909 583648497 649788357 396034733 587576159 906670399 718252401 352403265 984701025 511147506 982252950 570205770 524545478 705961197 429964194 435857567 421411176 310763214 767801949 955758953 739240356 653452922 215130660 10818962 611186054 291435825 939399631 588748228 344135683 817996790 812862293 669206011 143800134 110787057 798104191 990626560 446333188 161601740 405376537 108744247 168278178 948930262 674214642 757674502 240112416 865394509 873902959 654862579 682331514 905175955 886501207 273533549 593253770 71842749 179188405 501514059 349755443 168191891 560909990 437186827 170542999 591622933 158246099 81063735 787420251 331072897 787474964 396663150 400985356 41548587 436756021 796722471 553917179 403513313 245052516 551820869 854740757 874990240 634296340 583500041 936426693 150975631 355969382 125336632 997512921 535209255 220717735 539322834 704840064 256397375 932218862 364545237 631024483 316951539 196868144 833285418 587992209 694891155 911555400 739273034 692329269 756673999 103254591 228365816 708716453 453517151 664806725 739055610 908494315 149779236 765575187 856017751 824422926 726381912 520246166 728147240 761368782 596315636 307350678 27016818 559689191 943311682 226544637 871766256 434466027 21534047 676243857 963035869 893173204 937373064 866562523 115700912 981719279 419162331 368217392 198290062 44657651 23940207 266683832 528428352 228551154 381480157 272125174 179645740 10557114 374209887 870463867 390800906 333976092 510206964 342067653 227468830 499138752 528882723 142411465 470028678 891211117 452648692 491008976 864899763 702894550 32810907 679099606 12386924 967167262 640829681 291410774 74974403 263797737 639739889 173630898 280247266 187574727 508001182 134339865 38620239 321254123 66137606 506819735 405429168 488564819 159141391 821627829 779893519 92395216 748587723 803975989 210644165 137493808 657806464 104732154 125000380 220303166 423431064 234463213 268128694 973295826 286992518 111778521 719174433 983394227 305838521 636249762 486660477 922356288 586244364 64990729 860248224 567814083 918469868 299212402 728404975 532603776 549842085 39296231 433908034 791720848 203528422 180011470 863046381 905146616 339010806 508387733 506474306 30141005 964134724 72602783 453285181 24238737 367872722 719799173 620917144 176370528 833820872 375137587 156922476 412388551 51912162 718886375 509109229 97091537 743093907 57788789 517548550 981681970 639886837 51358699 515565178 348448678 961185868 932999371 230794825 853756327 816264242 367090753 477952172 820287326 478073511 696188183 397610927 592374249 737901621 616091246 329937900 139775726 971380232 505303038 908110660 367116981 998063958 784531006 796587302 156797210 516380568 780885506 231335366 63994728 946079251 188588716 261757602 913579078 773397370 577984698 857088452 967798412 422842303 403173387 962601138 354860683 147135667 808048603 225295232 746435249 101814469 600426006 95956714 224161575 170412006 611769505 901974061 458671203 317596769 258336351 530446343 368878887 495692691 807560030 426455945 20615428 844776928 398688697 816110447 930053195 594685532 414208551 656214452 388050406 580311092 195978594 8176426 60298268 807440447 772642032 78578824 230931361 964546002 699671189 11423654 98293558 816843351 799582185 419276302 410972412 965626478 468862388 274939059 907392532 49272572 256934247 343423988 52842996 685017087 880350542 383061401 278940540 992568276 680706385 42894443 904088087 252249989 549856931 809252732 724550152 834774447 889344768 539203836 213702735 148351359 738220473 624170135 826340587 23517664 610297960 495637173 241471513 266361125 534885246 559090007 452658626 703442092 713752127 289303645 729175163 261057086 568410863 686644797 217423362 134833153 753132600 166739609 217795284 223505855 951660830 409729909 20392455 462733996 725368748 874592316 313863253 778614922 36540313 750429360 212977621 847012838 406080855 521593616 959737194 699171441 874985510 93946185 148856919 408335262 764340555 325301128 706196160 618082408 985569024 137346312 737625984 384580672 149732442 597190014 462326192 605483015 367740783 187088908 270435179 242881638 394083262 745376480 291573873 325388630 457363237 935094445 19700752 114684734 693176231 480648328 484392108 745721019 71758325 164451688 863749789 505724057 516689188 680384045 916911895 571934283 230522278 998931691 125762767 663442520 75066086 455706327 723257021 342291887 103186275 426060294 225768674 696807466 630418484 384861657 169277893 278150036 512545377 72159342 567133114 21327455 770580671 351977072 177930326 612492781 82173483 135708275 685442194 59033605 889005966 316063158 795497101 245856527 727083223 251430911 507396349 615616230 157076495 339154479 72113928 639634271 719462452 802414049 327652653 643233628 621305573 434289518 816798085 131133055 673279861 360411443 31768798 706687296 717662445 852899950 754775902 624211450 365505869 647119303 648640474 458659541 661599364 526160973 839568604 835120250 285909487 53829682 187373148 855016347 934623086 207225115 909665094 708575296 500623756 309779774 634865733 445424582 360724018 95417724 988962544 614432577 367651083 997085796 938622271 177582715 377572956 422983418 110805884 508041441 396297263 342530053 167051404 600857625 702467623 565839262 95248088 544210318 234100308 258101809 27309369 724795237 832016646 285831938 85879142 779176455 69454771 625548132 857314710 693110487 761034579 525076505 884885574 230812003 225702979 72945963 158731375 505722355 278668635 757195359 131446078 652829068 712025373 896380692 186358677 493823996 595340547 586435933 156918659 452478132 678759475 130960433 469904018 573792273 614939562 122633940 588436920 796625894 446695806 721576222 384005997 997878352 792306924 36758827 51988284 990600160 246043732 563284075 212854721 845808574 823663247 629250545 829476518 939308782 278152574 477183651 231056171 676834042 338412116 997900476 652399349 51812601 487195834 947843449 731186564 917340963 525728972 615500004 167228077 860048836 76779681 851209935 639301014 572091233 144593309 273736256 857739075 883739915 664772270 998459985 431046765 993806409 864606675 21381968 625811597 842571702 484044976 621348062 552219940 926691995 355604558 375066154 196978405 85362682 858568590 938308780 430787999 386114244 907334379 949613787 288847833 324726136 567307002 993976395 10118410 27813677 35613243 535483200 383492660 594179067 490604577 219478282 133758006 151384644 575485915 77961856 702222119 918058941 906903184 96815652 57367605 986786687 742214122 951871112 419619056 775789649 158728872 635011204 848993296 249674433 937626242 740964738 663895073 403244767 205722285 903806363 982836059 168007222 18543393 654126248 486912369 306228199 737721242 138045217 6105730 119956288 922083805 280349556 625643595 137898565 607031777 343436894 15964498 651751759 619248561 188744883 31863216 206088662 828207884 764539886 668233588 631788819 9948484 513556017 215196657 657709629 992716951 492270075 948877631 244880774 851663777 33316731 73869068 970335352 226524526 160994733 891946063 118194096 650455380 690607027 65531028 387143746 884376699 293687261 65048111 45888656 779834063 672390903 66995772 563586739 740657497 234420942 602408288 833529348 560832264 773186398 146148076 35065121 17492481 509885518 805800075 252368510 982697087 612048975 253198972 115986910 348245054 728820759 354314188 269806143 982899721 259575160 243814873 64123865 208970491 893913438 186255465 85702824 423304105 992123225 940169194 196994242 354977012 743637258 149678040 720749966 450806794 859795202 581052017 400929078 875049107 785335584 54525801 813215642 407589490 954139035 775894868 17237508 357413434 382221300 245531029 122402620 722678752 763329793 225134151 33255247 403217125 167536749 411565887 684592986 576843986 458471628 649668986 991613537 745500649 937264037 450185311 592763499 282550678 36371567 678289022 667013483 732461413 130242380 337838126 668791201 513084735 732719425 94576049 174454614 650622712 148877251 782463783 350245152 447546607 751857559 61484422 830473127 17737524 715440514 601179645 933563609 118097759 581157339 913843397 801932303 144479472 827633107 465631160 496549448 252443977 536733828 935139175 696256099 116573273 589921805 986156899 763605545 555346267 597679887 866464388 558575146 657033817 614297600 535088755 171999833 883464464 433970939 94018118 63113333 807790864 217179871 911751393 704945452 456142062 685138774 911861033 463247657 747074792 8211567 251460243 368641478 922626165 6692003 933019353 608012612 673861072 525513896 551717459 123912403 504498529 941329288 604548484 695645319 764088459 452951593 324560740 395188880 971515333 688137278 81679477 72841431 203549427 567555110 477320933 475522530 440759903 556882715 221178296 151193203 74838302 823600521 395379978 774100663 735229884 547948234 395133192 50762507 943011621 14575661 757929053 169257063 370405160 564693146 499508708 819202666 152387204 985000722 619631482 136582107 274716335 193343766 774438202 324931369 47356574 694122084 443644352 263788644 249889562 635649509 834430632 201447785 161315395 374768780 98547208 964597187 470538506 543163360 122761407 493222671 414330283 210435052 67982344 924979334 874533175 388688040 21614307 206712895 661509022 164761099 889126504 934108003 906131367 140735970 759533699 748191236 230068926 326665760 234536704 185486537 587810755 332036111 814653956 340208880 520825901 937584805 641293370 57618340 174476758 885022031 967975253 413812195 97050372 761148762 793321577 939940616 742875701 418276035 83549903 694687659 69189796 557891914 188304837 36533439 128322907 279259586 679420878 714086306 616010764 4126176 669184243 12919872 939095403 165013040 285739492 990817348 291501602 129738404 448229786 794560833 120608831 281558778 804909148 962319465 431152807 444547391 8452292 665285359 65039228 346851850 347976052 294693974 381669191 811495403 771282108 29483221 216321710 255718979 779025143 524289209 732606241 384779348 154024891 562564013 534858856 283666429 157024055 181132653 722976841 189108353 551117140 728060252 145624384 980113665 815768280 635302304 14163996 774363759 192550601 446971718 958551229 412731937 668610986 846205752 853803224 464917748 879997539 543083484 71366200 890802787 216532733 840268670 124850552 128826406 673290113 947672417 643690421 818617188 818678051 627918379 369086798 251111460 62484767 620685344 29110550 948193490 346882059 762257918 847446199 965381735 563281758 159641100 938562755 279323254 213758965 297682681 426451475 459778316 930110072 20721019 644944888 682394218 19754532 971200450 833704651 243957996 462352627 324773536 855190176 879424646 391585380 507969302 469222029 716559232 415475603 213966284 900070914 112593770 202617473 661654781 190949601 661648503 994493637 200249721 732167345 400447174 471494015 521559208 973934232 13043301 668272584 837055799 183503336 757420639 411295619 239219279 871664063 360140299 775204542 183123678 12135241 644258888 948877413 936959490 882682938 972749079 51160767 284557981 680733005 929733917 447937517 690239605 285889040 303026848 761260732 621661851 675785473 130268265 545272452 740276858 979844380 559920999 651669227 478798895 922788443 856624406 110028220 793313363 948521047 490762804 601986867 185700966 493160808 387490835 632481033 793576095 266941968 644071246 663330105 14526552 70127120 2777415 532350080 104956403 534236437 16847448 789473501 942264562 730237055 749879863 738613889 973067494 700929235 561485286 410724492 113444357 581801640 505089005 384176812 92906147 599265396 693705002 552036509 173004724 844951706 787495088 435106738 591851628 789462796 575569126 124799823 887139137 254110589 51676896 801168720 609128023 608061320 72437339 745330346 619254957 202601171 203645045 934163956 117642954 106249831 910825478 417651804 154492418 299557674 483938483 192483054 924537478 618792752 895611193 880057419 289098601 505965212 751211399 155638080 651982111 892988133 286130917 899646614 89842634 972713915 794156003 632494419 281026314 193633006 219310919 408115675 876173826 534878303 545236426 792224552 829617023 93845628 717981355 953579563 255454396 934905970 16625277 670108208 632517616 757893568 75564217 225013309 636965004 9866331 249055957 751406109 272497902 115306074 665486576 397441937 842343423 394101771 685856315 345312844 890926980 896796646 427334246 507673840 866195201 651779610 197508726 74294605 766085220 275082136 409086316 547746959 934971856 944022068 703286800 971788569 647483150 326775967 516386017 25818496 823415658 322251921 414499604 868720003 764362523 666165689 819032784 767968738 619468683 958537101 991418859 13666794 741998414 589537232 787842088 12246612 348090146 614153876 841970502 77461593 166923699 33824017 35561213 290963737 60657551 705440872 688119481 99077324 790402183 17475004 234696241 383688854 217933339 535441239 498008015 890239410 720297971 172952041 477436075 700405029 797607438 526368132 549513658 223141062 860937247 888607911 396049729 128648778 655929878 178720438 781337864 911028182 958061931 86468460 974700463 354141312 946269501 895847317 98666388 724567560 703569411 732863218 467216845 366484818 239878583 246680901 854382321 314626826 646199468 712169885 273510800 594112382 445709706 568705272 865289428 983459859 216279437 278636582 649801495 243676217 270032770 216616385 358331637 187674752 28456438 989829432 976733932 564769900 767929670 239427248 673770356 40037514 856524945 733492730 804542480 219843009 782179733 834195042 397058852 954322860 913304569 676466929 490723638 730527258 130230224 817949787 225781549 481436881 172023655 836299290 757624822 700825107 953490635 842377893 423265123 753963300 986784995 429064411 755630833 677306257 625990330 799445169 975706558 250152572 381054218 392034481 109863617 862014884 50788040 234465202 84445270 14148586 584392184 628437872 552509956 763188977 987972990 341114625 133514804 559995806 624336512 410392937 718871380 257397904 994173094 755198043 341961940 116656140 378405388 751987465 651504976 377558063 864132063 940895483 855024221 58015898 186293083 593756684 110288501 761540038 551200460 677005681 505777077 173637612 349051470 56320906 883641538 378485427 424457510 81219247 333669236 582120577 299294183 851455142 8812963 324906687 700761313 257413111 743748836 766407132 978108497 150174971 621028531 68205371 86002030 76938929 541952368 202428656 289860411 961302378 434686346 337094467 750569491 696305339 648824402 367396285 983413245 445029750 83791468 948395208 723889547 316704983 594128637 157119838 951196382 974071741 513393849 588577871 637412384 428412106 600042095 440688877 88269273 983954184 306472484 429254820 348618716 268798339 378861396 859006967 155471207 455704075 174563583 2087091 134323538 405557573 138886566 244900010 320706717 17653548 262284160 250885722 224510864 582843913 360524212 230885409 542620823 864516692 427556825 611608795 967333151 824597392 574081491 881850585 724573547 186345446 852058475 919407937 166058099 133231377 408244706 877864943 100750179 490245475 724081582 276687399 789208133 320405834 286600907 788297743 82198348 163394203 766821253 849647939 411110534 150055930 152651792 543060482 809477290 693404120 154171703 690033653 397714428 575776896 753296618 974099313 880264281 985550917 459282173 624671038 962271544 131303524 252060500 827168405 68233545 707746436 700514786 385296241 424356790 252832592 785592542 490196819 938518471 862780442 718186758 394613796 887681470 597357607 473096890 232690016 119815895 994027088 904356144 8664518 294484729 720377006 242987602 538127951 280396905 794899454 302374972 964204031 514821345 502898496 6495778 528306358 412941933 340085437 590854346 832123811 879792289 979521925 937084527 628489802 788418538 156990082 243438153 791596445 135507236 269018721 974909 529551798 571842856 426367141 295631156 602947054 768938099 724072804 45638173 549582010 113994181 817934606 891945709 139255147 238517871 123595114 147655596 985417782 109766678 265253441 291771406 439495783 326309209 229793024 544298948 431789479 707132331 16936872 203717688 84887976 16990436 61827028 934316733 482009919 516264257 397075210 367100773 71228373 395171712 815048079 691211966 57826711 708556102 466982171 592134435 720126482 633308205 441507400 945180067 136400763 708857904 808423610 440829406 259173958 556799226 837730379 896370354 595961498 837292557 480068847 670311794 71070172 758540542 337496969 677059068 991249162 662728273 192913261 490988959 219585522 449711706 97560863 463721184 52707765 442615794 269112801 858189623 167897504 147714182 555025445 639983811 725693428 162840463 679321166 547799165 650421846 651760346 679458822 814516586 709757612 378991120 47086689 159032001 247331641 966993100 515716522 334612590 517823755 852746879 623417040 479195396 569811878 852250450 510946716 209819919 258583431 898794424 364387393 507813256 391534645 646187521 579073806 89303635 961935663 377350201 296960116 749907207 162204389 938510399 560567645 195771924 332986170 724222820 459875488 826313945 269188100 666445462 79885377 789659120 113538559 97023681 814218259 881786540 738530825 873379862 101151170 45499213 617712423 17696673 523063190 299322377 36299192 232402796 811177064 451715264 894992698 792043395 960714460 102412130 691004437 521100418 516681153 994885128 252432342 263326675 27401353 714581470 964320714 270292006 791249261 730440262 830495530 304583043 693794447 726159565 490709503 994308191 116886006 991778131 797604438 218110707 532385308 940254564 891347292 517313524 892807916 199457611 412344113 707381914 146224956 867238941 5527231 684215299 937687678 568257015 744697980 507720955 390865759 511863790 678425517 196009939 948291952 894554138 596423050 6277302 26405285 847935336 441322471 955986199 560865609 626166839 887816897 195204923 136869704 227009977 726287539 271163367 633077501 247723733 684562060 8515293 409971738 922142291 754371132 244406210 556255143 192125467 596437711 79935930 460469456 209149904 117051212 264179740 344151671 50855569 224058835 358257783 877458511 835606181 757416789 994760703 591516109 217003205 508355611 667022348 748126583 922971004 767675806 663151885 449304791 518933708 743602957 35935507 982738055 668053181 127874354 837927768 533912014 630868813 834222501 342885988 51642599 102424792 646932131 151294704 768719269 97885735 616137275 378483513 473266399 584472015 105855877 721135768 414408161 34879548 599874087 892302221 494671667 860262149 58688067 812491598 591157022 375881554 128326237 632942093 283587358 845797011 643480501 372062133 799531288 609257245 838205796 462174549 632966948 346746287 36781868 630595323 559945820 662979528 821147779 984632319 342036926 264448113 917751702 120945844 479207389 729434313 782234018 209337901 656434527 911157457 395612489 228590775 660053186 447915265 999942891 604382947 94449005 102778367 652565233 695203320 813055568 844073369 981233777 277931804 596592414 971796254 71571270 338089752 390711220 584043840 714703250 724983682 858437100 147790554 870714298 472264874 46562484 31608984 421500146 360977824 441629434 153496479 398651871 948939283 622944925 872043033 321716637 89495491 98276203 199170587 261816182 291274691 219799980 737828294 737138947 373498542 919649995 737389098 162334376 769170816 631716355 78310567 878764889 679748392 296251331 443353660 316289517 943159601 391789630 438692241 84777754 18423313 282400858 675580447 343340857 599071051 535953916 232604432 832439927 796940119 664897766 544077711 841740524 284553951 759662013 290273603 54573144 185212382 340155171 493269103 294239009 792327310 292826294 489538672 345638011 364074611 821070355 855227850 550899110 884522106 906435817 124889727 538021876 464564326 375540690 873149214 729100140 710813713 352547213 459899909 17652901 501598526 653353670 604599427 290002883 263442557 323036244 789317496 20574460 469659502 80956084 814034090 192606402 768621668 734371590 98282427 724230619 735941592 219615897 390039184 205652950 439261474 123959533 851308251 828766829 432801829 640815099 854687554 566156989 51746610 158531043 85468294 255785886 7821419 750210565 235900352 887690181 750283711 504912384 335812229 793212014 956033409 739388908 755333481 770937060 536135500 233937660 345431202 147308099 729564533 718559032 800741083 530050889 107259653 568339632 578442214 917760321 55550149 428213855 500821240 379267857 453090781 958010861 433697448 555545260 292875625 382389272 265820607 181866209 525525719 76793913 489085215 247700889 922733927 954442805 159387755 290312109 681032322 851390036 192868052 935210783 415786773 933036485 72243007 819882143 559144890 34841772 591336584 321062499 85468031 597279046 254198982 315368421 647009922 999110798 938566790 725358557 575325799 997628432 830814050 839670971 979805675 723257783 851371551 124232796 582279980 632098431 788684367 626708273 656847373 918525594 67688054 984747952 867017004 957299086 688225460 441433539 586731014 552253088 402916198 941470702 67776870 978796865 664747355 151740828 827207986 444541549 736240592 594398769 733208355 439933648 651594141 258066924 647774192 753946243 670741553 667970084 411921793 282227226 668141761 765056895 788932732 958064844 517667765 643267586 763297912 388382641 371172851 566494945 360638901 240608400 725637042 813857194 962447086 706508047 639867617 374476146 362151364 257674922 659828782 678400160 52429243 456575422 467519730 736752833 727307577 538374878 764235594 560497299 338073395 329393798 921989989 871059427 739411957 938863896 303218115 616694985 331957435 836988481 849317836 726783469 253596501 932519305 318806351 258500204 6971275 229539743 805667481 620890750 687717360 314371782 515974291 833900982 2363478 62660777 880291452 782892973 705290899 671409387 717147283 410349617 648222178 961743150 54603567 858478771 816751942 123893592 236500084 60460029 68437207 7119718 798122707 241140815 608913355 334892482 576480983 724350812 425894289 55748953 601289999 60456447 453394162 218484479 877939618 773247044 577976752 678229052 825233923 766421501 531221034 554730153 280847528 282555884 582686400 982968341 203538823 215490960 747093620 827528342 985839472 951133565 581317655 570689226 631622565 699352918 42284928 462337040 61133729 197223434 513703693 279269493 508157555 277158994 10368301 532588504 942675194 126936942 916050026 539018947 888265085 117714797 461335270 352657260 577462963 927461203 64783126 976763122 559743663 801518167 138559282 977419200 475844853 177209237 315036081 236406792 894455412 763074012 358763105 176501140 747891190 947474305 169514748 75065979 49849941 71422177 655252314 684149455 259230435 282361745 943571629 903297848 948930902 449475007 275738850 376667110 464245692 412373142 531455881 516566138 578127057 183833586 255181756 937550162 343275180 110835061 600821093 728608740 8472097 749153073 351107770 430720347 471479956 954612155 958517484 93582000 102433888 948087380 899908213 490975080 594762085 911640377 647386887 533122972 940164668 142831682 25016522 962969374 134305919 835795845 32636012 584676125 642414194 742932476 487770158 586087205 395173266 632146284 72268943 85583855 318628954 9638421 126717928 14236001 414425286 766959105 206938890 236852079 526892499 469644353 421865176 878495100 543446990 365374278 190406786 466909727 927693271 376038772 495793459 425858882 189846071 193373036 830575387 287033130 982542548 467627706 827575660 382710285 627713835 337488422 356987978 606631571 7950863 89838166 253178473 613893544 835848483 500680641 100709922 433856523 90018736 719097430 99955541 776622529 575979142 507623109 291095008 614595376 379849847 505854428 715744053 210602798 881911623 221274121 351325765 804395606 502640783 454956042 882286621 282640246 539912477 6816125 537671084 330853810 745208298 765858482 900250948 773121705 267187133 434774951 770938920 426220993 34907786 155417373 725378164 873940543 886549043 87706955 311227244 534592501 32807409 282613591 68815979 719677533 136547427 459001459 169107381 523348573 386587239 158841999 917707060 479436705 826505374 633124440 419489670 564441517 897993728 345802688 288276290 647927297 520212476 129647579 712722795 834612538 375207070 839261469 833853352 482148782 752812284 562694618 419280812 507499954 593047697 762554566 939219866 760611941 118338745 518003436 497795215 144919313 747759514 284544105 123484837 754687128 230743605 48589841 900371039 86730418 523834861 723544948 893001721 503321556 378767040 623487289 352805095 954496895 681152945 591226505 413700267 487379631 598431723 974593702 715230172 608020470 21355174 487248790 740965786 158313647 648077936 3979085 316409167 898949807 328480302 408418803 49206148 570104701 312347951 214977116 381475032 446696997 705536525 6497421 683073359 692278017 343510459 261065470 481591839 468940817 256141920 860601951 808500636 730019593 600230627 260922450 377919853 58821243 798980362 655798200 645069360 402459508 699868962 395990963 475873526 973760035 52135112 251756729 397275874 354724344 105034686 819723570 16401614 947982145 13226828 48326193 379650988 806362522 990876259 500069932 219256903 873424521 201529932 46804012 869818710 849256249 194825524 772252222 244020711 55957200 858459345 604164186 406152456 427312219 348765462 999929625 247064113 935502785 983185290 898234097 371352042 22611163 103704649 12817331 983166837 932265815 85180041 201346995 531266498 962401968 818285457 738398979 917113593 706172167 301042066 86537488 613635538 192269463 927707131 161188456 680912511 862311649 234446302 57361245 54554607 10031888 706380602 529315622 470646900 830527905 798589195 951891505 46268183 20201856 127280479 620614428 941048313 499452309 903550254 214727182 198776562 82937221 994873523 483430000 949929346 147488125 218469180 595232222 773029519 47458584 750606084 465375767 914036958 942237109 775504089 478700616 233682004 329748862 938540585 846885083 554384234 658872729 228245921 542858013 991737961 659707851 109937626 531969466 975234745 162619228 649032113 914790762 553852184 949391692 413987483 985930450 373558582 36429933 741312287 970128682 727845989 767692985 164084302 53693318 605536985 585628355 878600629 568922884 164781105 343054245 806780575 971434309 953945221 345444859 843064080 185785115 250154428 245305889 9047454 941530791 823191014 523731189 204755183 278020439 626908373 341439273 379270407 523267985 402678554 182637839 41727540 58097468 247213202 840119026 786546737 804423308 401263821 307931141 944321936 443731065 187716537 596995468 696142073 128361186 538644051 262292407 837002513 367825927 720484154 121451109 142816830 434734597 584462215 71357348 829170482 642933311 580988580 331818186 32154719 601948372 711726309 36388794 995544869 383212589 819314871 648540605 967396151 299190725 65975312 6722517 661580685 314758364 158002306 300511562 84561126 216572200 602001827 348392889 537075499 392834691 264500415 182590347 936831954 620851192 474290171 624332573 928500151 519863084 42402388 380850483 898505646 811783634 6695149 173664421 162569974 344952635 784783295 693005207 783532805 945352645 575719009 183868755 872426607 188231800 561382522 274603128 10299644 473160923 684469802 388981169 94603090 160085546 559714588 577983055 922373747 301787737 820991 721283820 500579467 660529228 291879736 305734416 18145446 384916385 889854059 517249854 323288180 190038730 231198443 697747740 883408573 382862438 792591079 710241824 634938282 113751451 605002036 420517865 557733504 493722483 250623442 718868480 312965844 886530487 454407189 203907535 607849662 705439537 782160073 103045610 537720738 886468700 918354018 963419407 199197415 992332168 515837986 86215471 177674172 273371991 247006874 204404148 973814456 508031049 2691564 672037091 387500299 487576581 591498960 62614752 997911593 86063065 347387330 380272848 566038166 460423932 194484555 490269660 293394140 245235241 367587021 162632574 511195084 377509635 757007725 705703555 750459811 968823422 158608988 849392170 470409824 172572111 501336201 26945842 18686183 496483765 696914777 835641376 589288578 704735610 1504771 795287064 51396558 535213043 538544257 862014618 564132154 872820779 698265305 305862933 550126180 19615045 823919238 714694842 824215030 875965635 953354824 891552021 752729792 938934013 558861529 967103706 690543031 273533717 465218224 143228584 793203824 235819538 906328801 234593072 709983639 741252114 947601304 500719465 507558817 504553134 489181220 53021788 65805904 636962564 261288023 847212144 738324975 880472091 535867676 752215482 898955850 450435159 477316247 368857319 139233411 37980398 494928031 127193891 19182509 850416202 94250651 551173631 183476924 161463582 864969284 555883333 32815579 895830887 276901382 888891306 741621756 303403326 704125877 520294122 443247650 630129457 895530537 536100753 997857858 750015253 977023680 715652150 709287199 181879882 282846189 590415979 395730490 277329961 510724195 212189150 16182904 354093073 153011750 863469953 87708524 254892601 110092512 565461769 53534414 702756709 433013907 814308601 219606076 897354700 900405045 106594655 845010275 79568628 343464551 306446169 370495007 46293788 64043531 375430118 684383264 789267597 695232834 510843470 760211849 138000464 332385771 668042665 424349958 134759796 519001421 914487005 656679862 916730808 534511936 485462263 275726622 833756308 635841304 491069784 617946899 543817092 24181499 152011483 126886486 903971628 812482675 661745909 771023527 809233675 889942066 532555926 621224317 704358505 581864965 344284120 760595980 880545321 819456515 345050519 108183973 636151593 624323190 783429214 54797093 409269098 185144078 344846890 288786283 834782110 740810915 397723426 985164882 240655867 523147924 862704454 606004263 2839976 5031389 995405956 102806426 438778618 141958073 72297336 803926648 804682885 164831448 531573983 183832952 692167559 676995213 372115723 342751749 481881584 186487603 198834432 690071827 677323455 177144734 278324763 971921849 627634598 817462336 571512236 932092476 442045749 685592095 808357498 424514733 113119582 74429108 567083706 821333104 252887941 889683555 4812870 952110106 926166288 502018462 309910430 845877800 775170093 450628442 851437611 814694549 957225230 263054155 951803633 820339255 831322361 458452789 506801284 649354322 151310459 297474444 401962513 775614885 990224901 832825371 780631382 265854534 286566165 381591109 850511016 915254122 698267018 409394262 86529756 208726134 828383398 59351739 200472543 159937667 371382357 422103725 326657849 118968506 453980791 232246347 605240155 153229885 291517255 634778132 627381134 340376949 528522564 398461014 524431088 59303502 566482217 939640358 229232875 438114174 581878524 218164032 526260004 284471638 381098903 180260347 439721249 580813870 456293851 833293370 921644534 176124302 558063888 449868526 398575697 243670568 208135548 430915011 164005273 986806165 669485980 471221876 955334181 628180898 316886522 385445100 980111962 553573713 18875153 710743106 395269948 149265731 855733594 653461955 675503937 123792216 896600120 219082031 665360323 64472554 359000978 496604643 372578605 430599178 369371976 650813107 334054229 855755067 425264096 534859268 771313951 185729262 955194288 227944493 644610778 821344391 897205861 784128096 214772212 564649515 797113467 241284667 254361015 613081353 890236082 525936893 896679883 194642865 115004826 618659933 183678100 264878329 631010357 927716075 994851316 604632606 172539661 594914575 172203571 263115843 698689924 296314580 481852153 920974488 958115359 875776567 533324735 205372509 129815333 468864413 187927512 774444346 400654122 198513488 821634295 617607772 878319446 509865738 438034054 685604712 813315079 242757268 267762666 952332244 990008170 633368002 909392179 604540414 513653146 744705676 393711829 906702208 219811233 938730271 664851863 49726478 393432180 42407686 126567227 712269770 884666459 614139938 810861040 914381389 912199883 889929962 615987899 814869343 890984811 431434252 558793312 917393086 356046657 421426718 812786126 664516313 117986580 72506141 856046210 379741507 677121037 45514330 718812133 299871734 654785341 702193300 223635164 66985334 303625899 706084592 26657488 795879647 758210466 417563264 495868281 771239183 593889660 698652272 764978113 950244331 569787815 619594059 697202609 829325485 450365715 714726515 806592715 936687957 884548685 482398595 355101514 135675848 622854478 592721659 841868965 541004994 41553689 715242590 824997965 74252926 563685210 915342315 89454974 998142083 143297022 808983079 252447826 798498871 741755819 558347794 350515819 265641890 138585060 169598437 915384086 873762186 157174804 217976625 204342358 162077274 900177666 299301899 100287941 93419340 183037070 772750547 780890538 712374737 919205493 185511209 245683315 513823248 635747572 778374980 488832982 226191072 75413422 821823738 823568116 1958291 207119259 108969014 46531181 956572252 957074692 746267406 580356921 172945687 485355386 419156737 614084155 579334095 617327566 102227994 576390166 226116144 9702224 245468926 891268956 531056659 798700860 505201116 898429533 734281283 847835918 607288362 65116436 421321006 600821389 649547551 120991664 4379400 507363851 484071572 681950045 215672703 670112086 512434224 65552360 507375874 970052354 472454382 705159736 159557995 97599192 445279019 196644765 694874083 463512720 521547971 197363092 946774759 690271286 993305115 238383535 931132904 623045170 124571252 279776638 798367483 415154330 319014177 988499717 440031869 368628923 775285266 37003953 919866053 909625277 684338848 984731111 84588110 413524957 263681824 503179363 30780185 968911736 137685244 512434895 101685112 342515592 240735070 732631894 36205923 126059551 859211346 774111804 149332512 267707460 37550205 61327634 834013884 229416712 700875514 584884011 393705130 896448522 802228191 183610535 567188167 293533154 775130778 751056284 227776387 7362922 609565245 704844717 775519726 206077284 339544630 328538431 599353922 191660998 715580493 267361962 835572063 885671182 855694375 820866661 857895175 27526869 131225626 752307080 626434837 428583339 78834772 361761619 773091379 363702020 849258674 454496657 889011141 43609224 650785133 871562666 299185903 28451994 159702641 791495909 956282710 748448207 596449232 281589508 945029760 328818947 588309207 939107916 48581670 618706491 843432759 965287825 157298693 630913533 544507396 173791641 49228197 378551340 342820814 187905107 164991712 193682471 559480615 667682464 935296098 867067121 652643672 644985251 859541704 686816663 965001195 729530044 447858334 539261975 125070167 569506445 346973056 820077440 654133510 692510545 586008065 571961993 617563684 563158487 894180445 789413625 758176407 198264845 316543626 379046442 636852034 250078767 267437201 954161564 665112014 908342982 761791958 639616882 82316136 353258302 807202060 69565351 46505826 297722343 813671111 976708853 138283395 826124115 106792913 911042567 246947706 304907465 604986732 545678764 147587271 41265228 873488087 686017912 355639712 720951522 190507220 1779638 289043407 695330862 492941175 607976983 540378987 652335300 638234480 510720795 173055831 502007258 727865039 675566743 972651808 407617176 813399003 655499920 268364253 631726010 975429334 49960969 195645607 203591430 488278056 443297497 242499890 268470015 227227227 317877908 896144281 658402555 847023879 93607077 957296471 914685464 671141168 72146225 210462432 220514153 909341154 792647508 562799264 367554753 309252061 305359015 384608125 453313455 168031246 629240761 843065081 100424923 315699218 589627865 105783078 729785912 259775534 521219305 768197823 9271987 481217691 943777553 877851282 742728748 191419651 682908387 201176856 200550089 53554076 562620424 656975956 987464912 25514491 770582516 161161144 239798076 629152292 331334717 982275826 556047786 540890570 767590764 263992557 475055815 357994619 95673482 720541408 56316069 693480101 492294765 99656538 188864232 670438107 979799535 878964283 114389208 557250208 551998448 8868322 161269164 173367797 959255698 31971994 59938598 248376420 949010974 628545069 224803796 827046101 661202852 451012669 914711104 205451995 686382432 741437743 835677779 238965169 248144158 178555557 968814215 369274784 819103947 908609111 804361851 890041201 147541773 408585220 958384400 107032521 273788065 370229766 453741466 105527186 435832849 143184020 496454095 996771277 21852603 131441894 141130277 265784063 774024112 719065379 77504605 11370484 848571063 879561102 830125341 811461098 946195202 261142605 684045771 20577013 250572013 27258024 36104065 817891189 194145436 69794764 874984136 613002904 617257847 579602844 112302001 179361416 807428493 25771761 237336816 66330914 127509130 289113620 352079013 276476488 251916824 623965380 645120006 775792131 611896031 610871590 236718400 533390784 164075837 204757133 781310023 192684051 466805248 574004534 832928356 558442005 391144363 858859479 51130070 887379286 718400025 295619604 845185639 90025657 672051860 936557319 43096290 382489662 115484358 909372432 772523717 702291807 586780449 96245469 443301895 887406300 865460461 30580025 282211361 138927001 55258662 733352424 719375903 932079722 926603752 389838767 624459923 132465799 754063158 421548880 987916358 439341143 329734150 394351053 590224716 495240220 835614083 795019924 632880998 592723842 969762721 752174908 569556583 218563132 442468102 557931298 146094400 476045866 137101524 779050488 901128682 752970136 77351174 843745312 871607332 145290505 3468743 289923823 920020487 988284736 169300198 48501949 298159455 76889 656596548 20513353 329676316 733470334 27246698 551304570 63213209 318590671 778500462 541692872 507011412 560914660 602755344 764433138 748412051 822959234 47877526 611628447 14530189 834256378 175010871 204148655 251210844 347234354 713463164 388033166 773846533 384247211 370487130 773666317 733433950 342046651 788734532 414700209 891692047 759904494 416105523 579860836 627570058 540909243 431749115 62837971 36549547 126000888 230138246 22742307 775168886 594334944 37889962 269501232 6779715 376801684 942408096 967093452 687806982 681158598 259784979 732442470 876855114 164040510 265185961 283692630 354651374 851096471 288333898 282572882 661409194 524049293 993701213 454496364 753621615 951154815 98528796 675588113 705962987 812217387 674113958 675104105 925158907 688696294 228261108 563204807 963319689 277332128 457908689 420969495 483974360 793087727 1846041 359651817 355969553 40279325 824559880 161275579 389550301 486242723 62587646 849994725 531846326 208117736 43014697 447188454 806227575 298817734 333487726 650000209 210217766 697253801 997795158 878163901 914616328 168857182 681572388 874515340 527517700 939573217 381714247 633378308 900899717 679373794 273633400 768614981 401859994 613231591 18623310 965838408 336475128 968650022 491898633 713394271 135523107 348233155 478839411 396161912 694353855 860035747 278732710 227570114 418221836 878482899 839605592 577447948 988449185 984936885 296409564 579943471 506399833 418649667 68736464 606940608 721948030 727978518 911152523 92208401 229210067 82901135 614599473 321124247 353021809 387660312 869619789 555525074 471201379 661299699 937404910 810528972 318631713 618010706 888172171 94705065 614248483 567982299 467208951 263590529 805847587 435611760 374022573 359275622 580772338 830818824 893016024 83420151 114476981 455279007 473083501 641816013 808695694 121061372 525537129 612352626 421097113 852986211 174781804 523616897 503750673 161105100 920036782 621983751 536511709 49273941 99893603 901225147 978085838 120107518 598113466 540941927 800186647 750258793 946371589 266166613 341162201 592272372 472469867 825648825 35277114 464896968 708216549 284185038 393198509 952478893 368512662 251442113 849219666 39805565 34495376 364874335 26269886 969701309 436328924 509016286 96483188 565554325 990993866 890535916 274006785 633511741 374840887 674995716 228514159 347903060 866806231 868979204 760330173 212323160 162976242 99454536 888024216 930980526 547087490 7988572 697125418 477421676 859005406 679700430 613388928 54591686 150281348 449471154 354123573 580861189 502572296 293351843 4248871 225749071 913013438 320522631 137567833 162760039 642330782 868501648 4292816 746299159 343422986 948590073 222045002 900815297 731866359 984575638 697149497 145842608 572858259 987343460 650674066 468731413 372116461 480246392 258849824 637051712 102094246 826531494 104937991 462576700 190817425 652150402 227281697 592172901 524251595 740377723 739876155 656115918 223635773 681931465 874786069 705925353 793941260 375340546 349476753 31298242 769531401 221673242 529899918 404355325 17526957 249752505 188508968 213143461 57903491 214424530 443447773 389985299 868871893 386642513 547766537 890134606 593793454 47005496 477512544 462820024 358235990 36436939 794078603 289459284 393109810 55964693 61822700 965817574 818572259 937937854 152565851 389132561 437457768 501969049 86099865 933896746 977331271 367292009 39048738 794013438 585556760 129103800 888035339 946717862 846324783 483983764 634652558 717031082 183500899 845995606 633401753 507707035 913952194 29469358 327795823 153826818 697880644 741654532 36729725 136588371 177451639 692210866 506803587 585156375 79935916 347187383 105688354 923228751 475998641 787606005 403175023 3058214 936548708 695131091 544457389 273546327 790209046 78512256 974131968 635231234 971157357 172329190 722068184 337183551 877961592 124315183 626922034 485862783 84671886 238443796 194430649 374956932 310055452 471569952 829777851 489289082 155453404 433790794 361695913 103162550 549999947 576684237 56137250 92493901 565586926 978417436 745012609 963692358 61063115 879509784 916751532 380169927 367984602 395645728 901270525 557277641 60430358 973339206 40020634 247903697 614254982 930263902 532122262 918785857 159001456 284249485 78971894 122930520 840455221 657512079 381354945 365120598 881183401 549773236 354036637 221617694 888501634 278608754 421307898 976078002 748979954 504470865 634702590 237461116 635484328 689083040 574369702 583737843 680758364 195746818 599593323 808362415 468302718 255458820 151902644 97446932 597585921 887041531 784123128 674076586 936455704 469187136 545858763 505794674 309919601 239629361 152088952 916091621 678015646 94211416 920420685 631633845 49030883 195036830 346715332 640125551 749655125 304498853 526630864 13528873 101455822 190103315 84730937 409534043 953741875 368857829 502989306 123286333 922700980 314012085 212367353 324344318 589811043 961790316 166520100 386516334 309070695 373629472 659111312 641143290 232090113 728328082 870746461 673443545 993023269 742672425 676853260 233040329 524380158 210892359 579604184 430268137 883823989 741234164 378580273 935530174 910536260 662860779 22057065 535586172 545169397 985203298 210462767 862826674 975075624 331213669 593500968 468075006 569145291 600052668 409677701 838969832 549592101 61546696 728222093 120733248 924487916 763091677 443650330 811899760 979841436 880234515 77733058 671892942 79975788 511392323 142241241 888311391 193457163 961633705 222001811 666988652 969570852 269154505 645890733 210720857 637783343 925995138 80015857 825767423 184247541 174555852 260820184 716209404 39605510 179482156 38872058 90144561 262575461 646152082 724874375 152119957 411760820 418320277 305184379 540055116 617500052 663190769 958479263 320251180 882281328 318729237 422364025 426072890 67482255 379219545 513472257 128020441 770273980 550864278 390173831 191203734 157183940 375003564 421170222 480364909 642456771 726920200 651936547 138924104 412485026 471286614 611290755 532610492 228386036 106107276 297380503 63632 171173363 46697372 415985221 422793173 386332985 32070396 233819828 504353342 688813589 494929131 35589571 821580754 460065627 109979657 29170327 722417774 869629682 320449997 872320496 336440672 232542217 172557530 602077840 388511637 773181324 292295232 970818270 693035822 800007513 890295542 204585999 548293946 816530375 876886934 811085530 900647150 154448167 488413097 329028117 101911313 528383824 849528563 823862033 815211596 513652930 103434634 200999151 914126131 925121012 130697505 617818010 705394334 234323351 206339678 632237000 138478169 625693453 926602672 506326287 147140891 903085978 482374436 753694923 677692421 149300347 698204125 779999593 463232767 517155656 474746200 5022846 617363324 802674095 278210452 905640076 746184726 440341703 309374778 802102085 21774081 189804630 92538889 33616557 581841371 498133142 752462334 272447224 651312503 769226903 263186875 547398658 753500954 270791935 919503100 780572401 620655775 47728026 391052773 815358316 580511696 809683974 551124060 652203234 753333433 765468068 368977162 210685661 668941049 112444405 654185482 344181069 666783791 87023857 505341337 543233881 198260826 282240525 364062856 459402534 640041220 622100876 12971255 684552383 792753611 353953944 158831070 630580709 583067470 520827253 683927665 793445415 100473415 365005785 464584171 490557774 874106645 960869258 219323255 380887957 659159182 143627251 113138551 638437919 578743449 837821040 264619769 655068566 514386689 743211002 392546130 708272516 563307542 406696733 691176516 210215305 946037017 877634369 285571804 430056822 853003217 999510313 272685958 497363020 299163416 424639122 627235136 883825426 94631335 906760781 401171397 554058266 572045247 148256033 207025902 483386057 209345390 204892756 301518654 327808735 356269014 181895494 332303263 248490105 457235532 486630357 673987707 539393600 745724591 427668054 508417081 749873165 641598971 228579743 349437645 884088049 849174946 878856953 163498677 386793358 568191773 748566859 868294616 864402284 40927040 804190487 108865235 273995175 617949575 331687416 429775528 124661469 99138273 65245116 60455318 39717600 392902610 524083009 993173791 102703257 784344010 786679182 454042635 948398076 138363270 221456372 131222466 706847772 137789060 81066875 557243919 869364309 217541682 539704922 259637145 929175400 259858018 81345182 909540738 569133261 719564615 960464702 653412977 954821633 297601155 633502601 191298914 368472219 38579096 197432962 702502511 759581069 19130734 455517793 945245169 709262930 649145285 61435907 776452776 350007058 309365067 19770974 190835393 494836685 679750364 946031687 46335024 629772031 60851281 9772938 227424072 276791251 285310928 99197404 356262409 438209048 122299313 597065629 714182088 975396134 299697629 278776490 565145479 404568964 241900702 811276274 971571482 809853146 267030261 185696123 733942850 341927796 370721244 508463928 586329488 623357953 579050209 820399962 814713353 982758335 734829379 825102320 850376332 879608448 930849385 710339607 871314721 290234865 289433797 574539629 516976647 402618848 6001395 293459000 476557937 245687126 817569800 902048172 414051946 292095462 456040469 268289862 718870901 791277378 568780297 702374021 591018069 621051144 262980676 368746435 649441593 40458314 811773294 682646916 831313630 834200060 676095909 680409187 759671225 262611025 676464814 323285418 267946532 821753946 42408279 877530618 346091415 139250763 363318686 835191750 646441797 793623832 892779924 535771384 646844700 802475017 783795460 353430968 22277582 921625995 499845087 931613578 15368779 962787507 596894090 543726816 669352933 681564582 493407115 296634673 189315509 895903945 809057174 390987750 67029018 102650224 240022156 91963648 256817678 654370349 123188229 329833319 690105336 950063168 480892328 818291348 458851810 106086094 617511636 471351394 365870020 415321132 688505656 531451360 446777287 639859699 925343108 514153822 932680299 765039734 626379977 280645529 95461728 127505494 473049204 820481552 11747627 241729232 141352335 899665973 524010514 141922919 766385818 4640771 462906581 920115197 502136769 605321418 728556703 403285332 276136405 7454389 873883438 504357745 838848730 427743882 698214976 788231561 556688546 678165101 432910802 166843387 574665638 296405612 626252190 679449835 751480869 15070791 895152511 889080287 412287493 353146013 556499054 84725061 781098286 249188678 555864997 492564912 17204480 443609417 892386186 642161823 620952068 625919372 841356939 583642726 523177888 655700653 94655638 8906666 505724456 183489059 510397559 681443508 649479616 583440204 279370386 223209965 839362790 340641600 159982222 496128655 186898459 556698258 220742188 293438729 18527111 971725668 747370626 334305810 381818758 541814943 938672263 542903186 483508641 669218806 126731520 123206971 513398421 59571504 70336044 506626307 812720892 482794155 111631929 672353667 167651640 316448311 882481973 723496572 742738494 645060811 455880372 210008748 269388994 642728161 331895873 846389810 114090964 283482236 318437539 265645352 755776850 162424903 299076296 786787529 161763926 79971960 51176217 385058199 674133299 926613025 477105819 591208901 859424825 387143515 988799245 830746363 515025352 4237528 325985785 385003837 156599527 546201792 355996235 604069600 370285834 669755019 52239890 788798914 501979793 340890608 401131387 776128699 478010484 494649812 52991257 11016275 17436797 157967542 398379059 926732033 714136737 933864047 470232000 229766209 626310064 566809345 63560052 346938677 135367772 938110160 916499767 492620704 950630103 987115737 720932244 897766835 238457066 661082092 778022670 340875353 760740171 219954317 320022528 851685092 213427587 974942854 718787918 23001680 396413429 820246074 294003007 408300470 942595171 287534098 892908348 539988239 196614818 124708408 572856955 773592564 602320916 124789730 281285114 442387171 330540426 194954336 723704798 440190288 526526066 920161949 594803120 791094448 490282098 645524057 827892527 412212964 174876722 808655980 147260904 534710182 492490239 691837891 728221758 353222482 205228368 504864827 775595898 452834864 825489444 390337473 713761807 339326348 73680335 40656327 956635273 437683526 490457450 541767332 949986908 783195622 638274240 600544868 582392134 4128889 22846877 159471994 347956148 461008414 211228975 318506082 658436534 476371093 872927794 649876009 127303866 159313249 130027815 349853339 188931061 773455950 524714754 445326726 135570061 907115484 495529003 765568585 311716598 192932316 557422649 233964579 908449476 966532735 357401544 63201144 428236883 365201828 548183383 409602323 939883149 581013886 903739674 415761241 860128699 150607639 467555926 91381785 652842888 842319150 355148964 956404300 503407730 170046395 977445029 294324302 642757116 455550980 700851166 913785347 967557544 955858467 26944363 605528534 775614543 889759465 584537188 985468307 291142422 78446651 998907897 502518844 358175919 248430600 955172464 645161298 877143648 386393050 584707275 676073007 28637150 865378910 944427814 889590054 824759948 335316207 960462342 398070337 999612999 638696434 169854841 565194508 562361318 592335896 408873980 297709129 780762681 429327673 813643108 373294039 180099490 519231395 827851681 460121914 864087571 556222606 433666084 636898324 791775698 8836535 533263019 382261693 207234515 288969166 104668360 707591209 456213592 48981915 641643482 749567560 231403748 850496056 372135877 732155467 284456214 805326865 962380910 441928002 988188761 979736407 900470618 696808619 748947698 695358616 445806017 744112656 467469186 876328884 645379167 995450139 254283631 64961190 775514530 544356819 111274641 591000157 312881615 796358945 690661576 365976313 784949586 376402383 214531749 15844357 110134531 624266263 153074895 156391920 615737249 516843409 862524494 654138369 206883659 674750296 594126118 342204275 70699635 332933892 712495622 632573628 470177102 13765998 72219079 617251734 676773798 133244846 104527699 777220613 297579197 730699394 610084304 279714264 347823829 893064672 485550015 548979385 832876120 695779610 501727150 806412718 479969899 563763462 781899573 218536380 853110741 288764191 449008693 208529087 183865327 580517031 879027739 897017279 293711631 134271461 583854198 945864007 952831004 569210890 106775682 744881386 863291135 482440850 573878381 774073297 965166206 516643389 351094482 913869025 978057999 792659265 841474585 879812753 574059781 747251968 441287145 58122535 421351794 599864383 102765539 85220261 659060491 115237827 788471749 85522982 110545613 780047679 868570836 662134791 90159255 382914622 778974107 579690318 148843459 508188562 418401144 955517776 899004969 79209368 269577177 356586178 811127683 685465480 797815969 794847469 876791208 816952354 773787249 297650516 835604145 556924296 977985659 606117233 964434135 398435668 649989317 789518579 549619226 77783666 713072722 19542054 714285675 978940655 325444713 657778993 589870943 201471536 667211040 997542835 616365737 278777737 792698978 149669185 712736064 230558004 165404262 448310758 882783931 747065155 306743789 632261340 781665813 633707880 918009371 81142614 98293718 398556379 240053947 453914490 602515588 718083806 417895781 726536435 917975511 776326298 727894000 135912596 229178581 750006078 950029175 260415783 81242636 450040106 938723490 471416002 439284997 469199864 998738597 856418598 465776286 20271487 150072243 972594463 346907639 81633304 785440569 988232823 863408457 917984931 837999009 753927077 538130671 603758536 909136488 497703286 967511033 615487879 339055099 706970 140929606 51101421 881590864 219010540 173194588 565860199 824700690 233946632 185221241 875360724 138598904 680873319 732831061 473727457 263746226 684305503 904853700 842758732 404089584 424418777 932203378 540827251 462190611 308282196 884955136 28183009 232629009 264404700 971053444 392565351 86333540 156704739 651235152 683330147 789552924 10950860 924412890 863121852 524944636 959727782 39614987 900250254 610852191 133974076 488447204 392643460 962014047 518084634 968012410 863982376 663425614 300885551 45284781 910020573 119334908 469323192 168403640 144915201 851505230 203441097 312031786 142318042 576703458 719015447 38843588 327861059 437554141 348109052 373449805 365802215 236735905 558002929 711300421 677138236 429752255 390407542 338722388 843654066 830853008 703346187 470988117 186688607 609242809 322902691 502532773 822892730 288946493 319779725 823863101 617783824 297707658 92312778 872378356 571639753 17141290 191568925 57186881 344884864 535944963 956940711 665983121 93278455 10896946 167402472 699447785 303638339 11929705 58227901 84328990 803566753 630538977 293937268 764187267 415706465 104939732 222369181 72845938 611274715 212435774 28578410 503443895 819470840 406366880 849364808 700885512 583325367 208408771 911562131 914944020 467832853 124038698 130990892 307470158 936129486 672837085 300503052 140363033 396741391 395128643 836400327 70644136 923886283 377805298 637501737 994991187 252984533 774776731 340856339 805936325 156692913 367649859 162477889 143169590 517251732 389091644 181787573 240822829 235005043 422598609 168298 802596594 879156550 654622656 687287093 91760816 898782802 770557769 981475078 127363505 181995505 258160461 859477682 893032863 423365955 786281948 268249676 58353740 31712107 261011871 117693337 587714090 974994347 887498889 94513106 125163817 58493648 21933229 165281038 510709495 817397270 774562154 704300618 495224574 720407727 623000651 564848391 670596363 304770126 69164537 83944361 288983768 213874635 317391219 81083349 952935206 552359394 41790529 254908516 69551726 800477816 664164983 868220633 866452906 843796806 984067932 57584835 641679347 619662342 914082874 247632163 715257922 254118099 471040105 452958434 149026890 578875440 585072512 457180082 750323123 342468612 916152829 641957716 354554108 853755469 136990722 504747129 904221763 847480772 859482224 833755758 445610199 431633699 90556840 734928248 683162054 994524843 793833799 552730621 935271071 900824652 400516296 734500027 132401494 955722888 358648377 280914763 306982015 456691100 171608023 79275995 636330059 696088709 427084868 580451603 944598265 148817205 723296681 698956896 111520556 299441233 95747560 487575514 722336215 444685532 630346415 109116685 686192491 538735914 90195092 664237562 192468235 717789948 358383282 180032507 601837065 819083711 299169316 602257569 868556009 360954803 905037707 514169059 636013172 283842318 827744166 939262443 340326084 797506417 640074271 536518897 256983685 330042529 90899419 439920610 703549773 337808046 159319779 986477285 550759244 338519658 62919476 599645340 570334136 867985601 558220743 503107352 492897002 131578242 550245740 680732682 654254939 826893120 954612790 612901848 647120516 645900632 679590817 667338603 57361604 527098766 595039781 390498116 498987771 427978481 318580334 133362050 130263363 663278120 162447787 979339952 903383565 716139010 382106305 20889260 425729839 433778804 878759930 876350534 309655309 159051154 68734276 973673060 50558643 474365683 58956765 693269229 374469033 680949909 203417016 802202942 259521123 249571549 221454096 366838543 42802680 433112656 369883633 416794586 928148822 479282026 656474625 150063383 327258458 946893109 91835881 982367655 96431449 441190702 683375622 315852220 260002484 649899902 617989344 436326217 690127272 950673801 762360983 935451577 962590896 777758932 124544897 404723679 823220213 428559778 701346808 338315456 733486535 106719847 482778472 628260591 208655279 844882769 100214633 754578130 623431348 511917116 715425564 236410324 436437671 725958383 523797921 491096792 779589037 931047427 711986214 477003081 423432380 525287270 742492995 972068415 644655238 166668221 902716974 79697552 202014639 864315691 204326547 954763532 573262403 625087994 30198547 843659457 879507351 189844942 698286428 657502460 691907616 360482433 889065233 737479656 671159727 346701391 678240446 950315346 773847571 349646436 362036275 559889406 559690922 717642504 788947122 542972973 123266556 477250419 159023962 204968312 610758302 120969457 669377598 478483916 225689199 732335455 172125098 644047112 95588175 143836827 702029953 739711172 543775285 211107601 242914302 614647706 637549478 488095594 691175135 164209655 193444770 547810958 552160410 225385380 699524929 568255935 629408715 730648307 444195175 957161288 786184483 219262313 188532848 806545045 401740646 808013057 523131842 906036790 413446649 850694041 88063321 400487204 706042815 987263050 950142744 737543454 166163880 667949042 871798438 388823061 432189947 314584505 386167137 496623496 232463545 567318320 382032711 103816573 150734803 547295695 212316093 904919416 836285876 107001148 397825134 805374611 371530424 522702949 958903989 170257530 943204296 474132376 419826012 110959507 441340730 116545482 513285879 60288138 242403127 172089479 389771963 547163206 61427376 205661896 615316533 692426413 53406919 713951120 507516774 721273072 412551401 471787582 158791192 107842361 700599240 836290607 992979432 189108018 97415053 755431810 593047030 935770374 329289254 432461927 557990339 119888300 924662673 446973599 704851843 835550690 465896544 872492777 787267353 691176327 414548880 334483268 366578494 247260089 889660591 802169058 177756871 542735052 60587746 12596497 868781028 524877570 307859677 818286025 618246495 697887938 777376948 918020900 440490728 876108627 371406592 560160541 897890859 875520112 126345130 932376769 714480274 651679205 318753192 283450449 719549868 431504515 292828556 711381250 30386882 889169575 995603340 319369459 788952260 699598005 692713415 184469223 28141362 361752893 695099434 433990837 143899651 50550724 386437126 778733855 894551583 240723737 149850922 102225067 903724645 153952887 366324793 916218132 109637845 80263937 830558554 543441206 302986284 150805165 611340314 918879705 75606207 525750727 29205831 388125155 632618902 235607432 327479040 174647141 467661153 672544274 344615855 518396406 137023819 510937823 190414736 788465756 871148006 132109301 147751912 200433639 750554185 54416664 502910793 263136420 615787889 256125936 555265593 440693490 41420303 627314548 105556133 925751789 403655994 325614226 81001586 738771843 333156697 173595302 64457948 86595155 831839939 552918851 119300186 816866843 273550410 468834838 144603261 585562822 196638768 414308117 869050858 751011149 327021121 866050941 829050328 186901624 192880687 673300798 951129161 393787545 243299043 755891911 626401034 833169119 173621976 588945951 645263831 835607290 248138164 174045048 662077188 234572289 258223985 445260177 987566558 982723692 411446012 523922781 32176016 467190906 357090869 846435581 809418429 199590537 296564893 841441693 15438837 788401923 627919363 291516643 351734756 331603051 501200706 726041001 461870056 693887276 491406688 275275683 426569145 655165326 143709126 459551350 665788898 227124987 545389676 443941840 984079828 761679244 854220067 193621163 373282421 1788177 323673985 442428212 700315110 370726066 277353547 593401961 702832957 280420447 766368333 418459280 216317911 416642211 738539351 219418272 705387472 707878093 451387592 690807526 675063954 925110258 738325918 271218902 824646311 844402198 794342115 999911227 981339734 418317677 596912459 709708930 174057686 607219746 925404999 814437021 808666836 84425429 69429719 572552765 596565355 266534814 773107345 675100685 1291200 97032539 378432021 314179949 977668305 398201905 994803077 56918284 700579585 506000278 698812363 595917173 930834462 430892080 596005720 282408752 342781169 946469532 80633223 77725081 639597745 605438616 736563522 174213518 246428292 871879854 172269117 255161767 493639352 80929921 607623162 987235170 417604513 17500771 396285909 999390221 559425055 23407232 640460580 93774439 109639039 907083089 379308529 74322777 757629523 300826816 995377215 845570701 396278774 963946343 997171472 202971172 752914810 841802249 260816980 433988602 640811161 731606889 641192714 802976531 743762212 611472972 534047553 92702331 276354829 672622765 824868062 425650093 2834652 648043441 297205946 774080015 273752084 818050526 427022610 305152662 29904148 6077102 299681270 709220778 932347847 112011265 262328847 886156541 960943375 382375867 156722781 400196508 455840378 821433202 518647584 642692418 768010291 31207049 286363607 810847261 770429100 118327393 717152139 899154599 580381441 567099566 601901200 221903632 107663938 290124238 951532597 810168025 486079035 82244088 128950991 216850789 382246573 799349976 670126628 611717899 491533245 994253874 258240402 725658530 678327533 222103391 632334478 505382093 755258924 164102624 847551957 911256851 670423405 629642344 667468334 707350649 556602688 673413963 558589702 825511310 994100562 608364931 452327783 620167921 753613297 881640622 165624897 687954128 940558732 581053790 439016472 319430446 970308608 69331415 459649262 871442615 225095698 443965495 244423185 329172803 350885743 891177853 191164445 332446829 891016395 773691322 759737429 817260876 526373858 787893 69992734 907065409 557188720 14592354 808153235 717211614 485117953 621141809 60502168 453766512 840216667 413144875 113184154 64897881 340651325 424168108 70762734 626027268 702970728 665850565 101963953 320547871 99476696 789822157 68259242 874840261 117804422 744078733 970670652 991724234 135777246 21134529 391029631 427487944 49541621 239322933 313200307 414360164 365656379 584959693 798104302 921984659 786627340 893549692 201349107 233402858 277087396 333692794 29546710 692106358 800103296 980305651 964214712 849947067 966770092 237733921 986608372 381088239 494338436 864799242 804540425 782503157 492293553 88316643 456873262 595212248 156399658 935330513 899734852 177153079 661209882 217869026 43466801 327648866 171928066 687146668 538205814 439211765 266817215 523974124 294243704 199788294 68420928 842251006 303750130 700713053 906076455 669013534 784747454 683944323 698311737 452068578 423390038 360810545 611696365 333956539 1800781 24960255 434884657 68444899 246109953 184277570 972558465 394859464 523199924 873025820 109196953 614898205 29390913 918603214 594853366 945832523 467158257 782261112 852007472 557663185 288051110 261673368 355734661 776321031 950879662 825219406 168928778 955288253 22293598 178923717 293028230 195268875 394413571 177142269 67975013 884412449 62107008 779917065 801355437 768575915 80166514 662245303 666249160 986504355 308786695 175083100 287448111 485944706 978427779 833681292 727685885 257876348 386304453 750823484 519695179 78881023 47122170 963269907 740656118 275587873 978207224 997432746 776500687 598151696 572728029 723595770 606377184 149068819 615801484 990069577 349913392 844801288 111370219 95658750 64316820 383843305 52161883 627910186 146750014 130399252 603333596 92178479 122745623 845826845 559974557 9428725 671822121 62588820 755928635 625570918 870222390 490072565 447593470 269503228 190160687 25810105 541173419 540826543 63098242 709591444 692086980 476566490 354655097 275135213 93260067 679536584 128840223 370107458 816945933 443713650 7406917 458960801 642793572 234269885 622389800 442669984 389934405 376325284 393749854 914580419 336903802 31062908 233624322 398981508 242101963 364103771 481314897 947290085 157246080 88336871 199743966 183217978 937717178 561728221 971284958 435200830 174257615 424616590 861542383 947116762 275646191 913477359 630674708 103238751 759567837 561413269 81818104 128963524 499856372 51824304 535873989 378720329 682694355 56973278 420409876 203003522 633286563 382582105 405785967 813794295 662150664 876608739 899843261 308823890 316114526 40701258 562496841 86010057 159791346 451962170 431539669 946288636 804947730 489861481 100272627 928071104 390119766 543053425 148709268 69518406 718103404 860968089 794105954 407621270 48517484 316870503 697807111 923404553 6162754 841316521 345422645 658169422 8157253 588508444 933162077 54102495 344710313 888339811 105389425 30843911 620271351 482435540 568235647 942435078 399918293 716899213 912711011 344042924 769745033 252739374 775700792 902518742 413536129 925871917 694371470 1124114 288656853 911928868 9701248 126802242 446053932 282368912 160116235 26338151 771788498 788432495 444445696 209266989 157494811 843682224 541490804 549840131 380503856 260056125 145878639 252742340 21406072 754479270 382764019 243178371 837586592 186490744 652566018 203011287 640286160 405941498 27534909 546941738 241042035 889666548 62220255 794384826 225109554 846158489 674291229 358672698 934618254 945156567 932982010 143795291 842891816 178010968 331557414 99081280 187338542 427653744 523766998 181790331 484032904 890122262 181939060 623910382 321537493 173649257 307774473 447356892 490094360 654303228 102025272 256257273 618809130 608367386 117584530 782144899 338803829 942816729 531788867 631929113 31920098 71323850 1813307 130539340 873166623 336796575 956836739 460302465 335308732 298236585 107670462 632682182 929797184 577808961 919431917 378977150 699285235 396848279 108045723 99793714 3949460 543883224 369725168 859604808 235289421 392101238 750137935 76345940 258409999 927970500 965743185 227763138 292345082 776885339 492746796 566562840 297190778 172220111 473987937 663500573 923935275 149957405 661282346 189129954 378851466 761968723 215133822 609728056 226668312 466046581 584913420 179677327 864910391 454046653 115976990 856567806 619879530 372305676 590753398 476022235 406209235 845940664 867007243 916810646 441589966 251778580 503312340 357409414 484574275 797765453 116534637 418036367 26326566 762842053 204824785 817137404 455692793 979645780 835744459 140483228 405200292 434293224 662568978 973767162 88642476 381974795 391911756 997730968 952724068 487156817 724247279 765760124 678634122 925509761 276149797 628077148 509120137 952421809 617877960 453841451 58996757 781540352 589895554 599700291 939847543 184314886 262895530 440385143 896487803 121646780 955421393 898299393 195624589 850781884 939493782 686564154 875362268 177628769 62208713 218266054 951658876 909170446 303038237 22537470 274080172 822096806 114283771 606909815 318453421 488271599 73078970 854259308 418673831 724475588 447745938 348569940 133037362 909711160 673462893 335633117 74299692 550548092 524476973 399651419 113474733 272738767 513872550 708011319 43331811 106675767 395286140 861028697 298189452 809226905 627625688 134247630 428036041 32189259 737173950 973348937 138793254 605533224 702997409 410365290 118715299 20502199 267776414 860076934 233402909 290002465 158055026 658592912 445187517 1983565 406486460 926193648 356329586 227534158 760644760 548166983 153360910 750592961 87573757 694223646 826332068 138769828 324700888 504977575 916790425 851025514 570056582 675118430 268298614 249330430 409697354 868296381 510947648 912298652 808925749 99542084 96656836 782740051 43682796 545687498 383521657 348012662 368919093 878337937 791241066 823809688 88971662 577353066 517563334 772679926 567394386 98999136 231966906 521196025 857887162 667022484 820046390 931358338 495295792 597431680 350443453 72665821 984215230 531663312 374114445 495308022 614078346 771415605 429203233 536773981 837351363 665920709 840880532 589589829 272100517 389514056 504717624 229203866 799545039 136813615 997892102 366818055 114793868 566105923 715947057 960783183 742902567 578091433 113501177 78081523 89485610 167995006 875332771 707774971 296492655 172736004 15193290 264754158 649254715 997785795 357009197 904965276 300140508 486583261 422220377 587146091 108125779 354152214 184197169 447262905 475622778 331584249 321160794 640651334 777362919 964723554 347167451 922847713 957846999 55636521 615269369 13610129 288275194 469593320 626435055 238372714 729672665 628174702 167254579 269338498 433057376 519471661 905998349 124819222 631959401 435406907 230233368 311267657 596332443 620082572 191618196 461508930 604778982 480793103 459872159 555205458 316271290 280376239 319484872 747245690 395898343 434368543 438423952 356902377 657921900 506228177 579451371 579189663 535511059 660671481 224199148 49093999 578279580 689855449 759406357 901838610 341269465 873716541 259152743 922019860 38284502 188021640 653930713 909239576 728073585 932872787 542895279 767011137 862625005 211899723 273176826 24839856 74767806 281449410 102916638 364859696 311536239 686558528 288965079 706826870 480957762 754341830 458420259 933004139 916228605 83477290 577252904 948078122 33535104 896141330 644869971 704355535 849024046 537392770 915381269 657290959 851867255 342560268 7027060 638548343 950895552 157567329 739696463 519592906 619764820 722127426 267574529 122764884 327152517 185791611 504232587 260009644 112775471 80048586 662131531 834115370 767785501 422980314 260271757 727001366 969273534 403577498 663680420 79896921 268697227 310402451 697323342 913300289 648920954 829563339 137890119 914052477 818340152 876835579 930362429 329196783 5087368 574162153 84270914 349205662 92099528 841766790 846541471 94972268 528946046 248921792 126362635 375588857 987269748 362225587 384887545 51715989 332302664 877930803 678615015 875110437 571055451 525865956 147656484 275633857 164469747 690894384 806241051 332608325 155050543 795203980 894183469 672116698 557815101 785912492 490633824 534064053 237863858 497145822 701663923 310205694 660348787 81581416 38063567 405070328 151538899 342799602 475376806 681566251 165436864 716338452 599213911 415710678 513443855 89840441 995889997 813230273 310597278 49122178 950464045 994161844 609589150 802827220 789542136 953515057 633535630 647229050 499480901 864279152 662106057 280055042 770942009 923323801 485403090 970409659 166589936 232574535 242437629 433064944 468762880 257415469 69514944 254209907 257957649 535243855 300779981 373155679 134759819 823338269 397630767 981714512 92881076 163628973 665817742 914702007 32783375 508830660 924256939 7930163 932978511 852807785 203705529 791373962 521579222 308540700 394365696 155285839 512952376 754838848 426056568 646778556 859628247 392050921 32178916 808398565 708379852 339324922 644671492 926281617 192730098 743102140 13523350 683361073 917153294 862168283 664570853 148231578 392168681 657870626 927903352 793574914 250845449 296821877 973397751 619583326 847310227 401145896 639994455 622998688 471376527 166606245 751149145 331203366 590121485 737773012 652732030 463569645 31163585 381151630 307209139 174663179 154691183 449863399 172184552 685117058 509256087 916039823 82361369 994871101 714962702 555448614 281036047 853059052 569692655 978678786 669831476 726984524 331184517 465137485 779813038 584043472 229707836 893241736 556603423 166013502 664698187 113606033 595883965 637157468 520103375 820903927 967212648 296313432 445269439 788485449 80640960 291918905 936961043 423906932 605738690 736585482 301354372 214837651 172404648 116367983 609664404 369258785 907349728 16090617 51950898 397228857 740472522 713786392 842122170 582654031 793326976 162413493 199434052 897009758 781536055 93521448 298237752 466916650 234074689 473038497 740607845 448500725 179321014 376049493 508174401 606913497 549890276 237781763 506620007 978490428 535975163 325653582 304354962 167392347 167644416 152904294 989720063 325617942 517884168 870660196 343792533 75681135 947420935 590797026 690126900 923430456 103765173 591360684 715009058 500105571 373018067 329272783 916947170 974514933 5090323 580317756 54231409 367768547 532793862 155598934 859024935 569693218 409588734 261506162 523868801 19986980 811433561 531435807 34186533 825847008 415547372 714663398 566724303 148053374 861188876 763337373 594795441 532461537 289638345 553489529 905589663 469863062 348996873 602293692 577496178 391187151 892751785 550722195 860155914 334400859 62126346 606376239 358461515 882939951 840106277 197599351 601555189 737337691 870129394 886202329 602895361 376249406 990002433 812893205 804702441 158113128 702616796 49834969 909300439 515551279 176725934 736185927 99885698 791675408 503548805 587392563 871819707 412369781 897292090 157540163 321451453 127846280 977202750 423710826 720605566 367921302 750080551 101601922 951718859 237395721 499656313 227969040 403569602 544958285 827789894 558740811 99696285 791436245 182593621 105132639 251027128 975998127 117883152 731201405 422307314 485594175 994955251 96356236 36790921 400866526 805781510 519369891 674299443 777514340 40325151 950757235 550271785 952483388 872249484 884509562 829044055 920945454 108767430 670996896 474817887 226549294 883857144 198760375 818208945 11559301 121256170 27124474 693317498 431306642 343035777 769516717 274361926 862175089 260539103 97573173 757911511 690688969 219758074 988715115 93719951 616493395 741524445 405578462 611517740 841433915 411813211 601069032 725475445 540637168 162508747 188054746 32105524 503758421 938352753 31219160 192886314 640040427 741933409 590860778 362566177 596917222 197788483 57110478 317075221 969554801 780782582 782532858 583790695 409417125 498373617 752788967 159922869 82997028 722575332 687743492 469332483 145164886 264459431 756528248 544396474 413802495 535542444 754065965 584173676 533511752 456091001 33249252 397470649 41214809 885333756 326924196 824568541 835702528 115016940 857815446 13003990 85877234 634116372 171364168 623934525 796723942 790393965 775833746 869408641 176388185 434253423 944176661 431502667 669057877 738741367 853779630 201534277 254734321 656191829 163107550 774587931 778135154 86805033 895178533 367015514 966297239 294235541 486505293 859242195 371584559 343547191 439576050 690464966 388668335 2128941 4335392 739689634 979535669 83100020 560878189 478038873 31219205 812580017 489705824 457197492 373450547 979269272 959408762 141322746 252999223 217666581 639364559 390460902 451571515 699751780 292090479 599342051 383576137 291872993 345998890 642926965 373766622 531082386 7975486 361123640 957110208 938688923 919487005 496531481 93926668 734193880 716242464 880891097 276016997 982612392 789225168 622517927 891813443 384570763 384163293 379052750 400699963 901613032 324124357 188437002 489560737 827393557 71933421 503904134 301543313 774807382 16279685 721557818 509902831 692323754 233348851 788545244 385002340 113005055 668625109 321022016 518894084 816108953 79813553 276165808 863144865 165741979 69707566 978715934 838139928 941215128 755767269 83647896 441200406 509721659 602975347 408794471 170293381 242722298 811762002 61109636 884656528 292771251 950902528 12977450 592985006 783295489 582171772 464955213 899998835 202630413 98162082 770649835 79304699 508725348 985909062 908041453 852648987 31626671 392635092 245043832 911211195 394019414 413815025 761594978 162015751 61229511 850378437 882646747 434553707 188914628 784073709 620462665 777000559 19906474 645120971 569002177 526663330 908882084 25492267 316005454 89338115 917922449 266243958 281588014 892313407 168364805 995615657 709446873 574843256 373623323 375901874 574139321 962295328 311828834 770136610 90775855 971722647 688603580 624676757 81417787 911466593 123220179 707209413 33974787 822953457 765328371 150712196 222083253 722327381 785378835 219293728 200064977 882302159 332322445 466034497 576618885 851231419 813678600 120503585 465556562 619577969 251752230 231172077 364063834 882744509 532317054 914707574 807848690 187701699 862913131 352148819 521950929 945385274 593602604 477480767 568682944 951956233 229569151 731214956 21008549 902815992 528257253 276324525 8865913 182242737 785308430 598369000 927501834 282989257 441696063 510534040 242964093 293570260 62706870 564771952 859149401 740860392 555514677 162512835 846509299 48025232 299167085 138709397 57370939 359368380 554062199 435969329 363544362 413111112 927850610 105389370 619661136 891179570 433700038 305435023 865445564 33759259 398071544 157413193 578311522 27656546 17922374 109631325 123803329 931159841 961251540 186939598 752239856 406427283 646537123 141654334 592958323 890958707 724543165 394092608 706957384 648769362 343804993 265964693 832553316 671559882 899476032 673387341 846621791 97632193 750436496 307246463 697293827 804902674 126060845 132804015 943445354 292785605 496572836 558595412 693466258 496947810 154068020 982806464 9267357 786208953 655426509 168970985 754334660 723665107 255222484 243421652 1958972 994232503 285462266 73929760 188316835 664267954 861226896 350465688 774923894 217361356 171840 55200734 252948942 469950731 378331957 729669028 834625251 381344467 628727492 396513232 814365498 341098989 556229566 6756699 567357519 611464501 395852185 2201393 275491284 44362514 757381333 511445638 43109022 441054283 137985853 536361300 987912172 132970925 449422864 261201410 331893514 62754434 925021470 429183971 832336178 55154186 64648613 565699353 703256438 190194784 294188182 67059067 650907022 163708348 808847868 698761089 555360761 651642731 227584223 62666659 104223516 676088966 277259056 361086227 244998134 357138825 557146065 508535179 38984079 25367917 396037015 30159990 202646358 13631637 98585246 236657090 905458472 545996632 371230067 59369557 75973073 748401427 393121729 809743410 41667421 242165677 555171539 213630590 170446000 367598385 202616896 286295868 86475296 735127091 181346578 704344384 74510924 581427805 849913566 461690272 712288627 123712016 803518004 561764858 394295520 339110361 196653707 193832586 163342630 718933926 342676836 241616974 903451809 569971777 963540844 622471087 93394439 961159272 838385253 662056836 557067929 390535573 208141318 32166034 567743279 893529665 666587842 289342927 730294711 816125130 7844683 4548098 152140014 305303243 33216199 96336025 289078686 154826530 690210212 88261725 654711104 821741920 313029708 589907496 8433703 664157980 596361269 531606683 139640396 538080231 107757894 142809178 707140653 440549001 478647485 669163640 204859147 62602855 801877480 489371002 624784603 736229821 447818759 541238838 885577494 977510014 462578512 732516301 858362876 699863682 858459584 67923698 999961709 847138373 522851231 986284808 473024755 76582471 721176782 520251321 531028219 429055587 41161529 174102282 509578221 43788420 285422254 266211565 217307315 353736604 166806480 755802115 522085375 677034772 49566789 897470983 351779234 421797634 928649781 450907532 406701405 34425956 903029146 12070228 482122433 782760287 102999991 937860613 368561926 211850405 942192382 981115783 426181529 334033093 727091175 135379884 485780869 481000596 785572418 362743235 838262058 892400861 850563518 708876066 271365859 53434941 523684561 967346145 118152064 27784479 713484802 137183184 995389491 602948936 416171609 68962318 616444342 866843481 976958915 699946276 256803304 718958874 256058248 642702886 755077693 752400276 587583101 136024941 84811776 318274946 142729632 343380076 915515109 756392813 393568834 998551150 686901960 631505116 600385159 670437190 585219197 209662473 652925593 890255563 194993107 994405607 304502260 916114625 503877953 535305463 753193198 243203947 273820670 623394154 957337497 984838658 630347401 679560065 418822954 830329471 148399476 911763350 558640850 916051793 65146859 424988461 284578964 382516773 528952767 597336173 14023170 101709196 213654497 290030561 173995253 450756477 340818237 502561390 197263198 416410660 943842577 652253645 440138561 88650465 456042071 861085468 285612181 953600523 322433073 39895028 819650584 527408441 138721310 563672848 280152362 783333575 689629981 349721298 124212032 406315587 668030566 145229372 403186605 416890183 82065396 540597144 717452353 157214167 6319141 915734232 30963251 540826337 528916870 954184771 784549713 863668525 468704751 147577804 732383050 826102023 820677086 730384691 561383693 337956994 353075085 205080222 861275104 603862142 645463268 756836292 478599482 31526189 207816544 265349653 143324454 486749380 452388453 96928638 361462287 692859436 567200035 448231044 822384338 957927034 718935152 370043027 870840058 547814889 645745018 593794169 215830428 640760671 258251873 658663119 19607602 118778286 978867491 279199960 550088022 264118253 942995314 379418179 389438891 747453748 846363457 202494025 882203087 175535980 953970573 51261155 609642065 918254313 533207514 930694457 845892189 148298855 107169941 926674052 620368869 941205827 450565958 116248238 78262141 393460479 176667571 754233069 7498941 992157862 677662435 492262664 477565367 941239313 764178844 838869865 474144215 126833880 573928353 642493881 411723987 578060977 513834482 491387685 257268788 601034076 221367497 604138993 45340172 145124962 446891696 866128122 287275054 758235433 535092284 775087991 946900026 715739273 93447990 764847441 295837261 812643186 621397213 397810015 460949455 77777195 159357738 655036219 344850577 944417027 959432197 954882954 618156602 742036762 347543777 30286028 324861506 406730280 42850102 938286733 388768864 645177328 590051985 443922121 44148216 78898501 647187938 968736037 140829280 339050805 946778896 705743250 122292997 943714122 226677325 413749300 798891379 96858047 794442188 385343212 399736488 888530896 651687824 870818473 733904342 70512829 810444076 768490397 766987014 327957766 337640591 358828002 385853196 995529595 643261472 995262828 308094630 825375203 522069668 906694991 822838230 34871700 819337029 770064530 224166088 856684121 646309212 225010722 999778564 918206984 788399741 880119335 819709287 680367660 167577904 775814073 699273227 935120444 299656238 318025064 107635588 914098195 20444092 578442085 399172565 178991299 175263785 244633890 186737725 763474371 466073532 563356840 939045222 634041596 8040406 704318870 200377010 142500206 282525199 785352869 916932584 191590811 588323288 122537374 560004082 708644535 949922732 5781158 624484863 767054739 792782426 29803853 564609958 827193596 181751487 803620907 449542882 97534804 689956747 416207599 664823035 293400779 559624196 873716756 569324610 942121278 51947893 677169745 804016962 939706156 449115167 763618214 464265018 594147044 110549281 375001906 218352056 395219728 105547519 834286689 236084572 639382184 228790150 797883942 429924969 382005607 871067173 814099677 606116076 772842745 412612755 801949449 737126803 502957263 810985660 874790541 479164604 235273896 26626486 143439210 569535150 488811804 858290494 44757500 792907648 195319324 870330193 46363076 871497868 550137621 963043637 37900901 308805238 611087880 790830606 312666871 220988534 671551293 457042210 933730613 75280613 894056771 651846117 90906726 285743551 524206520 734394733 302894872 49899067 815923249 814633453 858604653 83373277 531502920 959325671 303611055 183720969 915521478 277003081 818565414 752811399 701150360 325455200 739176964 397883497 309517383 344593192 965317628 134388891 412688442 257670895 251876789 363462509 453531565 836471474 798087716 834390274 788261532 293961245 873326685 362491906 152407244 155919980 525398593 403204310 57185261 322545481 318664832 393225090 715273501 851493628 924850872 943057894 778933869 889239999 719008984 421863415 5436556 648062296 914060456 888834662 203467177 653222141 627747762 725404612 778597751 399689409 638985152 980110243 645749797 843718989 690433093 215344591 390263338 42293239 284769242 31249164 605377556 296096726 774450650 920806272 432660509 896252409 600670428 291561569 520124441 306855699 504765539 962541708 821366875 739537405 158680860 310588092 776654253 50221664 957966807 827440613 547480576 756724344 557637079 256698795 470441736 681648317 158190653 138571407 959464685 723707305 103283220 308657596 801872412 317211346 562292266 73693664 659285701 838702613 794792539 540523070 848216742 768434047 47367871 569495624 178355724 82899227 796800621 729606610 171708587 590094447 449166660 779793547 418446169 375251400 157193129 897532558 262550762 732647521 732767716 249645549 797988903 388743846 440620532 493197987 971188472 670942328 386132013 197394764 582155192 424052909 335019280 437395456 196347791 972151692 524952175 348462878 262770383 232588596 394413453 282280410 914836504 262032666 245545020 45621480 538344515 780835763 722430411 389154094 476048757 361818408 75332561 977490940 211091113 669767445 978449927 938764935 934678482 458690906 636361282 670059713 498052181 853762650 249226789 761586730 959776085 496801365 708180945 71591026 506234273 427019021 840874220 20240928 229915597 844702969 739010490 125631801 905795069 870186980 273399864 429376373 214452190 37233187 819368185 156160719 531146649 769728665 38748967 380338178 854133257 962644570 819405679 493154866 192229365 386525713 334523526 704991169 453567139 203276688 25358545 573891813 81592272 932609187 448775892 497714148 845680528 746639160 703136459 446309562 15954681 719429281 975895029 282408008 24479092 569584167 344962153 53592937 123347664 157618641 605254213 762463715 125680633 609846815 605730103 502104896 388897422 773630080 4771468 412838010 184515566 723550113 22511442 367131838 235243588 507286265 28642073 397439206 475839162 669057674 465800589 554657955 379321868 464618257 81119777 294457094 901901026 7613483 9238753 657059817 32986611 129549720 14792128 743569544 542308538 877215187 327105268 875804748 673707452 910775185 660830246 564204336 362010634 203475379 657713227 841879340 414003413 80671350 476510142 237455743 940263139 441324638 342517891 72361877 814724964 280319411 860321355 991109754 269161933 188432684 150108842 147822031 947785131 208724081 651912607 617738405 590846349 545302397 370493536 177220327 872267544 808684794 774234106 279561122 232959705 926088960 590153247 389836198 766802791 121576621 180705110 6592171 87823987 299917585 999332379 19628974 719433028 752094357 386832976 874915937 346942646 783496634 142139277 856330099 100522522 513141440 546598776 593218452 809184186 5164914 542109561 716653883 395584255 841897294 745920737 566823869 867490206 760800426 604340364 73802999 783280900 209305416 629073152 802941524 320658060 892134488 885761813 765917266 468699472 219329797 67213879 633528610 77333320 676830829 885267048 325038687 899823463 132179711 512390883 245917128 398193526 584938607 662852544 190686736 983822297 543154981 628632497 167991652 738241352 339676295 649055453 429415787 210308810 975558048 421296856 880639614 545454987 124359286 776288360 638304886 613850356 864455892 273699867 113188620 129903047 621498570 497297981 850804451 356077186 201487959 310430704 775227066 721088657 241160321 783804148 863277191 990767142 856999947 265492561 361795701 37597117 682638238 917928455 623186696 771119006 840902435 760389087 677186676 981944961 649672280 651641661 556434809 658132658 915047104 20875547 755909466 983818280 847322346 224274355 410690653 339286004 499236769 947461870 103038596 407149370 478330002 102021264 95360432 747538382 288402269 943242223 956425427 212351022 14923154 793861216 654619209 724792444 297341315 272905365 602315378 132425818 439863158 806911869 938809107 320285144 965644531 570699222 190004440 343598942 777447433 151267569 944910890 977044864 992827677 289049635 947915586 456117330 451212638 113503565 658122055 609210943 96268801 118414835 612126638 463643267 644653522 575875171 803220879 56633923 176909273 725059036 261060213 515632319 628450328 473502086 137716361 287827278 191279223 28263469 654686052 364170435 732767734 412572104 678228392 232168372 39631121 244033786 98323629 700625578 692191737 89096267 723009560 403698494 70421532 539729829 916993913 672187906 827270770 57002826 383955072 985962577 668270597 435147173 605085438 640448331 950427890 879716216 949542715 614347546 694866033 963894790 891088053 107088141 634358290 41119664 387785045 189282710 537203728 22735124 682356333 174326336 674589012 905742582 646703126 100440721 910239974 714910286 961279973 331984685 888311667 360643096 1917321 680645977 18605505 368811258 671540583 642738324 969101223 336944559 34128555 50991864 139912494 588309137 668694574 999044680 885492247 65281062 63556245 200041961 98303759 916504585 392458409 704442376 487349838 478386897 401832205 739512772 199018586 646648877 15537012 467288756 567808784 295767534 950160318 241807323 769458869 241385473 650173405 257057619 908929761 233033298 777789436 400048844 66953571 95838232 302818825 81986617 303540597 453718705 447663200 266423398 368208695 816119968 117283880 45138053 354302568 197379000 500619282 650837868 107312819 852219074 893252545 721669921 489637167 489611133 814656 351712588 118166806 33269472 831568085 253645163 330282341 549735150 81265747 444669594 476389618 352245716 15849265 479353105 326298883 686381298 85917010 641888984 259002937 263566336 518998434 87139346 172480709 121234700 120041501 480973421 595392539 769270547 392659879 881821873 130624863 217609930 266024473 807406401 303408489 616256391 95821645 393811230 864824689 887645416 306546461 238332355 816866995 24304569 574377430 953199610 767003222 667015298 864895610 927393039 484402125 735322920 412796834 469106196 949462875 876287960 876027717 593919342 612057800 573198762 711579707 963327943 807676161 145348539 987159773 787218632 982861980 535324694 165513498 723207605 442309458 370836314 765651929 988642806 400724382 178017918 366590753 913690918 14276728 309695040 671233334 881693113 121215922 476281651 478060277 21537441 312953689 932955867 575767794 83856558 131693466 957164466 814879748 969665273 696962952 9972910 329793550 296875748 938115308 779422310 201054096 811961299 936454949 539664700 847081320 773222709 84274282 820405236 304928550 572403472 379678712 236364668 591731766 350721897 555855109 783221349 655324014 597182218 532880835 744408393 931974122 406210432 904090743 788133087 284889368 882134492 604981969 130259710 637869474 280074505 454163252 65229146 985697675 544771089 193762138 276309211 346859317 957472754 27691309 230252617 695467577 988607203 393004196 29101486 229342051 120198160 377066974 366793070 330040759 934164268 262242420 378996083 174672073 225717181 740051022 136259014 224735123 730373082 264799081 17498986 696408253 840617085 445204941 297477637 319840390 224468373 85333228 314068696 129233032 693232293 790547546 118749687 932318660 521396361 585102970 265424951 638554088 113274432 282097745 458349431 621263779 51021954 590223071 996741808 248400598 362933255 170024140 473133287 671057267 280394203 676172612 595025249 530606666 25353371 205613296 788693836 944503081 128733468 535521510 198080997 561423931 136723202 572684294 616529421 939440143 752551789 455154616 563329260 81054194 190488710 208014248 407942808 114792614 139722563 171625469 820225976 404938170 514229033 506777043 805316044 382749963 810125364 971736099 74146315 421497899 344422696 254028167 227573109 312273093 614688320 788466823 697146272 14488935 118418003 441267624 748933258 441532985 497892013 652249019 644668649 343010351 219847745 550887895 532400628 962865046 434868567 72707313 435259074 80049901 303729508 819723179 696227509 584500796 473333362 715475384 87038859 320184804 325534385 495629657 821540953 7994184 467399666 66579528 490201484 129047713 613603471 870798143 338133711 721761327 843999633 512853401 665617929 983614279 248074566 47214761 411323827 511548787 867403530 179453783 669017360 186465027 268078635 539951213 506783235 830979422 809057 858528654 104147442 492994089 920892477 885789576 428579221 155014910 634700702 310772773 212403239 722948375 264119661 238547804 103685029 843024524 782057872 403983836 814521918 110146802 892176251 125791428 160164811 567636910 610314654 83702812 166735039 904658577 306746353 466979375 177470098 166433826 219765119 710600271 940633383 136269013 336916243 354611962 450884264 44300082 738177545 224272032 777108794 502489888 798544205 721555309 757340287 851788464 95590860 575327986 630995106 530150249 777199655 435601487 818887713 496587216 252661068 253385051 382587619 282625784 371997391 478102910 784162702 864156966 549466622 52300289 960161840 209495040 46901172 691557986 230474791 400416799 68814582 711919428 656782650 299193133 294793568 342137153 534185465 602168350 367054549 549608469 453510505 197970601 836198079 218072696 574490713 905908422 913542717 876529306 21285914 245548982 184584294 480881060 689393969 737824006 837819128 434255584 301785781 888421719 278048865 30135533 532967404 760450964 444603541 104492750 349614029 295036700 754689552 495143335 821492888 143334871 317437495 113804487 727945249 511700144 368600709 302371905 627882198 823238739 739330856 311433241 58653158 31646188 440500063 904862139 853424259 822570926 433165692 991498029 732171440 596486839 3077238 435074460 617701004 751864178 76126327 286195212 159010249 70792383 922263321 308272228 386484878 172175884 426805193 811203612 987877773 837348724 107110409 728571324 90054701 427799497 913629949 341466975 821867124 294039796 711520512 118125569 900135938 27087233 288238400 861551722 900774555 712010393 324895142 564208077 51619312 325999249 73247472 498232894 755977882 453218501 893829902 120882367 924709090 307896372 893660458 51873972 91006807 324241356 285301367 979429400 193884506 80618342 503766701 909076387 904140728 938243911 621455891 676796219 962377587 472490874 868024514 617950514 453766855 791237884 369891556 604361750 141783200 498103464 840916674 309858993 741881888 777823996 416415119 357971438 36852536 573752730 984319720 135624853 648435821 196461930 87993314 670873255 741275783 842326550 362724250 352145309 111891260 477702092 196567594 195816792 105059147 407749844 393855074 531200619 723348337 90175355 851646773 796646162 816253553 319585095 909342917 919445330 997379122 445182973 965395121 878974893 360996138 538209129 626214450 807378793 139168295 835376110 62324228 405117754 359595947 81540398 63970806 481015472 431422378 815281733 887825361 549924674 284760216 384402050 494406035 753794276 633483825 243880708 859774260 71636491 902770848 13824357 13705801 950960514 180085102 918008757 15049982 199262581 652880901 62978535 758208385 243281924 89091022 539282581 856683119 962074510 226266451 659199628 463712349 782160430 61797010 48517256 943826291 96988293 862735759 319043350 739652724 622951615 72171770 212714492 261645763 952947746 951014145 980871135 339823801 692373572 352274464 275201398 704109532 562183550 718406772 288311409 996679598 88326854 905430246 534772968 562214706 690084976 424466853 210111965 928948974 575520342 670073555 493649365 866945180 60450982 818590362 208729198 353375112 897266204 824266331 647823403 615108192 668403265 573149762 552585491 156406059 903348869 945158596 254910117 472298381 500865804 776043973 257763658 526098774 826220180 546177614 11055978 11290105 968143017 60515247 775934353 386554666 3838204 137615895 714451059 816712800 918116185 214353637 913072390 155073225 627664717 681779576 825041713 142626766 23997216 971384524 782269837 918982027 774303072 483793683 68197072 558707844 911956590 354236164 651767387 764087423 290806560 151440266 288165096 196518068 692632651 23006270 706030135 496100365 345649506 4854225 614088873 808267682 183338189 214750733 736963128 997054081 560253163 13328831 335232015 947881971 775479344 979272466 484473571 340293713 211196358 425235295 806951641 291216017 39853569 629432740 293942036 684660573 157948173 504308637 163561386 772211909 329506723 445033366 96873112 433368013 915126285 310385465 412812129 446350234 503118176 532199834 940137822 238262901 602520023 624620203 352537070 108325845 181381492 835637926 640607357 308166140 205119119 862480479 909064762 72296952 35271060 292037178 557926916 970367316 421901294 187041290 174961006 889375739 303761339 32680086 99388171 698576394 337646462 759846316 646898256 368658103 912802292 233615488 446424614 215577028 349290861 478280873 922999304 961125382 365391633 846277099 41143946 63482950 980414660 829291449 906639058 429062558 316132330 783093715 716981401 254196981 282941264 758472230 926814217 362948866 820780667 501481652 189003456 985172430 661076192 944100633 202424637 700142939 132582527 616042693 745093796 702095294 668036610 974085686 835535443 74019623 423472262 746062188 940547031 943671533 865074301 745140699 735141370 230512390 288211598 22154374 988668446 599603861 208816472 400708678 651797873 908351619 356253288 823070489 471880095 369688339 647143817 765579308 60827959 565624340 389787471 673533145 889352626 665281602 380044176 834189457 217347035 136552206 887784432 686500472 540273120 645845696 292755394 127842487 539867951 270560266 186180796 345070787 596555663 444204485 521426910 914205600 230304697 470510888 846581659 271351953 848276133 416422314 784714014 304964712 375420053 129550193 668418912 434169458 504287561 777096194 909130768 805213036 6684552 891390255 740958325 383343326 381738296 193590428 36227697 138079300 200985213 415897867 226740032 335583489 633711587 648367083 244469025 239957981 834413632 192039315 2043686 604842151 346488618 597983380 619619216 110876770 945552970 727140584 934888716 102466610 421020233 79361174 641729866 201744937 417567810 237348044 373907468 954459486 507201946 51678601 650814850 468346602 46309779 238220514 309791079 424968783 128408086 751107430 52737264 671777428 738207568 935191662 486302846 250044745 163102096 509269993 341738908 183387085 579026245 222423024 538978972 493012320 725107281 793742633 284903414 174406393 357686340 790913983 991301310 736303459 865645268 773041927 753418915 375836250 846342325 606339454 63844328 608627950 755695038 294913799 899841760 628771952 189772761 56584018 439794881 65581610 189950473 374941904 659815303 675162658 829857027 15097059 841963082 418141578 223665543 242542477 831352629 717624545 704528531 107248541 811171008 162658191 368703024 355461233 358999550 397022443 521491783 68992514 761815595 514697076 476237951 193559708 85527805 797883885 173243752 222428961 233681027 217982126 941682415 605660240 994650660 293893258 897494797 245304509 471089690 145982905 382063748 314275745 837464362 272747529 833554349 598522185 868177843 901838648 94863414 208666006 995324703 443493766 642781346 857279436 474205886 28782644 434255972 19437456 113007678 408075592 539915170 476154874 543984081 476052626 156503560 545350262 707147127 931175508 29619609 795836149 341786956 378995467 647885316 501587853 151707907 551667048 600525725 58912448 817926941 576228935 356833823 477154508 338682558 172106413 222087091 924875250 784361494 558399610 867582058 867421358 107923357 416014055 783803497 99407317 815474909 526450242 511641155 7688491 105429173 196488107 153395017 139183169 767669419 254395033 803107959 649804245 170669270 492023792 432699984 566742490 509758752 590375812 50669670 145762242 148636306 439719845 94443014 981028390 371045455 739545106 477083889 98089097 782935749 404335089 239242588 108229406 200586204 765330343 973912256 264182078 116344332 479908473 537104760 418583827 989248390 602595222 34914057 732397826 211105881 67514508 199431304 585537938 957801398 890083984 81703027 522392068 841266303 118654212 804410372 84718140 211933212 176557018 451354782 888278300 474690825 735968392 246828687 656974756 504301053 724789750 261013026 686863318 917619574 343842063 483099462 440333021 201432642 620924321 994185737 709773079 70707854 335629889 82445590 461874625 190989829 954714969 918571691 543139865 734311914 4080192 285372584 196762706 907666528 772341568 361494925 319312259 896187110 471541942 505269694 549027336 19251760 380601673 600770642 507935639 121056730 752466961 405192849 127185262 344360406 652996406 189734829 709396248 974056415 211763832 138789104 583737210 711836745 26554472 320315881 199563306 287960435 206666149 70756446 873986108 125645067 218237608 377163878 433681352 727676001 93337600 475982700 334785583 807430760 679675378 487764327 956539286 640583382 196588970 71659200 54031436 768185064 604089826 580431536 125676437 805508994 270364492 67697370 717222020 988699099 18497918 97789266 287002227 523798275 869478863 679540137 72181997 108305084 994206479 361918296 405694744 40693600 552858250 949575562 687219711 891584869 185843960 696314182 198757397 255035105 545181057 148106709 780155371 152127981 807805516 901195797 125604937 328941635 93263023 802290894 991856829 887952743 401879752 48631674 467456680 925904998 717306537 529967406 116362709 214592318 42628840 345771378 725470328 284089649 182814061 241024185 977280955 836712640 566103653 335985757 818147046 432556781 252675297 119986262 128869100 352303657 452125386 753580896 503228512 990150949 70814834 469900813 521365059 448675711 602706023 29861222 75157657 832708844 158021101 209847904 920240061 395584087 581413127 762893392 541781911 983412677 808795838 718084793 982337971 293935493 555129023 3827182 212448923 944276299 338620638 665363072 889456284 841878839 150137346 651291498 748890617 919225655 125134469 166370870 415047985 854956549 453567152 305080928 376626109 753128666 408606957 78492272 500599104 974253808 988766981 415996794 603416990 795740560 763495224 368351577 507396198 397624573 827933128 203131932 135499214 297152947 399314564 325413438 215628521 344237739 748700552 613105198 523274029 974315323 505941306 353350147 99659620 9146634 141042144 420889852 855870858 169977293 932585430 565688409 736645766 912112447 193157740 459464950 311375585 963792720 781846853 55481903 9095777 414517380 497540162 723816083 681561476 248910417 11847004 681505424 813562682 176333440 699108496 675139034 437736947 326519308 86236660 273709228 610724202 858716080 858840006 560614228 87079921 595248692 364161356 981677138 28444412 297560440 990903399 38284346 241204715 936063938 392503769 466235103 105245884 533141148 251513451 410214899 47575291 354369577 764577605 812890598 843193030 100206793 89458944 373472757 641752683 992241840 198271778 507200196 778327633 554034343 565087634 977882064 839768378 77232722 147144484 303408192 487239960 861622766 454642661 800021731 642581059 774727232 306618882 970348787 353598926 2568067 182023836 558780384 58916434 854312813 790164022 133464569 78192716 313521467 746317857 184204806 453394039 380098668 92232526 477211709 859471061 642172223 898188941 648110333 512080072 945785995 942290305 582992674 140374144 28966877 119698175 918704681 183441487 126766634 146529576 436118158 204216993 590598914 442282755 84628042 293923311 685242628 762607732 151256049 786638895 836130043 126488315 16482119 269248599 879295455 618240831 243396641 794933404 14177564 390781865 651996796 338816996 406897132 571245123 996276487 507762755 717514451 748886440 753884944 501560311 717248245 977386508 180899270 709190166 473762140 763954353 289603837 529237182 812234974 757108749 682010361 419583020 117847574 68558095 620258199 115852502 653108895 131903260 160584907 214999465 183056874 927924354 300463557 154651602 349924607 651620510 60807439 874962941 297873417 523722751 640660519 362978331 287988561 548339031 999445561 628867618 2520811 458097104 72906162 892227637 576253690 304094685 372895202 153378728 778515473 273721365 696219708 299646149 223635610 908553244 683370102 128785311 673739834 658250536 285549634 580016195 878218450 689761189 169346633 469947703 316348284 619120032 190204150 889190698 290219180 720037098 961442888 31584006 760323586 13514042 384218940 187900726 8953553 759296783 420044438 645341827 843478430 470432135 526375202 535467783 710045190 445282155 705849013 97255407 564651341 558641218 471059436 893805318 335894123 275064869 742192690 683165070 120260369 84838999 302475898 28881022 826795030 209049117 900451566 388559532 706152478 662040431 242952496 831136685 132109394 487047650 947262453 390129940 367874101 442938351 291562484 970824202 565043363 248437815 460083187 258584607 302601678 405982592 770762577 614893414 89972571 546597560 660698831 666959990 82800825 924431364 38095886 792258724 625464093 877183228 441334400 758325049 413609836 847658573 551681455 413756855 351430520 358529842 900157582 652219542 961427105 149259056 429927772 430752470 273462183 538025948 492332202 31763916 84852979 929937526 193281062 687960984 970090255 696015444 63502243 76283927 822978182 490957451 875229562 450117553 281123395 167462565 847687633 14435023 55176025 522420333 389018084 881645892 401481989 54772531 596294302 156738003 867168076 30679336 739500217 816929754 116551038 273005028 871606831 88494543 478492190 827211326 662614817 392657102 336898744 490898351 691961867 575983529 485975096 856792858 264478053 86743861 359126124 130302466 674971186 301759386 358723226 579677732 14723083 638460709 496906960 199786261 271531265 438310640 347798720 680140614 628351209 478923571 990845538 178783310 510515187 388520485 249226063 432194425 412235732 85595763 74594854 339339976 853430731 194889914 218720581 815946713 516873870 740918954 971943692 333798956 668932263 835199815 470746566 420070321 491204523 216748549 270156453 737628071 519210983 933440514 779946687 875678015 734471050 749241283 226050588 976087088 83767184 296876111 512239547 606964692 170179608 333355806 724701914 767775832 211842640 896972768 573084804 485714565 691534525 987436067 300907948 987695781 280171214 572719997 914583865 197093832 56755989 40557477 942747545 767078706 406715418 838317859 992823434 708173063 525374790 60113055 426862357 611437886 112252150 132894415 139465997 725583176 46575733 433897531 579929328 551515599 883822678 526545159 390233385 336849191 509474276 792356398 974219063 310536341 754121028 756714021 893091706 136742575 456474722 225344642 140242050 318537206 113495000 685977217 352260016 799527998 998363855 740567831 515789749 136076180 887779470 930524936 580452944 215800474 725186740 867319362 17747894 490049291 923550668 864378770 794400434 995214427 299116780 20330569 738142527 571363636 767295832 958159104 722681959 473908799 57788620 489902811 686260484 125221453 974193345 73242926 142658193 665594753 682472684 738431304 333052862 512253172 773224278 826007578 760764784 317233762 584687363 32612972 8391727 133694939 517869513 85141317 513636610 576122995 729566816 64342748 306683152 946374510 833651798 823536442 367856994 789892498 91432806 758940569 588323494 695086471 10260465 173278791 568449315 542370675 190587280 493587689 203679127 913648673 654619243 27803967 948455736 463562974 510265500 171458628 912447005 225071463 328035820 344276071 401546897 632665748 161726416 481444447 865319488 136348508 136971205 264543362 323854328 349200000 975261251 883461036 119710290 976355541 733169215 661612772 335707712 538755468 863709605 572034694 292647365 724954426 978047220 213495699 797197676 512542026 96313381 914551872 862507000 358678165 540011354 247293941 71320819 924734174 106168145 752475519 101120270 364518204 163261991 818860169 150351746 189715478 160309893 543108662 925158066 250099528 611959448 375258615 86721993 598496923 360610133 105636538 501642691 792606462 546476360 749478904 990750188 185122252 547735344 315610526 428731140 493000506 574278950 971437154 169770830 297003665 995725589 751915291 668110158 407924594 999736954 82723332 927966358 6339929 513453937 41599388 145736691 179056157 969512210 802131271 435458713 125095631 941491708 909041156 335592854 861120514 662834742 172073105 434702859 244133356 997167567 428436591 340374451 840443880 634735295 566664911 848588697 421018732 826206739 869388100 244908866 656852944 197970205 205454186 459865176 303523150 289979187 917349038 491969566 406939441 555687388 499705906 296105218 304360967 955810341 917792887 90408244 956911118 453290123 919698470 2137703 47814948 211617637 261009582 693867213 959261246 718487936 353478962 59913027 752107273 683440151 880232624 534857025 609534922 353543088 860573859 440873112 175391491 585537112 527920091 96731226 582344078 882423925 256633004 65155314 119578307 178068371 874498119 314302613 988458621 781962869 280628034 37732756 714998050 706843219 85825029 892215914 508126474 224458794 562839112 219132429 759446408 228940669 779097833 790928419 635839691 489409225 243856955 760719515 240452011 108754947 249808764 305249647 675423918 205411070 683146791 281838759 489432847 502304180 674715729 695403110 721446436 842174994 120412494 741294063 617235286 815242103 317436407 489914460 96142159 267590213 953723170 984736113 424893512 559020170 447619391 518092359 660903207 714248346 987823659 233331496 670619042 448834066 2900247 408098075 2823899 699819285 638619989 692260570 557597224 32426122 887792070 385725333 442681307 515433530 353410886 910998484 669825050 609216498 788652801 507447080 268304699 267490247 217868237 724444021 263544333 180218170 81353381 470901446 633709704 459576301 468731064 613427011 839126531 570397967 405984625 929250452 72561587 915977312 586478412 599505068 67528363 676938577 661261056 30762439 710324581 602613425 705756000 586264595 319762871 758986721 954381644 215678705 130066697 638598792 689052042 403207698 639942254 331905022 905028067 328371022 289524218 639912892 186495158 512067460 554558256 115348189 124513101 212569295 888713099 292642887 290268393 268245750 55824195 947708997 301061901 551627205 702813121 203293735 213682203 890215723 14559960 57731514 884281604 486722177 895163801 233359816 453985959 898000327 522405854 478769137 763213081 817992310 427800931 599175372 870576803 124594435 764489820 605943638 536779610 419138652 85787883 263713536 599645321 587228118 935187165 403113261 363867893 805789501 91631999 273094033 192331158 869257319 819177744 981452477 204258434 245695441 149118239 985117338 87921680 219283016 228667495 391588667 510158869 930072623 547427593 831573146 430431159 337223735 149747520 516023814 846797268 579936285 359665854 192819755 285116712 42791423 253719802 272796650 265167692 711516136 66291941 779503041 248591589 481616952 488499865 849271946 335485470 921144248 284031099 536814160 867127831 476118380 217803834 148647680 822558157 482158442 35519945 580066042 531908054 569206745 555005858 402858177 804305029 425155682 877385967 426229930 445733950 398587325 814896097 746425374 90639662 68420065 758931766 477666625 102375980 511345188 415841829 213987678 565003797 776571093 117635412 227633815 99745821 405327330 158111983 54476439 76191736 308998318 380089250 467206856 87457102 613523095 823706081 155048511 462981882 170544693 328087474 752588318 651728300 982421873 399704300 509695035 188987648 203441041 254561050 10289681 492163765 933008533 4126765 349728526 911650037 514318426 91292700 714600944 81862746 466269383 409079269 674312701 383051603 198720018 365331183 809593547 17627853 599598374 95215522 780786496 621702286 962473724 225697721 247104540 666604397 890433324 717368629 758431654 195110700 418390530 572332846 693848368 966540752 4577978 400740008 374979932 423252381 304082982 974115625 701730196 997996502 849577119 44089379 337150309 422956478 860891198 734068187 574406630 454488364 312818323 379905708 924049807 249538055 504483609 650085741 292456711 577988271 59696223 678850431 314456355 777678990 311715390 755419812 206929032 700139944 479459468 527961493 442385261 606046018 81824611 855574519 933476198 141154695 394767409 408770118 758191525 40556388 125798231 538648876 550801124 276607456 454773185 42431141 863858027 56257206 239920238 825634245 699264603 598670385 468873415 43876836 955519494 592820631 341846633 95825870 831146921 537143552 379446229 695110426 850485219 202952194 822729379 62347301 584221360 88013501 814320337 999094396 665781729 980589036 13593450 515038174 872548497 991526284 319608468 424712612 134345568 90780583 884305455 831975072 576808326 242810574 799164734 686853145 657145551 566585738 648042720 831969241 324592619 68200253 833349936 81624823 373180562 278874640 457870357 900418370 622386089 473583769 24312141 885645193 692209177 726595744 626823717 76055191 827674640 748822572 255392215 293763922 489221626 955347744 411823777 477843051 705433083 830828493 443786633 706352452 208786146 648594678 972120716 28585360 647037832 48954057 745478253 180883592 760751968 490629008 742945129 271183587 911661844 516867955 161311544 327238526 897830825 46076484 127769383 149607520 23968243 589639555 460270747 261287379 313026617 102889141 983961265 394985164 613792946 74188379 475032163 362838028 981673553 537348905 315530091 608202178 724664695 381007706 514391205 571833160 162796600 412353489 418801167 8590930 364394570 202582373 973789559 370503645 989062441 625870676 460909404 838867690 23260374 265009449 661755694 162898139 799117985 311403999 510273572 959427281 721941669 448681913 694104341 785681965 809720918 957990612 952954226 844492983 67405029 631964574 11644738 378892153 259049084 318203445 698637696 766701423 489523083 587329983 726286123 323678837 468686917 783891531 68778350 856459161 583091903 519316802 146520146 581808021 113930776 909582639 543586210 949310174 647160477 344090456 369924922 246756211 237037628 648374157 208887561 526653675 796695639 534086092 695245552 595984534 515087730 685443156 246367299 680845666 646785858 155275115 810927988 305333061 75966120 44244092 536942538 733443973 318096201 924372235 40720821 399612445 152084111 426891522 751422412 436025429 815758033 883951900 414220907 855200562 497854937 69013360 122151029 742367716 85164973 331442699 349236107 44829909 46722502 785481550 328402227 124348722 365053522 362596212 929825408 835893785 980067596 89063044 261650945 876195836 413840991 787675213 34586980 299339559 744258609 728617725 569671811 152308126 332840188 663265126 45454681 228619211 735586794 640803022 639496911 168134374 49749160 113166279 44833163 791829215 711846241 648840379 337958971 144749551 568236508 357236406 654457158 439558188 531103373 78148622 871476761 579365224 389451556 816585635 68608223 319225028 847172507 890070580 638245382 128967902 642159646 826190061 727210906 184824082 597759002 58831379 560858327 885124357 213647661 377226415 197139509 433151599 888559459 756347512 46031302 618674445 709343029 892726971 713146009 938759976 293340335 587732848 30094978 329594404 852641522 163650003 676516580 929267782 104375940 993262385 849866745 21132812 921053097 466657981 653633187 217776387 891293213 67370960 789594747 869084373 622993483 562211513 543357285 120979977 573772572 433869983 598392569 88871954 359030928 901041233 31762698 910317074 264225765 462148846 130087320 817096746 10065485 238013638 336041165 964708828 997585757 622534864 599399571 114814848 202138242 169101788 299986217 42906290 824599179 793528866 826952779 285397480 340115438 288869577 250364321 563383614 145808085 415604196 697256592 596723254 955245981 805924942 918572020 198023995 244324052 136160456 773144759 78366522 372446042 31167354 976967896 86451574 451050470 426213126 433359323 144666579 520488173 768132135 81891779 587976163 883911355 237424409 980666846 674928021 973922424 700411295 876034929 224393384 501999564 654945815 31477516 28439574 137138718 612007599 917557437 136642550 491288049 436286747 447939416 568906319 777367969 734699202 157137785 883420097 218618398 715142142 21636779 13956868 763370736 584295950 594026033 950039716 81471311 905462787 431010647 119540547 797624186 510607396 723569624 138386575 297757415 702931401 769185288 788425829 523637950 440876436 768516745 183952405 845683896 421680098 108108679 939932215 202226280 609252814 353920404 183565633 675321551 96825927 594009492 9989134 977136587 22986277 165853542 876441514 791020779 272262616 519974339 466028266 461545556 638399760 842379404 147227254 940003189 879752394 533018709 896488804 549270075 68602532 45161941 249430889 938838382 526071969 5228813 718337847 658019768 644796825 990628611 790775843 202101385 31056771 790409264 174509648 346486251 516089915 700575849 13158201 684355819 638783643 14428143 980602376 772420246 565035470 501592701 949090388 462013809 5842253 283266369 917462803 609662069 843724940 242001990 736380338 773902947 364985532 671061946 451632772 649079712 314115016 339653276 617368806 610269113 140814566 509642313 351084384 625271699 987374770 709060175 139279395 420228269 716979523 286301824 300372270 469023653 815758759 908566913 596022458 538477687 406240776 975055846 157698472 461837789 908786838 490302713 354470835 268222227 329845098 43946578 854835959 899054384 640585341 100780528 554128379 209456525 926952747 911778076 771834783 253882471 989801179 375808842 727029277 581299616 52504689 207240573 526184764 67267237 904507494 475866875 923940182 500871365 452260336 441533789 337796627 84620811 271102853 165265314 56661857 352384568 207423866 839331666 758093185 673852660 28375690 783536094 907180548 461026826 231392035 856789544 483174989 597328924 423802176 352179580 862187549 666151372 587684255 387639136 682617796 713688992 286287756 223518884 893709480 358790272 76574914 841841187 71515839 370257267 368132011 366759337 278102955 935997530 737298406 522032241 405268736 179422808 742547118 273947437 256518845 271208423 261041824 234885347 366045020 121256806 662119741 161375345 852613677 377863296 351357421 267690130 429612129 453806241 582162874 762922222 747640948 789188302 271056735 634983154 185784370 912995955 236445003 368881028 499289741 640318943 665454401 463195193 386619725 417326241 74835430 242625012 538832577 83817778 78259013 67622241 30310506 923191281 488738204 590513757 958437027 385403721 593965492 78206999 281627904 709508078 122249411 973627960 243687728 613576312 62096395 123078088 425829645 528590413 324533672 190595717 574693415 882474401 375530081 296949535 849079283 784812722 922669563 580936840 20716247 632667139 354542916 886066699 999681457 922141079 278296844 893072387 924535021 705804527 238633089 947658064 239873822 336002066 829117149 844716634 823655875 860404757 558113125 668646216 885245624 711612122 341324460 349921326 490498040 606347064 55070634 488262154 783569275 386422027 764835970 967901082 550921208 751065767 804010612 982414516 81672459 475075454 843556945 628930486 136351206 710314433 140199620 603962962 352477642 388116054 326292593 129991873 484363174 594802989 782471077 79459643 701326981 161991721 3234410 519530038 308148533 789221729 378660971 377842280 41177810 445614067 644780564 246140701 758215744 716655174 594238259 377058226 998356202 339525175 659650545 443447849 148607803 150037065 821924707 179590807 261947789 832961674 840924852 11537328 540636399 919915491 113564585 633716179 29690306 146259725 618668530 588478180 481599929 310291576 432447886 94920333 919282903 948141034 890462250 639201308 208457582 785829702 518554023 366291238 57984820 121446716 834942492 837837476 922704061 70792493 760645979 283616106 986012235 53525366 843812802 495475812 871412556 457558115 807686147 358160595 612397421 963718871 695284884 332001773 898266715 648586178 379263486 724543742 224541435 586783420 566876359 418173926 226652100 624756331 213323805 862071103 240633244 293439943 83388977 71268824 932545042 558052023 358252146 149460016 806629778 808106829 693907322 918152507 262921426 798552462 403595032 569265881 397712038 336825220 897124993 347241019 556246435 744796674 258136446 194730639 139194499 342364732 85116857 325909593 30719103 240923975 161964183 477318129 644628502 263811685 201758183 560155305 140153914 306145899 631049625 853547822 922899417 389236287 711804183 297610172 651166505 122514686 954747626 982293765 74051256 693252600 588988170 733114544 636908037 421659963 68251001 522144840 634205399 67393735 289742546 840316951 926716651 565851383 862467663 572180493 532180512 156462039 669052805 8996902 573321348 730767908 527828362 68818976 366087605 891101031 867595451 762275326 537757331 795882380 20660368 550977023 424407780 42914106 758282047 787844776 74671140 467104330 791117596 117787235 608346451 619406177 994011172 543437878 834748677 736664592 485349577 107669135 51856047 401027351 139757026 713571957 75409961 399548437 779218636 759463887 268419654 949334310 776142166 528453542 299513821 617035757 138042233 266910382 431960599 643594789 732625370 403703082 56583347 207254092 599552915 755395708 841842034 13330945 569679602 874688210 854314079 787320266 171687899 566207945 655133664 607415846 986579477 592909006 79003190 155807175 543265037 258536193 721720074 345294872 731433196 37302150 429032461 423702250 859603773 148657867 776868881 965109656 26279127 595928791 500903927 817655562 828596025 569116784 628606715 17818196 776994926 265578589 70822335 879654844 461129153 998773727 357020072 713142983 334171996 799683113 70219044 217799390 992187285 787746248 848690999 617358374 745029137 815442604 920884334 639315964 545108614 703348686 645234062 541049767 390887165 606309121 430923321 224377446 49992252 892190110 445955984 935961710 314220297 345733992 98869081 488213046 613080159 912645694 858212965 923261570 854795828 893914171 147047969 57385275 767677545 918000048 642959916 974108002 233456975 640033318 95636645 99379437 229562557 240920757 695226210 753690552 188237569 799117362 725967429 397864574 86917130 578570888 55265141 774338966 349224285 643179211 770071305 98901417 157768656 642784672 833134568 377046740 287879239 345305800 233463525 107393671 477732679 798011020 91092093 276137053 671679891 545148795 386258356 891243329 521660690 747403671 308037667 274810291 958971775 930465583 260262602 700358133 78808170 449721685 347311244 25764588 775715873 471472275 692554807 147398602 418736514 72034755 315169716 957087011 127161641 69770716 828492520 996582179 450180929 938549094 897160700 193918607 490429221 599736358 333493450 726112518 502353581 505262335 298501854 851189549 879243895 558545507 839923809 533984659 96039567 143643695 640393285 647766148 698341218 21145027 58415664 122319000 84363122 631365496 943490340 190537941 537127831 535989799 446469502 742511817 464388477 660042970 160779439 870060588 394324745 260629508 167914390 108423641 870232301 448567488 887197148 942337084 727359967 561562034 361079859 542876147 913743547 84895350 309075803 262797056 219162265 136909326 76854828 111482403 744492640 464446576 717495777 336242349 96539330 896845087 100590788 375215219 296074338 407579840 148564586 226097836 18687573 841048587 767771538 632540829 797423657 866644053 125064072 886553854 910518292 385333042 262691229 476962350 429716283 845091574 46765389 964900028 752015500 724653450 320045113 270903947 869154106 342720416 36714106 870729739 536261341 153744268 384355224 880911888 231715897 223270806 719314982 927691719 434673347 935914127 897639637 654937985 810940879 79114625 143700321 409264232 162233566 149183775 873985740 794951450 889051052 63952928 656817284 802288705 518935543 660990015 182819867 785046347 614267435 833950115 267244050 333159209 471577101 962287404 585364980 59228377 241661476 833202344 998052148 478748103 733814738 23001678 72154746 993016515 69045180 227032909 497821812 801260620 948309351 679861471 797100666 171800256 684276580 431876681 249122031 310992504 377912799 925359008 474023099 862079394 218253329 922208264 488164825 343693264 55930073 776256920 226446542 234778353 932960391 496824845 953769692 944589357 448033694 525812393 809835694 549770302 529524056 361945098 75431865 880895480 803655934 36126678 484848755 826745905 5959590 379690711 100494628 749574397 767633614 350715069 153809517 215456085 531893962 775759053 600804494 223372767 648448257 357378396 33714574 898071997 210054493 633062329 780289372 47795666 826410093 689352557 912035010 850833533 549578459 170409362 458914580 9387118 248665730 820148920 867359244 391122142 902808964 959302856 182101131 379505245 63265812 998178334 289102119 767688238 520257337 99227639 272109646 381108878 293167495 233368293 693848878 557425883 649560812 667412141 960591961 239737118 110925186 709078686 263961765 350752960 512970625 562403490 487021656 54526258 698386478 269903494 968118845 282192372 136493099 777764080 245332760 479654836 21894600 63879313 120745175 164681353 630157996 868433850 970642589 174026468 827463238 16345601 594262986 992559981 982861146 616321281 207432780 59372403 917350412 740065876 114432996 462104687 163594182 650295841 95927520 139711065 716057282 112456323 248614375 299607795 832986034 556886268 175583838 563985939 651295711 992044732 687421771 718292098 35157894 853545894 972560921 230603700 641787389 693126726 887488677 246170651 34777356 120296343 963892698 303438959 484521026 837612529 863245353 165225685 684144927 907435157 714832688 610458920 787665811 678414137 441785476 467387591 246303857 926651048 911204241 536569693 86102204 227023314 364536358 407449181 901211032 337998999 888452091 37998431 824340688 711627781 620406757 376907693 435069903 314721186 802900233 937322959 231127487 499628185 156446500 492363349 960898908 528219749 852149807 280364434 648073892 19844103 557035582 890449623 672359191 986384847 843974768 459617663 96186913 755141441 302909319 914248580 52417262 145849730 926297668 281563461 121539402 517946299 472861536 451777560 669550830 827554184 372155445 747045459 82625353 243533616 70021140 245520816 833282448 836162425 203801787 133175826 122333617 934265335 416084341 175126922 29809005 414076687 4357234 785356299 836994347 209005643 158520621 608165936 78431049 535295572 899811891 505290392 311449813 293107467 522867539 88961643 924666254 647496484 515210027 817515917 257326320 785981988 3767971 896491631 734663387 845371402 697825070 557704985 478853791 311950806 655750551 764158067 23595517 631117557 963399528 128473761 84823127 980357995 46482956 291600013 213905739 421037542 675758428 443237334 438000791 302761651 88183052 423819043 545962988 401533355 171690978 317868952 144831250 76255667 549873377 495274738 633086578 912258153 233284598 443968660 294399812 485867357 72773613 177700224 288150802 355834214 279274943 964009050 640709793 580030423 622146836 149951889 98977035 97282532 519602182 101021087 957358365 390799028 684265328 114190106 919657619 417431043 26488327 964784368 368655858 614683683 418820162 502534686 846280429 115086814 765599111 388333358 978890029 380706042 17967222 811204018 437192356 92326908 969789132 305636925 308440935 400940608 526364771 855006183 681614912 61432540 580318046 24358121 766385695 691955610 533367402 721961898 66804407 568818612 262397425 926393091 790667794 93059692 28489206 372441808 945799596 943679053 616690562 972000930 391877117 473796369 568729087 623214086 508179541 979507077 158807377 745022606 556432552 165401833 269118626 14045790 373480648 874138257 754277331 363487945 44640599 675672014 913868948 876955560 842854457 661765688 345140435 244301730 25232419 742455986 933413454 405398586 251042463 681174008 311196585 14651495 915280005 6429061 443086438 823104260 140147705 642926291 186104727 796274812 655465214 600215112 263483337 914385470 362628739 796881427 147776811 709900996 937392846 136627351 244155376 327580705 270308038 995244299 79980573 126444747 222521298 270889254 667057840 406994669 998190591 705473677 990778045 259178198 408808587 562210210 521827726 330153491 499971647 373282487 954452292 326835942 728892046 126488519 947003403 68555247 370402473 903285885 111454860 782167316 344935186 673986133 637809804 316482797 797534537 260106062 573618643 866184777 891346956 666682126 886681551 54157256 74097606 294717598 833732184 895886421 57001768 945073295 208755165 629824203 257037879 668309066 995653379 545198776 190522151 378247414 572396622 465694446 749086859 617027834 717714011 778743867 115297487 80639505 903481570 30049492 804674550 595876992 138903706 774963048 494150681 413010796 284787084 643403220 225566187 271949134 477864719 569196016 891059919 708165213 40566679 810738564 371697521 981064454 913900092 144724760 42145687 735540432 478896179 740448906 586541706 102436835 432046707 850579138 510043640 134779661 299893483 836351735 177106062 361088135 884536571 827293431 349585879 370752729 173837865 359047892 644845509 667852254 45884151 904278378 451457957 993210332 377066911 860324775 365231155 937857917 898448836 525949819 632783299 560777059 140892084 800435520 794069913 177726949 730550207 642210465 954042632 207931376 752918358 218109964 272709902 474808736 629698455 363645242 670554731 237418255 579810344 719533209 543051935 594114553 177785186 403701521 946832087 318799194 553817402 810162538 412478190 195300397 959672592 528220342 498625173 870420424 504014185 21245086 906408481 2972967 604804424 436878253 73926201 207181782 329186923 725047398 848012685 295838691 228727599 216264263 516478274 588051890 916528585 722655710 955169901 325973544 206051510 40756318 529623634 238066424 213239846 542229851 814383695 875769782 881742022 622150159 568295713 99227809 596064316 742814818 899438281 792742617 332040549 985949307 417106847 825704581 963155062 561914079 985799640 435109774 490833225 23089469 509870578 461315205 831067053 391268226 592991944 355576262 330511290 454998034 658519168 509554715 666307839 910792713 599714037 855799971 511041212 98310037 525971933 66384062 960006759 8949405 263362941 235224731 626737918 840391126 377068882 478404600 324988010 238457285 714977940 68810735 555598362 991799901 350606497 715237237 823601141 281942486 315366097 348140969 508658937 133671041 527758106 712426874 21570741 430204570 820512523 982532331 445177783 486447921 569461459 627412929 568410360 758867530 340629621 346679025 958898579 361808358 698667970 189581507 878264449 247736987 340842970 140971911 392240470 157843203 858361009 868966080 154780677 623460722 145575938 217768542 364988038 504545930 944703940 9697600 362575690 593132233 968792176 109304767 174569682 917754362 180770528 124337590 241557820 227097937 890567523 917847049 957456887 55543233 484016700 367210529 774672360 381623205 776816300 465379474 256431731 191009219 383408672 241190650 575783289 913487127 69796050 667390508 215016554 194683083 965766911 463858659 6316821 109939604 652560394 200099198 108005244 646524569 990901469 479956656 693576595 84611237 192706699 549504517 478640847 512026553 591426673 95039118 655660793 386953992 200041429 426293327 250069843 679339617 27815951 484748775 531095477 749657161 115450819 269098254 507764580 313132905 50219793 502209894 110470854 707729106 133540885 435224093 814188373 741966010 606840588 672714388 738907071 869651705 148697845 964155751 725044648 500212972 541004059 35738758 290142624 431183811 69385103 893433452 989320139 612370721 868023649 445840432 803820049 675078640 909803340 715904304 170563629 371450958 374903157 294737023 747831708 938930032 523715710 315222362 673970748 457170898 932762793 327373953 739898747 771793097 958732919 829102644 589308715 745316557 595978719 199893685 59517210 726300743 517226790 968076147 408833053 112674390 925800970 866909949 447184039 655907253 543799679 956703210 645956311 158915582 860560134 459091542 683365227 134096718 273843696 967053761 700922167 403908516 771158552 266454542 388142433 681380704 329038170 144060889 254399362 774648648 10572984 506269759 225510917 287714886 971611956 748272461 19822689 341252935 390186812 215583271 617148098 735560989 309365704 833563490 96143747 187631668 357935653 776843978 68612029 175223923 516648372 388392552 803716869 447163153 426771352 811147830 764065543 191799962 18693598 461665823 107343127 239406353 914326305 128101388 784527257 363556640 995835750 933720964 343233411 764356703 399220533 98235305 132345270 381610616 433941307 750378592 91736422 884566921 707836674 35387873 922943034 159995223 536482709 414085452 976133155 288700696 659825000 489829608 754802888 958590578 833239173 344643007 344419462 619583009 683216902 24593260 648415858 212674026 298161232 200540013 467519736 409271198 876261997 69565402 474099584 470515988 861394927 926923483 92038338 788462113 103477235 79586457 683110557 117048116 31770292 216076249 694389297 161792722 657220458 611931871 440126154 437564031 773217492 742428090 685579535 473642866 759777422 838983459 81922698 651508518 882093890 798764938 644515004 166439220 632909456 821626048 569985744 679210767 138508216 277379671 427445590 435869193 68247199 714406709 330799480 151264075 703762351 215736116 760817620 228475258 43000633 328707856 192972901 990799598 76845325 297509972 81727557 242511128 694550127 750555377 689112304 952757780 914466770 43056885 667223010 161580762 206426694 742213721 825443330 238090619 350368469 43168542 793172339 533959087 296977418 627126649 359030832 544870624 895127559 717711350 519435034 535677248 705642794 559860801 485507418 368252747 892854387 733262969 62297464 981138398 873100576 883479509 456471932 822932582 894073089 179021395 775942133 32303608 315599783 598133551 925800695 598467676 708253456 955836354 424863718 478242566 402402102 438206229 188284370 69014593 314175942 706957661 996922523 841152796 763568843 144540873 911711979 770648535 870460312 676666949 407415458 581181841 456708436 159666791 839550661 729454212 459174145 265300751 733085502 391760412 606490087 176503560 170223162 418956743 213911822 521441606 83524128 691429341 61802281 252409072 321985417 241035429 848627555 777835299 289758946 12706408 249701525 821990592 425960111 286404206 595781772 599603008 644499342 319890419 490908331 661247229 611151343 156971128 179867383 410966192 874009513 134648719 612417890 298301953 727202015 926243137 695066256 433502867 163198394 757775329 382281048 830505754 589097799 481980034 83408862 131264805 572316434 468995464 861307196 60607790 742155415 840614567 778317837 362747456 884931096 141429087 680347837 206174125 467707759 597425367 756105175 819009907 187900851 601950807 536867305 238208706 601325772 319048150 42727237 89257910 782645087 101341555 54414700 661414823 73091737 253738067 944747588 25348507 942870658 644348986 222831520 67125190 684708902 606092336 517386727 134901487 974187111 128186293 688184477 603106161 782651960 188938678 358395010 42046207 184390687 598904613 114440085 69474294 198363088 438442391 246435792 897272332 338775584 987269177 397829561 572003967 849972943 700201094 842956990 66887726 648972514 405252588 366692903 890397031 554724324 827477899 643917615 646952292 505284303 366480994 377229465 394574046 635284310 730182433 130404665 661914303 361096265 849168429 725458413 62156457 665184776 242287498 159196318 360017922 157227440 674738545 893583709 70511903 128512144 978442043 928040211 474853380 425669357 899029748 409359672 958907 995772521 35630454 304090042 75827584 798527384 839235990 623004601 505736448 574469375 450797320 920868323 853402462 5542409 694578265 690415256 531971018 913702856 941249619 483425426 494453791 566615709 483148845 402816822 828198905 528898973 453342210 834410021 742789615 717502912 367981905 937799940 817009607 945437643 143004857 243142793 759899134 328626407 955950890 947369009 345952584 99937143 437462969 629383457 643499686 737392694 926065233 167238727 561332522 989530590 734961311 759875277 683401264 14570598 459421189 741940275 824460584 401089065 639200111 933879056 201768566 8946434 696737563 193726976 429259068 524232252 4243236 331400293 425674797 815582701 977263629 873112959 19777367 672419108 331783912 999876058 274019944 234129923 143798307 353838558 813022681 344634280 739611082 391602001 683957419 781590447 237090175 897949081 756166011 918523725 610520650 436916970 334417730 415862674 603193584 199571191 574487622 774954786 626128644 334423411 540312587 132851336 679737145 118076932 656000863 924784018 940397900 427331846 214603835 370859148 243262434 9336114 912840121 694049220 153261658 650670995 25898800 595480893 825446201 168968976 339351520 128452282 231610574 661057448 136046606 837806027 591132995 335080949 72085535 142145708 963620917 391521669 850403196 211099507 924925922 281292723 512233437 238988811 244834501 605273738 174865124 620597775 820159649 400279946 589461563 948158994 969997101 772035583 994487309 242025822 914768758 242614468 65593990 987391645 730914126 589950223 818896747 287280465 659938414 555227061 322393591 561280587 967755221 884245650 3423555 202063771 549611851 919389006 258533784 988293491 698232338 766257917 519309312 471413131 190265509 531073008 950058577 399574900 83419075 930373644 195773853 816622590 26081608 607953286 383821160 138333051 188763505 812834334 771938625 663375324 206392047 556194498 349246616 97993548 349848642 744265025 438671138 66617741 417570895 280513430 18870889 327725999 370272399 969100573 609978790 209323841 735053784 772825113 68839703 995943699 882738426 668029965 646940900 717696509 587721772 237335058 190204483 8097860 393605317 558981247 881437355 355467997 624083455 453551367 640173582 683587847 706358606 394972843 576111933 363583805 570296260 200083204 62625726 469656526 865753395 719884254 379542617 201439942 82587070 102336025 947570108 951922920 834713796 355881437 599424993 403604977 533180738 273601745 958389315 833971109 45891042 48130113 88417054 171135442 556382170 596366938 379278445 653108673 68639009 613106933 391877424 103512528 956917239 591720093 931505752 902415496 990065996 727511960 641700258 982827304 445159787 635430261 492221319 632613473 769111408 551521248 132212099 326597709 412400552 933787846 17440033 554022418 973560628 510545672 728978069 58368636 940457169 342147811 498163741 589423416 279301275 247719648 594779014 783796613 682431879 33166506 467219509 786737110 305631204 992346246 665546982 118617451 793480699 773451736 555665180 801672229 471189525 290028376 667533082 672080985 370591954 170110044 310919365 456597284 384974318 110282431 491160314 530824841 144113597 825602631 103988734 861666740 793311631 122370638 846975950 208792845 366470385 546491818 129471094 268068783 864961232 905030515 695382730 625786994 894418954 698365963 283577545 860264853 892326154 12979137 753682414 303032978 510410071 898543499 390766800 780990650 12660481 618063438 3563525 418049769 914531558 53012014 579871987 233729821 423741646 843745210 400288551 828004775 440808570 410111879 192454633 987968760 923912771 383684119 305886914 318490047 707545265 343731206 160765441 90501413 816815390 68980118 109899648 514354878 77468962 673328001 481606267 620896352 40622525 626602209 126279304 537049579 853971013 27610533 820936012 649776661 549560545 60717126 354725203 32126320 254185941 662400998 129646484 401530310 658225981 412315954 259889294 882046756 995720131 908214839 286836296 937619664 285878844 685944115 262998104 524512191 317241140 788979820 858114289 765135370 281024098 491102682 384953861 753741977 551373825 323838481 310813303 96424091 787176254 774126837 298841782 191644699 511442075 89130097 669904498 354513786 107518384 27769185 111530200 697218489 731251876 943526962 839351159 656120261 509758714 27927821 394759764 541045438 839469310 330050738 69594088 854697718 497432803 368949409 550808160 643675470 792198990 222973958 369021505 449313969 745664658 385450887 50748294 86867374 355822225 678088392 924319126 173771347 925950852 677357816 961579121 982793659 244411352 245481214 571187854 818963386 419147271 959532768 582269925 126098730 493179095 292740854 588337728 675118665 209852867 302268706 14541884 61850496 502543171 797676645 782723797 519458514 105062342 319313620 308160035 902966560 651196360 418039766 653137543 787845636 289631397 564049077 936836613 750325023 109366161 675946925 213244631 279933053 253484963 777370266 526374423 965612748 713553801 311941597 513508700 227287563 95619977 185841270 847224027 906637408 36309897 593796538 491173791 585156628 619766537 769770856 351178875 747123877 936482600 571368911 539663622 275282102 256470558 569467781 518831592 200865697 509395315 942497579 123920664 183582386 190637139 143511807 548491505 558394760 357168420 838324463 619280638 661479772 949998529 432330769 652008241 745548115 858252316 771322992 455105768 256248655 113305816 149340267 781339153 762149570 475286081 817349750 633405735 770854847 463540450 154137114 121232952 295146886 978709882 967324668 286970105 72877972 959399177 16851984 315217301 832784204 792333613 268079883 946143098 746238091 687132125 663690642 173300425 950129795 303576042 276711036 131509366 90915796 363383386 481288861 619312980 207165655 385926225 801192174 896076529 86040438 821519657 468184505 682839932 909372618 946815949 337988805 285271113 709260921 38553379 154344035 157111024 72973165 361866928 932076461 580690427 992575858 536704342 71064006 570270267 449610233 887236370 853883445 262296230 246053318 391458522 351329387 311663113 310923040 268501326 828647961 726830088 193318437 136151269 15332879 943903958 7196682 169511118 183826094 22464749 715021655 835328237 570467568 961543474 816140607 163773897 30817559 124211099 731356414 536869473 426018751 319950631 654506067 325289595 819049344 743228655 634280822 842638039 260808430 117596152 32810333 428636196 368598708 15366210 183293920 381437188 662647552 807515509 757822346 251903942 602707686 593451714 758216325 29593480 137424954 721701640 706460948 385971736 731453748 303832471 147417637 674689548 826306928 508775924 396283657 310155827 507110508 772745174 54323300 19573631 670271721 941641970 37980922 407112254 939308819 235475795 83182326 959657285 468743111 717719818 700175284 831866106 871054727 202262405 523312087 899548054 666204883 528686334 449021597 326954372 580195194 18013751 177390 615975554 950629813 912909562 138199593 278222445 910029983 743516321 1552073 626457981 71983097 258228624 620539623 736700132 275715417 453754354 798343469 916565617 812691528 153808753 206303983 60213381 565087868 159039137 8822641 247366554 761871600 187571118 130610848 417768358 736858372 30551185 196888712 413057413 784497778 481622878 543598168 478465547 288055662 35105137 433674616 847156211 367827583 574352419 202858044 745896963 620740393 476764512 499740984 33984078 912488757 61672091 804932238 20989795 908064951 947849016 637434948 743578611 204823318 17490535 132745539 955958303 464530182 786414262 474841847 359615547 356261418 787710045 106894203 588935521 133567411 682854502 435588834 960331124 33282689 790466831 772092015 20221354 327831095 322029891 230728083 2778943 696689155 314773333 145214549 727609575 115657834 293315206 677789202 615361335 493129558 471534582 602248167 700964702 928149049 717913706 749483812 469068106 513240138 999105004 704403336 17041227 493219953 662148929 125314529 397197887 391748245 229259963 111656700 500376216 31032396 315389590 506035013 179452911 319634133 914378595 719158722 680215790 77424637 798698166 313955064 379695835 731869533 119950298 747618297 429360635 35528776 136291748 617815920 708124981 59368396 157628481 391206977 835197139 138113091 508728151 65704073 502557538 965224574 143281899 272723719 611654043 563388416 874854033 747299813 108761584 52862719 912276141 208063043 814527285 543889757 850933857 453344381 483629665 248184124 891526023 156144616 249209382 136629030 323255894 661496013 899305445 354146181 815927071 935221360 697087064 379448922 967770764 280701703 914935995 680294576 956673260 504630921 966737152 7156423 938489873 195533626 665949123 523206092 971046474 41499613 307454005 120994623 251626993 488916754 274556215 336151894 879721334 627136554 910922223 443437025 459596768 816624784 630739547 498415961 790051800 664167503 28154807 829146323 895943820 217923308 643556158 368970028 412764283 344133804 173229549 770810809 602112910 609423544 715249654 277617842 613537954 371632958 295208102 179135641 700389176 875764918 428061060 773151383 90114938 278425566 957794503 381448179 200762579 510924646 370658122 404378693 53999789 963757978 324062301 641723331 22133046 75542236 886257963 659007807 401747106 772919417 834659592 841789567 256112689 482785450 200355721 234361977 984893364 101031433 24742527 426943899 364674064 62038521 813979460 805851902 434658743 459146170 446230259 976137977 578606609 391802862 544956898 804096904 376694929 436113591 188203978 593235279 547407689 767099590 758771625 463396945 158317445 793717945 511319491 457356638 313592765 404332763 461527659 411498128 839266996 528077268 457509033 824381249 132091364 309484204 151991774 858194506 915391773 321845793 359198448 831468777 205683588 341154665 732827559 64915813 825795687 676037546 860928234 847240114 682069575 326092730 382126863 121213560 541656684 498556843 742009540 800408610 642321598 660505664 212719229 877533175 306109038 849442174 658472661 417659239 386127447 47281143 867919728 595952034 31613404 178166453 10053493 736809277 77680136 148075324 407478868 402798180 671450515 403365384 497586994 796773458 844081261 344911021 693437751 328069249 107496542 935881255 963427904 250831297 208539868 511067126 284684070 905707882 196724825 882734850 18841706 830139820 22385012 73143105 136698947 541029219 128117897 727942696 249920977 929878914 491127386 437837418 371606370 41884123 466279874 19027223 651003368 680700442 133738555 622005457 685370745 486073079 157347367 100034699 690713023 464841202 733469114 413278517 507892718 251033180 722891514 726875689 762208264 896059817 661162853 367844821 342238925 133892364 777915704 807536172 312969000 233486434 508116972 514841004 630267783 513069872 101768310 995964175 138876635 569688122 788922685 312252367 692279575 129372715 305064170 319824067 632027783 209170220 392653053 526263770 185359204 344719788 888975748 238529944 135156187 473879745 297991411 597952526 312387873 816597065 284163356 730626413 600998662 960773534 878095174 397161993 222797885 374249604 446822658 294280591 186649889 49764589 419387692 814061790 84800587 7025153 80487149 421753592 247318887 312022063 764494270 429750502 102224203 554994807 293531325 693181871 608068751 843222538 656979578 380456965 123368344 343419473 960851398 370274180 501084878 959748681 462763188 904562630 806070251 459779672 932470756 747494674 94774381 825553063 474552633 407909300 941069336 71180521 77315960 337293065 213819178 725196806 673967911 163909729 281821622 121331445 263215871 527751586 260988730 195294379 836678587 378649406 495387960 935716698 702018017 819023363 866866768 356298586 642679972 195114639 784150023 308304218 966129302 518680979 395471663 101208734 407647174 504510112 831550395 733810292 93724115 717556706 828289396 62055661 442281161 169986748 828139440 468830809 652869908 683645854 447614832 820813609 443814371 444747536 100953865 545317978 968312827 878230158 223914704 180441737 780092586 611727329 541215621 434033322 657127464 268772693 465748936 606580032 375884122 266396803 407682041 158000834 211444385 714390870 674151880 39376324 585492283 649959968 727627969 850019561 992504945 965697740 206440532 798388099 754020900 295689943 946252510 554881571 974973866 195102614 288875399 865487765 615181867 842605805 751932614 198931386 976540291 359907289 490981466 346206281 144173819 935936427 865749754 503662277 234509903 281058869 437130674 884166673 487333151 590185261 693863115 203659840 886464681 645746038 247612413 469463269 267517881 402937415 792150225 922794076 83244657 8492844 870506829 582490503 843316344 908491901 440805330 58969294 153595878 134137982 434373979 467285954 748676898 757169564 449774545 203171227 984455094 254460473 92689011 308597411 103108826 387726189 141080566 368505248 643458948 700339201 370059990 562281325 967112111 650749857 678664068 144282645 673391519 136696211 892248326 660387153 125546120 274097605 404884310 25318720 975579096 324837867 792128655 332090903 364494812 433294615 631826067 425404640 736288322 587092236 792526253 772557459 345568303 685844345 129431854 329908395 928641818 310146855 61969008 934546008 702456990 188209430 321117591 969635094 399406003 522378388 192020032 279512905 311871242 870793859 983481077 440342978 919216371 244747341 24101960 196932339 590016511 771510211 467183269 349608121 845574103 463554586 366052526 62072381 923503133 876236254 790451549 611808413 37275207 813345651 148652999 651068924 274984512 764360217 553678400 939813690 408680045 383146605 158170734 35496554 253410482 60570330 448924310 662968399 980011984 263715954 985672563 299499079 118053482 750251 211459848 577288349 711921336 294901686 787011571 21647889 581384157 901870550 715949729 840729273 321854154 989199003 673573920 339309338 19305743 467800094 344050090 145883802 628611793 360799524 862073233 504982132 328427470 491395586 283727038 823896490 152989331 236329053 943688341 420862877 283668912 597320334 494980904 234283226 485712778 422832448 507131873 959946048 27347157 107704090 181166301 702067641 505794757 476680763 144948652 255682054 640689839 348695312 793356807 169435904 61756886 102050668 694912029 389627490 443760897 341987338 724997843 234981828 480990349 528706523 410041610 630796354 677986020 903502746 304361189 154324763 840445460 846818188 723132500 129656997 913298333 710507638 568655514 353797574 238406532 640872694 515745764 601092614 881449465 450084147 249592364 145863814 496009337 729303939 627011928 810895566 522978628 441966768 23921072 202735586 863391982 445615422 941219242 293662696 52912529 921692258 461393059 906684122 657945238 590132825 532473922 946425207 368439485 799158319 162594709 388618106 663478280 267361569 848278166 354411125 703465815 28123753 361018312 219199968 13049324 666350803 63130934 51872401 322099113 472359162 776050805 334246308 810309084 994772573 526733162 411446439 774288035 865557092 542949155 54791117 809727285 435679600 104303475 174857863 939243589 593368154 977501289 420465716 6394618 266138324 715387779 971666091 355392361 897965639 325748088 872413114 396765454 658257180 716714435 703451771 23993589 950350774 517478800 998004181 694540164 451141031 586510397 244016908 747699519 678541532 205482134 724390340 973173998 835776966 724272613 18488314 106154730 784079778 956456732 223267610 522159145 870425006 999501910 862052210 800929653 946022032 458009338 493248961 862319159 511513089 381319423 32771324 191738157 501084022 591554695 80374955 469296 954364196 300245910 102789145 215730043 949040152 230422762 436732813 855113097 749771176 707799734 491657108 929883026 821243337 870399714 200454674 402701225 993909240 67809779 644398011 537565500 618542498 714686359 963190085 97897947 405921180 686963110 617126954 760364846 212589681 597311063 765326820 707915707 691739158 834794643 163892873 881603852 55667843 566656894 331148399 485292262 955237754 896247923 983744428 603111635 710571817 533153425 262618111 235194572 673368110 641224371 77785244 55866687 353163371 56129681 485358387 909345354 420712609 990694340 983865054 432601562 471080862 453753874 295175866 377250029 148566661 729957839 933952769 615549186 358028726 984096311 1043565 425386769 298295197 274877548 375881203 128671244 737840340 411828826 565600844 362003608 864725783 210797363 602314719 429063383 333497077 118571309 250802486 500918852 724554763 200604717 202564686 458711226 772740823 445768931 801009548 734675512 204332602 652300179 663821988 906949449 963480922 626704302 61527250 839806047 681848231 29519726 737483505 14172420 603018387 707082186 23824270 103687853 794567783 192521365 850136552 824115216 691484956 390922849 361445620 636626384 40135531 231206838 913965947 216966404 839174401 709680463 868972372 235256302 356587941 643593853 772637970 313002061 443214991 421346024 518890346 140627701 752937462 611014746 332949914 974003873 842965160 940165176 994389838 147140259 329592315 172466478 243304751 41227769 694719203 26593923 475646104 755593977 542157126 271263264 665533811 489651577 548212995 567881170 72785108 682421578 915168633 649538976 621379300 499142763 351974066 83884791 512757218 902258747 625348442 691013567 228686365 18069994 654873228 206748570 890761518 4188366 848913605 281994774 631573749 917139123 55983084 84897716 339265173 477131157 774164441 186661353 985137873 996892408 61103498 268946816 344586875 156732780 390557819 732617983 812488896 26445616 794969280 503012634 206359413 452287519 51675905 264039890 338638348 344324135 344241878 693515013 628262301 581979998 664671443 718343061 711413040 766932816 218382725 513901521 13045156 769127250 389172300 674869345 560674850 463113294 898777821 270529736 816106684 561932846 53542517 998722579 969844154 10050214 256916063 958601271 845396138 113984992 869975945 312066062 773090653 798191718 580863452 297321266 723527547 641362617 973119799 187160412 324000156 118216498 297264133 153100282 947238583 101517820 887779626 106036162 841590909 799021289 12363219 41242108 577307970 306116207 260787602 529805685 155170941 362656472 140515539 158304557 239007690 52775506 634662301 933349203 865893536 680500945 666069691 969246282 184723352 25162019 468347677 403584312 795912659 984325484 148634648 860931360 423790776 472842804 214444288 801854330 569332290 606388917 545998065 456216176 996311459 346269132 386850648 169100877 52231931 218486649 256492146 120027067 379683846 228164753 657601059 576001536 795863974 352621361 558538724 343163647 115194105 136948708 594060689 161620301 828113039 182334228 26252782 98514799 821206753 827827019 346794915 139683537 168362728 588449692 970015122 180843892 464627852 508530380 355689016 658580202 494711833 387819132 787729885 284286837 823575825 313341618 982536589 238178366 818789865 436022393 571612115 686393002 646349640 356792154 550327572 666526512 129511675 272344019 354708394 917401585 58904896 972868650 743585093 123831312 392120077 715963725 742425816 200774320 750366472 425207962 947325974 152419769 864563825 158855777 722868221 52238444 976122941 888203324 119412192 146976136 333591323 324344789 234992340 179953960 883344362 225025722 964472260 12085301 710667239 312057264 876606541 383963811 706667227 966596581 815622730 684176059 463350841 643893934 980047046 366098584 511152544 311938687 624863830 695413821 169009217 360375252 426013676 976855994 246095770 628546739 762755535 594626695 629119170 403314002 621654649 492500296 429527240 747879802 718806189 16709360 400063687 778081027 966641313 911220645 191850000 86378348 905712013 124358580 716198183 58347733 959065197 729926123 392061886 975867588 210896293 332760087 862910735 642897515 37055279 627076900 189560333 857537611 457738061 973899711 213211316 996194162 51386379 821243890 773687623 201659414 220128691 399451287 396875999 251650729 97573308 104870789 330538507 773685297 813701114 968512703 275853561 743580315 107481708 219754971 465772731 641975460 376680407 242487611 872114948 466019197 445196641 849620554 726312456 474867454 523134323 21372294 680608784 630455487 520565459 591206498 568274480 619498821 911017089 539680017 431470315 488612215 820925625 339973076 850966426 250552280 535152926 334854976 55758651 462153798 954361445 844511741 452104259 266298290 255750491 68254339 770440863 898479901 996701727 588875040 36760253 880618714 82138867 551877426 614294375 981930436 258302615 89666920 98166914 677630023 166844448 570130961 342776912 821239556 579272472 459548490 376015648 653751195 544698705 673778157 920037281 799473053 417145335 239515515 354542342 195881932 484022280 266801961 95041873 831709907 571585969 648678750 959996256 493498881 13228381 346573350 4395993 409403130 304599318 68458594 22220415 53335163 331841154 548020629 94187713 824382602 921124702 358189118 804789150 903429895 535344024 731746946 225599920 182760013 24891806 794635866 183238238 867121634 93485609 972203600 350681187 819020634 231752986 126731509 302061982 702700025 745573208 384862527 943141798 385661117 452973098 691058921 129642717 995898422 621152675 708984493 17528266 524055877 724696933 949851045 154531708 766482365 278983876 293813610 129884116 493573732 286016725 976147157 479467922 296779940 29799394 542599946 933576166 656242420 799221256 630296066 629169373 990313814 169422266 123809561 220265258 316790877 297385874 282658622 41839264 503717220 431420904 299047007 262065843 626754287 642644306 429612603 133942089 952647898 58857707 663563777 381233666 880533390 144728469 474381211 686350440 722367780 475558863 101885024 255907350 639565786 506219649 470226248 309152026 826388273 758941726 930409990 675868559 264745442 139102321 666875449 600655891 893630597 530389310 791443691 426681849 410961431 785910290 599532621 210323276 918120059 869187461 549905294 519787611 38193388 368664976 684435484 448627985 455739691 895708818 788375057 291051312 618376212 233502865 317263983 934153629 400197161 691342356 282140651 378580920 981053402 887893294 152454761 534608374 82165099 125903002 434873287 144309239 768914610 665220640 458554723 523344979 186434589 969966793 766824697 488038730 343812679 849362277 742097470 452090603 631261140 814324675 981164970 771743206 682671797 631011575 352001174 593914243 769264974 339812611 572980828 140585330 743252101 551138037 952947883 82604240 137827656 943282072 492915074 951458238 620073467 201213098 383175279 492345564 156022937 457120537 733126864 169435476 561353391 118082187 890013503 496671306 483818576 715161927 289069943 914482682 227344545 527510594 962928449 381748744 93591948 514098544 383649938 701568131 616361252 809470430 233253949 16784586 868210898 485016699 712456170 344266354 62700175 243677442 444898205 764981834 893769193 172168461 961196693 415557211 847706874 679146124 339010899 454798100 215410417 682912723 351621460 233491394 100242695 551712973 972446779 640684888 795172915 672428409 356545022 378705909 560327898 919047566 502985381 262078084 345922610 622283400 676657656 875070835 26682423 208437215 575202369 511836041 615701730 260931916 566176824 195090075 343068245 728248557 939090081 955140331 989951597 224103539 165934400 943864071 614732862 799588320 811899754 457773132 731167524 310351609 356077987 414636440 307433930 586371555 223022957 261938137 574548114 801086212 748451590 246644112 385447294 546466940 414342147 729867397 301842136 597229568 808076550 430517255 502296821 71484048 818874457 808848514 696126877 181929599 350683798 883263756 286547259 565735887 251508388 180752264 851673933 405876948 703392240 810488563 630093993 350666265 553088802 998056860 839466867 69491148 423880163 331192039 696401112 995522924 505263341 12401586 519821060 594787882 157574405 144969556 619518068 350724380 47205152 872688839 229600104 6240818 794225842 115659229 414295930 436575961 476548307 248840632 213706526 999757636 485768540 620936671 158463086 78092192 214391362 571434753 356308974 271940751 673405464 823949728 124615660 688275978 59698244 567834073 369956384 629397002 88876517 229746988 408697951 139008458 643082854 275696739 594371321 439213143 26527406 311006422 442451825 557596752 764704883 773168469 396681796 16528532 87940784 492788426 181957319 547052953 896646141 524318682 639035046 958791385 470470667 440433559 383651341 303878591 381571810 128702860 907750763 930965760 633831985 732874826 334152729 466335417 540432256 565173292 724085408 817239067 352268778 646276840 380908549 885370906 421175604 681163941 46577071 197184586 155317449 295654905 519531705 295642965 813291960 186702413 951797968 115509744 111596974 87909535 779974387 734589426 663235463 909849656 894978045 770192787 754412559 796381527 368095890 589606968 726672163 503133844 609674368 622648409 549529639 838904965 821988039 624168231 770984892 637094820 153530043 397084747 509170089 846723140 142901020 118557883 763812952 971245008 55924729 881969872 253520620 445566989 119148107 548623253 98579384 217844564 770957658 718480788 76478564 354625333 902224062 521721392 466419591 178353956 678942586 829701393 309848650 602227888 392061877 372426178 628840439 316806133 299742389 25905482 845141053 319463044 489930023 819874304 760726271 82938597 506552063 868541826 613082078 838176226 180403444 502658067 658194659 23580823 622536416 812847807 580342474 684792754 711390184 147935410 830926485 542989942 791499987 369648079 959336114 838953674 819974582 20625300 196175725 386891450 368292392 184760422 176153613 574967720 200320009 298162441 687086707 375150782 912355568 938231581 818394014 603907974 545402815 410106937 332775134 225807336 745124934 888547504 34158501 975690865 489914392 848751907 68510103 142522226 640866417 715808260 9805315 347066453 384421075 872068661 87631110 925922172 540560540 894232270 297138269 713207956 817644065 719935394 870640345 978388658 17966514 851840299 359976982 765968971 594606019 107003681 865120398 739880622 194380173 716290023 126360967 386415466 561192120 643519055 930388983 555584557 167037024 415714179 517578739 677029639 566843111 318580662 895199006 413078949 488605850 104790818 855067484 649595808 561990417 715616800 457226615 895397408 577790592 542683794 868511130 875094990 514391414 730460538 234610104 547651093 740980466 957562157 961010663 615465728 138256494 690870776 792357648 211440840 725860234 851882459 335329142 334718978 386621068 272559090 857132519 838699651 745066024 459023374 716142785 545511914 503966170 156710017 507763875 412034887 747107415 790410637 356311755 670341341 911895251 931176379 477902734 513975939 880822629 394773200 420268399 99717898 13073474 263690434 314399517 658880684 212195827 846264010 74833427 38518121 763903113 145684787 975819521 530743328 467933931 733360222 537066146 686078195 75884897 85746396 349287994 918347531 841902104 309695564 8790422 384051537 173337692 917612349 134043619 659616155 16252094 250837294 699367653 900252114 512527909 813025986 515474649 663235831 381046064 442215675 293374456 804292097 246469853 179119722 322583684 754747890 474847938 848825823 408948746 19554011 711712084 15351360 676260077 917642016 227064057 790150891 767692923 795265020 729253442 886647658 924996466 301169745 15350223 926281906 652850154 315129870 205216185 15085760 908139804 107623698 994752862 302102056 642972981 485183002 399999351 267125430 320971579 873073410 830024851 9796718 345146279 353902401 223335276 92562935 275399178 635095879 419257923 828189594 257513169 670668837 208084260 217041232 248428273 864529584 944637520 498116694 640023976 159167977 584025983 325508243 326424877 999609867 507321835 226441832 159645568 643632655 984087646 934302871 91983346 64038554 613871300 761290530 416387643 164950640 843055315 37915437 803808100 2646601 948804743 116379803 394143016 743605630 2224326 865393088 544062909 575382445 180385200 151847190 847735539 62839198 80788580 744611514 813244339 381892705 775951228 173270955 59995861 879217468 849758035 288114591 930670055 704396414 785913434 930028642 495778937 740909586 492979928 897477272 535038366 505345857 504711063 856642109 461614417 828057597 152155457 992099968 185833541 900346706 188012786 28446799 566574865 589353361 340180637 425584599 512875278 552584731 500067097 519717356 897865648 645331210 117556347 360858067 725498161 154898372 716144911 38325228 260233151 137209989 232840298 15161951 501166691 633657671 149773657 515152388 689665846 918099710 292940497 95439405 264925143 806124578 653905660 138069771 235255375 778503381 541481546 615447765 617734067 278783340 871187188 603156556 479084450 656276887 374588877 831346885 462464801 955486193 480736648 873773306 761162653 731962542 456367327 494569901 644596315 339306588 171920026 718732045 955560755 717054995 249295003 931343647 135103650 49125086 820183646 245708509 586107165 58680475 121670858 77019690 97570178 479193692 138507838 723761013 283838433 41141150 703399252 58582319 317107285 175285973 308623434 536995366 41829953 105859551 252928954 474283228 576631138 104516047 704934587 320029965 556421223 739127263 879611970 973657910 596706307 770652634 88268568 886095400 986986211 186610008 56455419 324523495 460110350 255399990 243384118 849052909 416006110 327167096 111653819 930912859 313803110 13056360 300786133 779810042 172004638 159415054 724913025 900447332 650289682 862220393 527935413 847646383 496708207 702590920 335149968 756990468 952340729 47665163 623335883 420229677 705142327 113125750 60051747 20262453 872935036 666645246 661025638 730479968 456114422 997325525 386372615 891948279 796819796 321580019 25847857 257056819 643952762 577634360 940004632 661588892 245401929 949738953 911927410 572521960 343467263 57499514 375891265 799039172 285702493 639861818 442201488 261930682 131422406 528357787 585029790 513739901 351750542 386423014 48806931 484377852 832419393 727206693 459314380 99916494 422963745 973706027 645390450 253552006 323769341 426585079 855234996 644462790 977778802 864120037 572998212 143104169 812448818 210413038 4368246 492054688 733364895 151660740 242895362 355832783 926817915 678264481 251279505 443669505 156173858 948991852 521738920 700921140 984029203 546596653 718188317 717279311 377665658 107963477 224085808 325291385 738541999 368497673 719975050 257858994 608282231 715296966 105600392 657247680 607491277 140921491 953361460 756198485 387165044 126276565 289163868 945578622 465427673 161754667 180119786 726613263 362061552 857595985 546892079 480661260 664749599 838002720 861192680 529647356 134087148 466860473 877913321 715901165 695056109 96396318 556155556 457466211 611090681 162204607 351944962 235351187 150753737 41285010 742657940 496507094 682819684 156545284 742479840 83678420 537108541 967884219 50073418 388666231 869394659 116849791 253721717 642478682 849195192 56782353 26052317 976648363 153730243 620168305 362011976 680243855 764945662 925263643 541712844 691715634 105499772 762754922 828240123 527136207 546465998 16648874 105082522 52606591 909182013 380883035 306849062 860572823 451334410 982238302 396869418 554981904 423353502 167840291 740775304 146148686 313592175 292736370 861943647 653638615 893517353 388282796 561103768 433068294 456322883 358293325 773114032 788049361 528538350 901569241 808337496 844527362 125048970 364001328 700813151 551130068 697717619 869113811 765285330 403977065 432317140 673214115 247914617 751119184 533820909 972610674 775762781 313733680 66563240 793622446 986075042 232383050 820649771 195617469 279091030 224643407 805966329 223249392 610742726 953770112 932881945 750229355 394604268 639543185 194816621 490358320 54207461 383028800 861173425 881217298 829865388 52861885 102248699 265852348 612308224 111176008 246973247 225672498 816333864 233994402 892769892 346037750 99136332 835465966 545335232 321867904 407715209 894348010 680774985 206106552 833393380 629027185 606205717 667027367 50164456 416617682 529139798 72908200 898705258 394535647 857372265 999043509 654433290 274707711 186321185 913452147 14612631 675369877 271499420 683067020 165166118 267289625 189280403 767916502 530368175 809568478 111061211 919966145 520475949 971410645 756535867 176978625 32664053 379147105 526894191 920122807 708301621 878222104 114922079 746384511 185178358 562508481 592808301 771255896 548956504 658988948 608294457 306327540 959478313 653616361 619032902 243143433 700383148 454010144 937918239 348840844 979159306 330071875 138610535 760308298 600447970 366956397 169741027 69298572 800783992 152216300 485182083 588772388 679846839 591975130 437023174 190185260 488544091 628214219 429353071 923494187 604464503 88226156 618525972 228107389 323871290 802731954 717997903 722088598 237788594 465196311 678521787 731022890 789954285 936900129 50995830 714972698 595320429 312153101 901271261 906824015 79624339 779832566 159548644 53621382 12633049 949776496 753050965 170305905 784679678 247492026 77710440 227858306 452525193 111785916 139689209 345961496 1652071 884378893 107073181 651487082 704595492 756478864 80231215 706527080 759386402 353296131 422757965 499110665 152245389 266891374 367987630 644824143 727867469 270306695 142178993 238946804 722282823 287792203 667700057 268399596 782173895 361003174 880043317 66859758 750581177 390200786 915576508 324705127 50021259 294079783 57686564 64372486 951504377 855072448 631331084 278999978 864000422 657943083 895513158 697484671 418311450 309011438 358843631 476098716 198035895 493668429 270717459 60304356 20311020 466033893 144349674 481706494 758926726 109758204 340793046 154028621 337073991 731021554 340115705 913120133 675195306 696562970 803372421 712318964 18367178 914526338 848785534 938746948 734575317 709813171 548200504 700513188 835451415 675912338 902876726 149622541 893547287 579902415 569677150 593891295 7708303 926868066 69140778 54822070 96969625 749514356 151219244 6987039 900415824 790383425 510126500 104186731 719350525 893040659 302434028 251779656 967963932 686884009 137625088 776408109 468192858 190784906 799751159 894484637 639576343 384058836 53174452 567622991 433213667 623132332 623515647 180969356 669446292 845605402 929856797 330742449 389790292 431702661 526277959 828991853 415856758 138285445 825624345 97329997 478318014 122090679 258972954 905076335 831740421 506084310 99533466 802746516 799041687 119738848 773718296 480324367 531958599 302126463 789357592 337273392 402992704 254336658 485844176 410703459 731480029 478651863 899568545 751589110 54194799 858215907 96609548 28695244 579731791 313056566 191335637 158595491 9077996 361231809 178568060 133859789 726437957 194198441 505482691 125025382 323489588 844762065 624219002 787420991 722796777 433085344 531610263 856560501 580559495 944792776 477264847 125247490 985431670 176836322 972034595 500875469 263525867 299100655 148497024 535123373 292960277 952255550 133459319 586346175 834545064 295692577 118000792 79275981 481426799 794910433 859908038 385510323 897883865 269757979 257699121 562200126 433095727 317734617 867530541 794473715 893643290 425554252 877249932 495310771 968563553 426972863 171405850 710110919 265417193 436150995 594400544 459819736 735797954 565757503 508435246 257156159 543008069 629777333 620806284 152755042 463538951 67748867 484365614 63316058 237881551 149997042 558613074 538467312 589179308 936936359 738232015 535981958 443239462 403794247 104061381 640618135 720521935 732172510 306209340 15188425 747607054 903962745 928121913 428795668 463187200 841734819 592271313 50993025 51740599 244674969 940946019 154419285 602214304 762130607 652229776 913820664 445237940 848214163 102369420 346936662 703338686 779762822 982584487 383768915 214072538 76318367 716210415 229258381 25065650 669004946 611018043 234812355 563355143 100794000 971691605 36419032 778447349 433371509 310798544 465366782 895789689 765205433 48012748 677456934 134758933 364807311 576223860 61849910 407240796 69122711 2304889 282114048 350681230 33854723 99573935 51734298 712830010 928561052 372798923 603249510 757180294 269334644 162217320 52437528 193985090 741671238 523519513 891407042 776523750 440550114 568173026 981323487 699382484 10646545 351486025 201148257 781076060 336132079 308956264 212353540 468992696 923753475 856782805 771677902 523865964 876467156 313086922 816493680 401626187 635286375 28568935 82766728 916764941 739639580 495786435 300952803 48148214 600149947 796832034 827382612 398261790 422027132 318588198 126778504 65735780 404295414 308875583 531685030 234269662 410454253 766158964 502757623 997501353 37990890 111689757 646113757 232996680 255098240 8737964 330779893 924130843 95447417 674722066 122457920 876905939 754540721 494675518 350035325 422043585 415777982 63566589 979359130 743160790 665057298 160771382 31316554 167312906 415113871 549679872 931020651 308506229 904965308 548539282 101927647 928347585 259686363 99120736 180921733 911007682 835420541 176319486 349236376 282925575 815370721 740252114 480839217 213932388 531935051 260212683 797627720 826003371 106701902 514708107 242631861 498742716 551535655 995520291 786853556 72949033 21891857 823971865 529781173 265262276 77133081 129074973 482799025 489025168 871180369 508609492 882823355 672273840 294084233 62856016 994874509 824183211 899795995 515539508 685887934 742317858 73777515 360263857 971064366 939022496 272438074 760505979 308631703 189485344 129032345 917950727 97947081 518363152 216743857 82529734 573736855 121886457 787417575 807294885 237759527 358338872 850553010 634337108 492665532 699751960 152264926 116876122 172272836 894765474 979734344 470704994 47440250 780822634 47950251 382668668 100137391 348659866 448602263 769953445 623549244 111340508 591484844 723272605 625686692 714567353 402155813 883451966 646691097 480935878 614362910 109375944 91726883 306078448 560040246 395911351 10371797 946966809 440648112 194840592 597349707 500376095 346368049 849358289 644798403 831773581 475314980 961238599 512745331 674076018 675503377 616132281 48963298 696187450 963849920 990799741 841927240 983026840 539586687 749563661 317922409 384660916 285381738 368731759 831860633 587340165 240626041 433249364 989748234 940904497 266143535 463346105 603872330 332072919 239506195 803076371 220835723 736259209 640174116 512471876 996128180 563463687 570063825 641662305 850860715 360796360 22142245 741087372 144217700 223997297 712560942 968075907 404117439 110004760 265741148 396871225 218881306 852531905 831640332 13180416 438201677 588302585 1314196 307691433 431574515 821636250 469642593 795422615 270990455 204658234 810214877 183347600 153402420 518003920 861295033 844684062 458882251 689676534 136845531 61159261 88408211 654664769 739580658 284252088 309372275 725823445 527228816 63368713 562953829 119943159 589157699 137096144 323615647 526262421 32414374 172076508 45215144 842194566 940218422 948767023 115089305 777843788 699842633 619145414 43919478 871872302 426386014 499802590 211926744 555289679 521032655 962073992 25996083 563149104 107720569 382793119 14809807 578372752 738603434 467284019 913606734 741410693 497949249 889517845 697946470 119132645 301322959 778619569 40248523 667006715 108439920 982170489 101553141 602020758 113639286 575377782 154031893 179637503 551077161 505224630 878829176 910219569 745588728 736062731 66040140 657060421 513510197 275825251 210372045 360772241 174502698 843689181 352595244 984329764 136392877 369379142 252988583 809422355 67662917 532505221 767134011 451663993 793445026 690227970 362983868 109644924 302360896 738515749 963714247 142307244 758752492 52891402 438150418 998797452 282049328 203264800 722764091 754589974 68210441 407332584 635644899 581397720 774165285 105905774 971752748 481586623 760583999 966978367 931260004 705583750 198523769 387910886 410449243 731623904 595307748 529017602 285032770 453287749 938460719 173781432 99026306 224596303 990912131 212337283 77296679 588488266 633664936 820297604 503173687 2017023 119989268 888071272 103364585 592471565 662595720 468717410 587416186 405314489 838059416 702023237 167594099 949875732 767020800 324094654 922384931 522549006 872348634 175812080 263448909 214977144 311440023 304936394 946474122 576170518 889226441 169648678 445001297 564716027 964040136 671408303 196809357 469773739 399824400 879507942 105479665 538015408 738321477 178293560 805163478 170186507 50066613 424983736 199433214 717147817 493228409 687415055 619058789 223732006 793308573 524218814 701941787 55868966 185379841 397584651 701094353 980335247 380537092 967840991 204876465 607145358 342260436 745565610 146290676 513267437 532720432 379584151 6868672 795375057 436098539 794802484 62846509 796002489 609810594 124965387 670284493 910427429 455612643 811428376 276413715 917302959 352693188 112245015 364181712 328435486 760228041 398730134 232723048 124608396 545933123 870319849 850279874 949417647 157334101 51705903 563325247 861764336 694557713 299528670 675847226 763584956 562299541 434704728 988361782 892044389 27778715 586385121 392787678 300170794 760784371 280525632 390423288 25695402 106764616 141141144 200500372 511378701 208881400 562795808 22657137 187064997 898110530 146777704 450593066 417203857 364548671 470427673 277371642 208662253 109916470 576097065 145025010 324592320 958438541 208254750 687126553 614653945 549460472 680153623 187401578 305303632 315495948 655259873 977039467 589371522 451366872 552863455 871731929 777736953 508044902 579672235 652473643 994781768 805450035 621857779 247391509 330567126 701980312 506706346 723461294 311606656 501611341 137329227 645509086 889975182 240784867 445400564 286592601 21112590 891960952 595636243 609873647 663698589 603652967 67217454 562607288 594153748 168725480 370879190 259541998 857256996 286670895 396417083 886512984 602036028 24114266 440258198 448228366 977064171 62574847 117527486 972237366 171001468 322382827 333361385 926381621 941225368 901262079 868959572 303594741 33468451 63210182 442918208 259832172 632464689 252660894 896894771 561664448 439939610 339142623 448605114 358583910 424866794 8880926 90719279 937014959 354632952 149595283 493799051 139615003 33553186 742262989 184088200 22325459 912692841 259776689 831971645 641995780 984881332 351707052 165233480 996151093 370263676 635504399 343736209 173583691 589310103 307088112 765707029 425426873 561801145 605810968 127057527 772803790 770081634 845533191 468030165 567564727 49695790 373530602 381166927 379220165 871022099 726621710 293921864 548744471 620156964 554514623 213791053 494000621 912983359 935896417 613624174 493936314 487787919 112221237 322881229 997606755 942966799 556159622 767619405 981388676 429293714 848142266 9671272 986984918 474642400 374162451 592137678 920889390 649894291 130551352 128488848 241241862 817547737 988253626 87555943 61146383 276555370 473986644 222906351 769497105 525198070 921334171 713575346 929178092 599604641 242083140 326408020 347854766 558374915 162739941 433410238 892415866 4239103 702907685 610975798 440101757 757865924 367432516 355268365 544595047 292846653 73428035 802414290 183192881 787140245 468073946 813260454 989269037 913876048 937970035 811787125 788599140 296394699 131979706 354223998 912735858 234211896 932566098 811099926 79166797 894429532 732421004 123782296 191160381 913693634 536242895 991807861 312226726 101772070 330179475 432323725 385703899 496617689 323026633 598898339 799660311 138836591 865879477 361522040 16046716 780248155 87306639 561484627 46513206 524984302 615576763 192023186 457278153 945956360 419009176 560229090 831816076 711168902 197732652 227197464 582081266 196737267 576638164 245588630 684311193 967483948 102241066 768580484 393994945 946342450 236136441 5532895 81439034 379642510 812849538 108145518 363652423 750781504 681474838 189351192 840946228 855020353 671319313 787315607 489147782 402689830 187466310 155291678 17181325 909284959 208226848 393612040 374719928 142798473 923673758 110036443 599020047 400249618 56882187 531719447 824018850 767833459 767673162 978849240 608154255 579080901 597298852 617943594 987045445 545231716 31308836 535433850 632714185 91236476 326127557 404972182 641961769 361918167 660387782 236158046 221355417 553413494 985325886 29736925 952157816 499322728 931904023 460001904 904373975 715438742 221011764 158987297 548257617 625611755 617807267 337739593 516951465 955489163 579380057 511363527 377586867 587710668 36139148 242898651 593525500 900619069 525468878 540463928 452723200 312197180 983600671 733154404 527317901 582842444 662698982 901069207 663218232 769377717 114730468 59737920 494038782 296126730 846160265 521839124 295329330 102113678 745179967 715348780 317742298 583140723 503074511 349057017 708879258 471720564 461695067 711433395 31078006 261349377 885960891 563670905 407799092 536842616 414640047 529014739 850281855 382918118 595991045 676176778 183621023 113590338 332644848 690645798 789125603 617855075 972233527 803645585 307648670 766277110 119941847 667007860 144064992 719723276 311848416 175745693 697759728 711307699 65145608 650421195 902482682 44940681 333558597 134431653 133542832 283018962 881745353 380103232 651203889 728714413 506968891 605054144 558942271 914765705 677036530 261739063 732095214 108161957 146736801 167919402 764390270 312327901 496185278 360732823 265471832 185460445 390233336 344886911 729876800 747273377 632997442 314833666 787126372 336564593 532992055 305105442 452638031 538050665 199943879 516775486 960687776 357576255 250587118 21725999 178832542 65430486 563460127 640467903 286423279 384915556 728574039 739943897 21535430 324660195 551928012 766353344 60398628 277348363 789914569 935116767 111096070 55283651 149759716 988149640 544756823 305940076 647088756 81648038 768652489 436991050 726287397 481287688 853183257 482923970 591471034 860091001 603858185 511412588 934907984 904294492 471197490 512771972 630256847 140642225 48195980 830940144 446866997 716232314 679236306 28971811 365379158 573958465 503238951 914339280 604110782 474864889 358689766 231486948 397941657 349367661 531219860 57604725 458878176 656412733 489511618 751316764 112054626 447697279 367236048 944924778 423047824 65720817 243064818 103202617 721155219 858362799 880690018 144966104 502296694 826039252 844479912 207362057 263444617 984058605 761009192 305242476 979985947 354446583 389569541 979052054 457413746 239719778 650372798 385165765 321312269 349598095 787540076 620859003 697760423 241884335 86477746 516701939 775339371 40170880 536939698 280323389 548828987 251215038 88578307 951007679 593851622 51645788 843164174 488413882 620263722 561379154 282660818 855959505 747442995 909052111 859506241 234988027 3825062 225714554 1212961 678274095 106918844 878348468 267378221 629845695 499535315 701347605 141941278 402924533 335645340 601345413 878732445 960937274 775317926 915291242 207200781 751635966 972183642 928682033 957524718 83551311 419589056 470515637 512435410 567919461 816136339 179433433 7075354 596993031 38784904 334251160 292430951 45642664 228997506 993364261 975281604 928212290 942551756 308556537 665677563 541528989 579730796 435172666 675688019 996752495 878609887 855687770 14733419 704147930 918684428 852769230 985136787 666904629 748955297 60267061 238176857 191901425 856517011 979579827 427147526 91864805 105353198 12613967 169850944 368927386 312141306 461449995 308920703 311366308 751505156 421133435 790596046 507271192 556980286 653076658 824382084 94283467 539351365 127896056 731219608 956376985 941360786 350225954 97500432 379085381 546598637 533609527 115831404 103602072 677680779 427501133 890470951 419711160 310193475 270863286 19080969 314973902 481128045 877321455 7613416 211659907 525803377 461423664 554777927 126356962 35719307 395217273 979004814 922199050 310545655 262778962 895702353 976544029 664436784 81071925 204301645 864923774 44090867 61279185 364178136 19878109 703481128 923681191 430894529 268624683 342493506 188017877 180363674 46324559 905250636 565216471 760342163 654254361 683871106 812051973 127709192 174780593 269175062 292749524 227789187 38226336 392403318 485535122 192761394 706512052 690376114 96503317 213381551 276913024 667948840 480619049 380520924 188574224 637209071 640347553 67795362 780205342 286503612 689492874 85549720 248577805 907668448 526158195 712100104 770449945 670298380 537458263 97268047 415317585 404984931 890611129 52208040 181245321 800887661 641583595 123646434 524878935 537192208 732943168 381492550 190613041 762354790 130908824 6933888 933921338 951793075 61160114 218114382 752933044 10888565 611082974 681952720 110286998 801283915 787761625 539805158 377976836 828044072 867004372 921328748 727908333 248721355 524427255 260137754 91349855 828195501 164338457 660546949 871342613 418848778 228135120 281105328 826403589 146413329 916337918 167881058 868815911 240450566 500093967 645098729 36567450 451685475 133332907 718935735 896294876 910564385 472857348 858844163 264745098 921782779 81205275 87749232 857440262 493296852 947317037 754970 584371640 902775904 814575161 709352003 199544097 260246397 272042947 958873250 421631534 515683455 170655415 997356291 626982506 555140783 758842023 368791675 597430972 662168590 144671631 317642298 453769555 495495253 886022530 314673488 830389589 221347560 715762870 393520788 828427197 849895789 907833829 893240218 29443161 633753470 216853807 533583607 269584495 81285387 885481948 730016345 974742243 814296069 561283786 285968536 237015683 67982637 164824146 620884988 923465850 750965310 862558439 231290127 25510942 884550263 847564751 330777482 463444785 867354450 986120704 48605511 818525017 135855425 72792687 120500306 800899588 897219035 752180881 205151759 72414139 738965464 793120481 921710856 318148998 538460365 752507594 639278183 52598636 113327008 324847052 192993924 624184076 346846804 255739668 40360769 519728564 967511106 449135 203983084 950404932 741237025 239988317 521321362 103227370 678220761 988819790 890362675 496192047 469814593 14816241 619534403 498602533 452189888 574844861 47525191 249391335 516886238 884417577 82094317 871278645 571065847 961799799 291802471 247591942 967913341 85789543 759052217 632783889 604333826 755629438 797493485 199529776 243990227 19668942 321699153 873973407 328754225 696674791 153279112 910965729 830741273 974727241 361918726 716647261 824983718 914109577 137795931 932304734 814599103 369628619 240695366 673337311 155750926 657784715 309712660 707751282 323204707 105758235 428983232 763459149 771914791 246881942 533296171 764613926 49014779 39822071 557032235 108906100 744238359 89846061 818034833 49359341 507049965 663487819 96744341 483389759 157157646 910676507 910967556 916157973 762445865 601936189 789509496 667392674 435423851 856676031 378858894 499988408 683995648 500863336 999715223 354837725 414316966 763031680 923040926 723617752 51080629 320672774 772353150 909444450 367002876 745846399 680164301 719565881 536752141 708225102 659271824 428358861 899878963 306819775 150034030 432433657 178710060 206140055 910078995 131393678 666207873 300618906 749726464 544414297 489605480 901310032 103994055 781045820 861440121 410762188 275263689 693517111 514831901 786155753 909319968 738600899 384195787 700023628 980878422 725049502 728202539 803997012 458369411 381190964 607196402 11716227 432224529 785702890 915406579 688091355 23292910 961802459 132542065 82039732 363258232 88818210 487927302 510503800 801333048 995893776 697176389 837525035 873226414 192352657 650418799 888277344 374945585 314191476 282232387 625596106 929012896 333159606 112233206 917763452 282033446 825440106 676987076 272649448 466557127 176193723 94708968 46417044 307247745 489475141 602669253 685915231 367682669 742847735 50138463 468227125 503556807 162187935 669317041 364695128 892286177 643422383 654949958 351746635 757691398 992742237 88528797 883944373 999821648 685922480 923290007 769536609 506552272 103580098 632729251 880440917 178532911 446357795 252271563 991296808 333289464 782706767 261092394 748037296 53248732 190565454 282037715 803513263 284514345 979235218 787920212 57292136 818957716 456719543 484123137 566238116 385192032 449107018 851115907 681798877 410028227 746487212 70212824 696019426 876178984 539610100 921470482 174088758 895404657 716947535 916955719 49703628 209107543 275216299 36473187 227749645 379584881 564036004 973488319 604875728 329405036 992835717 543337498 204473449 122401294 154991500 416347637 309986486 676896977 379065843 870367035 140635900 294775508 143472430 829119643 680583490 632145552 339293312 263993781 218143209 145084404 99862610 48124278 253995011 682531305 423345650 651610458 878172945 215181388 10744146 796179644 152116831 64072203 721302023 416454389 532199332 245122617 817326198 609146344 338874683 994891743 738895775 965677287 289261601 956363101 394449621 967975983 633208053 796421211 69087117 600743968 828370680 778609995 236105240 426708500 805723792 644801483 946784744 590364422 851024924 244347274 151019413 529537160 104373101 409003714 417222910 688149800 332862381 859618279 618264948 320481761 928232393 236375369 641910140 520998059 945509172 887126302 512072033 860538737 732180773 442336656 664360465 7720964 812746039 158694570 734299645 249441860 854959911 859512255 550476087 61371275 848067023 384664732 251821242 959784562 52499423 664153033 387799531 792195278 992434920 267732109 171797793 999989624 943290280 532121598 993445826 769356634 164499785 114334159 868482918 699180521 464367750 746546345 929215223 292361001 123950232 801502740 143454380 790232971 318866719 580943267 331150491 168218327 983321675 401824425 914690420 926865158 33621818 512782529 523740442 208653820 267612513 385045354 734486862 894694062 245562252 161665588 262141108 721147842 886033674 2428768 687921581 921651570 558015128 680105685 584314227 186673798 215993826 81064904 304028761 329588080 303504035 307932980 137500835 497873696 296304054 765169983 496221111 466017534 312773127 770448259 562502358 898028250 786880960 621679215 598594049 257062239 396596969 563565593 385891009 99964339 516843890 400364343 267836746 958404017 763749641 130461306 516080481 900187075 725841504 199964788 845037650 736374873 916513588 852256241 350811026 411735851 154475532 924065905 622365040 746057935 587989050 622206260 649181910 991950338 885460174 902299200 392228382 790454245 94859706 169245345 714988034 191780087 633666892 323597046 584891969 626145815 392446004 519398269 587973679 317253724 311683703 617950979 48872390 173690752 403852544 47787510 179671261 576791546 260620760 796045428 18447710 14127419 877859809 946782768 323646476 863457313 328867279 700232035 583804777 413993500 292528957 739735752 308879354 51345715 555836049 878658102 106615594 416996291 477938142 230359571 147162894 618924521 747033152 321230386 825113731 15484279 560224441 87161140 603954649 328975335 587063172 555853137 979916067 631155671 24658469 669525789 354636162 252552746 725264884 771425326 589555871 504225218 625522887 619176347 969556869 487284098 924121489 770988864 510962433 819599042 159530958 459002311 598245831 393341149 824082195 865307812 85073874 288108232 629949553 276809616 498847135 409599015 300002536 147232052 788259060 448052394 993935500 492334615 311641296 518914093 650419716 726673723 97626266 243952966 300251807 265905150 228173408 805039152 941900581 450921086 599736393 382315133 754481005 824733864 948631453 274227039 900980196 480426872 337976881 520167774 747348046 669335792 94264664 152531309 370393614 985849321 592971120 332443417 631190617 240003013 357263252 734532810 76912872 209731391 169130737 60194435 128601442 234014990 173285995 391536546 187604378 101436812 849464269 824416991 752287999 121774513 965582340 386460359 717737666 637206391 881466522 486398031 987412062 491675646 721426037 94776863 950635272 187449069 15493541 683958250 110141992 194707568 98518377 818115222 508025494 307436345 386881485 546915140 409188070 574577975 422939844 120913684 205731019 447879707 347593722 648718661 685622862 236106438 420277353 736814418 670072210 271694082 15167000 239098805 318270826 28974543 253807254 893539294 205306217 147914558 860374360 714379864 943447072 314161155 615847998 269521577 178132295 562861905 820909804 76191544 964492925 746321546 353393469 754556588 227898068 829761273 415098479 912128197 642360037 491569959 528569635 644629423 653425750 874843639 779357697 336308683 779564799 900248517 67904617 277197142 517173205 946112700 457241978 778015103 726891572 324926449 803796875 495595821 730429519 569796249 978911120 234048160 883415954 321626111 478360762 154709374 456533768 8021236 173291647 704431833 491595689 919614520 33282253 219187530 430328583 54701342 197346832 593780402 665735355 757216698 127746356 232136894 121778370 932939435 851496791 869355337 783351886 706396587 554548588 884422510 872930576 314302068 764522337 796328062 296454120 381429743 340089857 474711766 291773383 613263794 330694180 201932711 142325756 641415582 601739585 310997189 707351889 315148838 584664276 212459280 523997872 425624628 391673058 674198226 855340022 584402100 664384581 762022798 250332729 156149826 340552908 183211838 253273012 655930100 283502408 585713702 306825415 439107445 895934513 660335117 16385310 507236596 39417799 827669579 895781606 955056470 390258939 105778157 42835777 635349608 399905122 10806641 57726643 183630181 512913895 918787301 876205958 715914198 194538506 636392082 999454696 844388804 662698490 884505439 898328133 888256241 723438120 306546527 266682114 371118637 269294181 396170066 520900087 639440417 142249666 615839197 549905532 808133350 899984256 709732076 348469290 598134806 564663404 992497587 509664296 715910791 344372780 253233954 247378725 271608544 693030693 431974258 715774364 115863119 469647575 279389200 61535399 375874289 482700114 98609856 939558352 387548062 805779059 53617015 61101173 719793643 267772118 619584702 83128944 307235124 276028810 767469729 973921665 185156021 60718072 352847727 835751093 933130721 300417630 522300747 281760016 81191620 624006503 396379089 406253587 122588043 524838554 677452546 505899043 262032750 966411150 819831557 824522427 343048543 743213904 408616094 866856067 259764347 703006959 742244697 704376290 185141184 778844234 971665087 804853267 73397757 130121028 279507293 24080917 607512650 362861318 215834406 606122343 639261321 405851454 407164188 866717960 236418444 957813407 88797440 136555090 662401632 328849704 761594253 432768326 493186707 283514803 640240614 70912549 746152755 28985205 869703847 745649683 396135343 123378883 29699876 209164747 842600140 670003023 756055249 97228747 835643683 510387119 393608131 902304344 112097571 532520283 615028456 416370856 515427577 925632770 40746844 548613529 893862573 782340389 103638228 945266558 295759625 537425351 441193371 819361499 822436308 111077604 93455809 513606385 795459397 85318331 372169323 880552002 300274633 450053457 267045989 812006847 868563421 812588680 186016224 232290420 268768470 718713333 249981916 533875440 500225866 975485658 195306984 78666818 917786193 480311533 557675852 819043578 666666714 126782973 996141414 588970856 917806204 932975014 603523880 753167832 985653156 594648283 281080004 34744647 62581118 769858193 993126237 510918747 164329319 656921503 32433549 809575220 606007067 894441496 658256431 801092017 780391190 818172744 877631337 399306878 441521429 479530235 710669046 860045813 56442816 687587446 200285035 299504006 660020652 286090054 976180890 312035161 46109152 974429831 959657939 888633183 698827408 907192810 359988118 216991577 208830027 676069797 711116544 727819278 176761028 688693975 926667162 501069898 125009775 528430163 225675839 635131780 352247348 403594570 458481391 128693174 126327439 805838939 50046204 795753606 225446169 752781563 192060310 761793726 850598979 587022899 722475038 377933864 426854691 354437037 708046938 475719941 368605596 232597311 310168519 776200379 108325605 717009165 390849500 796930024 880312968 324528662 203983648 231941879 703017458 467826105 26866134 910329237 473313348 572789465 222594053 460613132 279705593 356427452 52220019 95394650 501697038 926188068 358491428 421198788 894623436 268804709 381312872 352736416 959319233 376218682 245525724 213413846 946225430 711478330 317172947 196265491 665783539 593098193 620013773 307596429 445180593 164881740 837081972 702953114 905991279 407076796 610489269 626569068 564141112 198894971 98102658 814180172 82868976 454685522 451983899 624365722 547143221 814530837 605212569 209283031 239299680 788855177 646164518 63996721 797186153 957045966 392674486 328849345 94019910 241529896 549622532 915632793 605139441 250674611 791488745 215421594 175153659 586863704 493166173 831873041 69932937 792204231 472737665 739739069 682946552 78992229 835369062 396136484 788258355 517290682 914981296 884908636 561234670 285065060 789768514 315438518 418974103 887548648 220506247 387890913 620700157 130098979 572247719 743753920 693898840 792293417 708493615 579329206 757732379 818002488 690386813 246043514 864487684 357955819 986722825 149106263 609699517 622455778 945949191 264690754 987559561 591713946 979809731 248733553 238520226 13992313 859218835 893241279 102880881 364994989 180058265 504637378 761453106 221467503 40786667 609159778 57473003 813767786 290621032 151993525 620273125 429271739 785849502 812152396 679346532 313313504 158327674 317950712 760599455 627559584 218186062 659811365 623653944 491714386 106846585 5952492 693501356 423460254 167817224 825875085 823020718 439920254 512792114 310064364 451035344 742338007 377197640 17677182 609237369 672206850 851032053 502505522 681651924 361147866 122119113 185416541 315606347 316534190 743542972 333740470 302475284 326343295 148601052 18877546 551189917 383137109 115413569 281152596 725546841 643811212 644212191 606067789 747415407 429252951 271142617 214071233 697140412 267741494 903825338 186689181 568896451 4381629 809269882 325142599 343972323 747180247 626008603 852941144 821546745 640652180 802059002 442318913 479626169 175819087 169424341 233885579 799934769 696537098 664839739 661127062 567220691 187706374 180872403 822420452 221576837 130340384 402391261 972348307 551101626 410506736 129237700 682153581 23356972 300185606 297876928 275402301 102740390 441952293 835058151 93592776 73509797 355741861 422915783 362288201 118232342 263016433 896446321 35804327 443912740 354708560 478659679 672752017 641001647 398685383 114860672 89553524 576599912 764614394 217674580 361178872 366365017 860048912 237114664 614940221 414306983 971757580 484928662 135555313 506276854 6232623 530997990 527613223 14843955 224043148 276641803 651597221 159466784 926167323 374360207 910098785 630733923 801296030 763828644 494867131 757194577 401974930 832062843 883171049 92318333 589495737 270545669 244723631 555558647 884782860 394109516 54082479 159064832 818646488 5772012 554348059 446398766 822077339 934433010 528440909 825578304 143287562 800324962 907369204 461326419 712280226 952695027 608430984 892350190 722385301 450301604 198613111 518089274 834578836 27483188 190974450 594845232 795955279 170102612 508053777 666207459 273267158 460348984 794024600 335053371 496489471 365784894 43688499 809237865 946560524 20077712 20150267 677296817 725397653 22787422 327494022 98572838 774456180 65273018 46865719 869796080 31660479 612297824 945981521 74403265 720949143 556185260 975772657 364571233 577097906 417942995 700769667 190479523 36157379 214586924 414915788 804956874 565405410 257673774 887180991 100030176 977192261 132771291 287324271 931600148 983755636 931595256 555020935 541696479 86995336 863792598 220686341 977012678 50473395 279476993 38098559 353322377 86329722 682985980 372659836 270891133 316515746 583997018 460534679 210087484 305883706 829500763 791264465 182017154 779168414 635264504 509723054 972141041 605270955 295450804 40063413 720571904 366624935 984210749 184498406 632233479 234582861 982942455 681329720 230196748 375896406 279131241 754297967 974538355 605452738 103374424 48830384 24658226 629166394 720349587 468224856 47071316 419689580 503054062 751322948 706914906 66470557 206565633 453075481 550521723 363602285 2105538 167344954 148932470 96916605 133155361 76118697 127092618 619848633 730074763 277505519 585198556 325057772 989834146 242134980 337929039 423455900 44108352 762672276 446976498 56374992 314027708 818496781 535839796 456371991 574853519 549877712 46629808 590148458 443988491 154459618 140982597 591544359 405425946 735553111 7418876 202349362 201302090 402962680 359408384 460445160 116063872 576541968 986053795 808806537 450143391 191500287 227623959 887522326 2360422 358925846 934339578 530212555 480185294 159745376 641226714 206459388 753272693 148313655 131848145 532253377 685776402 591488965 217518829 685607197 483521131 423927703 664467055 88427148 958367730 983203275 505254055 548459806 48509829 269072553 228816155 895568507 772046347 899261306 642680694 608102666 158259977 966958565 224724269 783034548 1936536 416038942 17060146 476919013 824973563 26017158 961955129 471964575 455050470 634553649 892038637 192188411 337956745 710333355 214662755 643399278 26875106 901185663 57746248 564230734 740024087 911546880 214491167 305072887 740767846 216428399 510561513 444359531 592467873 943647504 719594165 734199942 646028032 959842634 544219545 202336212 868841858 590665708 974493711 648731906 486314012 30071134 152334456 350081472 418466011 835101655 755771747 192148188 840976847 333871306 545951620 455710681 536072246 869401230 428876969 138838602 594161540 671867865 558513404 518765256 463624036 472350748 297602391 701580516 599546675 140138856 537045584 831388538 752092326 263971487 931715356 998542550 46385305 266964841 875990876 83467697 489635993 774806231 239149669 914665813 830269197 465927654 294174941 484021850 986379660 830179630 245613868 34575002 637105255 33097921 386830454 654950679 979898848 514656529 44666965 220639374 954108746 794459464 252892618 813481666 227910561 280797470 469914796 556943528 977983029 794996278 212148523 436271033 438713664 148279758 601653787 617595100 361290237 807426411 663965784 359388856 600072136 110611012 733290018 549425857 282854861 996678303 949198639 227585955 48106506 413022348 297765161 609025704 570967216 885235969 837850204 371795556 898072689 810297745 541921021 743758769 659811306 953520707 139709089 631248504 444676620 954852076 823344183 787272137 69533884 126300113 565683832 24849578 505005768 537407683 485539619 99544486 435289232 908389123 485096756 19776953 554110161 334334438 97361986 44429170 371669444 610017533 940666963 292693399 956916131 144721778 932482083 869662170 824609113 578919038 785546514 401940760 119207876 759824362 208658448 807226432 12561440 199295163 157551330 95387768 146966607 143619640 898612774 318139439 943357806 819474731 587335838 706869046 155932621 611906206 403305924 147407637 286129874 73118997 711709910 443081747 249473000 833753372 716966903 224967422 948459254 531135665 767242681 617265733 323126916 466200438 484306648 64687213 552985332 930649221 474425221 568505591 248334848 865202713 419655461 731365154 44747153 528921358 657581633 187663553 803746926 175056019 218673684 576575502 223518099 724101997 673745670 333166499 574436611 285584629 721019450 249781386 958691447 855096389 392535280 548513488 390659888 330024332 203912720 924697959 99295751 761197636 731153297 939040645 936759484 892819674 115793459 921284359 639910102 901999215 264549253 631310367 226379964 102643299 719756816 274603221 945741126 901021131 257515134 267087755 105270348 246769312 607719512 560352501 679245039 952770494 16863215 581168957 989849562 263868819 487152829 777319220 889627041 602503975 125509733 84330674 680150195 756881789 310123798 913826160 932240798 509420929 534542933 650056148 594632041 710113389 295337468 286339992 162662030 204224017 966921124 296031223 307325839 561816252 345622568 140603747 557657890 185001776 987506071 476174793 782963030 85271432 41063273 436680673 720959203 326270397 267293322 650933563 535189423 135505309 553804639 968225275 71954799 406914138 943803191 99609500 497155283 743872109 466272842 6168532 854495353 136573794 4083940 88730319 371631820 418491577 238693822 570087961 865021636 324357715 619859732 320221740 970754421 696623710 607595566 635328290 880175036 735875725 256516976 907112406 903462295 525508834 531872930 39846373 858028176 783295280 700262641 371969001 326382541 443298188 431092891 657967774 575311957 205086188 757886267 622449137 912609431 783265151 737028073 958685676 324374907 616608939 73751690 588543480 885180965 76149518 906090917 726997437 347567371 635340217 34407410 579346550 204632272 292052253 472888833 674522614 486932306 176937681 37637551 88933623 696652643 397584083 421089471 229216470 729808505 896866873 321303470 860273611 4414186 441496529 658898089 929850351 448058147 253127489 598794485 94023067 537276271 849854222 594466103 263498516 505476997 115552623 715261643 400429247 305507944 259050556 477512100 605976546 152656801 506591230 374070776 264981139 772092536 692376837 586826189 859171953 760820886 919674021 184070721 338375556 339534960 278290143 236510520 491704428 260532634 448022489 235166783 427284669 696336491 373076094 15801795 481009360 772358816 971371531 136210987 344567738 7408380 292745029 676154557 25489094 624495788 480938036 171228765 795409482 470167707 512172392 995863852 852627863 478688594 540109353 106724368 797743885 387895033 797322345 645825461 671125520 58869459 647904902 624280293 863091869 169869444 987260401 626827292 245849609 17787462 78244109 799563370 62160562 479395514 255512114 226025007 605209396 301565545 121824102 659279742 934610534 867750050 925986150 370028879 744169678 306849284 739770420 802425926 901512444 470216581 443794058 756870108 70721040 215922640 627634682 535037438 949068961 917646990 225444557 874504209 771955576 220262143 834301562 244098968 678213640 577961404 173480743 949581776 318242883 1559900 106758367 142663605 360591248 929203931 627709262 967672314 155201435 15740478 499059169 844336157 762613694 462905003 446018051 932471307 685111495 614342797 172962077 832179321 834736838 224445457 326437295 780285775 214324496 60965692 41112495 324343948 512925444 205423703 727585095 450327937 292864656 99895312 920497815 810647838 569456550 198137947 966502364 844601303 591697138 757451725 136750359 146289547 503504216 732918872 74019800 198766139 162836550 665095215 83265984 946223367 784468187 717079205 288664407 881220085 176217191 693607155 963757228 156743211 458775536 957858719 599775087 809358295 743014475 582097937 204843918 543958695 702664731 46503691 649159356 386735233 733006701 13727565 421162396 627160191 950071336 398346286 217253800 313186282 935798292 898122176 436587648 136204825 535857997 695228372 578418784 965600804 466055173 491774547 650179170 318131916 588467494 315981932 456562773 354420064 547488472 956943977 763593569 910796196 521401244 820635657 927498164 535764396 560999913 35294346 899119414 778463563 271909584 880883705 161574163 968515307 630030350 773592501 234074589 950705271 667735573 126619190 260038520 472307028 803286346 136740340 823851474 656381455 406872252 474373165 47342741 711891926 196327081 410100717 130359548 308897257 234089503 716044197 485746708 769569736 896157404 406829152 495086039 689375379 387953766 381509278 360663377 392676313 702528384 875025985 286317832 395903770 57260307 593200042 182715747 433982497 814802677 822725883 529683814 31777259 590324647 913035944 276933192 552872070 183837960 276781697 29627063 782146760 109304355 960329798 536348437 418194540 369603573 794359754 571787074 802658574 9705594 878534430 514281914 484893519 62571636 424582586 239761373 630641717 936946287 226121224 616681609 19886738 423344731 158348386 881862180 65365360 984826404 946033447 636114340 117320888 127079310 600856154 549003761 411986010 14137216 158175727 283388676 983171865 89435649 108219315 628350392 253879251 341406166 171609918 157955482 602989649 122259301 729551055 734004180 470966827 100799079 405263019 230300883 855333732 650997019 820716055 13344629 169394706 96708713 544588113 725627062 985240767 531265402 537894460 409933428 587997627 931064766 212838622 604068424 320378476 517213379 31406000 159152564 270914482 876920694 883124792 163944934 68185375 332913598 782290579 251834596 400402270 460314785 612296160 795116971 108585607 9428518 198586494 313045065 942464437 149969988 311382472 96383393 384255884 499344658 69647196 721785936 209490431 886779887 334476315 266215505 682946301 137761136 712053867 480573310 380695738 44532690 738659560 888822101 694262961 200835218 535294089 144257304 251858529 838062836 318990733 994925896 967778754 220627077 431826725 143165949 135385627 505197861 744282159 518643080 86362617 417824830 219301593 613259204 791508455 14339507 698090013 893453180 192605635 852136334 348025506 604558357 182941660 62679681 587015306 112711851 989164765 150857946 393869286 495381951 196310381 517427933 243369712 15662331 542626498 597223560 297013500 199452933 776681679 114212898 898377185 142134835 998612490 841177862 906754921 277682319 903853269 88184433 109639063 557931717 194966634 654317190 514955633 506804970 634601562 828389293 1157118 50442516 610489761 776782888 815134647 190653666 949545601 11044822 935177956 335815128 634372708 470238453 281878303 512818708 941628420 305451682 154883763 163701034 108602974 783813039 697498766 654493387 475509392 24909666 908474608 292041648 196976759 557400261 869743900 522063111 899637415 873748607 892475846 135384624 672771428 765194963 827670413 224070305 173676615 683718341 211999339 710933325 378152717 411640364 286122127 302211015 310217874 664994463 961487907 902515234 731053815 911813133 629018190 191886867 606986057 110255806 616565546 660681091 500551393 443573285 3225822 906171107 450683090 646764919 781558991 328229474 729544131 140090401 556644722 972613415 344117428 245174259 478726015 498547583 423465458 93748724 495876127 576249705 467672993 351966495 641397526 160835836 301568112 188231162 921492069 754032621 813835242 688645358 967717635 823428795 310372491 387928734 725923797 739750897 125059568 17630961 488543839 729621646 154161720 59601923 422101428 843991188 640726465 847825344 949867492 626691668 356442348 413669256 433740782 998453477 681522049 511600327 805616827 359163089 939599688 556525985 117180238 668466501 424568853 234480111 666313932 934468681 710854499 960705120 666805330 831561518 126684128 707048927 978208962 514547019 760789192 333444999 971370433 121341538 637845965 630888235 567956447 136714174 565613531 239918074 370110545 18470161 787729099 600620819 426905092 296516321 647447312 942983988 466282524 302947364 746191463 11704355 364524005 986620293 20768069 269421162 504643369 712538249 86517338 690969229 456488030 864241427 975117650 924427525 913772704 661421196 389151123 452523775 323283869 600966015 218985682 161955845 5446674 59807347 654694007 805662145 599552797 50692968 26817551 491581451 994728697 487768258 165112548 103922734 939683134 682966746 571987634 634770375 526778650 846371160 621414479 980306017 334237137 242234998 968430006 498407814 192378962 272413903 375031703 616782993 141725728 721731563 297229405 821500155 837141213 963994387 160483889 779206633 912514945 880707144 852858226 36453576 949005002 863161286 279478622 945786922 34555993 473766124 411565520 111854791 432067714 190744243 606402830 371382275 610405047 332793015 749561038 636930767 342434906 440561517 266206610 765315803 49587136 615274273 541266749 687196006 309021081 786381226 766614864 412256616 756169266 82477296 506362864 675510658 277689748 698790080 959132354 387622720 835379030 234832979 265515605 515157743 977149993 856980866 421139756 755640785 287033124 479856822 495247732 27335831 841592113 701260489 727084355 681484930 481048452 698340452 481671285 518477723 152310297 735591165 428793248 998489008 221368198 106646500 111078428 687132372 630209780 224217957 542109782 490714390 156940077 686877157 660323663 857852431 486036437 967398595 457916608 788199860 43788828 631452117 212359611 711160876 324060530 561186053 634792766 240118635 387258590 416895645 478036914 703829428 165971158 569275844 8015236 693239736 913035143 446901706 266552287 146491764 742503139 534457987 71852798 225170910 946278683 350778446 848229841 256418196 961570394 991525823 969617375 283287314 594256187 1512368 142507423 82748883 274346822 464015176 482003398 540820941 68709761 264011439 242065234 558624877 641875578 836278217 128019026 904524506 331545306 162874666 683372765 874084486 135308055 630420563 174487656 618262328 420548137 857115464 721979535 360822963 121949457 110402122 75567930 681771973 707238386 334713927 588460659 595819890 440528793 282461364 98907279 959265491 202557093 104893120 747547171 447975404 980239626 558364762 544841213 118872316 482853228 997000403 475356671 732633370 561090549 609594657 223894826 792198254 858212435 601070370 273115350 274930471 225627581 446579602 322017002 340180222 903627882 6591370 133633826 396861443 354908667 725364571 717591079 381801860 437537174 580670915 103441199 259660552 957811996 437562723 283052603 716813838 34740885 76430481 687246496 985379662 53886645 909707944 823295403 785887305 140646663 376528692 516403135 391412436 572190178 345871542 944692385 224780365 871163136 90481250 766907841 840337751 453867980 714656681 21543262 245154671 721240137 79334753 315221538 147751154 730718063 902164118 783146750 593960440 120076039 283237888 199260358 371154130 918195399 919952599 592604690 892885213 751161033 687465847 119497987 697372510 396716116 918284730 404802228 3465376 189344085 270495827 838515740 346762910 426221307 104520120 185293617 638953217 645768356 228400284 183578902 981409508 984111045 843303351 301954692