2078 800988979 606582961 180526577 639903265 862794602 924775596 245816370 980806687 285534580 931780787 426244108 749523413 687793888 112169706 292754137 599948233 840183768 379202579 41831898 75073129 42783816 319878299 775683581 881480744 989031952 620915383 276756502 497453756 126596929 403276905 440533908 886415960 288701777 508920437 943283490 720787432 752120669 250892319 130550734 6114706 5328935 340372630 957052996 51061653 45487670 454271547 50027369 576732670 493151704 786172477 725816881 635755049 818755415 901927284 465841044 522602500 159521787 738954481 586702847 79313770 298952063 544167374 45876251 273506522 262469257 726799681 605826272 57892691 85224715 851086794 43198695 601452572 795915551 946274439 225008407 707097981 347460640 58364013 71389188 861095537 967641495 858484326 931633194 287220642 694635143 893336781 725150077 993647210 690415210 426804609 723894527 230643765 305735450 897674571 463968098 953951860 911476870 517631282 534090258 866593778 367664414 644186243 265060239 969884269 867711874 574337350 411970905 175203496 726866481 80755361 457540151 67751108 71063093 319100931 991175642 476351328 887552155 353137128 592335494 906153663 155738353 775845242 331593163 904244121 354555448 684806643 80723735 959687203 29993070 652084335 725861886 570556951 880014532 224744598 480257374 448582888 19342424 618448458 864027828 328226699 807869119 533587519 822131654 60652932 807476528 136601876 895318499 960746996 216075127 471368435 862052745 665477237 854861687 47099727 702984474 102777018 145254042 332953319 710745650 592315911 753288460 799962320 861212801 980200754 527957399 74214769 727029879 418533241 784889962 40234200 651860236 647501820 284896136 128003032 766709426 219867154 129698086 973991618 604136227 307063694 873081217 335040008 74433907 772452636 397574937 824406834 75824777 393941723 713218316 365695274 418294844 682017150 108947503 980710547 649298347 694820769 847918178 300164041 486812469 535861331 801352670 796735657 801815220 781488651 568209556 139264415 822257667 414480584 199065878 659307358 299986610 415242776 700121159 536876931 514404097 133107580 457878444 254078953 463815582 810822603 244004406 449816322 353801737 202293547 535203677 786722623 678719638 790035038 277719910 571065710 795390472 137965542 959069287 232422648 391432142 658975241 271242647 429391985 764258016 834167625 912425918 681435748 235248722 374486570 255064218 638941764 958225893 438568246 818765006 323835802 993753852 801291109 937313626 21820852 406576429 768659306 76302787 121260731 914385406 154199800 644390806 429319238 238331353 224728732 880562968 250981188 526987616 701237856 779981015 520918095 642128371 872646017 485436374 535168683 185322926 314037484 382453176 256418046 112668426 900637608 127860825 842422294 148548041 357008389 446589111 576672999 612700914 211492025 981431023 608914609 873351269 244706173 494377534 340021674 625492333 936907413 596422025 831720868 563122751 23089461 628400201 185374119 209590926 576066123 992136017 456918959 549554815 163278251 163600549 183406749 637994784 823080704 636000818 339647008 237803176 58574917 221640499 485396180 946733836 241721969 732323105 175044066 382648415 287872557 855248219 919770992 408823218 558934365 220471240 750741362 9532228 345844314 149561485 122009183 371473263 55522206 333034718 50016465 519460900 814117751 494597972 831940145 7854309 210287593 272077718 614047287 257761241 771030570 537866731 100352691 494903443 683437431 451490044 191131115 295230407 850669366 618353890 84057165 164320098 214989810 46121540 85773508 609674218 282670499 162381001 444682019 106847037 615494123 8575838 656957797 871701818 922829700 470191533 520854365 978185934 403110397 304693541 657753519 378809892 84612803 955561090 787395381 953713472 802492161 655887037 149204140 159552520 438774363 153477719 244383492 261431004 926800605 284592871 637191956 438655133 255055283 541475896 963609754 763445471 699192540 556743975 827869976 291218784 80888410 674654732 580645702 687835049 896147693 254424397 660800471 172704094 965556767 575446899 89508307 666463367 522985605 48470612 59300369 759507990 129998441 806937228 748835092 301788343 99693377 264511236 111202127 181898939 931706836 814467040 518870101 552786209 383932405 743524909 179898580 780420417 281633078 450667741 447505938 227251385 351627773 235075065 626266085 956480971 78545871 367967907 629110622 206767596 522060274 948510986 677945456 914014799 446654913 63299490 233236358 373180837 295257706 734964292 16126519 633731742 603017689 123364762 430537041 880258914 625391820 854200565 921659485 488746996 476120439 16492292 997500384 64425473 361924647 336266900 530821540 830662338 218967866 238472697 592651536 965150645 755793386 15249153 186964683 734368626 139694651 473160183 300682334 414360475 976981594 632261359 35828228 984524047 329609432 4724879 494783813 867939441 843167934 929253122 717664690 54053724 491849645 358121675 353984092 742224779 761938857 252557526 333058448 455979057 393676825 396606596 916912876 733349648 969513969 69188420 177498526 364084854 261756491 623602605 141679342 291536220 132123778 790650474 149341464 513342957 223535126 388408266 302250474 7892574 202222672 850718827 172285988 808296085 695545509 762565872 900971629 72600476 749241088 552211908 659662110 273763138 838957059 252672384 881529396 504708547 45474042 477528132 12695272 725617324 252389286 480117154 183524978 74163948 27465108 694161265 502045464 559466327 597182007 387145088 443186317 283131058 142507940 183630492 627298857 934978945 188245085 938759875 839199470 894433728 755445580 747854478 198343186 646394628 642772052 965016251 787828171 754146190 323264838 128522100 600565483 89307985 466318080 752310561 899644570 512909824 705956140 941469130 135060500 146394853 212044726 208953903 198892960 655537759 272357643 818409838 68666839 637602973 468516986 211695465 170026003 948247474 363198312 856756032 764395589 171407142 761385469 50346208 825454186 88061088 169798408 881260215 200487134 723286379 878623638 109492603 933626142 813170923 568488329 386701865 680642654 79487630 749346081 693493886 915611313 920645647 173506520 417923131 565237035 270758911 32075101 37318026 329820004 981134491 257139814 368873115 583327753 556805681 422066986 140405337 26702999 186266743 198668147 220094157 482618590 196051801 479751897 429613362 188186744 973878645 448170770 741555310 723127155 611524238 942149148 901157284 528040839 624258984 10377302 287899440 471142166 527256498 77588828 260678418 121792361 757826096 194631671 52822559 871551832 633132966 836374352 876275198 2492766 215622392 804550092 977652433 132372101 698174656 440043221 106904941 174249181 952992819 851835480 97888764 81609614 872199134 78926937 699919967 509050047 555989296 13521502 715621003 858334049 235782157 579579822 622202793 855901771 23502299 985136024 788249067 628170778 975080881 382431422 800760607 623683575 734265812 830592546 906905589 3432065 145783498 786394755 775080069 819143893 495408918 542890962 114532240 714236588 335572438 365700537 32291417 219504134 502578908 415752844 215891177 663285912 584588192 939754585 270472503 882038030 534003964 593644107 437210964 583879496 206254098 124477431 873107237 58940579 874433560 425240425 626372340 683120262 546166797 193970869 289436858 607919848 837056281 7224262 550871608 248276738 823519003 726525862 75530114 945718151 419944347 570129508 373871298 255944471 30785434 714421920 27472039 968167857 357839032 278273405 357875264 48849058 268382735 566604415 711207126 155484711 130331024 198132924 224338630 173741208 27664392 610760424 3978804 504189072 759633899 713632758 301014642 581284688 700758608 842642985 137500321 832240357 638458721 274653753 936475391 403538195 555785029 255684400 733120362 438677288 922141097 480591404 737440640 551017212 921378717 934186658 452785546 791575931 463914190 176233996 386922735 124546636 465676314 909538873 175685240 548023406 984532019 268013342 262064230 977424280 541382956 803960321 16477745 7515262 687713364 413914737 595968428 757265300 653901492 239529803 890540142 49714834 918642497 48121575 395146547 823434221 221602240 994669728 521447403 724703176 966013577 829561550 53016627 101815447 304120173 615550349 293163245 853812744 642210833 506051902 760193675 618056279 773491330 190624691 33806551 751203994 719116202 485137412 275962390 803891089 843309984 597150367 188218092 20483864 837819474 236801067 438063405 770369858 640729839 7266315 835096578 149784971 677840853 783080511 822308894 335220138 372092854 554128618 450669471 799757363 659053993 932893329 890002106 486000070 681285590 642176512 302736443 618891970 626559949 769371505 248932006 830576490 352048184 694370296 934216436 51886104 125975501 255552048 702048863 21340956 957371407 787726757 128318994 252001915 514712001 58149819 270494573 476837738 944422955 528380184 658837751 293276381 780816075 503883729 962488310 467748430 8018109 834452457 691898992 241874468 987340303 686640831 864309734 317089429 100038790 163184783 904924620 552419455 57731927 249229180 407717926 158931466 819109487 915948040 637842374 903038464 423844310 777948723 608393609 406983356 682391455 592992593 665732885 62365270 988429117 637948566 7418459 960438865 743299813 533178387 295835709 409874918 917142707 453391230 918735122 741273120 4696528 590673082 199843069 223669334 276451175 921883168 443620004 283464714 293144191 4241980 295554548 839896535 902449009 700289330 240518547 193385028 204848393 923979528 286650899 488503074 995239389 55094813 15083497 400437847 787781968 211776535 430165560 517473294 9271746 371115513 595820234 71111663 994998861 478825639 333921595 401528435 348507133 169440326 259019988 747693226 199530662 304366449 79373915 840318754 526861446 281287135 977309409 356957155 558860828 827826824 179314275 491977234 352290462 117036690 80928857 271481554 558485366 62010519 60358520 504565976 486706101 695415192 251926087 851917411 114495201 133979058 489105604 85061338 819611198 710305835 921677920 532044820 362686757 168836850 398441459 307181876 897412657 125422846 902995824 604272522 214213122 681058619 751867116 98053652 393701223 272872736 432931578 365181026 303810712 462516604 673766797 420256013 170550325 439720088 438880809 82869555 616575743 867806651 634775515 220203439 581900965 862455739 26069136 584391090 39397805 188588874 862805366 447316022 306902159 471941789 106462712 474038196 665718235 122771170 264511860 13149662 580747301 713724801 125340613 747281064 705668349 791738899 200602897 47477651 845808263 303683032 692045070 245633871 361167925 968416804 710292557 898778232 814441325 165037663 695316802 404519115 433705465 766484558 815558837 718290151 852882202 914064582 232198539 3230387 721738086 261722460 414121061 941919230 720425084 595997146 231397587 159745946 744578459 314876307 362103909 521012352 244533492 399512908 871677982 118569382 202002862 867515745 791703511 648540361 664696623 353443335 277876117 204917098 348209315 30417915 123809070 651322319 517498805 932983498 35861986 27008823 830337100 460067612 987201097 129433880 537125826 31392613 517921071 469591738 372486845 15931973 388587230 702260996 947558822 490752804 449754678 265330347 333728005 292455255 911912840 172821925 64627342 447286811 98027621 852494553 52687275 52824174 794138424 606676640 477894447 131725254 79394345 273675634 273524546 640281595 922835253 568475554 212855220 742875166 446297627 409009191 273795591 198090391 491070087 298590841 393480305 126790761 486266846 55026537 115670438 922318239 679049971 19896816 962599431 992572313 926160240 579744036 166510027 879777058 785119669 202437856 82321291 539486794 45411235 837166671 295893823 226829577 508818827 236617028 465681029 569057588 166838024 839499947 546920048 895059735 413329024 658055147 738015296 148888742 621830743 99394747 320967084 545544323 622683289 618511705 890717596 54979202 937233643 763890531 431832767 764064146 686821423 772074316 668661142 23279537 572588077 274880953 746116676 51885533 622161122 478281903 371284042 50599497 87525961 513675269 561261201 844197110 323590141 263419218 603714842 458261708 339311466 551636666 408568418 223969230 193273912 344522548 902753429 727382490 142541271 133536067 641098152 207785147 73944922 241572966 873609277 751844644 892037627 542777221 25014523 539882284 323499934 266951426 966885912 66567698 795798275 577624273 309225835 902714103 968756484 768329183 728737394 274727107 102976427 660594817 79412419 696846040 722934109 989804095 154136837 990874622 761276190 897803378 178194427 717223937 782627762 233134122 431447532 259832374 609384432 292307272 218754549 974822720 996608906 691255450 61415730 75332622 962889193 549719433 692231943 276741717 113268403 770750998 69571015 870544435 398768918 481590082 492256088 106105725 531440302 978410318 639991896 397159482 787021092 171722568 531600289 582511225 472244964 520167649 371000780 848947010 320552698 980972706 190545895 454904763 243249438 95645529 17672769 44794472 440543498 532800360 622255687 370478241 897955444 454678383 958021771 346305426 639657436 306476755 962024414 63193101 917972267 876566930 430878248 404092765 172433833 672948188 733896375 277479346 239224529 456516308 967506754 265411943 990372271 120338774 526694409 991799745 220607610 766149087 199668647 492598652 616368608 918006850 642745841 318893005 663174821 639047420 194425386 811146100 93616494 256532437 48440656 91070570 773709225 278928851 431619007 436507633 270614526 980765924 313581054 852311952 800020732 144714321 429726435 160500423 30343892 832127962 607602354 517451338 155874079 445740568 730281990 974057319 776367407 110624154 990743023 819878896 817297792 320653212 466816000 358394076 510381121 950523880 43042400 949433161 659417956 616576461 602526112 769328546 582210734 878703614 817315181 235541319 679908529 15109476 726700805 103960743 907242915 715517142 471903998 245409857 278769899 281026894 94043247 380521582 126647460 123351830 178277499 683362693 417620484 728268074 578714296 128779117 145954222 476250746 707225713 167606998 73508769 630680198 770101715 676367231 908125390 362499925 794399911 770023220 977743979 414394387 844106872 65479439 283172494 560015161 102207759 967194797 198148954 852769350 296234347 453864396 396171835 212141441 593813608 160156479 378867255 75589480 68064925 557936039 640721550 928365427 459762257 7891334 226558314 862060002 528819342 253554824 254057773 601045159 173863203 404171467 281410346 330207982 83064825 535018872 781369158 345177434 64524278 37710995 999544387 100564512 736870590 500934913 414391787 19894353 568612247 253294358 166783513 68689704 873650897 656087852 634795488 111629162 83117632 701654469 986260129 4611956 968047413 295639954 699109875 653286925 373710562 62614799 979419680 643853752 680463814 330870078 184802529 312204905 926646693 173453408 616838402 548529378 578639783 26551670 809703402 899601734 906956847 386575874 453610069 968674505 497859533 101673862 107583959 790707711 316917056 814257808 87813580 28789455 969314854 397448387 129200582 96167851 988762895 630278517 914261769 416167608 905583210 903476732 807305063 114134419 771339506 880938582 59262354 550638763 848051754 145992400 51335899 15188299 209968397 234040446 398015711 276892118 233115890 335647166 306922246 952284626 528653060 316845640 105664957 979745778 859148650 344487725 45173932 807048127 767140992 989319698 806007624 995181574 178251177 649072882 791817262 488242800 819019065 826286377 680106167 877541135 268674902 403410591 489485378 478327811 892421947 77166167 878314818 231955348 586782454 339878119 788065170 281742175 54136174 207558540 622566284 128513006 105243251 66913036 203137515 526866250 36588635 753099024 93507715 395382971 206354376 128312728 852897756 768860771 193219160 879864800 408754369 772161656 652625596 745897485 473888462 729941864 793618796 280683388 320154967 261537885 690157369 306232989 605131924 128573729 729114226 651900683 35083339 97157136 739717169 794009670 727105436 636255013 312170296 290131228 885698206 49225737 908920831 153223229 331702471 904959601 109964547 700338440 706802164 243702964 346863323 16352219 661219446 748949777 499993093 247202214 721739850 564839135 449251064 94540985 238465806 363247366 484289441 413911827 661914246 473895871 558847913 911218299 86375916 645709442 944789434 250517908 425455855 777587850 511085105 446939867 906145350 691449767 32011632 61663484 242360448 197518095 523810633 564209782 967005780 663371733 642942264 151474726 516004548 972682405 892483737 182730234 321637807 856275200 220465916 308652632 876579510 867864501 300162980 331319499 531741291 794316257 49449687 114909680 268250483 161460122 859723478 800933291 425247694 523516132 855837853 141601547 72720145 339779845 512844069 932954684 226705316 817575819 321146 610667549 53253892 799549820 216717 444968088 563009829 557965709 908288222 8455003 934118175 172967706 519255962 728428315 559580515 909875661 580041076 397330561 300537609 109049963 591886937 958707255 60220020 4555151 882569317 948524126 617246375 239399196 309346841 316646135 687645375 614371665 286752653 818853224 658062493 639179110 811837207 902600280 551838693 969506256 443070881 17768189 162344519 568997053 570642853 64925885 209063103 355364805 260349415 769531218 72430958 548379252 419430959 125823328 901570243 139931612 206331055 491867797 956077609 454450555 12271295 54137067 76176613 490086014 760869433 351538305 404841087 174012457 552219256 921180238 212823129 671613009 554952475 525336615 363180832 541756490 920893149 836376742 320423925 339422111 994295620 426855424 344260225 104989878 432022975 860011722 480447170 716426027 804390140 151424877 340032735 688291335 652857760 628729639 960742669 708469121 678255877 460217921 472327023 5633124 562542168 773114536 997242000 61695141 248937482 463288882 710775050 515921864 832255230 216143688 977972579 591314524 405851581 708997145 537551899 832077977 195122568 822762669 54464551 90253265 738821829 986402063 470414140 873165183 178364847 922004737 662571810 75855186 133584240 874905478 763932673 620468159 809326512 789987582 101006463 698646345 245090379 155775615 788671676 129491736 760399118 345782900 884882485 674191670 678925988 294760773 294885180 180131998 547585272 660436705 345660927 832578577 849614493 192484935 626318474 355304226 855758386 122236514 787254363 653713871 901113665 624892529 659192718 721680050 130686911 954732614 420456596 264709416 753199928 487056363 600638737 646918972 521449996 790634690 602017466 140650753 957113728 608937544 33692150 97475390 258298831 819999762 93799293 985972386 545795395 992334740 718092397 429852946 772769207 163719116 550316839 1996445 18714265 526262348 585536770 156359110 265712466 676436986 898210741 361972742 642423879 169474029 866499668 7221590 859850560 669625294 108694675 445916954 143890521 455395433 243844283 520168018 127902277 738774925 370986875 632068686 489895475 326110054 117384422 741997012 490733840 540393378 398439870 688906923 958711449 77153537 125834751 336725322 534278899 755166910 19275354 512562477 108157253 380293829 428752447 765158013 329786842 689798871 125843709 354328545 906683535 369901095 355321969 27185752 705279708 29209435 600835000 853969466 658161259 218829913 201458423 614978687 638014327 349024326 368020495 854707987 951009101 852885397 160610242 718945875 292330387 17858539 761607828 231396043 243804288 253573855 468001632 820638869 92297463 666600944 950490590 784374648 304920370 8263176 439934296 754970310 913471381 904743131 901057534 468010531 958488047 551287601 723733255 713525742 205490457 770848243 739365512 192320355 699643113 427962065 56844565 362484112 962325511 709968116 861232611 752569511 971530818 719362407 494762059 857723201 18192457 896507044 812170109 928952437 729898433 317338243 503245505 49914314 955969498 93769527 929982375 178296786 83187880 603149873 622637774 512681726 817437706 992161665 126899004 362792153 132619737 960017557 910645850 114552712 144758088 596829514 323196777 383789320 46644646 217477801 744892368 524776442 928284473 70676408 903579327 343596266 585200856 370472328 807153067 618849762 622228869 762781279 505623416 79003878 538354434 560774806 749382354 248117523 809009485 940598617 644389936 5625440 861871950 737146367 884335028 551310763 226554958 913527155 128028428 202872626 270674610 543622078 605033063 344965898 748003858 53479497 108389965 576019967 242969694 106453616 378807558 793475872 583466783 595957117 502330020 436102308 366334540 911615734 318913438 224140561 655382000 162086093 687864747 436198975 79917565 164748698 972974286 552764056 761706933 693012840 962130577 857004313 928198266 274271098 69558881 662651519 954705108 179607308 128320443 992523902 885267110 432367886 921421757 571085188 468232709 24116368 661662731 438173297 489694891 258913713 751188247 109979784 581720784 366772748 102276425 315533634 619329849 333945216 233837451 514018828 967764462 398542553 447151908 412213051 254053072 234597255 753649493 143319443 681482671 286510505 125883108 437104139 465730610 663682700 763291123 639093210 212788274 258661983 999457674 366378791 117346323 270519161 145515819 613285480 668599354 829366739 687647067 948184405 284115498 816118801 950053178 677352068 125333153 157221687 933192105 666517612 648103934 978044356 388318201 774696631 351597861 780661030 262502950 542142112 29386476 946816679 844851128 996527815 700096564 967373942 974576358 841271033 511512256 634648723 744153673 234987229 639495202 197243220 73395169 840652056 374631278 315439860 256185567 697174214 13618334 56976622 966293454 922822559 898913266 945732025 142804832 836986259 828683320 569040014 6511982 693558684 305262693 502506668 122015642 660477600 420090959 412194954 360364919 958070016 637326676 333984987 796424577 431287613 545863841 592029180 533778097 86039243 888927693 750472878 191128357 174578602 861168146 682924682 372622022 163683232 171345424 680503867 24524479 673547950 902140783 422783132 153730757 292166236 739653675 921632552 195016379 694703404 888451657 499971649 395392164 111865190 817453760 828356326 685001384 93053538 980782603 17760661 626872071 805172319 170724311 54914505 858938033 776096686 45159789 587259302 67805213 103910261 310988634 240312441 381084326 826023031 209517320 360898482 902869598 524557008 39401517 925990619 257743689 198967505 78487245 699749272 640964202 620662090 97509921 251071095 80282499 954143237 93197578 598833052 290244472 889783061 836507773 284550926 97634976 668744219 122617942 43926837 266097047 639655513 743079224 657422240 517673654 604390055 37525899 523740739 535995210 236449092 482088768 649412502 259386684 658032159 651893402 737033162 604815676 782107037 659963935 79790075 82333913 438425289 481589891 260196889 602491936 962445221 755070314 772694989 183054216 677254708 159017522 707736590 641136200 391388098 389397861 452780648 998708634 321683825 80579438 454862418 595611461 713341720 986907851 803037549 343933118 328364467 633702467 723135719 942719699 740411404 24627500 557803921 246359591 715977465 904396008 458700061 345866763 170550321 207458105 375155 521599589 353007237 375476564 871060606 179750533 936700301 449403107 417393051 898375292 342077203 19889651 292921463 256322500 47567803 133002921 590887549 866474427 444476981 476022842 983382951 671006376 575780811 637724940 112421077 449068855 285181368 893684646 473170927 468960131 226649950 222010459 768440868 665791958 361853517 24711495 322626665 430597687 633825852 112696874 777477526 437033501 45410071 303546818 168661635 305172365 982047284 336724399 455566898 591770316 704209390 390897332 157610822 919373826 315381401 263123706 837257289 507589293 496965063 218685671 231936387 391134594 353857294 91486119 351766241 902952258 984937349 677259399 991328187 228718006 217622570 677782439 435673119 893905334 270144044 22577637 204674060 852472038 259654797 419796082 104433231 609321293 468026363 968155935 622615683 17363840 142672450 920018063 693696773 565275246 140570622 499243398 523012846 578414978 740117910 703813841 476211200 616207913 546271815 673950772 634649328 854571064 579913977 344311293 240846679 490685190 457638619 115790150 536394848 11076022 824609451 801207756 976425618 898691701 883958193 660791424 291595496 330914797 722720102 497121906 92847020 783403959 653693758 238765098 888509968 187444963 130137921 329531563 739403210 193994966 197621051 668053389 171309525 292814961 695072031 61774120 533944617 264620293 219117958 211470992 928797313 828939157 447070923 548723132 69364711 748744509 104041740 413878112 45939871 367611487 128615596 650329521 136004361 614037520 17268662 459834743 464229779 810486627 169727894 821235941 999109072 243185385 149993949 76445363 506389023 586406537 659243168 797489593 708561833 972364374 355185381 602900608 555787916 412841140 560354880 675486335 901525981 212682601 113629997 361637973 529090617 706461541 315169090 851905952 382824701 257089593 188532376 485820138 547917943 504469753 838379825 23586561 95798040 274534650 133891748 760387914 847965806 873882844 489881117 413042652 493466537 448889954 964737382 779833263 312261376 183459043 237532696 834375710 638464839 194435327 795371722 694711147 267001367 519434807 716444360 477346305 984529710 585352112 130013116 274510221 96061795 709214758 283077767 669094417 976061753 871278134 36362868 643667087 655402366 136952500 690857847 149849760 66454829 173776336 730140418 984350087 317956231 414695118 962300300 562214236 867670442 550843612 945414255 992066366 873570242 963194301 472463031 334416023 333952682 293846552 561019594 255455332 871477607 769122865 739736708 967770440 77241038 512251733 351793167 659006264 201519482 51611493 295868844 631284711 770363633 550556543 618868799 574082524 362298785 969693973 618276017 415319166 868566808 13323670 268137509 531379530 469813922 819527585 581099803 231843078 186211965 199731665 343606669 565483144 790690901 131028902 936236824 835809007 633273170 233293444 218874812 296864408 886818665 610905326 584912579 465408431 685675679 900688575 207750995 404754963 21363052 808326839 364510389 281423269 174706003 591553850 457591095 575476370 610428308 303016860 301393757 705682384 212069282 534198167 122504940 921209659 673595084 149320563 416133234 313030954 652584222 758823759 998575197 860690954 350312815 224369453 577640255 709619561 675995083 581745259 394483364 639715275 506182650 220629191 661019727 248049779 175258036 737415112 386831168 944270957 829532684 317135618 149226258 916534424 244699740 372244053 246313143 691138803 508807737 523501108 864791837 441661132 457983871 373872061 396215423 893302717 873116302 534315014 806678996 469021720 467823862 203913288 918107908 554751952 600913776 33309187 404449241 12832862 752766291 210567540 857617377 44866946 954313854 461059791 508077821 981884850 229941212 756567721 119388104 658139905 604611401 17201374 982889313 916135338 586994836 731454731 569828951 622427872 880373600 816986559 525342765 735092505 74252357 597956863 565989515 730925505 258269952 782660741 865451202 859959890 258222227 300936938 406337922 668630965 943679623 132477384 882388260 640186868 709622115 703282367 663096748 125587302 799490761 730971830 864785017 690140127 621072192 958101542 951113457 397177864 432110132 534921289 943032679 470162286 261506879 376256378 233948950 68617475 513991390 947248132 90218747 903539211 405826557 233987124 992068822 508045929 415260690 618736845 428828499 889892790 847048459 326036099 733552771 798461938 140078153 925335716 256935802 162284345 943486606 573649504 464991795 679397889 643568940 229671556 255831241 9301686 959850024 982911410 649593749 796577182 54921083 367967442 172460301 561722543 534529213 840052061 907367405 451026327 563672736 247427330 728009512 592240787 366246765 115709103 544523173 498364216 706042018 577069578 636502336 367968314 562371044 723972323 224344571 921071203 476260900 381928779 827821903 264698574 429564818 605553973 453089689 606601107 493522185 540480878 113726420 902241061 428917822 510626247 970180694 550549892 442314489 366046497 593770758 901424882 700383202 123398516 59752545 749736233 679144248 681336740 197566736 809089309 107347191 266637334 301836427 949393365 751405298 592114138 189166659 787401715 20491954 458515137 570784473 106337784 383924924 768935478 514552567 28347583 570554004 381145340 600128691 27582969 117675621 629064101 220828393 120769236 976515082 942749958 532304757 235230406 379833175 648615096 285629748 365141556 458772730 84223096 101047065 914804057 341427261 668509662 476477472 649796720 166204125 272439008 234289182 855145121 837604469 316951624 338147029 586895271 777086208 232161741 468153557 655422349 313527221 222495543 900925325 586428950 758276524 554381579 40624037 384009216 684362094 682948926 118680092 961899022 856800662 938917689 891650888 619616861 539600282 833089048 995825149 697128182 530703582 738422738 615216113 746048365 671454004 735209827 930949047 949528777 286621364 667849732 176986637 267631087 858952483 386252462 650294528 216791423 874605671 132402338 590940205 719947606 715368606 237434523 891073989 253623118 73771988 202555881 183582854 424136646 83705284 317475109 468978177 134883182 836381351 2293219 777788738 523342253 72841166 133748252 739930633 17526973 311616119 91806550 711524183 933795137 908643493 567110527 821548048 747292862 705912542 29390307 307733642 608331609 689118437 755096221 411946983 469577057 856977088 491563675 890177136 924712889 723322842 205910099 943742719 536686790 611326421 524504520 734660720 119646664 653319546 375494300 504907541 973513803 836734154 906754073 376395391 752857505 773070930 107304132 555460734 889092872 214664061 722385640 949980275 647787902 747229787 213986668 833285157 706243432 649268498 508455276 447751878 889983289 459307578 810674236 661108037 950645654 610855571 997087703 37902681 795219297 771843064 557509282 670118165 629500295 369753898 988957727 864568450 832259536 126591494 332448729 745763186 33869442 213767250 148277455 625550788 670776229 648413714 312321471 860819386 248535756 855940362 602044821 666756473 685161194 713580162 830150886 638934257 801847554 372239927 603828867 14847426 730694055 648483074 693514252 511294797 26460736 364763046 752001194 170233157 213602159 280052224 733092003 171580121 593227614 366638555 891718316 681907188 662716405 115673243 582929437 320182387 463036755 283245100 481345784 99787231 525020647 528075510 439566231 539943812 368497672 137877173 468325454 755978516 103805698 513677631 173055178 205358119 847868212 953892315 731679392 780307503 717076727 352995096 426441490 716649018 936436291 673218579 556659970 272938046 336596721 193455483 157274848 328671387 486777943 712277654 429748402 116940926 62715025 311578595 33095426 935225872 622471465 997438206 29005965 350666168 306407065 624593031 993292911 467112157 847513012 250366540 260427741 823074362 46379019 385673585 660786044 108610110 301086420 674534265 662216019 171687664 670814772 709872178 422083607 233576398 817290392 27030161 206275063 650379857 336751354 860891404 178207821 419255855 160620788 891185287 784140752 370110307 616272164 352537120 630339530 996144579 869929248 2339267 332063403 686614463 604070851 747597258 565835187 959876106 242083327 704196115 863985132 190517892 436638502 643130549 437949214 211143145 593026130 69359663 417749141 932814768 998042269 501628726 939287102 71190090 740596075 498957459 797139243 905583127 705972258 886994039 726406734 949821029 910067154 922142612 321103317 6639651 491575169 229514686 872436598 104744681 2060161 912760360 329703020 317697748 287070364 56958079 461359619 889769774 371617200 320334836 352319793 526171086 25278246 969630029 186765532 991547162 225253476 180269133 723433797 346234563 795914256 365067320 630946657 282289768 824426492 579457504 970192749 596964792 496522645 486207966 831312035 504457450 885903975 294974771 434637153 205018374 620046057 463040371 49790995 327453010 994738728 204487984 498380559 25546392 533435146 565157991 999940291 376226817 910406054 369476320 249175963 722358429 24743397 894542424 339259679 402742302 594767234 151041213 27573771 666515052 810268162 210493404 963172552 840830584 772128844 736056657 821154519 74668159 599289568 163881066 9817612 982841778 866317019 937820509 818718242 526294935 94931203 494062483 830736421 377873040 524356871 264530639 625687413 466282910 723785757 723915339 559884911 975857245 355626762 543978817 198673417 397164128 766682890 693541420 470714668 179319659 29384003 381612451 674110877 707102236 604037526 827415386 112577344 821071491 692242770 686160321 66637726 762188366 341418028 337489881 178812631 582062083 823855489 51411935 80967282 857603495 551774754 598065327 678920289 346245667 485440635 201081442 130061329 966506553 546960307 488602432 142246414 552959306 900226843 301093748 518536398 305796410 171410608 482396444 371276419 833391085 858275063 984434141 276410320 628941924 135677575 936859810 201571024 249532553 905417564 295639492 640112283 920148754 670819958 481562569 555097679 258325797 537993086 364055724 436342872 714102019 567260600 434018106 810996837 487262003 265500505 240281136 454105577 28544209 894613567 511259379 680944798 888136998 421732756 907253796 480090213 782461694 503826784 441603054 489266222 973352708 723150633 956353551 203578194 188902486 565295157 179486579 647109716 444913466 702541642 965112853 551511500 990441053 203567836 58904493 145454170 955842552 190276736 548877938 873620688 648914923 830073112 409017270 922007706 241895323 801850619 49053788 320479476 83941084 585662909 266353352 864434548 774872349 876674303 578698227 400038439 686520883 759307304 308835941 309991394 722956181 634748917 8495959 469090942 934626249 220184061 281427323 688286328 463501791 968748663 834769192 382845404 174996932 72010589 848679180 502742014 377833154 947439707 730424632 124427185 715551149 441715772 293153051 621800347 553497632 347835215 367114856 554017244 823162900 259695410 919244617 551859496 391762074 711130147 16590539 433963401 369901866 745078354 884214041 138453446 861392881 627289116 807521048 292641437 112225147 774483883 707687676 465852302 448987408 624903962 177518429 722679457 621065225 560855483 936823440 366343403 719083199 678481159 505405550 993112193 440468838 892592496 789888685 777479299 453676979 971017106 920410850 171111758 884988041 973166334 35674797 327673146 958481404 255607270 810040617 910202634 938507498 970032166 19944258 254440568 81876382 670980642 752065635 844579685 780548697 241546323 149604183 864316755 449673683 527339197 290991047 969701352 832706486 681709726 198727165 403161233 325904008 340343008 525242919 574984936 131312432 263130471 965337442 560044953 494705883 285446436 209881773 885268233 989851077 549528408 733706673 476077420 80304984 260837401 397855972 198682229 145610748 227245894 255938267 414075412 797348635 589016037 698232264 49274280 955087165 565184115 411777594 581531227 987513903 404815620 533796726 828018026 499058671 590263196 36172140 192414535 260618974 746608041 789231868 69030735 16626398 374625575 230770709 560349897 760833821 161095330 931115649 520908604 79467833 574409179 782938042 88353530 215525759 405325561 69632197 663460675 838097012 58533325 723931288 195069480 16293394 685986304 581512542 765487879 908162579 411481643 923156438 313202125 669584291 342145988 347640287 932240909 149036637 834925155 40794625 912612707 874709860 581337021 601050794 742222274 534799201 237205198 997415889 916926528 523247868 590659014 965234338 212730825 747307995 89101414 322452658 495196259 931957223 349579961 641428936 804056281 703548504 337037963 309757160 426948295 467593807 57853931 847280319 481421774 492115607 164326332 658607738 340687904 538892701 522207753 293901414 639551649 333624400 751616072 414584892 963168744 423697242 357141382 544129759 987654470 433151690 770015614 100483904 103956479 846333847 497516437 638326083 24166519 944874904 669521830 845075241 934870375 167746107 487514904 103945361 441671550 611141278 567373019 49598719 868645420 909422726 585845313 650019122 618739693 906087748 456561696 195714462 335511511 396952398 313332631 78568962 239437638 558269788 500741168 32002514 929156137 602554037 483826094 96961072 999288091 634518432 986123969 342910708 428904481 721944334 678690416 147222004 368173352 983693491 906335185 580896275 203074791 862116429 313873309 353752906 593185914 710314846 143680707 804375613 582830242 785445445 988858546 222348720 544436841 609694482 436407037 366227020 770212537 153226092 20714748 28923603 13315259 900602629 603740005 740038409 834582505 982825839 69374598 641241941 367613859 34910888 572448262 372633928 170685942 458574311 686814792 915035908 436933440 302271033 833121065 58786920 993223973 819671472 11043478 858853480 679980558 907762658 273990733 443600364 589764120 512597038 413583208 993326361 909110510 578265513 362660452 997653256 114218100 275575550 825985886 172801105 93910523 707386897 547487786 849957556 255882819 861622361 568230060 602686164 579094739 450141074 115488849 688575533 883558017 587497573 714294021 279173631 231255768 653400659 876006464 424315060 629193581 194360118 33685217 793549464 511182599 71303990 611779731 791523062 916054402 354385357 115182060 113840525 532707136 351888404 295282606 495771086 725672662 643722628 641929312 642276219 198077345 244401502 274728392 213048344 55409030 698922113 173931580 790199504 833331470 548691622 602994130 851455707 365060954 52236456 429021955 453028382 877826500 908329133 945878161 199044198 487396501 420479298 273484487 400370568 354672776 501564250 337845725 96120624 770031762 185882832 934333192 192465165 280537117 642379148 702617103 624426890 718767256 509194185 208244949 291893291 701389872 264261011 675284672 549261988 884127724 824176147 401640917 122364600 886721338 620069875 670082869 580511679 96731232 785203042 79904291 452095992 718194443 8794355 383102109 162363360 441445834 729642754 752440994 120749032 220640844 300517418 35191627 422913718 132036172 939888744 624283058 368379695 453848046 841425899 381000742 829499434 913813825 616688231 759884470 762794177 706294888 921807472 865509488 923604065 105245089 582921080 781076201 637952117 882903126 705903002 676655303 331376840 525322977 482357177 5767480 991011292 33688844 150101998 533739422 755850619 565684893 39561706 185704746 227198553 587119034 114944503 380688152 951864842 262130257 507219825 337534542 365582536 292120197 338469480 515500609 510794300 52894034 360730791 955251302 663850075 95890445 600478537 933580643 1685559 489941030 915706803 370812727 348730367 210073546 937470517 145409800 199582743 820229275 930353399 537320332 419448388 597659718 601840568 372504340 328022806 390511487 178788923 793075808 252297736 93805491 544332855 687466575 134743561 856491932 637759976 893410475 359470132 3967699 600198371 147547872 244343306 918092908 253394456 816769122 962880655 572544235 139494755 666458284 513024342 683457637 606560290 486054436 610234733 907974513 251044209 330346438 535145014 248180851 620046466 489750579 284062377 78546797 749462559 495518388 797691699 256677030 317454076 950147658 428279350 991626879 668745349 775463228 807599579 482115285 318661591 24664452 566772060 793578335 292614962 207831534 721177897 878387726 307162509 586876041 820372200 267668427 110828984 534372623 134913184 470640253 595843876 312303798 308682213 198545297 123015756 652968944 653513722 559629278 586175338 940996613 287059637 58038518 941771278 722290775 696074078 3155150 855551764 388068329 508233790 812999943 430372828 135941572 333896679 787652381 238634878 997067508 442582149 42738937 456939107 694496465 213512635 491716610 80766893 569639861 434302438 525450830 452015157 195186128 346206646 738786686 916519958 43115996 638558085 726462600 387082237 274206181 969781744 328344612 385516021 46602034 563248362 777960515 456302492 532060188 109994626 871702338 468866493 836029223 823854669 693390211 211144549 534048486 364073273 190785401 245239422 905190928 108290666 324486020 394228457 118952643 878289694 584624969 335271207 877547041 954347769 92607725 828792587 790770354 782183656 108143360 551939145 22918565 730656842 50292969 810193421 439972845 227930084 796873153 702545221 146839000 574622438 506060355 509286682 471778480 545178629 819002250 131073211 954104562 106815312 136210412 693665612 994133711 119178473 579554357 668153006 838984142 634982773 113751967 146910540 797370292 333482301 786174074 581703275 987480818 121054645 389876959 624392831 836433209 585124833 389592779 655450274 109699673 900697801 691424609 317091440 462481354 966140063 47988367 546509613 502050016 546440224 530676611 189501017 493837078 367170270 208147141 337722822 210813900 706220566 81842892 717149931 812289372 442408330 883793324 550596617 502202226 362659453 850943225 73991565 625028426 285156891 696387086 355714263 818732975 75837608 340391377 344812900 673576052 996407664 893343376 902830686 195429813 725110055 328097357 235535131 928309121 496991344 196446615 52045607 247902723 856791067 748424208 770327615 931817358 629552389 665663353 70454615 545988447 944016260 864574136 582889707 312718950 89622013 171018171 749394868 288136859 970267637 454987471 366015247 697972981 96472888 481841345 77787900 611403113 876560885 768591652 135320388 661545901 455761762 432909342 698648470 304734703 129404465 675307624 337410768 81467156 373162854 344405800 993576027 956712505 87934659 930144732 50076554 846671273 327599705 206144087 613879333 602558474 356989900 726324733 632497238 568040048 980678517 252784160 650291516 15197158 897854517 944324382 209272230 95739409 110780841 752297633 480412407 786664842 179470115 900539238 734827004 598326815 554219027 12520977 612841796 742778540 401133743 358147370 490222523 596615327 233946598 579490299 969113528 583757703 64878493 667198139 354518246 122994430 846606720 356274511 15005462 10418680 446120328 441050393 427162512 791372037 467414217 665064086 321448928 40325521 329724096 87687275 789874132 35933454 789565279 65274453 465994862 413758725 917632160 184882518 262174523 716046422 386078334 671457260 202369209 546800886 181333859 773706656 231307711 510113897 194353097 51283608 516290971 799957996 952738350 225469669 142857802 768317269 611274401 286343738 676932896 718880097 245321030 714987172 729411116 16936428 735407966 911406102 855469960 585756551 658879646 865496730 394457823 969511021 677524956 844806976 483940112 515708244 274206271 644643154 767109782 515565932 818645642 262279430 695076010 319868881 491787677 47018664 953075321 398498225 994830481 217851181 625025884 575113255 68674922 322235469 580772196 717930760 915680865 6084476 795070068 31293833 915179362 376065961 933606334 286596886 244890757 727213538 666225981 107056236 770225800 609911067 65849985 740595958 886749999 88274833 233370245 320687584 171052559 824778541 742925619 858830535 415871803 752384580 433210001 839230770 497454037 297995995 252698814 794854058 620457379 520958215 472783202 198298424 924309898 37938506 913351213 796070247 182404466 664591347 835091868 148048642 892158837 160690010 64419739 95600015 414485497 218819586 227243820 305679663 58488641 649002690 540009672 338089926 394866321 136673238 629050872 850062371 281813535 668529295 256100483 779032912 562820614 714213405 335703046 560095562 162012260 555451478 520914791 466854340 844712869 750172049 829325094 601777162 29731824 932992291 483484055 140476766 334666943 759713604 580636214 386340307 458760751 621687763 186714308 353700946 217532165 636850505 12108783 638501470 473172251 41213806 994232219 339066088 496627048 953434633 994638873 740737151 465140279 591079069 819453137 503938582 587879516 129067088 733723233 502199892 699423248 254132554 274379232 949935428 466811156 723964849 453005578 927240786 116456417 855896769 299357226 784141698 362517489 115637079 47290457 804431009 464382944 969724684 622952178 998992569 656936546 996558360 94199320 911941972 29629863 782821123 643131531 900642962 259308026 486327755 568397789 95270068 513590676 692885938 536174013 876495084 888287485 134316371 803179517 1373972 662725513 78046928 75626620 319188914 178186425 428562023 436159446 509269469 491108206 437228358 351502671 650707844 249036266 916767666 854894059 383253160 494167443 899381256 418135289 429294201 274134546 97630410 717694465 918660309 589375094 124429254 164960911 164599952 285117733 785968648 947673920 150393038 750374404 491652297 515520379 520717507 815770240 175974427 186221252 478223782 912003462 14796555 563710612 197832094 922627355 53648688 17719545 701937828 112174790 69244573 132151369 207928299 770182228 372786598 406855134 573360137 433482718 915132642 585353283 569035905 878532180 544437731 567828261 86410902 66666644 808311583 614946962 197619751 770497688 309850979 899209967 610662793 58056913 608396438 709358315 217250737 149366199 716104190 224229573 17254784 594759544 923483902 197065804 271700400 205272338 326067920 280478979 764260749 66566185 823379325 67420848 792320299 179985392 206392778 504150266 459807588 844363565 118477633 947371493 168731238 627814855 582349297 344301444 645012226 261902420 351500882 316662731 149063493 470348596 282399523 554693497 677305274 536558509 960877832 93927536 611454541 367702747 846535976 434542915 387070575 493597633 832466059 179469231 226023357 805101246 64788552 755944746 818162510 700288091 263029850 448124222 697066697 402951808 829619959 867436356 471610618 149828226 809969091 819927481 38201957 475131888 631119385 806309187 391881729 71259042 678417044 435193543 715398696 669953709 248352850 952121570 362536927 266693123 292900424 320847245 721023861 757769420 789338030 277854712 709740511 762659399 540237437 818967256 855038889 503202212 454600824 619957923 598092895 715788579 666396011 463822412 441827343 746494474 318149588 35588340 818279749 568389338 699043207 945777944 33318601 565130727 331883264 633792414 653209753 553776732 560859797 524372165 674587602 108835654 402093709 957992364 107530497 496110848 862322231 446078416 493493189 420188322 958410580 528257364 757335614 89888315 412677110 19557821 427426043 645383320 980766826 216070143 374433006 716206393 830196073 49066729 578879615 823505369 290153406 691362030 117879377 5486316 190932455 458219248 611859788 896430193 318450290 952454570 449788596 435547137 852129893 918969664 309653166 306783708 821279910 831496664 189583741 130924218 294808066 896405532 956294685 754344376 202216548 631830060 279045384 751640156 260390669 36036611 982427527 456336987 739140946 599693004 359437346 992565692 170502160 290242299 660803114 163329285 816716538 43341567 978012429 341599200 267764466 748447541 8787472 500959791 582905048 597947926 844871666 729846055 629627056 146507591 726137794 294997498 429568755 609503043 107388933 701793077 867026814 720504197 746528883 44700992 755760424 516408482 931742374 907437169 625338892 665102759 1530105 946172659 526410153 821148853 709611436 875457625 662236599 11823665 885406560 321405671 200373002 228461605 469224793 307562951 986720530 966898566 408784782 682042137 723839880 704230107 333151957 654698011 180283457 212870572 319636419 443311215 679353171 522589487 941576969 371456995 933485487 830972475 121189703 912443308 420779120 936304563 748609131 748484391 586615474 873892918 174231597 551062365 180555563 218116824 419855509 245999621 467837132 895432433 123187121 996294617 731291890 597734688 824605003 705016480 192050117 136907095 703575686 94051277 795544432 466032781 365763364 407565590 55869199 650253558 583644570 967943225 829006297 287943561 301344063 345151869 235452621 717052381 709910085 744964154 185263972 409437772 618805416 137561014 179141401 959959988 931908769 724931298 546280855 396327236 963457432 341898344 527621995 828684704 132834885 486076868 74581998 422093759 43542757 672165049 685987836 946915674 678417552 553456381 310587296 833100758 868114391 749759675 929748101 645665805 886391667 900762359 323940855 785329832 16678244 139229729 878949424 246086251 627154547 494177610 884217691 471829048 322412470 254371436 795849074 304538153 866944130 619993258 980686222 846684109 822849777 992254415 298135433 863400303 446390667 102858966 516292453 803443111 868478269 973000312 715222074 469995092 233051889 134431999 990365629 96676234 581792486 563350234 789047911 574057514 936877805 636016645 526326548 558766427 561814911 595715186 330551937 411076928 35537769 422367902 896009963 917631339 489204400 21152577 974775362 699873466 363997707 92324479 511260251 910228659 907736687 149909408 470396931 339584423 556859940 110577023 743962378 427528920 722739235 618940813 41415914 146682938 21808948 90301900 845328427 439524592 407256611 973838208 241137718 522813125 692060078 720507377 586950853 207041129 477095543 65404203 301673616 143614443 801731473 868098393 998057834 65557335 886247030 656008545 5338057 616296090 816447738 99554463 529448992 205226859 818931420 292083414 663459903 896426163 434462256 434412854 716479823 100774212 905039290 414505380 877986106 311517100 902613141 209220238 973317127 926096094 424164014 657471118 374692025 461910189 713348266 989798639 531946088 24827125 697889703 557279644 767250658 164173976 611008986 522276666 961807967 284029998 827959659 578653625 218173706 910654364 810828821 951070591 136274550 619621351 880408295 611242289 197605886 973906551 177984064 688274301 544583847 689412271 647129534 407003702 851164213 424370468 243469480 254666017 860713510 887894270 764370964 255917879 928099361 328682336 916380607 479872656 476296337 563371283 873370253 924216363 714457547 278884048 488134069 521085675 875127112 769340164 83789759 387779759 590375745 488187206 384068920 547706626 292891674 173621442 854204048 611336880 628183486 547453465 882014742 660061337 282002910 815841050 548221581 510994312 964649535 24227376 387431707 160687606 151636606 305241280 962774657 714687630 974149913 929044786 207102291 605194451 770428058 745056160 504478370 933596015 540975456 454897451 591797122 61669565 730442323 850773852 660997698 786649593 734093687 869782953 634528997 643809056 673746609 619444526 188748093 59962530 85884637 395824454 725884015 247924686 112942948 665348728 376122899 597519983 291328676 344200191 901667657 936746657 753504689 864798547 562882385 497642014 680723191 937775335 460614463 162215827 77438237 438611456 571978221 777190644 134450451 170842119 498996638 663035303 97671841 914101778 510589555 565654440 980332605 76621861 164415020 444180380 850647368 498385770 264196691 588601043 594812796 8376791 759632451 109738915 873991006 88247272 844317818 1318176 115888266 453487145 963035317 776775465 687850493 79193999 89894096 768803038 279917581 201679734 225301345 263122444 824692926 691147338 792381831 869053103 63722549 42721617 881436086 205556814 375393403 126973613 120807826 708857493 839585284 416053069 571343806 699330032 861325946 784078038 7622986 337004083 29134859 498030517 68562624 539378267 189125000 915661722 353999748 181952137 262957291 489434934 517024188 879630540 865252944 307373578 328601025 550974296 645542410 686484536 137039161 184096943 527776933 82787164 657990707 367633986 749980702 610176012 675609851 960648737 24178558 738325622 22691356 234100001 145570657 30191346 755192827 880337234 116223703 523051368 880846038 662985705 249993021 236177207 919786545 222243020 278073836 830983035 311241075 100478055 323529310 120217007 700907453 512545584 623670870 375499314 486121970 9193972 81578674 464074473 525190502 172323183 484734083 323800455 719974657 980435295 269765811 726273480 284644122 406728573 352535278 838232148 390986273 213735994 158826403 947916015 155939095 13371225 607218745 856301679 81328174 804214389 921632482 299033319 220506459 362231415 917358909 542797610 569965670 664780956 892534192 421034136 189172270 644446806 85909108 752645298 918727362 669250167 174631905 848650763 656605012 75847991 309002857 625209084 542304414 622147425 496927161 55284499 257440766 189063632 278263525 798901686 156923039 904443127 180231143 95603696 73436678 882287612 175355703 206937875 39872283 168807948 483414060 857992141 186663320 534348500 217269156 316343715 758359267 821322492 367151648 900111251 70000106 958182147 837969044 44345182 819930042 327032390 998311216 170412893 475034525 437538458 828782710 844988124 619564102 230197413 586810419 486752545 955530824 892106965 154166111 582440283 491829636 317993234 415409569 427947129 868094291 860093630 349052108 651245090 680494233 572452966 509589413 260937737 404182523 958720682 897930111 972794758 259486765 584998586 789223327 811989910 11678784 240637993 911194806 651149441 145851040 130454099 567149169 887342139 155310418 753478117 373509046 136717907 720313238 105708652 500827285 104879454 822547105 600461406 891252874 695562632 660711949 153158126 183427478 226175797 981732343 897593259 694985620 50135131 987070171 189559926 153610820 2082034 268156565 19368320 308490407 228822966 271919955 573165005 529534844 591893804 815837531 154271298 874310991 249592608 396801809 732046945 131705801 473460314 895855888 703828329 522410340 852976285 865570976 673616928 708691914 201631319 488068139 489608281 452597507 602153689 241944602 12092726 434325729 496593343 627761467 195770781 67562834 981209511 665989952 565873373 695079084 494330559 226056878 363527412 424404246 417017167 648930889 200548500 10677250 942352332 271354217 904423715 409663005 308432480 877516422 982130703 937989245 189575005 57170171 157215408 322552935 120321093 590307882 659979767 491059382 494021266 685054181 326808635 242662878 298991914 985460410 570950736 49694612 589043272 198866432 92443652 751163119 641137399 70163993 669029772 574177717 912727568 259587197 797430256 763404641 870555890 821352536 229704390 899484761 664272089 819693052 822980439 755064743 77313883 61951224 506651513 93365337 530880991 195571501 566454263 499290486 980619712 325794632 887769578 856791214 509169055 70409967 155043418 460064328 905255826 612824377 336322568 135976904 809510040 49415204 958939644 400271390 231456225 543763580 927799560 889359503 96920888 887811339 369124117 625267492 717869857 262484643 858189448 384627449 193506981 96029093 847612245 285318151 808000911 71341961 354850151 65957247 87657787 433242579 749702171 5931298 519399906 333404966 906420570 469113503 928380866 636019787 640280416 823350943 624381219 25124937 68365164 120763749 71792104 608234358 255320464 8797733 959987693 820319879 545866368 48820843 345559469 235142003 324135258 412438646 369385789 589508233 290901028 221879139 456856421 188627904 865252923 726521330 758600157 354778566 864030294 301202683 343755321 908500935 959138282 689536343 95904985 648460246 560127221 33088593 786104478 830637176 183099181 909325073 591778205 238140869 539273997 413339594 92682599 908830993 343146267 121058837 995979437 187600935 351202713 969309992 779090252 330575203 196857591 841679296 963390922 71914265 368265173 217248697 76702303 958448729 254129116 380967797 414785824 999771197 369378664 865948796 968047992 744666214 749776503 594874436 360501945 699519357 46432785 830951818 302625753 775812974 709903185 328346220 275411829 570407639 518924067 423402294 771998025 633674909 615776020 794715730 918983544 688300699 933136637 117959315 121610322 848339232 139078100 137264175 958154154 440435854 390159349 26109872 404623322 109566175 803099059 959530365 857173191 950274751 155353899 763416172 23767649 980044649 81739184 132543580 846113118 178042317 653674381 870291961 595422714 389688136 26132087 479519665 859893928 428787683 310939558 140617656 599260234 815625259 840745291 20724886 263037935 908598539 208734651 160668054 243139510 492322171 749092259 768145741 557859555 154590302 14712544 807949106 96741374 812771036 992475032 733702777 294072948 299692485 723714085 81238352 249336085 202499301 923350596 125515085 237930470 171438667 765662306 33669457 980804703 527926539 72532747 803931436 287099809 974552876 960171083 763507749 598986071 628335882 394329954 808014160 823548740 71971184 731120940 815824734 43036815 25176364 523932312 388711858 233968840 153297655 863569463 375239168 571315917 983660350 45878377 778701815 323264626 279283487 149322834 515050378 154081007 225337649 209009901 456354672 360429761 619166385 690983087 83288670 359387638 470643623 227329646 273474479 376177893 699038645 837338526 984426612 190763798 127229911 690626786 40931818 456293501 611730399 341610841 413508815 785345897 885748306 796337399 535700942 148199410 969120369 809999045 22930327 563177585 226461397 439299682 650815064 42046377 314512971 844663712 620426397 806766097 296394265 804499784 315234330 349468559 174646143 521351210 376266498 620891310 868532388 721854939 277329901 106091848 949614414 180305237 58062706 988139384 840681746 768335494 322217456 504930179 723671243 614733609 866687731 195575239 184674135 402217299 138260234 860334710 414029355 440526040 553868309 58716292 243057379 76269631 739531722 456471959 109856304 349383580 91171324 794935579 462860131 774846759 991616218 251694715 696047727 567489977 256574933 374960488 749242296 48698183 870128953 370950119 513046632 895285356 280702002 67180485 528171801 737103649 874642248 16066027 693369250 134681813 778583075 867296577 80266629 508757697 575109066 216068565 71784887 915749848 973399116 23799728 592060619 750223320 600739367 980802010 311663320 440263543 683263909 334553015 455723414 443099552 267805885 499142596 378434542 358383865 753492790 263891803 116029795 282394482 809945513 514404922 752488993 508795030 307628621 81150324 969402436 981616735 740849011 893337019 124804965 239730794 311182197 677228123 70618104 668125339 172650143 613677892 127854325 80626182 804546543 268610632 400542150 153024780 72090106 139277252 664741331 613441041 37386136 163299104 157116729 885174481 645360815 524667545 787417041 830176202 455725740 708333151 900745460 258127254 494066013 338624785 12777230 84715410 989709201 425060748 98251703 6345097 539829734 656578534 370556958 655832318 388190440 725387488 819135683 679251751 680833212 587390188 40267277 78006581 795570002 297473592 998859044 434459518 124572332 399739075 642125085 776964453 688256261 885065940 427526165 949986733 755139772 799947106 597561076 272800825 816921602 971930915 890107366 396339018 56613972 545843610 32585674 426395004 551683442 334237071 86289968 50861139 748826923 302045496 766036788 268844080 84347615 511233781 971879159 924611084 409233144 236784284 917773371 590482983 730611381 345240985 668076552 711144426 577835716 750792941 341214818 152457976 450791642 669942017 252731719 758129613 300566487 947201973 323222146 156460595 890795402 941545443 911234632 708115776 957967818 517076166 599987772 39903162 134999077 289286204 82979981 108279540 589340625 756213635 797768060 847173979 827837128 983559853 123631724 614665839 14684436 794622754 188607130 137823435 883653978 193593619 532007911 310313754 339730136 805063681 901542197 258760420 825844149 89220657 850909132 262401727 524532238 626366432 272099731 813604000 956997768 953400333 308261278 429919435 257491619 636985456 309442246 602502006 199639671 372963542 27087009 134760899 441855702 260412611 398402034 815272636 792384682 965727713 584413826 642420658 693194994 890227908 452592836 814698018 24598939 821161287 466709403 684148035 567828652 266924689 370028481 138254801 911360422 712175810 749808483 56867956 518730873 603422051 826738987 894829621 20824298 485495759 569743997 792160439 726232431 653649431 177018834 138114350 402153199 347665387 23652486 257056907 682014714 106826528 20006457 312606257 142730977 6161450 157296733 218578923 967187024 703823911 486622110 249082132 123762845 128627778 941640 818257773 937944756 432114283 784858447 400955731 845954819 896958201 940958866 996204291 766757159 692639413 289027528 637745425 626763220 152146260 368114894 356619143 996839395 354354094 931160283 723982393 679166377 75610851 903603343 170594288 142679895 827196733 975370772 906576534 190741071 428704657 911662393 928701898 448742562 757910938 279770726 823558760 446253534 322960172 772105170 35471825 538032638 281435885 389308764 811581700 98456445 716714057 685535706 590724250 87704953 332453469 958860832 245098696 197880136 748139057 87127095 758590573 389890798 76760614 508649554 474716247 747026101 468331235 435089314 908524888 942667459 601821739 928074467 405462804 715990575 638035177 52552300 594546994 959633460 871143561 967217568 232729578 521487812 396296089 829756490 320628180 105401760 674237853 152862455 731853010 91532604 25215508 537175123 873244350 908827708 491632517 278953391 303148622 446137500 427758879 702027687 888292119 987429356 479227416 504757595 147065908 317264082 638431950 967367650 35074759 944555737 526524939 598566590 160545068 916845266 397006597 226823765 969341000 734205882 527078195 407702762 191652306 781323027 448271863 560736107 680795907 75610375 939304500 445539976 566631044 305969939 919828064 59246184 199739080 882742664 881301911 789832310 799594113 43105809 949947731 112943884 629562459 619735441 83169016 330713544 591889290 664554804 45241169 169805015 724577652 654216420 20094542 343913045 49189674 732357189 884176725 371707821 909508300 240429125 790122296 186623277 170007367 93275390 430094416 764777127 51711665 11880346 836215371 256605332 275163547 874444592 602001982 232922252 891980119 751415177 987388168 896788397 573812267 942777465 963700682 793872941 350286222 884671365 704722692 554726620 577865103 414612075 690345208 246649281 217518531 194134379 861800076 755220339 739344528 638482650 478626159 453273853 466430051 422252276 770389545 524627315 904428895 125556334 317741534 354188721 540895174 17071464 668383098 642872732 994911472 52259336 588223877 682330412 424614912 137795453 901632694 878216118 369256321 824927186 211326010 27406056 476904766 515617523 82234358 501136861 237659364 53451838 83497772 682300631 377751960 800665233 231154337 262259355 899234050 343061485 172438798 175567642 586060630 577343182 29319601 427503031 221163912 583585816 760429993 789670706 258128949 233321893 139813514 548649552 125542881 402995180 471019921 797379634 395638969 329228522 653288223 343094540 560194157 577449430 78169237 238438627 27163459 389001503 505999982 338976208 905956545 1153340 302814813 916450673 606560574 328885531 871930570 503779826 941295942 909981719 47249338 732106463 219957572 74999223 167787537 174596257 996178478 956731310 657968214 692885160 311720486 171019474 475998775 483750429 333564339 437472272 89957922 245671191 765506505 366255329 255415451 102805313 487224088 625782553 596321049 736357549 803543309 872551279 667442340 488627167 512424263 219238684 143746796 504734654 399025687 469174908 118285747 640973282 108727133 650009450 521651832 534926743 524245751 336953098 529254807 477916697 474817433 861361899 154134228 683477430 726859149 174412955 729050657 612012300 518551131 309875171 326664261 802632461 574800099 373795284 378083964 583948795 699829699 268249376 555571525 404509719 456074447 162149804 230251311 184514106 819772988 250543749 976532636 511656920 160413946 739273387 247389884 336099605 913243256 110498874 132304169 633111691 661152527 300633639 873417355 913988549 794291780 150854345 392709342 871865447 453699609 689467124 601538526 585138669 932409537 917991845 470883611 429483155 376905257 573954889 695826819 88498652 394474167 616424874 534853733 441163537 839929028 110376138 844881190 792654468 584946207 577538567 114323730 126970798 707049721 305997581 368875290 879933344 843905502 3387330 60510345 890677035 653119905 264599964 403772820 861736472 559749305 343871145 833690052 4159566 336947627 588329928 67369803 711541841 72061607 192889081 337860676 885610466 250441438 638732039 171964428 377579206 279384546 971417348 990133126 467363661 834818597 622262860 592609151 400368604 705218757 60967947 109625210 752489951 639385758 976235795 834519223 596155215 435036208 308871880 201014067 423378748 932802784 913450169 522883397 352531691 775646097 436207483 849416206 290743930 961509287 449046517 319773638 166031602 408057711 989243223 232906997 731984875 221052945 966560981 205205965 591009333 57076723 88476454 247223904 457392856 314398731 510531459 658163666 217077832 261150081 404837165 581656358 630945846 37666916 369269778 130204452 311008760 673365001 440566057 444881894 210913271 599311458 875894021 638557818 361956464 675438646 750546264 84904797 691695942 19092138 620953676 710566274 541564735 484491904 465125937 766459902 536882745 810350873 69265553 822593105 959209752 137960352 834232476 691316927 749382510 562839854 785909760 534924758 949788407 839395627 458283209 25039699 823801660 88304125 532528964 286035526 941272062 997889429 185946886 47462912 200884587 277824061 960475341 291252270 393596311 567978523 593369310 480682696 736604320 238907112 958507325 92352130 903989680 862444291 958139567 962275129 759179380 743411284 21021858 158420515 412848129 676067074 366795591 271432148 624007354 504339258 698034008 589059072 967018541 722742520 972760150 698697348 597007268 325664129 139525927 574209167 372875621 960544645 636431978 870280626 359182481 520763376 723913228 333353319 288374443 747623740 376982205 612149639 374397808 796970555 525944796 822467022 159539617 676556989 269102238 330208836 147563481 737458961 505648515 598088239 630542812 470719639 606728140 568446635 310619924 619860662 964845589 175435422 627891598 649743688 327229149 381795901 580745395 535181568 850282915 282019066 706603382 112969709 62268343 182317825 989258224 429235692 159732674 310518321 39933737 935563668 1451898 768077386 79177476 939345831 944992297 981590535 859728721 171788466 581925857 861873900 394542329 744379869 732776840 838498993 581409515 793968059 511350514 964287030 234797610 238999901 586705972 888698374 841710763 915090500 42291649 426372856 37998610 635570957 511282678 408478951 455552473 508731582 592703795 624572579 274251941 329524544 667482139 760652318 632792927 825901219 553345888 945888237 32391355 404364132 513512007 550267059 608733400 710947352 682922110 759786721 898173321 905244337 783586943 846176181 691980555 417185116 900028428 820862616 407660345 996204892 364748381 459729286 863950117 806330000 159809136 214186012 293653909 425592803 99634515 208745740 296959358 202899486 28446458 355010638 581646678 873757566 763688293 998677368 997827995 324813826 454235751 870805614 917622082 293356797 229979380 410343188 517161137 645582402 40490380 263877193 210007273 690433526 705573924 374002745 815068202 737208885 397148972 110236914 463548586 672340140 285147598 241771815 111561519 970835564 721536482 668082118 402955380 437802335 493354647 954416897 89161042 523455786 918204256 227288892 134082194 698498315 913571814 801718851 42380825 885021283 828115364 235974917 33201405 820367115 88269478 308261725 977249945 886570743 117490723 851583075 174242399 699390670 817483840 38794934 5875597 668873919 537815778 656617142 839909000 513851162 701945628 214064529 398600187 332069049 80462928 928146816 393182728 920348669 974257904 778387341 408489378 539271950 811926680 205706594 416448444 28261048 669646145 808363436 903546361 337467272 903627637 40211061 921182854 345611706 353689093 945931039 311139539 510942351 59171882 413134960 565279648 254437555 298354335 170418697 521809456 783001234 46089875 696723300 251878846 430805276 893678902 977718563 723899913 824735358 498006497 678883756 560407739 895662407 281174530 283152117 520881793 452876521 221695726 863223563 825006448 355474413 599646145 225937202 896662662 620889977 467079008 497734783 478276153 879232586 139442850 26598148 258727042 128599510 958350081 340191817 257643956 895201782 775737390 979106096 953050031 384959409 901806375 569460374 606165733 118079698 110463140 207287569 530754514 339255437 45458677 899307384 30570256 816138976 778270673 86913735 351991041 610903456 261195157 157577136 10162516 691874862 165023034 183587642 750984159 86941078 613447223 25152842 540843114 661724632 204988661 46136777 947237729 405915176 175661711 203339561 202189929 483623427 267323157 84664950 876878705 554434260 403455978 117696087 781984508 608879525 181864862 203380056 77798088 351441533 761704508 35877843 282094635 927860045 941169694 119648903 307273411 112079611 262158439 880124909 939767612 398247645 713673985 982921804 340060664 306098238 327650983 655885326 121495883 38798158 471328078 937500887 420017638 439904658 877024858 92185973 779796832 743689881 54680581 753025027 718699787 549493964 131906305 544175032 225373271 885589697 43967021 328933031 137762424 75363127 74325065 418205114 521244475 116224458 464181136 968285002 380232800 552708032 577745028 972960861 704468345 872735294 613415908 721354114 118393376 398121502 102264756 457877315 536304349 227883346 206410082 604147844 123376684 783515640 28922900 724068106 730754764 310216082 591147396 671103929 109830969 626883525 895369016 647207800 846966753 265741367 177699817 620205999 378096070 201028884 470613341 400727745 876439301 554738542 31257704 660903626 361082815 572301426 443101403 251252801 426054805 800614501 198201711 14649337 258675470 283117 256664160 190040119 529279675 160566840 740590551 951044516 731778711 309194043 222734652 146781228 483038742 432392857 712028191 808988163 790898727 133623625 461768044 580053433 477644433 280452227 945125730 909709605 958668167 175381603 789402419 374833390 535445727 299904189 437548854 618784131 306706262 583463547 125999725 466837683 75951586 893676058 990935058 627442664 356485781 890091962 421715813 168102651 780720443 261916449 200782916 919558845 103159337 517342421 150481426 950943659 347081924 378635911 422782610 471633316 414686965 447367619 484428440 897586076 948287086 302466923 449978671 134300029 90386637 624930545 661377997 836387818 489862620 865712739 245599874 487954966 493142014 167732522 996919041 982734593 108561590 990647593 473167104 287399809 417394910 38437254 794344887 118523458 137927777 479279238 409352724 108011400 714402840 819689084 275909518 934938843 126784140 774882398 517512319 64707288 252204874 363386897 26626609 804505471 965195036 564295823 609237188 208035641 387781401 436854260 94935289 847396883 427299115 863056469 315313730 698650387 649814527 695044597 482684674 796406317 251224482 514157289 801460024 826407599 623680427 952653564 769730897 318991509 481457606 371385222 456500937 499570658 148304991 432789249 930534874 63970217 85736558 396020935 18659509 649541503 311806856 516092037 641726278 26159561 649314578 601423032 971458692 803500562 542832274 936134022 298501559 683434125 312504438 853447366 751054762 708606925 695439176 912546410 350562252 35213041 799683454 608418347 976316536 669930518 621217634 122725561 109186970 33435444 100007481 137275050 979869647 410336607 337697679 529238454 253906058 242047190 996880415 286263780 770675680 236967882 117299990 956658439 891521502 483784202 498357473 348520460 223081779 290281975 709425790 332403928 464218021 934109529 667701080 326755482 432576650 286049040 865870482 735739662 791830881 266229025 970466943 487974162 510251491 129169562 404310315 705213113 948882139 17900999 909383436 629339477 933061402 304241965 495956583 894633178 84855373 918028615 800254133 996350604 90148363 924886320 54855784 751848243 380873059 620859756 106997096 296674399 535843648 245322797 280574395 607315626 127177909 145453034 520742900 970036048 339491996 926116700 651523354 753130919 854374803 416078877 351955561 423678502 967604947 202861954 551397850 618857766 535548310 217105435 125016384 401294623 132660357 496307785 740985413 255528931 5784105 756361974 15530914 313591740 223940329 30048347 821339323 853479650 818323857 628140670 253359085 635820590 417691865 894499345 347767004 244071577 867200788 305478822 368056436 277964948 625682927 724721038 439517175 728195244 683297164 532824509 85242589 427487271 150477325 852369519 839346604 702495563 591782497 899849444 100424914 279613889 902009546 226791678 483627212 221865350 631713302 666037365 128514248 518492659 838438654 635596560 754345797 78167312 170921183 560893712 457872212 379684882 440269871 877724956 626972500 294916043 799937955 949709908 333563338 717048805 149114163 742347039 762430509 691523796 731331263 218928285 916428823 295652030 370034966 914406836 861694389 846471809 538832310 945754102 425094019 341756870 261239718 381228986 236309298 973917657 446117051 852666001 92846776 833052785 625356134 269663345 570647301 623900324 518375390 528284416 522219616 625943834 168806472 931867381 870648491 247682363 913070495 298986127 360392214 947426388 291680513 535414984 33316068 700397721 463676969 662289900 55580713 29157295 837318402 41696005 548600528 121083209 480251669 347767768 145133971 907400956 798251220 570648266 142472946 224674773 933692515 818661115 35164860 137413621 679301963 412117856 300743989 619079337 360631174 406941023 561472409 861556098 604499412 597224899 735361735 712474528 69591151 543402835 613966255 60126860 205035004 576735742 177131759 303964863 177446106 114781992 425177830 905617242 643080765 940354662 389494600 738697976 80272481 473004711 657529363 556426435 476817406 901776142 498978693 383781216 839776739 840869549 616245908 668303042 143655825 128599591 527143881 653941304 724820018 638445866 281716695 262918005 427608842 711146000 554580259 135197690 740087384 86137163 991806030 432826661 441586444 802844528 657485548 623474684 368403154 576445793 345784303 480183833 799254392 266506434 534691055 622515206 703411251 942507082 888344330 394532031 967483486 289692342 956780878 346113869 344622442 203217041 879684826 185528494 372682809 8248193 100189244 720964542 216393410 44042569 501563419 157661462 970325238 380799742 667274290 256056382 605148957 434452546 680348578 636492073 20260873 643839876 245459927 471135701 468470168 429285175 227365206 408362820 399988870 512230254 393985820 11564067 608926557 570496050 432355048 993834430 963731180 11456637 311105208 773447746 813734129 318036400 318312016 94839190 523567553 187459361 106715049 996708001 590474013 791060243 315806578 670707535 191941373 354020638 10939882 726978964 42302765 66888085 779489680 814514919 275811111 397795385 454930103 10974968 999513872 614155885 839148554 319774848 964396547 607490534 779486970 185822458 601434350 8021779 57549422 766868062 612011635 881300894 736297275 740040546 809279177 492157612 621031301 903108169 53106966 78426155 828991809 565827709 253573680 561738395 105191004 130501081 666390703 592529663 402883603 793221291 607319595 79552927 824731452 306235256 877716141 988605032 220752644 599939174 57087780 253412457 432445030 688557309 380046927 324608469 417286473 976260423 507890690 527691109 755836841 337641112 484258650 226707410 428911777 820388338 162369622 151612561 942485887 322625436 991608331 575813475 334852638 360132722 972934585 366611507 421963715 923031369 967165710 756409827 432815336 452210329 410579083 672651201 733716096 813341234 955551472 770284065 968920530 722418012 16018933 696554648 135026395 659055518 430391222 759129110 7962191 291485118 881028232 434338651 101018341 240568703 93807408 618706476 111163547 761902276 880853157 410002838 585013990 225473579 126400825 157769924 383431034 426299500 453671263 752507040 362278260 592475547 532956434 362703029 598841266 754966970 696048702 248314504 414277755 966491481 891151070 680109194 843104832 799810855 557937935 335366925 268943445 619440303 304857596 487235370 410878226 938978283 482375840 613827470 921794853 827670552 661555017 544392828 328389325 865795816 75769096 494100888 150540716 245186081 890178409 119296226 272456177 646014970 80795733 670716229 255012838 813713935 675271008 74505286 930324219 364856865 576945945 918338511 94246524 911782465 405750736 930906445 673682082 900958526 319910438 313790318 620776585 699168147 920739532 245371761 925611690 830912307 152137847 151836451 852900832 666519494 183475051 534928517 275090975 553244130 687394032 758377361 175376480 841880686 846085560 135520800 171605942 51799027 225805004 874747823 440959905 444442005 577608135 18716967 547699089 791995883 137261482 444502776 145665 205363043 893381202 970915136 824970536 575714782 732594203 688904898 167891334 373750451 579354460 654670417 552281678 335368274 271756192 858577739 735590357 507701122 351358375 319314598 196364199 101678761 746636810 845088183 362430712 921834377 396226758 113144113 78837308 782019081 448130539 107908804 237851658 867433816 120730287 550836701 506830560 7874409 967167416 165649590 751513606 775900133 867508437 163077345 77738570 241646480 937436010 483615627 847827494 221144700 910957511 284728797 267299519 356078465 83270507 3890674 402613960 1010044 907007285 651284761 839358810 852703119 580992103 170571590 552177521 651343898 484295148 88306217 959308302 937802540 887935845 59611374 1145561 64893871 853688532 355526867 391542458 737099803 667667974 560823716 698525654 657477676 408561796 239741641 734640294 468128338 957794978 393869604 234772687 798495950 166762981 710560566 738455115 911133282 206744677 636372170 80271837 924671540 464555623 745583652 864799263 62392875 742812393 758875160 154928365 733411918 183247722 756525359 459418633 130904823 774054811 658037191 142812994 639684155 284950529 230417274 865829378 409759829 62033358 700781480 560042824 825120632 266595843 432288218 152144487 610242791 419835232 82319639 439552230 351731618 257803060 59246659 242658819 551194209 8080483 30224544 655476897 646718492 564617809 769810875 300619539 249038331 124000780 457953117 514227491 307188873 460045106 134164490 490638954 683586960 601213508 786311295 541360763 243308636 716205143 884431073 423847896 209101373 209957201 853915949 837871726 102625183 734135983 659814688 990418053 425668655 790890037 23668547 65976177 940566295 750795167 200487449 387414000 826147761 782978990 770741836 602247464 893402081 837103648 954377833 527267552 198129680 426981122 641137022 939914141 329610949 718246902 760169219 139910387 146007264 30685624 318751747 468744088 181810784 806633233 922784347 153997076 96763302 212945004 265571714 550789479 103449968 556650523 204007119 547681794 467437368 514185588 269988512 62920917 316106471 953917188 71291022 341249858 422744716 996148560 887619697 852545289 918174006 748148438 153862306 619980986 490986278 342382701 738672143 784071533 505459851 364343755 175254578 632559870 988766096 698968617 709166986 24699107 958686193 762875513 705543582 88405721 616682542 490233085 657220773 87592829 723161367 206058907 747214914 748258241 267306753 315715965 454943246 440130696 840835267 379551421 968074983 645541051 718980183 655366598 819895784 648352251 940578502 439623453 679447595 480231335 841316876 6482661 322167050 968870051 128515025 666935758 757088709 807913136 265207621 1744913 578138464 796762359 749054157 48683678 663214680 349910536 481294352 347801992 155348196 323885694 632327511 458385011 422622849 139119142 85993679 68592149 917030694 319766263 243444259 377032353 20129509 137537123 916322217 376451550 189121775 702224287 113717223 202472079 507597561 38063976 11406207 234834192 866685987 354314927 600321846 714350215 870944843 519708913 711364946 178683247 422412743 132392391 548340769 514122144 586401917 417255792 322826438 565477142 344856052 694739044 764090779 705137944 526058892 344189474 524337126 472007266 366208050 393218547 464893193 754103613 552678580 158632985 903664187 902325464 342065722 707709453 861502019 983356708 74909718 66598863 549524329 475512092 430982874 515906271 784498894 490167661 992597962 752001536 70702234 610839534 130936122 947612921 49706088 987068326 530394230 482662832 946248713 713407843 655583435 532607712 495589209 279543949 439793677 545512561 661175122 244569905 710752665 635048108 915459481 163248243 822561399 933063385 638823320 60072324 12722396 857196706 56706485 915467982 587807126 678227700 71845032 524498616 208782496 493645104 167255351 589642690 547506151 400699464 515971207 430544468 88183687 354449610 633547437 373004922 860721242 724732847 504933708 547749021 455819720 273053834 546152714 654157825 436395003 707037665 159282325 522537156 516190617 492150599 919491304 308170994 836755971 388969195 94450830 453935459 948259934 404459086 171767146 994602197 302537948 602462615 543986989 822145032 812630550 341791509 42843437 943228621 993471833 848505217 113752117 702413194 985816480 898556156 220012803 20910161 297414557 554404705 319854078 422098897 468997127 955362444 600345482 868268891 576493828 583948871 12555164 699795946 314856429 148010537 505513924 215895936 54440289 607412029 924524959 992199278 20588469 332631968 367648255 959782813 712463569 630323828 395625346 396055473 101797592 359704480 674632719 988225093 879931607 407630611 157874805 953061905 30769792 279017312 746325318 812025169 243799301 537439991 745870692 128503496 918534065 514846792 719655798 142890567 591320073 907278116 168192441 699660904 837624578 19600593 675184083 983650606 253579149 163116269 916259882 957811482 986282371 198285643 3281345 181052671 449543173 741635986 278886887 931757937 728191067 363512532 132220892 945376901 559323442 595936953 642110889 881975444 765358993 529318353 229003669 811844335 471964246 523147684 53582890 539973242 449213147 620682771 854242642 434924524 890761440 958878656 148021458 774413590 932804160 971423908 165000709 147842544 592411635 237228081 862578448 252537045 704822092 911784850 274927546 326236523 113860757 10247732 385466320 44267848 597562297 140986056 930286297 115191090 285227804 578926923 198675420 221277876 594346350 30564275 658479711 727057197 843083477 382813421 357906723 546083607 28182949 312441053 980965797 475004817 765067205 923739792 84691421 279877039 386872068 550506501 928026935 450595891 979034689 54120828 729004167 399040183 678113977 175129035 280910010 200482733 221716406 734460009 221066021 376975261 244822305 279977261 230813116 696380438 771606339 223887751 173687858 789941762 727589285 163791456 110790544 97675417 858870336 965759833 165495601 183706760 677346522 345736280 153405905 957704425 594196351 977045149 133228175 791609689 698528413 315576988 345884212 344698001 540663765 958991537 841239272 747587326 545712198 786797077 354995009 529920449 459133288 722546731 873308746 523867388 272759973 451697937 957292856 777243439 811046430 836061208 352771417 617574122 633766899 271075004 837756672 403807437 478524854 690801149 360609288 184819613 224869437 421476171 335478584 78365784 551975194 358641312 447585196 839441399 897846544 881074402 903255180 311066295 848453946 135625690 47959604 655675157 212937767 79583259 183743852 360165840 90109939 18739114 546006607 983697474 264802083 334123576 707938720 491046511 122195598 385383961 579991785 177440172 571935325 705509586 608973331 177696836 985626491 737916151 368143519 412252032 452707268 999804227 66126732 307068816 636640073 861230931 440783460 549386488 149126244 758413255 189611456 389596831 875817536 792752273 948271260 109729389 931294840 828045533 963509144 992749239 87430775 619264075 500386159 82671760 883235099 561615436 855269742 814989957 36757919 707637643 846698896 954659578 914535470 846520665 265476587 918279101 224339254 215189567 621084968 356226631 206095937 611560237 327134300 199104094 717362009 434999535 157762777 867776562 594910986 767981669 855107823 476837951 857131523 425496442 64690080 944728612 492426407 690214320 244743647 373534447 11113522 477091260 877324412 951255977 418038179 330405182 771562924 215530070 656894085 938828420 214156911 416856714 235487079 810587005 814044023 239693994 399937985 9607945 48312493 286501833 34679285 10640454 302322657 802659165 514642609 919466455 859364548 888385893 9830297 820261104 550118898 851206042 5078954 580102671 665822495 530633871 272122414 402174843 262532383 219658944 805181744 556911162 466195323 124522173 320632070 222881719 739979926 506234979 394885035 116247908 864288370 296850289 44009690 64779587 265713346 832106608 911682505 302133050 76467498 808825186 270416782 308210283 330396796 198883397 803576746 439165884 600540204 938296145 907033675 226288944 32440920 746412803 44330216 218183960 438742002 446441877 961398074 645141009 17482399 325012319 248895484 751164752 240600334 197214287 822298099 606305231 634837176 307216200 153770944 966350297 725707612 232659297 211196550 344025252 591482091 686262828 309429694 745720687 853608436 267029992 767856797 619609592 347096332 565629366 131598953 241590404 138372502 463618887 139830362 985529537 363954173 507082228 97390575 957850505 996456715 855138785 463610707 610059400 230044382 713134042 927887379 711457673 792109025 513986571 16413662 807805140 201307062 859633301 936350016 341982357 386451805 70958561 228351821 985412130 9495777 189031823 505337076 553883169 859720397 441762 614983208 411879683 154154335 399905078 570227287 986739411 884840890 10273433 653194800 326129142 693284307 327096579 619237087 599542689 375778566 631203949 733779939 500797356 453405278 789703110 799907492 326520754 932770619 355026901 817185036 193449174 589288770 225623474 139313393 803983328 963909766 98963051 665713234 745082660 343648005 392558162 780009865 848964799 666990059 654855512 115092410 893189744 745052404 600828845 687498790 246235701 991651619 733855552 226181621 69848792 677307118 165671118 718011365 180742173 704083751 825480647 160781961 918345045 424475600 543290985 316480753 689773675 520448735 317634290 249893193 782428188 493815981 158041410 974210623 314444882 779042735 430452105 792469342 412662560 760857557 988676824 901248391 617580494 819908017 380136445 770282304 629243299 691489395 71744072 745653644 577578719 25606476 415200261 683627879 163289953 667756225 479669381 708068617 538022609 757087236 256209665 922632358 678179168 659013388 66792934 432395918 269758417 77357988 866546816 912109732 417868870 241046380 924900027 152984612 857694817 422947718 658511397 961913704 963089794 748560461 903285493 724762485 59285667 596043927 165754982 492540448 182311967 277441616 754052039 663275393 384219100 741055571 147000955 8194949 809650595 800589133 808240996 610868977 338080988 250156460 953388151 858712003 656156902 598228671 416589466 22185330 17806576 643305017 809408002 644986885 867999339 734080930 923825382 643801437 883543409 44360517 945912089 916451148 986524136 60488162 486424017 454533737 847065240 301990860 697907690 608531333 860457757 10941464 296220376 780166343 427165448 169038613 156478988 438515186 127329204 282321243 975403090 563558164 833054737 980595272 278078259 769665800 339161019 873990820 87002835 879430383 386149554 977691530 30870266 652597944 626593260 518617535 42503297 132981382 764604405 712852502 385568388 440482272 820435733 249945007 529531695 510284296 67361287 636588369 931913532 839408903 936364307 379246092 152332036 127880504 18690577 372125302 565009587 498764058 363745477 912378999 239215491 89104844 614710327 143229899 410612170 886990424 601728436 529065797 510380469 174288110 134796829 410194906 90340036 319590361 731398055 416507097 48711392 493724321 227813171 705923789 121420119 484920039 221809570 156890906 661885533 645006524 369685323 247947794 834831361 805011940 188434248 294493787 591088115 111155097 236131053 961771364 462968630 168179083 388543457 519696670 549778831 273203234 773331654 733493086 847883532 581801586 890949247 871655863 188990153 502775657 38906021 26672506 304103824 153229750 496665780 360528506 743497594 854877044 652614516 356801643 228632405 339658021 560008213 382583588 914980788 589407605 230640988 299046725 425531802 76229593 855233308 228678537 977406478 551814602 110583927 121295689 379767759 481794566 746094811 314665670 575660177 830748604 796757022 834556316 884734173 87858362 395488611 767385152 388494777 634905135 185933933 106034623 841531292 508241156 118811481 727091286 773696186 654988623 551805344 260881562 394666683 224863461 161210836 632742448 720274218 113196644 614621127 440121466 787322459 465464751 768043162 223380086 475915508 96339819 91815029 916448233 866260939 531216921 894359201 440317394 705772509 17447371 384900936 371632825 36370497 554120646 113957173 455780468 879986139 678496437 607637909 435569841 22433598 885715895 883315440 297703242 264379984 288478662 206218134 289948581 919769567 246164110 221141868 855772691 297002768 962322921 969976016 430778162 58436224 806417606 214304663 171544689 333834422 397943499 150787741 933994172 473657526 747152128 63418595 242962312 369485156 600616120 586489828 777561074 88892539 188304317 584577105 109101261 855359612 82733404 712284970 729308304 247549729 160380760 573865601 246976520 261239574 264065998 981122668 709393137 22529951 72894275 43393419 10415266 336030344 220004394 929092155 79176367 381219482 101345964 299070870 630177236 426265506 595335564 17614177 793827651 231782794 706235360 226315889 957972679 547415151 268762361 51654690 592293037 757857942 944782261 679914645 964812535 399493162 616663929 778901483 749473109 5491779 588774311 258369239 767728500 632266843 351459759 408884495 310220159 820598074 533097458 183814581 765392308 999550353 137384843 769666945 667078665 787725207 484724804 982317334 204314779 760633028 297469317 960230700 998984542 694428614 824706147 444146149 828215084 138210284 470383365 17664550 458145675 578938668 98192633 292606534 539529895 81532153 929319401 239457146 290958384 506122467 199728305 328782408 896125272 466309213 260683449 746576689 858363906 701313210 397026030 663367573 303447473 191517199 475414349 102288344 580570265 28230846 891238093 299806053 313910232 487755985 646943766 568047696 492082399 807087859 774397439 450982605 404168993 441887072 728862622 605489284 271130770 120719842 666351813 81024301 645122570 665295773 590047855 752137485 504173468 951423010 639350206 240467377 504097101 976759782 199784370 827897073 367062554 311463097 101196312 829093687 635993699 393105613 595963409 100248578 433372256 121680922 510899402 906841565 546787617 662388997 547854870 878799941 401538143 213656549 486710576 474766925 844532751 399271280 530697262 215681205 594783683 119682488 776840901 422414584 248959845 821785130 623311661 581004858 526320924 204512084 511596657 586413050 384698483 176200331 975903610 851976668 351641278 808599750 859207901 791987587 311442403 195727665 347657380 62570842 302735340 74563865 950967087 643834796 753370419 222759301 602694490 885571557 395808852 556609065 933228202 651699746 546305601 413302448 482961230 939406059 814059344 245263248 97461392 593050869 126407851 343742074 65395548 939243794 620509133 473651525 972170048 746979837 375030028 288885474 460239598 995619749 906911903 635655623 421586403 93599558 390390634 548428395 888646717 162336167 130043621 774430210 934893114 360643086 328757022 26385623 571317697 735579134 726759622 58318436 250465045 318928271 932966434 167169545 541644169 127941443 342880490 536970487 894154682 800462925 654370448 243693321 135918053 321924045 992447327 254083712 666387946 787109678 273372082 80549444 221359363 785783928 609656222 346568711 808678439 929324738 298718783 901235342 299475712 243924295 770356101 194976734 518501415 829969699 825034379 757669638 323306562 414622170 325517014 304556618 874570531 294082134 399192901 18277036 274787700 441131592 37126283 615575701 430082212 246348642 232541636 822085902 508334901 333969475 160145937 94368637 949337418 518822642 856247263 395526561 771033149 699635022 870172455 288816469 929922770 244225054 232905303 682018987 454704815 315194256 862583864 673068205 286204260 900898677 718857668 875913371 143886323 527863642 360050115 869036884 405583962 463323498 518990939 707831384 747955557 446849774 537905241 433534346 466437113 509723441 350986336 491898449 404352198 929283515 452552054 103833977 114665241 290114678 375864276 672397044 324985406 492989984 999833792 894968139 673506408 411835743 335073826 534982435 933148297 712072578 651537903 602340072 816808301 380341969 867071065 469078028 593928347 630504489 578796330 873932372 634989154 353944547 999048954 169092427 973919613 217387083 71192665 175798248 614019791 657446421 529711717 387877544 463128242 726088844 58984277 808155875 451841902 164894706 485277416 796878959 286404038 305826864 856856251 582544601 660504298 218900154 153039366 450932838 469736652 794029775 890920204 704568557 347050094 400650729 919858881 791921151 946785677 927154595 454948543 562134828 492319766 614663331 839831527 100141825 790604571 593968646 47659753 299785184 466854150 644202074 126722203 169672679 230439819 721436254 551755862 916382042 78676094 114351969 380273947 81739428 263917985 297872464 173778882 948720681 450687164 926380543 278169185 191683938 922464017 632850876 849580137 270007095 387141275 239568911 332605754 914925483 870049356 203397674 403886349 573533034 339012969 340746051 737427682 679034907 639143670 651347746 71789170 271148237 240929441 314171548 729215865 319634131 37725627 303085057 36185067 813843387 322473008 486080425 565653959 295953835 710840187 987001603 367884567 890379566 314597391 35333802 448616510 207740406 128254414 705370549 172532514 999319937 95394844 262212845 831287553 961707682 506417136 284266481 272273155 213427999 405220819 641043602 79126212 799822484 815916709 912473398 713128613 387124333 142198052 387687961 628858543 691387291 76529078 312103889 431792748 352954184 922416300 452824314 244698763 677416490 203821979 893982586 112187441 836776538 605346181 797382838 212617905 529424178 355164733 467151576 339293085 692083278 120140416 425428137 696126831 274878174 490866388 826562295 947631583 497748752 571768219 608688391 60094595 475197731 739091324 176308094 703481145 136528474 223750901 606300397 150724723 773155648 119407344 151114717 779841169 30878774 549583868 223059067 173842404 335645026 363428527 766988255 300892736 761937870 338639764 937247011 831856777 380155693 421426912 902848577 105723361 640173617 889529751 701419731 840226087 126874159 780907555 965955715 749331267 461960033 140863211 964638180 398591322 141674709 568089751 476134666 685550117 927301204 342947207 310155134 991612398 355278164 815264931 123252528 77647184 453213110 617200001 84486059 926448041 933868207 712357621 653042828 830421211 953973401 912112500 850638161 661087654 749659672 91043017 741764138 766451806 149071544 483277852 394432274 422792901 875187410 957982870 850741156 676175466 587320670 39325172 72147973 921299220 376995526 705005647 802454020 574076141 881224230 134904028 166376610 537297543 112789031 73768125 385288420 756887407 644901662 285505284 95727104 834597803 123425843 667001909 398254845 992304407 437509192 478616128 67110328 893278486 951635539 60654268 299047887 834123235 847800891 588832003 358105428 636625616 592172879 119293610 880969514 677430926 490897044 60838469 691336760 176767272 789904940 761437550 545946062 666264641 210646570 599556021 115871440 631266803 826221869 803939944 774313721 973962572 808107498 909332376 760500424 139562450 264924041 919875241 39045451 2448898 52311184 53647123 393259649 141110252 509845629 811000071 749450588 12074234 348181931 281716559 428826611 724525319 707159691 352233363 405959944 41983457 858879621 804706146 782422576 451695231 752849760 304383007 961065317 682699484 541341837 824209068 312776128 498152177 285235223 493598231 241262565 975908002 953281890 244314238 15292848 997661802 630527323 220956784 915890677 138585731 3709304 973920897 50959259 132468772 649662383 708122895 962214697 858620724 740344081 471797689 586617792 141809154 465448808 61986303 269703503 269654652 921069989 418802190 386416295 469141922 25334419 612195838 905496787 430880332 360839872 350316232 122053013 723482767 393633323 889156424 621313120 162025980 553473331 15695655 211981767 547082572 484397477 340939908 890407304 892574426 95584560 217168647 982808077 314416340 178547000 770898365 679675873 173973771 1247744 740082765 491403170 289703857 77961985 825954987 255698558 860516099 667155542 885418929 26099349 493446176 996847467 684831190 68908767 477079602 268074408 613802552 724170608 416092554 188497405 449381144 635819240 415617676 474947052 839665532 943081315 457641504 24639562 820076624 50093348 480869479 418909217 727653660 725591507 917634646 971753376 795448673 193494586 727532270 178877817 418062062 762161773 898088332 966317417 399452070 651247889 737032331 939354980 161888689 909771000 788293055 320140953 752543307 315194807 944481380 965430602 783662306 60766146 620184601 666685085 552752120 132575808 64256058 593658523 425864961 843666673 488904292 498499240 702785179 507008180 273525369 967553432 649093850 734149686 11617743 97036619 366729240 473390328 291020391 275010061 503114592 509340458 597158262 379582460 897055677 137822296 956200133 151205181 208233450 184800610 765248819 502535052 114595793 934061615 57701087 163450509 807529493 805088843 835613062 377896098 721596991 577603734 94595827 629496893 951208322 793768903 114577100 235819873 875593496 146119773 462612061 637927295 979252988 510031651 378803086 524002509 993876606 907567652 481523264 316533984 33759577 587361224 671945604 641368010 918236083 735106808 403991936 216045819 982220734 623394135 570790653 559110861 981456585 644405657 856241921 397482454 503800600 32711822 564569109 258113295 863024414 812460049 274366122 103155530 841385169 373439116 245767735 573567045 963754918 452707984 54357199 937233501 731595118 478830144 69387709 976344534 356354436 202489170 829535949 373789189 414497774 406494295 487797669 702629247 496064868 788170044 637377782 603341667 452707960 813022385 856694377 17583372 640210135 96865646 798720509 956619097 694209750 224022921 242256240 910115469 855303313 617972489 684065901 68968134 636122612 744185788 671990416 564431729 677029057 803255434 35386976 689398442 933531203 363638075 55104806 406257691 59722549 759129614 530039851 167637122 836315267 653462594 295577135 883699689 588415964 879033242 691648954 67037979 302978432 658602385 546660081 50497446 417235713 994250542 623476787 179013321 833055420 187417976 760864095 914268282 988516866 143406117 306525013 591291078 932898267 560611634 790071404 447675765 284349323 319774749 307970774 406958620 502190874 938438868 473164252 582233173 328912492 276237486 139614424 208842515 90362586 253688778 791352289 268001032 230999152 907912108 402908468 327346269 892003600 476243237 78257475 693138882 923041915 197669720 964285778 490273636 901204414 22321905 228924734 804020263 265291116 453609529 991104507 74422475 196346087 469943101 745097122 623199360 864614441 841198411 491768802 975676614 785823060 910289864 40291241 211019292 46861973 956007150 725572706 287185768 39269864 649207516 508815820 988140913 402206852 727528151 571751381 370668682 428487858 956801226 713517592 277874216 756429943 560583794 142448273 946500149 787453267 297068853 535160304 766906389 547944538 842135275 444439254 135225100 816574086 432010611 613167442 338382231 993051107 314355606 422874102 685123642 252783815 117652642 845887163 222032545 455998719 672316294 928869986 970323784 423372182 664358852 273379854 22368386 303616121 760636728 140993324 563475998 262029381 323304374 176180488 548896162 811335006 563421724 898173467 627756221 530869700 797255736 492692999 936994307 234826003 478371021 310149959 787185982 20889126 155438394 982442356 760293442 672053693 845038692 543914059 263838802 246366489 326357976 937579341 716030942 935219983 583971049 37540703 39900050 624317009 453194809 302249967 184545205 559687233 441801100 941149412 168193309 730068900 672802232 827869667 217224193 961914191 894594145 552372277 382461094 908986403 184845051 450006352 259893940 325587466 160911652 648918237 266295216 625638544 488221941 174060149 299090657 323574784 992490161 287433398 739696018 823137499 385415046 699872860 824424640 950761713 402818461 645934580 541967727 165841668 564273315 209607018 453898962 538764635 828647800 194057082 374233457 572227423 442546423 284048077 462361023 468943552 506846036 800177653 780057603 801258396 770218346 526039517 92797128 428128049 382330876 248462534 4303251 799733527 210640007 856099684 992320107 345781629 823644569 565378314 442090979 592698733 602957869 267261157 454942061 422287939 169108222 103588129 874241306 160948547 186357287 912490035 767406750 794425107 219082728 330722522 411043400 226463539 217531887 354237759 925704548 415841067 411339640 127010801 485720985 209631159 585945343 92116198 79777475 337394305 784321329 344190107 67893843 409693318 10084538 348336962 581237133 35480568 909472828 825376937 256540906 538576779 226345293 651002921 92660360 681160125 532719219 703295495 80995019 799232283 779886757 465551181 296893831 186574468 813521130 130220733 522066862 561307510 281329671 536617031 484105575 29651234 94563829 151941273 793102914 166214977 498490164 326367412 949049269 564818224 309291892 923538216 223801812 421545077 76427440 203309287 884794958 611349539 248163032 752417488 870190997 605867339 924428977 571285521 557917892 157133897 676340123 129736166 475734786 982052143 460688198 27669442 100240585 118445308 916300159 233662938 84982678 886849366 997764168 967612201 937518551 918487279 789080670 21751517 326594236 540202705 678522455 299121488 557471730 554445680 914709114 90280420 859276702 946249669 780672678 970043011 583563402 383894595 525987859 36983636 273044302 7852946 115188667 41303705 690085108 780813332 143253057 668231499 209252431 579250109 428933928 102664760 720467616 57141555 987609537 165078704 124501505 328702444 204613279 106197237 576585849 496464424 591777166 656852396 561803940 425964212 766721522 840139098 805409746 795062506 311475012 413085731 47286063 52387611 782794500 112151329 173629180 591540051 453857222 340438078 970610818 756779188 333015095 2369216 206034201 825462735 745907636 632634629 374216287 6692787 289465870 518619691 310319245 480019251 879254820 33133272 663882294 787494709 748685118 896476001 473684730 53699509 202715090 3023632 555326172 63139099 167905155 111083230 709798272 580632731 438219513 863007003 928081396 477578722 581922221 522129067 697740105 203738213 515383814 782213714 634081155 546932698 674369490 633658479 508032995 374419710 437671368 989829733 118404429 84125314 248333305 921647170 795514879 298196231 891417979 235809609 995219635 257882287 983165085 880731548 629944292 483707803 467785839 318427054 614270146 641389526 974083671 281993397 845362811 819016254 220489570 25644531 204365479 688917136 620279504 279058559 92284946 387324348 818983 956569157 306580546 816352928 485668739 690492353 565299162 281524355 938348242 527037138 266925505 93900055 999494279 589747503 827440188 612573288 962297991 937190995 887807843 764454378 972732981 456796407 141134090 11854830 905103817 972392004 418336211 249940189 99943487 440442685 795319200 441415003 734107799 46491826 549856226 919946276 842587266 103621312 893192944 255625527 800662549 802087533 579770187 420497640 230246729 891486702 274542061 668201711 491710985 386591318 877342755 27673749 570744167 370680197 834116609 307071064 78923950 484712149 700185535 589922423 847064763 6562848 906589713 628896449 915566280 221683508 709402793 119832263 193181279 462669988 684645006 736932151 869342175 905686338 754389351 151162098 486948317 248103380 500847176 430655434 386234631 331423234 627739798 988380396 238936044 209631745 199165725 644626185 967275205 761826973 855546836 98133249 731460672 742954634 793790769 740399191 9347362 788260919 928179477 606644427 570942488 558123353 716770389 705488987 897402037 110938507 219706958 939520289 821143914 741201433 635483770 793960874 509142154 908612513 447543109 752245619 411138136 224995646 856588846 25799931 236411191 685644511 829281352 90224067 969319961 162553663 377805332 360867684 964240325 87138498 542057610 533591520 820097391 292476563 809971522 564506475 23913096 14803567 243693141 754314002 102711206 200094 325623181 235672944 945367807 111862941 234899484 275801579 930704691 314636300 961973618 896132944 900541180 34034119 80720952 780800573 663900427 171975390 849131175 748921538 512912491 739661555 520214716 221069023 138099390 927445341 659227015 796307757 473294345 137047393 506663259 31856265 365028646 56956364 550797448 374590435 940037861 306828232 369302270 234705580 374080906 231714094 215453396 454997364 698797672 789598109 349260175 256618099 808967509 941078325 244218757 349590570 568969222 564317718 749032672 854848984 437525055 206758354 343680619 524994894 92273705 663318191 441322862 61155929 694395267 875585169 652399769 381455455 467276463 876390776 481111779 321843978 723456403 329101998 494687534 423699508 892480550 122660900 582808370 15549002 971865978 153690238 889199427 335574427 86684088 290073487 926239934 422810002 87860618 268571796 484181936 15307952 881983871 690724823 220206080 565945463 220366492 872753009 928106748 41438910 797371821 240167870 457125681 437989782 572819018 163725931 564790445 742768428 596875217 910610369 424287831 392925567 339726574 673943312 746797522 898040242 412490476 98895117 218788167 645637512 413542325 147754864 290928788 415154269 997772040 331644440 659479519 587709504 655014617 95687791 2711165 670566249 542356044 144886597 720796724 818177457 911725395 742893312 967443019 518709934 693252691 860446957 575627774 87618309 959252038 77876620 603481238 267525858 992948093 940743535 967176625 941224308 614463539 560793976 193967612 460530318 240984895 135835012 216762873 473674294 818820188 85000250 156883236 243778972 4456168 200313844 94855267 658349594 557632351 284051205 640073086 225768493 896369824 527809752 568531302 215545084 335425516 718787092 263038728 509868629 942186015 152905876 688883578 379173282 959425973 434146453 440499360 867807403 285539270 807221031 230653565 214814396 745363857 793831775 276353218 999950572 731118045 803992614 96229367 570577029 771044065 587650165 500613124 231956047 381989532 7326105 541247965 716130063 793058994 4540261 251855941 751974569 662778613 837716788 640805986 973403848 556172565 983759845 408668611 400298648 132997747 86294056 423945281 942007638 448990851 164069535 344689792 566507056 831646220 534891716 194341640 481258544 457321691 35269001 909188428 912412803 307701320 65143416 222354151 140611302 702323756 6287720 481132762 15676950 851349959 2498350 570186085 176779888 603245790 824625385 162851139 187082444 339731609 841980799 145828169 624361411 22396376 89027719 524494444 400612719 173332856 24999218 173135960 291467564 463565984 588212265 634563139 953507435 204420918 956698918 731087009 785260797 946788388 440107205 453629446 592410636 547765332 505047802 856250817 658194235 754297840 52325138 391673392 573899505 602544236 807079896 489072763 514637763 648661295 102655073 877895682 831628059 65181320 324963269 107646783 21434211 104973929 48287457 469383869 632069673 780006447 239323472 128544915 631954359 226717960 690757275 411198063 380388241 100832113 404450628 269433034 793223815 471560662 935815709 638154600 239613935 795668410 77584050 523496252 940253101 305262077 193381339 993035958 490426352 773609451 444248683 35738562 100852486 74686953 538569725 932837350 898444683 648718824 786219574 789672512 277357861 744124559 508511749 729224633 23657614 344562805 22305777 330783690 538604711 668289282 625447187 40206153 513935555 200493239 311086605 7332056 2469577 616695990 764150829 709797530 859741338 71917571 38704789 794162387 973913745 922978860 545623397 425573400 389471497 761511055 507236554 544654458 872380485 802086185 483248387 61849229 867271061 844774199 711009706 739061853 433189329 663872476 590534278 176757721 72904087 760497996 580278973 665655807 40012186 750186206 548281034 55057300 359138038 222393382 320865454 467640738 104945831 898110059 987914404 977131841 54265385 742084684 201297607 877898386 864454812 914055978 902533737 207785181 486666984 579224582 63738043 194067233 487447143 925115296 812221125 358404532 399536632 26082316 324995179 885913382 807472056 202841646 577293421 382638783 626536901 746365616 144132617 590033405 494406222 135070784 2267077 620503052 10170651 962200182 536986889 648463743 520165101 40891121 515458441 817887188 73306858 211625595 359782944 920832155 89017366 904189519 417486302 944114166 713869816 174207644 566402973 887157019 907821772 117865134 770294150 650783738 900175283 646304796 713655913 667792634 664237172 309941835 958798012 237441133 204257454 504041911 680871678 719640194 35258204 652913695 321494558 451856326 965718436 329473423 703468207 832839386 208645667 579194469 372887299 416583468 697526085 313336091 837810556 295084166 142733412 541808100 505314765 51025583 993498372 52225714 15731889 224696548 95044948 331479765 464250463 175160120 895597161 638721203 124841993 593958062 928489318 782412869 559800188 34280111 263567589 165600792 831238290 36504978 347283672 955201489 635559653 796637943 426993550 694372760 826533449 941686373 160153295 456370115 943407876 92529218 266979384 376717601 87832990 389219033 553117702 714735465 792600967 397581666 380053623 872062699 562859762 752840321 640204379 107952837 85531048 500513337 746147986 709707218 782251797 370705473 654234398 263935225 686178749 902750242 470314233 272782975 259122270 705535718 868111862 572594489 227543046 868693723 77232533 318308987 96892681 424959345 589468497 606891440 29698432 916478294 129718245 440463604 106218140 871440904 437375661 99880899 167316515 206762052 898751429 187878085 111701498 330362637 13553261 196090730 752415286 409218750 590448443 854818942 810433774 257504043 654275526 49300617 520464526 450612094 553065185 845988698 628313963 985160470 29740075 836876150 75792602 539747986 296407611 479801007 351842175 184060195 807274134 301274834 946429957 882847065 43544582 651835420 770342111 354777400 799367624 98281343 212436684 419801593 987641124 421999310 136297208 410259529 836466146 453794151 248717230 875591627 551197187 530018052 391133941 715425029 515404666 190565263 977107762 857860528 510099319 913161381 530341743 230441243 596208145 92130405 810333176 455528890 950654836 605141447 699103927 154056378 959433696 859853475 371545634 871689881 212516436 69474753 904175182 363637907 729036523 921065451 703433968 734508511 708067596 588374467 490820164 512598396 170278358 728198854 884616013 159979969 822994017 986239448 451475480 395480345 827577468 822154241 975495867 645809053 131451766 947998798 717777431 853216513 891627320 900973757 831576127 446649295 759545058 658387225 81122517 779853380 446755798 752539523 87193555 602863377 523087239 910533321 15820782 638572796 613447062 415850642 61673151 931379781 197434373 81706331 31944656 421284968 518946822 213482679 73490902 641162706 760076424 126651853 145524709 561016396 648477412 495750443 503995871 703069943 736881373 7268711 598521376 121985222 658528643 74851972 51441114 429723471 354637579 470623759 800244382 573894750 959530957 283911522 219722995 740792617 751716597 89903990 353869095 796928040 39109402 879483889 520696561 8040749 826685466 125255006 623394385 113898688 600588322 331259268 392717326 699261047 475684971 155197475 19671723 803330689 328398609 477005140 708638557 582810532 915248378 526678479 751369101 139081662 437816488 248114549 549537098 882995525 313629838 318007359 683792410 395706583 218441684 562377782 706994198 718710823 433377523 457474554 315272077 11950324 221851708 938954300 566098480 747960793 298382464 620312823 288830101 697945900 697560822 667034323 649024964 919845143 908139991 180257578 908766086 279553259 747600974 431793499 27561035 425313768 431189785 257154652 973017187 549208936 782267631 97784985 81800491 299355109 75530541 999047110 894897388 429500613 789669192 458674517 858054880 257855935 182775127 439549278 13013138 885653057 153289537 950719377 649219060 317903628 8935161 360518324 424548523 791712982 12063001 763680920 210356613 669049185 240875986 562987 105207265 232905658 704216831 50238128 806658464 650990999 657111478 994182807 836772324 706418671 389991112 571322414 697179344 170350370 588579190 145445485 720894793 213846124 718844948 954689042 846338336 647792784 294485620 707769995 510123955 494415734 85875221 780657506 302519978 427487148 514048053 656320019 284617998 573214100 18482326 399073260 966881085 729861201 881898333 364413442 337369667 67107913 91955458 183674029 401741611 446723926 88981247 231833967 328087852 684232956 749236235 369107281 291477386 783469957 668597240 828041472 702346383 37967278 144201928 200711365 295620653 44164258 318996570 188001222 210350226 471465809 95499417 962459187 460358700 921217798 824294236 383758971 654631909 154248797 472250032 727072357 684142411 708410246 678839294 159249318 579089870 962307209 234024226 59575432 245998522 364171219 91573131 836413021 684051445 690328785 975679294 218522276 214706826 648044169 134036028 767140200 240384079 90231272 152430603 61727058 929229679 118005459 320547488 339369453 318163914 484714874 396952122 37377208 888840988 627816512 991572003 472656604 617097614 544284824 770254036 236708272 31946813 216148961 804160021 962726358 231551056 555674665 315296746 17051334 797291749 609361693 26654017 808857764 623256271 763519958 288938268 529260354 912094567 279711296 309492710 373087595 207559125 129521207 363365470 418685769 567408245 603779424 636086876 665615016 104892385 608942912 762177112 376015294 454520688 636178828 163899376 430194043 513576911 839447953 545951672 118762803 658935797 288212545 613960018 594025633 458497257 908555803 262162544 311847237 268722101 552265370 129159326 488464240 882144133 447702170 851731821 76337754 502142488 354277689 185777666 785178656 699123931 181774226 93031348 713622862 958269884 735674908 30025582 145232376 841418275 6939994 416245236 152518998 674594892 278416635 676264966 643375833 977536746 668179165 151794070 879403348 452693549 11829486 721397075 480949057 159685635 532655082 940516869 683988865 136538918 132166538 924945691 219743274 510219838 701430630 507625422 782014561 925188556 415758411 10431085 418573639 398795828 622838821 119783234 31599520 779881546 843975881 190540348 434867083 394785665 128188459 33987971 142834714 367163114 434216425 178960610 51976331 974155589 975480836 337758422 757115738 44658169 571478429 153135118 121945026 14122448 753012948 576358863 781836625 439559103 647546416 436943829 602043950 213717543 8525542 394339828 77899351 546005374 840534644 204766379 68338995 373238390 912331403 425095672 529857501 515470797 618460824 435785135 192009067 565740031 144571909 877260794 361373407 774226289 654903271 543822168 20165736 921620956 10224962 216558643 933984199 980038092 525663090 531960795 378908483 159981766 306430151 562226621 342281276 975428508 351449241 646757733 47818046 608106160 737961184 26647296 838065176 466642674 60489443 512323489 506336741 95760365 411041043 96831709 785200544 51096125 964545438 751657654 843856107 681054495 121672264 413389842 866366914 483941224 925618399 475277243 400826691 901292802 192337716 193056194 908268341 325200113 208762722 876886235 478503663 474889763 770572024 734307493 240922123 673428040 492885265 4667938 659087468 863723981 681015196 657292873 181325270 16059987 809932055 141752778 642738290 677847680 71422824 510140889 633651526 267191524 571450597 762109021 325989195 775419563 847100087 423024118 110865558 769367101 64061141 18825098 951135147 815457996 922090504 449367883 62357583 42328892 162838990 325457883 246067887 654582549 775295670 982986398 510993034 934730984 667195702 812810423 933791510 129953870 918147195 922864685 943404991 925693800 90364392 191137324 736754312 556531142 427932692 47446827 492466534 107392292 353830328 391533000 638004100 226299147 570846579 276982366 646690517 476781981 325902836 12652087 393541004 776866140 825239662 571167223 810447531 122653287 451851452 772897682 65346773 760950310 385675450 438368168 558773108 183769517 378707262 189403181 227057433 249575341 533975277 422899763 25003131 779314263 863078851 39799523 124040969 985384744 85019633 265474827 682016143 755343364 375029405 342849151 385915080 650210530 70720801 228150634 530554359 426009938 539300410 860095564 845868140 124561461 948953200 437100791 540397192 740653078 299956082 677486379 327701844 994783781 809133808 422376388 611444720 667980849 993132758 521855002 151363604 996740169 102190607 17090830 331975311 610709870 97514893 676608272 590831728 694292740 658262167 20589223 689804612 532039896 119083696 278932886 244320055 870218414 55060846 392838896 893213992 177541304 538514841 523399566 753402720 936321784 908632623 544880345 891804779 785112572 528978412 115372473 828715753 461910456 861876216 609992209 528407212 346762840 168175528 234846661 143187233 494350839 170010810 456984783 817484635 886918396 210787298 216351073 44148944 908507939 379065459 399109882 920293866 428794095 591266740 539336168 723075384 283425517 406448789 50603491 453002483 248015704 927093219 206244294 699356048 770631559 502321542 443940291 75331517 857334126 14342298 876452281 130309584 115255865 801089596 111962395 832858945 167749034 691486830 553537410 441102666 356563878 465498610 108969508 137926254 262529933 190429127 811421552 373911139 35402044 407422705 679386354 359246998 105927292 485023427 293108000 128441564 261234740 256328927 897649517 779200531 422254153 505644280 361560917 572352414 13497374 301696338 767763753 730323593 291546919 843902323 723371765 486395126 387049024 81967952 586066556 7137318 652316594 208830870 641457146 183318915 97437756 101227583 488588389 40346076 949911838 942427888 183711614 559207559 57335012 23636782 377621772 767793635 91163500 842669086 306010330 455189767 797556298 127818907 138187351 25105862 786744553 207576221 23916087 576611637 969032794 219844064 189108328 821175227 779873491 959842496 944242818 244641439 655387127 463126731 353592436 575404676 359920207 322456120 50946036 719047581 815525070 642903365 736493863 90200790 166589839 154570398 156009630 424004173 413499944 672000104 835217994 458694918 733494596 910649845 25781456 905367524 428000156 603063928 470695121 226549715 556479393 814003838 679406334 943751559 528752456 450817702 230619092 796873097 367851613 840587734 827177889 632067362 153511682 284535061 686827989 811482600 432965802 663401484 309888092 491559360 612670136 402495224 371655457 474353082 709145379 484968560 33298019 358887968 57655825 907248804 107763832 189698012 447145499 686203802 296533310 645712926 427130773 568219925 200830298 431465275 908307888 578608004 486830131 915233670 253636304 855073177 582620250 982806691 779440480 764687071 78916360 756243131 272372648 808325721 840835158 331290416 642032661 476145530 383757044 450009893 713839313 358036255 686660577 941065269 115638259 547092630 99761994 454363873 955714544 687258462 606767504 297482214 881105899 125466932 636917933 140065644 526355198 430111538 319512401 333274189 340408481 563466367 139040838 31024834 770926564 655991049 15557884 394331570 363968389 519068156 477578946 951444686 927287938 60513960 939721764 158353990 771627035 808084380 574535236 489290800 902769839 580238057 235460118 478371875 325900208 501044302 719736737 985898632 488767610 182948610 68699623 94754825 217790310 796266687 698437782 91069086 126715172 683151053 962073143 470443190 648382746 65754047 17019802 526957762 239642914 68804955 530670790 190748540 10619374 888514233 892983021 727617039 663898871 91779740 640950127 704042423 829151139 327877266 70090802 394881790 109304141 247864769 742562532 427656911 920132638 95561435 472009223 631854807 952345040 117666190 433043457 155233328 110567262 714779438 304637627 228361084 983008672 44554229 288258180 249565582 643686254 32661497 796422389 349534460 598565318 764223732 712604243 834358960 835564625 356960571 716341914 436983878 933618767 305238353 90825182 909952475 299838539 986404695 256246223 931995971 147797647 840636027 474384383 357256314 779177069 533493349 770285476 900029305 890402680 588374410 650758111 338835096 693840036 835098785 588085187 252079911 980493642 954526053 852590630 902151617 108207673 821586242 317279811 122883438 596872659 275751849 455517495 576945862 467315881 473282759 503239397 448133623 689880202 502392461 197666445 312378454 566449967 356450350 422347899 124641587 131785459 677420153 623049044 490405222 648570350 371066229 322714217 387564785 226000843 292810190 883703051 510140901 695181778 382379529 425390196 413589929 588771015 489115118 593501066 268276992 815585630 814988859 538789403 134748697 815234048 133573205 34447921 123252546 247691616 938732838 399207372 740555511 85068437 806753886 167152781 532553572 965444421 745568235 657629837 146273412 395580465 771590069 506119549 458546599 197446509 971112303 392211391 290876017 299372535 215558982 778267970 247706431 315931807 516959819 379141587 573077533 417559953 128709773 23035259 426284578 974696948 499960366 334331059 122188846 140084976 729124804 944367363 854270384 451112671 201059965 744218921 535745830 107122986 700882639 172364530 987812965 478390235 304514213 59070795 677555260 794517862 24061685 913531005 254916499 460290252 79463791 919451441 160218086 928230345 490899218 909074533 655265757 707437332 71689336 978119608 196992693 42256794 214826645 72100611 853724982 147548432 1497466 555022078 788577430 175243599 627385639 991297618 219062948 778113227 898137499 222224198 399808434 872637445 863963622 504140531 138389462 431286884 82821246 144536318 252714446 886173513 774128107 798091068 48878817 320978580 928377075 750804431 111429220 522240103 459421664 698054883 651048803 506848979 713090618 601723081 202438073 104048204 795277112 739869605 61373587 921531679 66855771 656535119 831380105 724055161 292914426 660704019 868973516 436303476 814320182 526541858 717538256 266650345 948916340 663939991 724599383 367713356 285416109 406485952 138244716 925893328 252958857 496269920 27515745 549332767 236451408 874856862 529876461 19165574 155138451 68226941 884047272 459807883 716530892 520595693 727399293 516325368 247452554 423885676 655180650 723829955 840913471 957781034 635800343 649465757 635900720 812596539 293389711 977219298 94956565 948759575 138420649 945018406 799844480 964519097 523200787 157802644 705063642 115259219 593425853 598960013 727984173 403771335 884133634 271735878 944500477 646681514 986550820 770811313 918369673 732164669 917654418 441059942 48306201 548879113 203330036 134428736 274718317 386178139 736061308 506475237 524797522 475633899 165570677 946526538 440862805 115058580 641725771 282057301 752930063 434759989 641869237 995790115 773800449 340180259 574173695 416241628 811438192 300258963 537287189 516424483 601513721 229867236 702658857 592587095 420021828 268821973 383313440 129175376 188322248 339940183 6178897 185492110 558237431 545729071 800679705 260471122 527108365 88946448 173372908 616441240 672681657 527215808 187743911 874384933 300254930 885522952 798217491 829703556 444460593 872821618 933873950 515706324 541646054 326097682 489608876 36357330 677583052 748178492 413087095 909247543 306789293 66958404 850631975 365018411 656317093 834853636 156856770 129864646 856694798 397292325 774110054 522910674 37996678 200171753 895751970 97530283 495876474 984011139 942884833 226593101 565417289 775976399 164372274 220007621 541867698 331391138 910195115 673826686 222930883 631764537 709535692 558565543 429262601 820323 346082487 899579103 860726492 637957805 439085209 919964944 334613342 788054507 586592493 91421822 736566672 993248182 597244557 237096077 15819532 421278337 26292599 841082742 445141555 239514523 235977889 955581967 785480710 641969689 848276352 939591443 846574425 177240951 288954041 633921717 607223377 107695352 78960740 239167971 245356496 788756089 371527974 968119133 132008385 123861498 457144384 536913877 921054253 43632916 203981018 486203626 67523877 310611199 7867265 665882318 544044182 234437886 166061574 767017112 328879364 860684566 254972617 490337955 244878441 922471405 163760019 885955020 836383698 645268014 889311568 666572307 765395990 267202460 558756936 707899450 620398679 43455263 412677538 907050421 154413840 877971258 910845272 66260050 479528779 700948913 621712140 873787278 513253538 580710426 170528358 815854879 3345123 730404662 342939018 557776779 333974801 180410770 953144588 461269736 578722062 116045957 247030594 179226123 631801333 825317734 407225024 750739858 579986051 733113499 680354350 755217016 970810383 122189732 893298713 803343652 153090188 508128669 512652528 714433995 927743734 629658722 899327718 382751886 216422094 47383875 392224831 400023831 744577660 450545622 209313940 205554974 715377110 391364716 499798749 260638060 336432445 706986522 523639353 554188067 840050031 446421064 177365728 335863316 733944647 256845302 162221861 464920386 851428317 749424658 907998139 889064665 692138571 22286653 441213702 377895422 723891871 300171304 756618681 999513458 666941310 91391138 885027647 96394649 640890684 899839019 122683668 859356274 893641601 998706343 272196127 889525338 170047133 862658038 270460968 955396638 314104305 760525202 516196041 89043434 47481910 335810434 82449738 575010892 497278866 148843894 401941092 45227956 797250903 505628569 255004910 778523691 258987353 356052140 4730938 43743308 260526062 631752361 255912055 986030070 309041217 20015015 354031369 123030278 299588519 384524518 32844667 532402075 335522510 988553310 882172045 703721903 610671662 939822446 554757972 211868253 194290745 430742205 557126797 72681203 420533950 178750782 494129177 663491952 427647786 984637803 382620699 325254584 124229586 16081918 569309574 678520952 869924046 486918480 162291151 947827516 505096893 684566671 896635646 642770316 790052772 312292634 500317840 807140522 734614640 240241028 314165907 981257120 178929849 917139525 272642770 620718782 338086873 26247415 40827623 504564819 651470619 706156825 295375699 799786810 242570312 50824020 485506381 236847747 208284759 638845670 243211365 184698758 955154592 845800099 833123062 148249714 850467114 140964021 250336792 682948566 661189154 338679818 54014770 23530777 411921820 459137662 220336974 398144033 769500395 900134194 107054467 645285982 502090890 166202698 411079113 316583828 548541799 525851680 373399264 411622049 39450395 81154527 768040494 87485000 596189109 691476644 382218332 301934950 234011021 538548854 21513446 117204296 819385885 519783555 154670219 349357211 734939289 102225826 164513939 30633549 815533986 771416394 178235633 964334379 126032348 378774008 370191516 293682412 53333379 326628063 779427782 766702105 334973591 389261585 112202680 986778370 748340122 401441027 298289353 440345419 916401528 344910203 399365550 229246076 698515363 852294244 699010828 603853914 843428515 719975707 810155190 80621483 527617593 914121823 304621233 76513557 151916523 429370887 154720745 549651050 680829525 199766447 493892462 33761818 596568782 442382636 777237079 85983451 127099277 214821621 337402137 377323195 113693475 521320175 111448921 193877440 762318721 362984208 648111681 62337037 486973540 710753351 500038699 867903479 306837638 219547186 745563224 424647681 176792228 990781645 289631743 110221450 522671445 104989736 735636177 881627231 502113611 213505032 528082709 687870165 212173434 315731889 720207021 473647377 698488615 691201951 238059856 725789949 776566399 867366810 804876019 154930715 400683855 93572459 668872208 751496056 686045035 830936817 187195743 491972893 694319748 275595145 241073344 725908132 323007438 673960382 445874203 786949836 40024480 454591025 897837850 973505795 238186277 612623098 761204241 14605258 63442563 164633616 677118746 827362630 385776994 867232600 601056137 852259476 422661206 571982554 286191856 358657408 177665282 633546998 447809329 646540276 738325939 886062357 544428311 966332423 839726797 80042930 906022012 965673303 878262274 631680689 341889611 698430355 709416726 147799170 463896843 91901606 211331662 245256121 454059938 760943220 984549367 314063474 241308392 136402428 766124887 656209721 949788816 924099043 396158352 123463369 896967134 618429794 637374089 876001508 923666417 924475642 714617157 436431567 262029042 215841260 388859505 295337007 288112555 855086585 920017366 913326617 454797733 382514514 358430976 586944288 89522874 180762231 151936321 411969155 597282751 336361020 282434089 198003462 630415434 6255295 47583942 765293707 593282251 273901830 330619984 174763765 80925331 575090253 661617532 807573125 944832267 604653066 983073828 783159937 404329501 541758164 850436738 668410124 829903076 784838313 654681564 525092026 238739938 788611900 770415863 825096196 267976084 346982702 989595339 721459328 658364981 136628840 860013959 787479472 205808197 656187945 465668478 124274508 113060852 5895822 481149159 130365936 699632721 267374426 513030933 416628369 83137787 672512687 36180211 291890746 106148650 296696063 486654502 965938648 754974257 41654925 103893745 98332731 280246602 317662785 272654081 309867440 569289371 352174100 870606938 967500910 165952139 487203571 420685620 194514404 794951748 46188050 698330377 809784755 723304058 175575727 587280066 308429372 520273718 37845293 451156844 495936290 361090585 652125546 678457768 415882559 347175270 524545127 233649399 659095430 625174070 310574123 712552683 857210635 101816160 961318990 75355720 565787192 620519163 969027008 261471326 939261460 827372921 708035015 904183540 829176272 982608739 458557545 816108075 805310279 114717617 95947067 268293471 558102635 258582948 57805837 84005308 270348425 519099550 99183440 694159610 93615688 572517879 387023278 740907200 334119710 473634831 362765718 6597155 145629609 59807976 836381787 417322295 140238615 79829557 920647902 833349768 118043672 649016929 375591622 733176750 863357592 31081979 283293922 66562806 214852873 121294875 105786902 953809309 92786399 598479612 239057978 603110599 241042849 191274933 706331676 121115025 700775034 208584939 659447702 612363803 524734733 768454010 332785958 99719895 500326600 562733982 209980922 671754802 720542999 164667227 576376678 213764530 481988681 347502217 809979415 265954075 896026349 446547647 373368038 742538164 666524022 132251057 336066577 259360391 973486987 356530827 16701276 805040468 487049033 247818603 63526952 333639240 272399316 93352105 955611160 412316527 862132954 504744415 17002566 52772518 546087943 452467284 601976337 391525235 358461401 857363249 519709972 579159694 128292281 97774742 735840528 94577068 149848509 230580086 167469717 998384941 636606985 220333 578596848 277363138 941746539 977203135 802191052 639210574 721757290 964136407 918904525 3504245 173627985 375178121 5416819 467410492 217940191 233022208 138570371 524041814 970954874 687395359 930369328 298073181 367932427 511964158 468478353 645229470 513966440 900068283 595797601 277911557 459132751 676916317 989791612 972334441 360367468 110823252 263585674 97472635 792991955 326594860 831844212 163521981 154279157 840427588 128879609 137978835 592896560 662616638 941640428 464018886 548189878 248058360 603770700 136555299 22951216 89504557 225993317 588293225 976764026 62886341 197415115 941480875 900474643 700945795 858848038 351938218 593791099 739099329 331789218 338664115 520599240 867029740 914780615 159357220 314057565 282085809 83276754 587354892 915245570 214546112 284496235 117659675 982006676 677873632 763182001 247528131 800818375 348432567 408837468 560333780 823544548 293443070 207524312 746028777 330513299 954783819 881470703 557036716 83764091 226795340 40177282 517758173 201446627 975188490 378645387 932420445 602992214 260769423 385543093 286750788 877358467 414117457 307837660 126274056 998693008 685952496 153217941 820175691 948985137 881820126 800828452 802073634 950300204 736963645 596926904 479028353 159316684 769384104 12648381 571154417 860455227 281978368 124975131 480305254 937913806 825987583 55097595 661707185 390474036 525331516 515628142 720148494 289541842 854847630 747439143 832820288 715321857 971287697 378376170 441718446 38704646 625497172 676665435 678359517 419791251 490006191 460767803 119377658 456341471 745237027 779507616 384732594 485471578 39891300 587793904 366360090 114457472 871179846 558062302 752566914 78014049 679542110 24647104 596004619 618616223 151669292 360904694 904579003 24733108 979594101 737256707 565722941 226459747 181644002 133243993 884413928 213173346 874904044 991726276 997120502 952743261 529199925 312198862 635668518 567495095 423499184 691264481 720748092 99212753 311148110 651352459 696581160 72022183 794901535 479573154 346394663 981354681 987250779 980999964 159503507 961662670 229875212 232679481 610796965 772343811 423695378 143148977 978378939 612144351 989962680 159461735 17229166 852731475 343300045 953524197 464320392 431389664 246309606 856869644 671972597 752276140 70717887 823714769 873170529 106680535 674297270 417390703 184020963 418701644 332953567 431809993 603769349 8177010 283506759 131639412 365665377 759296843 927179097 453488678 773850379 337340074 533548100 446458796 18153994 132330249 217440231 866238978 267118456 157449928 137418926 829405784 205294619 376124510 795402926 271765630 815186772 796233973 838420895 785593668 295488796 548172465 130093194 844134320 178981686 213329873 241507514 333995445 532717764 912403274 741475627 459159166 520249641 500283185 815565509 975103908 111298751 148832872 600081862 590932104 399247760 921434838 161403464 47208208 955448997 994980905 626639024 19496306 188511626 641233328 82554931 347802488 903097475 381736340 761962665 424856579 210046518 458563116 474793824 693286913 866735138 496127318 182161050 462453627 73044749 255699179 408958670 758258006 255127968 940306815 933440674 277762584 134880938 195452448 51227980 618982668 807287402 504498708 570544546 428715939 874355590 524091127 254949339 291118208 761421984 904012410 206838503 422015715 393145317 413918994 907549252 59687383 128606702 561321871 391442767 45629482 406228586 473808933 62639828 862904253 34834586 957173312 804961595 269560613 225442409 171652737 364468704 53131523 323661203 231343885 145476583 861815504 313030832 333995610 304635437 466657093 78798198 359378691 154479400 704461112 173854458 609283812 901184854 182288795 612719585 311027731 165120525 308193444 736441249 177778736 153610687 346650376 916441938 933323435 769328708 105726339 153697075 640303039 61299402 67638988 37850346 477794470 297552986 950109845 767559883 982598917 972134890 563294165 608620132 531688779 643045172 850454323 389135316 280227615 470005067 647947773 468711182 555729804 542334839 748112888 940077669 742489113 184406627 951127586 789331560 563104892 93855029 101509131 936861800 335164611 678868890 391872637 182987603 348328218 506387081 830018922 869715814 306662940 792437066 22961154 788600143 873473016 84901513 966628651 708722638 659035179 652363902 492325874 368045120 478948153 538227718 706064119 189273498 95303405 358169705 968599818 56214745 424301596 115993373 519362172 697168271 34428605 55109167 807591061 714291060 801400048 346323320 103070421 394119073 987462356 840770628 321150887 109557786 764077835 313043443 532535263 883832553 407988823 549243699 204607842 742476203 566774515 629156316 522542634 282893123 93763592 989403656 45127185 85770942 13698349 580009550 820309946 317250763 281860514 705643907 32550662 692018617 542484784 12284089 954697469 289606554 483666463 962942395 924511969 273817422 881721529 394017979 386194372 832953561 290816467 687212723 784740258 987487517 940534347 736587943 864855342 865187959 142242089 11825024 519410181 141936540 170417118 154069618 851584630 727386455 363988509 823419461 291921814 901525107 475828354 622143775 850954533 964721700 971291186 683049578 744030097 381942067 249982421 543978667 101304143 653294852 585032912 138139489 586898739 343449384 230284606 622785969 566428940 621172266 569384592 761880059 962936976 477034500 779201064 595889694 747366200 153703240 11144601 336515103 94608495 209067596 744836494 159433050 576863751 384207732 194346062 678698732 608921645 915577298 292007411 986868680 796867835 602850213 671221873 711652682 761170759 758833873 150175895 332549460 325044631 797543532 779514535 432682015 135498235 709745343 78710628 885928004 515385234 758311975 78708975 899882007 640398759 233631992 796758989 397965546 452391308 694355310 457861106 320390181 722454291 362761822 752862833 649735339 479058797 66206183 924999948 834616721 425092112 691671084 313790666 253427603 447820575 873391753 192260953 655014482 702765493 109794925 890182649 426908819 59503976 944130440 676431656 761576045 333140949 139489161 390363952 639499405 687544028 210771025 850484207 14047591 224286282 967955543 287722697 131243909 23345942 978580742 612662397 222652963 458257525 725418841 775665970 153550123 761718445 197500098 719539331 903527408 883538652 391047915 516321320 96282864 861128023 718036240 917314300 12270960 509825098 882324349 587555790 588596398 294446354 634458891 500026558 487281209 31651081 272191955 865951746 654613455 906690712 873294047 983561398 450542043 875742938 442187273 959737616 893047225 106731748 704402218 363962661 773939795 224463412 267913133 543666372 239293681 907651003 844534406 780524111 210706424 543186965 559041778 132392937 410505051 51979220 225870238 793313227 237209682 524499482 269509051 147223897 482236052 674606696 223917860 458430143 966690659 673284872 990313738 760925623 118974015 132584825 597095685 511032170 743483999 964571645 41349470 91186358 578856339 706125423 573000613 894187270 469154661 724093053 940560566 738503768 907515069 444773786 387416624 498613683 669902659 799552857 923584031 547265738 909729979 218001920 618121185 58413343 750806892 516494978 3577196 541844538 905020515 183497333 587323195 907289212 890912965 27202200 804546174 597669925 12976902 855241450 270735144 850291942 32276329 328816150 696184254 79422558 285584311 672736863 416030081 76747552 539301584 145248630 817996508 809393055 333119155 348375256 864846624 643307903 47859193 822852785 803448028 170777715 452803118 174673841 318274327 799552388 391190021 449771787 473382455 641061345 724474938 507859518 925153626 170006691 602657373 714727988 389829965 418195846 544083031 355977457 962140880 621338232 86018125 756575051 249252659 606409895 421992920 545427099 362927117 638249354 53900087 423265487 418009913 79689459 855309126 920569746 766180266 45796503 398718942 623385577 591583596 729178209 586068497 26441345 15528549 612700909 29756212 397238451 772610497 628312557 362614004 181708049 940031171 887840522 162658043 769582946 472845315 180283911 882066974 640361078 710670007 335786097 233787366 920203375 222723773 50965403 385801411 471617481 930419222 963756902 88437699 867611046 441547817 125257212 223479332 40117607 330771633 288386970 681893893 870626797 634808951 305180580 563524326 694655519 96530815 434156578 77324076 860816005 265989257 390456266 49435417 87921944 580583205 627459256 648583306 37270710 433720429 217607744 387737476 312144218 419150258 437666947 963095728 590217033 321137640 992864325 815095180 649213636 369107065 134216954 877954387 863358489 555773188 970000655 468904446 154110934 936904559 835885880 7219875 641816123 301408349 99130410 703567701 312297933 280958006 316406673 602044085 423040504 930885699 186440777 616471345 261890141 886748787 914467974 878167035 814141226 357407227 75404596 564625276 335063640 619014933 549881057 179740370 76427580 755677099 686445143 563118380 478266648 806069004 170844468 531745718 630808156 74437693 192398120 467359453 259458962 306341069 150485744 331077723 488445449 14023447 417003155 387491950 668597444 184303579 329530975 430077233 681179565 509275974 312821793 735196052 187149046 227317243 209395903 898056298 541859581 42455974 468316486 754106518 352696728 806707478 625309149 300768524 970961533 520352665 929453283 327081779 23880800 949482677 43377083 880984375 9152096 131685173 500393502 868801191 793592237 374964268 209435825 215401755 389298377 735677855 96239636 17921239 320494123 752020822 901678473 225046719 368133382 560444293 876213766 577008253 993133723 573962661 562197114 783658034 555845921 799664116 136487371 886317499 515181660 314079179 933762126 425369121 184701639 506980925 330016009 928576589 951952481 333996613 476590766 202000529 308363630 51248266 345392151 865854167 742895528 572559709 680320498 916236810 781297981 648522381 540884194 892293012 561395211 778319362 994773223 504647108 700254554 708522489 255828399 493528536 580620991 617550732 409700350 288481878 518557245 295268308 531068160 144269931 891235495 441929162 700864703 180738417 857691078 777537959 389956508 869857278 225642289 115021215 516865660 527161999 678093603 528067306 952999356 915776242 659755705 340205360 344860497 960526596 256363051 127722529 496529967 497799794 776212648 962240828 77733806 56906686 726850826 448692375 906915805 339995709 383101702 206818178 221634265 825087763 46114711 108188045 87507970 674034309 666955603 687960868 203564563 53184031 554153934 134911494 722873234 248907404 413586608 497206328 55120584 666421453 643942250 807013335 512700699 329577364 755234461 155653826 772178848 177232668 881165575 679393699 404245787 478824219 835763757 189605317 737531264 590022736 792050472 602489390 50476311 108213431 562411887 340919888 811508856 757638477 675940435 413529763 720904419 171155617 584300646 92381117 921867524 556193148 426138398 236964986 238252901 911447141 430977035 427131971 794280553 156234825 334004339 225735249 148879522 615416125 623000720 206889199 321592709 408072289 411452257 803176859 890759347 883946124 193667856 991544113 604603854 266496021 72170474 221403045 252306250 891644113 828624336 869664182 558944189 344356698 201746347 870692107 142243272 894718620 510470255 853412170 87144372 473708746 687017905 721965550 502934313 445909959 858527884 647402570 759397730 757410444 302245280 818044118 429644193 927746267 934687228 165611810 905996732 117643770 986590856 136766746 723495471 305983301 833935969 159517752 485555896 566605206 380709159 975765346 272186966 623154586 310302005 75742843 560639644 493415376 134067672 549371027 548808460 694596722 706641808 285754558 8305443 568424746 707979959 594427725 346377056 999551725 680945552 948812701 684455800 56994197 451622763 860875507 620054012 928578226 569609990 582469695 749159652 352970966 650017002 611009394 84024205 689523051 14050228 208846018 407160695 332694000 99318069 143469118 877711279 325413624 776268784 217899499 236661428 324603515 486542162 384411770 466527277 230470918 627055301 718886124 330733453 840632352 968974705 422218237 348352151 612532486 511097361 91305156 915250889 476417430 961391464 373471840 491794894 149750146 237598129 723921998 118640522 235381323 175360211 222786434 966972708 368321544 39584510 910003893 841641032 405837390 913212735 408488565 89144474 737132264 731959178 609137082 122316209 545016 581141061 435718563 310601652 255237684 655099353 208727749 840808190 344915433 127629061 446202792 921353898 421369954 300356928 19565570 778245691 719810206 181162154 497025419 946627756 488974806 698561805 389463334 926124073 834436187 953809683 976764850 339715298 65463978 68336134 349876384 810504956 906570846 607545520 665338762 627711219 575605991 305772149 197848882 903822823 65774703 462208788 834360264 371343584 484013128 537186596 572213928 22558220 351510909 591263236 591214649 981628646 216520361 349649034 485163940 839471556 599934788 670691374 10163168 732137346 227554472 393112497 194654575 779208734 283907411 829421079 322332110 297190814 332796464 774260650 658603277 281301000 317199256 517952476 209218069 201014024 856251792 522689358 309436514 464593393 138749528 196099771 432285599 155054902 520041038 932996024 232417877 460157883 319520558 655912199 801822474 540257978 180643670 377122311 403776590 506448257 885338281 655034361 797002851 955813845 630131245 540174977 804389381 720539674 633164195 153755376 301469771 995666608 30688347 594789175 467454974 4075227 671381780 899350467 234076718 345572666 732486859 342542436 666233321 511531283 565991729 837084269 33228714 513935992 208911955 372258757 462432105 888093319 354958713 154420459 256386280 274701909 713809631 834694632 553486848 33687394 35278880 186990735 812658201 732764030 127849106 386748585 174043850 408417325 97961197 472651473 520716560 63082762 173111496 873080537 277260394 37490249 659260419 464055724 340866754 744754713 71583223 500111065 800623768 208018918 52115910 771881971 271267278 65546260 155027146 784219404 332000679 301534902 166848513 234349346 827877041 920881209 579401323 881799546 796439110 240206634 665364613 339494318 447549012 295158705 4331328 466022656 320652254 795685916 805234385 383438400 372942229 510611326 886588768 66887464 398185938 180894483 722706586 828982459 535306564 704818175 315177344 555742586 764908891 473957766 753620170 319657212 504726537 158219341 250519462 435858204 648671143 819711142 379459867 4751610 964257597 716794396 690834344 536185280 965675603 447637514 530461600 882282196 664460154 771428788 15391363 944155712 586077484 915814254 160717591 164206181 209746488 759241542 40444476 487535860 199413676 526246036 908798226 495872192 665299020 473630863 804258450 962872297 397152610 302902773 272926277 483166903 338900442 631854338 304796016 809871802 72805369 231586868 406295667 300167616 540265318 298967184 572045076 497724807 929627572 454095491 33823600 699016052 9613518 191516632 502867072 580014495 646547536 270734630 112572987 900168583 465219488 754337031 305939740 797460757 547604068 349673009 556113561 111952603 777368192 203768526 769837345 109821890 722047194 985714751 767560993 686893137 194882412 652230317 57818178 115638302 682164797 85300863 994829896 144123155 477759112 660024485 321545953 609919968 175479302 767067097 977117895 651938373 261340182 915839886 855541568 317355923 321419592 555397405 565259626 691350642 766536927 14557841 687499469 123985065 971931850 558376058 175443320 931966970 176573616 362069223 490483869 61919861 686307490 960600552 599932679 323914158 377580784 870563947 190091811 838270508 721777064 778179843 13056785 970970635 903081765 946056017 393694065 479533224 920294226 311443663 61005496 845074757 637610894 121430525 513631532 724735491 17516494 506693918 777559123 24707688 220184975 135028536 811841828 915529756 603951989 155317748 62334117 325134174 600355772 779774227 200048672 9798771 767729186 459933409 590012848 26489394 123771690 466443431 308652141 321600620 209457149 440100414 612020334 489707615 850498713 82382898 380324651 705213688 636970526 637054041 595130571 252408405 899737861 808029673 157555532 309637897 215032794 76132755 922989718 979307554 794026985 470379434 930947607 976139214 437751894 174034793 792139194 751495361 812984213 467697287 96645759 859063668 346375797 88837346 561326736 311032006 675233796 760314078 341008573 213807461 989323952 204664487 92130415 581456346 127089044 886577394 9549364 167923861 560887060 283114082 890039781 11463219 919466315 846964444 821236792 703767561 670058539 998056354 250122189 609070484 708857851 853969019 375002587 896164354 589326356 549080282 428623834 440491969 687766615 201465627 731593998 221954576 351245223 657102241 265431517 836312036 411184621 249196963 647917467 690770350 583014425 781930538 866801240 614760968 894086698 854695316 327411223 346806453 358700024 399111566 726800871 974129683 707897626 607132368 102547311 21574900 777760327 696284190 206061816 713952652 939938143 71703858 643771153 704496595 474047847 528608188 303612068 755617089 581911812 12545647 760192114 336156810 485183311 505494087 939530352 893363606 292314910 826390370 811465243 744173322 311262914 141133199 45744288 214090649 783575809 935837137 572953596 85639863 732893917 623112189 846437308 428388974 30353913 79939108 982645910 270771976 299784044 567703781 910574745 757046408 649357594 701598378 939922010 672646853 212005894 968414157 293766495 598074772 686585877 572970560 180040923 863037612 880383659 234302368 416670703 129796835 564313569 803332324 947211425 301855775 243616438 388523553 965906149 553613924 207725553 952723010 751084886 544806420 315474855 143644275 14162105 987048626 548148866 198676410 996220054 445422892 355777648 51131373 16705105 205314748 240738372 478436963 847115111 509173440 869679250 50022073 464531973 571556833 792252028 781022326 31979896 6156591 434372119 130318869 60141843 642093039 927375670 642831454 856333120 770171905 328114348 768106418 33481818 401080293 889657028 188463081 770384491 845354506 491304371 547862124 966877085 976742191 864511656 332076310 338744758 891823920 923117293 381159299 971521315 692368561 928077563 319230675 913019467 837851777 552339710 43464619 68716338 73843958 227659121 206405550 755617768 106842781 286172903 356979352 333063213 814244191 332778774 508679075 508321359 471341904 636679962 195348862 951096930 140155564 632930442 289101734 352211821 853898519 696441457 116573468 386844045 335020780 536376935 685213383 951176372 560814838 760618102 672506646 485924469 195452837 171735717 641405629 471027446 343136097 7646107 873238767 238146326 418085972 990269660 638680950 660040163 8745892 710392614 783474646 728039281 909231874 12647294 174438037 252367215 610944729 853351816 620119381 659280469 517768467 156282159 751488943 660276175 28605024 617712462 749852085 805965837 471543526 60735809 273662950 892905833 115815896 88099413 329134578 100251470 677764321 623974008 2162123 595268718 261059448 855165625 618310998 271518696 572292080 950290522 926362607 83357922 715888119 669396223 497723626 224343841 275563676 889642405 942887269 235059869 88879648 485340043 966614367 358016641 245862341 438851588 494509055 462997488 456424828 830626818 81800036 452211334 797664975 428869891 216302750 638307972 113560892 318070683 436531918 349893307 717461866 161546600 932452969 157773091 553160154 447487349 837362906 305108538 198749570 95071589 384952701 56108048 568884013 819520817 298836941 273266090 556280365 409351491 40362164 194725150 749784134 242815932 743777302 366944426 907076288 723281969 818545578 634431886 36495520 655203974 215511803 681315828 287818067 14922345 648858511 564520749 735047881 305297258 482601193 346717189 994530430 127304570 987433929 493172287 747378723 184184898 23461662 208702566 837752067 129010240 421633066 985769387 538762557 412070978 605950768 718398932 391798300 263428891 867450908 364331699 853626439 196079116 615790358 663584357 131252193 590979788 739732718 991454787 809379254 71309443 304552889 88331682 505542629 705419405 801444524 601571873 397185778 350341594 421488732 572894856 684769870 462613906 216986150 322803742 460622029 957357940 417261961 34214774 54243076 163113720 927755513 267827584 232024938 302633517 946396468 108831903 606709823 155485676 148621808 406037080 560262819 565309707 527172534 117387292 670234890 700227559 61119751 371208235 922368610 105570923 544035481 153340955 655833351 829216342 933852842 101345878 817290333 22885200 637859277 64276641 879510296 33024469 819349620 886204297 160655758 344840788 417637987 193519456 32611070 318051087 415021681 139857317 342915934 381730372 201366778 156364948 950367632 312272777 103144953 671996603 104855275 44767512 690560494 9904436 580119241 130355626 204930073 275071548 300559206 704422693 990511519 193083741 59235557 314988144 18798751 516898883 907719055 735608096 60735914 505952127 55456966 909616969 751750948 472286849 132065726 699668367 919486172 752417813 487112730 740593096 422239172 853565411 504295883 604828441 143709391 444055835 125926607 624352810 298670133 313165205 517539460 887001525 948327000 726778984 157911647 565726757 247852140 913164304 659939168 107190574 237834965 930378534 790825286 29268735 410507599 634502478 690591367 661837605 529935666 601395564 802986542 857192152 908897876 390198340 393939412 34314690 541457802 311164580 853006917 10970418 124694281 211061367 859876779 411285680 443760984 300515686 911137264 992375736 926545962 279543824 774637491 310632518 78044737 418535022 528963570 205894985 914821014 618443854 405268527 766236293 159938659 991126457 605539782 77268640 40532876 352461085 41373733 592742957 554193710 2366456 897624798 689485550 352898477 162051364 495435053 870234825 881093506 715255396 160826240 318134404 152713709 419368096 905506170 432333681 679087664 879807561 689206188 994359777 123573040 3047969 564693330 766319927 666936116 176408695 654098967 928763199 481843615 988621668 667697948 794692232 756383404 113323814 959240538 333073456 916902345 691501493 247000516 951971408 351336818 871884020 329772387 346460086 687987526 554005881 917552686 461790281 12027826 785653833 372209882 783657425 975025030 227300339 564774723 457205863 954908092 707040467 56070984 714830600 58742405 587188674 481863065 384944302 839353354 662931527 570214640 982338981 91869265 96268175 794366443 814109283 472026821 431654670 139677711 619026686 552819537 967607884 551578743 277077141 212235318 78737925 956140487 143182148 598604056 959449951 451524757 113345997 253360379 237931549 411247513 730815612 747524198 886568530 973252758 50130967 814517524 642881371 732263430 394611236 561898647 617935094 584561740 13924199 493644054 741907474 296128718 960687326 4702239 990116490 148643757 89938797 512525393 378574969 37360615 785202269 54038720 479773546 949925548 355816914 132575314 309537372 54750248 225788309 774452880 707897496 461600824 745672032 944294148 286997160 138805288 513481576 939006524 606788043 183997642 350141845 885401420 380527495 281930711 915795422 295980407 848332488 782383737 990721005 524433681 601506005 785789730 911354192 579486017 479727162 406101237 789622848 98053936 796867967 964383285 364640596 214050592 642848314 896455703 446448117 149144198 492472064 229638011 706504677 102195779 875550610 11810879 824151836 928772548 593142459 28086839 53192521 673792456 557765034 464378160 166503936 225134730 614443705 861110973 434044580 860444609 976076860 736821357 936885449 343581853 787366353 763372208 643787565 788950017 228945799 714136488 360312828 808314386 747927281 960557224 956055113 701297542 999620319 180367211 670641136 760822843 853689995 245840207 772381970 217997387 143854495 503042767 554024676 341563536 599575357 216494186 63158108 4138663 238462273 161522038 244007559 611561997 239874884 97649113 784819925 736627552 29005119 649352374 510034966 615962638 940632220 182059229 161725869 580553802 733323533 629180498 261574826 883929179 440293953 353797635 68549111 585408325 704656038 488225586 426679007 283714215 697576182 785908296 815196435 876983980 388937694 113287998 476700604 96639152 542088248 798038351 282344331 813857821 242473881 624348503 175818334 906680399 194492528 3004975 402313264 103286542 931531861 486853805 897974052 871351406 13917950 544972200 500425398 246964473 456829275 32120131 642263174 303418655 469528761 797239580 269785679 382807644 682829254 333656278 531722624 952856976 599942555 523194338 65556476 397347113 756188918 371077201 626532915 723182520 916365363 958699513 134089275 161559892 104331270 839808658 986481375 223131953 986507485 414519244 624661068 7728337 376878570 190024408 757111622 507122281 751204674 571706550 97257124 150926221 187181770 545360781 160055337 651176967 526197380 566281628 802067413 368237193 986475734 696153131 157197402 663123255 730037863 455303957 838874186 349988333 159619167 859134023 750717758 57796166 542630024 620103033 558954856 390298 221679867 954324875 646031774 745984385 916646725 212280209 541670675 878807192 863644802 354270075 108711778 421422995 76246526 356231873 146831308 864542464 130270440 894542660 706978602 439578684 686920655 98402051 588979459 113585144 201057721 967792367 580786971 522945306 220279208 606734870 124184961 267016257 578276433 567591116 817414727 384112464 821307116 916824057 153249277 552379275 330832110 246119241 363186722 684892786 963690696 258450226 685701902 11728677 440700534 482783278 862181443 58613813 901783136 14544903 31043989 60792848 563288878 354241305 782047899 453171885 12767768 94160219 284304449 662933145 427090580 794302837 163851580 474935726 5287420 82316801 313476792 647089209 500178878 129457298 410543587 933166225 919975802 209892768 44428578 754452073 827777366 58070776 755720219 185621249 758563975 377210930 956995841 688845131 622968951 253012458 33261855 10810855 62565005 541553901 165769360 759123607 17244661 375172690 423925945 491683025 291700125 929965415 269148998 508491525 688242599 376878344 972276726 387453966 119786069 754728379 709838142 457226173 855655804 769322810 197001779 716358236 479844642 273384866 781021433 764749513 550832867 214019762 698343405 658331338 255050788 932730843 255579775 453655424 665077929 255283774 88170513 554277007 452063019 301773072 226236016 864042593 704391330 452278881 101376094 545921781 531955236 109818710 498312372 728641985 918412028 468249105 903028895 416243440 993050188 69488333 947977100 331657392 291348025 966318129 782280611 908009289 290456011 97502830 457501448 986106677 579308873 627370480 487867365 687450909 966362811 989613478 35429773 212270454 218615815 328846831 367694119 57323096 144768272 650698595 141774168 415891903 847859970 761644755 340204384 751510682 388377265 505998695 268146100 291762302 55775609 731259861 244080408 106440790 900322288 798607479 895375915 127908929 768744216 217130619 657515648 907921063 105084905 395914034 243677802 358141095 32267305 700953630 481458994 5151908 765120175 498748846 94834900 375213691 249783331 524171119 965152537 20712681 74750691 722407728 520967748 468747988 120012592 661646026 539316894 893618213 295689234 299276680 542474622 8057454 504607034 896910836 387044933 312697728 659519257 793933957 812303724 716923310 219244455 667536097 200831359 664750389 740683554 563995929 957035508 878926830 243434722 118831110 560537829 464114587 374105871 590214644 653172260 234327355 946508046 914881959 125181148 238444081 899539162 136560661 488553914 7838047 998470922 973436623 76148835 241208198 660694539 333554276 471837947 997625663 19867085 95523854 658218494 89927031 357447802 296151763 551271743 737436715 73180238 676735110 124836754 682137317 72279079 464557907 70981991 91295945 294145103 540443880 836280334 753996975 505970990 262629427 746705917 395240375 411889750 621485617 97730414 517570629 373074058 446915949 176100004 327370920 270623354 821536279 776200655 17826541 792651550 500053093 75784125 513426584 105599627 153687555 882351210 712480730 518063570 942984604 286562982 46674593 589986847 405214867 512411996 11733874 261656170 787219004 758108790 46150796 682625703 693723853 203054355 291073841 376232770 745994817 505124626 651606025 34063048 797769076 692056270 572339652 710185874 110951408 6251194 439506775 528302780 713528244 85871900 476227367 997191456 53587210 784323873 245471597 808968175 245601439 474929017 639807433 760336358 625460904 878176655 644518515 435516448 349961813 560374277 453945830 612664729 780905757 648745960 726737358 237006271 491491221 477723601 905966049 932172463 281420224 795973880 222839768 642408584 365158598 767350771 819592273 637726644 417605808 573787534 244357070 548806272 825177443 92516412 278532154 828755895 604605314 769117418 199920172 600893408 610308856 643229361 946693425 47146842 574375469 920503123 959449072 318737065 1162975 813011105 331132740 179676527 293129548 274911050 722180060 946509460 44237311 304259259 429633244 545420137 37426885 53199971 461736810 738177112 481414578 543807381 337086405 632465915 303739932 527697505 312592858 451029740 901472757 186733852 650630778 738535849 516514499 933116287 211475369 158891501 823399608 655575081 813581905 110746547 37438940 100728194 179052258 798584663 832560484 980844497 307907166 609545513 841254544 982326116 802499943 302322790 590133706 710936601 16694528 765167231 138420533 12862010 637914793 577562808 376398457 254451609 7751247 313686844 814883785 905271925 648364640 380479253 737522833 519995239 504465844 512187670 325911826 18740390 76812569 523740638 96750579 581292690 580457170 476703 293265914 996077935 211507569 663111118 448950832 26278283 683585993 573998725 13513319 895157399 29135994 145764964 433946764 847374168 986266926 450299164 704487574 957395835 945995107 777675401 80745033 141550982 780226387 191354827 846275177 241103604 781788927 906819486 783286562 318007712 195822552 348135079 723354077 11556344 157087756 279928490 441416560 927297519 135779090 599660425 351665713 259826804 182430454 585637439 691418068 754133897 112054497 519242502 503662374 770592402 562410 853890322 849366378 987167451 640582166 858253126 49782564 183061981 836452272 631634590 374011892 65729771 488103688 804704630 625784257 972020087 253952749 340782776 751722024 578429693 472490950 35112389 488663129 862568137 183974278 972418977 403368505 99171114 604430224 853618993 291091205 715872425 221289556 70917869 130716193 481303897 824653223 751403889 239531432 507457876 470794721 817198164 220222327 629680166 931364102 45741120 490760213 798961775 875351222 436794294 962423580 713094521 428941129 251768084 335671910 457814851 518546702 762527421 787109317 962854770 75374752 651796709 506412992 259647705 820254056 885795959 334413312 277071180 601601005 373606938 554827883 641204618 72341806 594658209 620064080 776466513 889571317 469457469 699456245 786336779 209763265 613558268 668516351 251825355 233964582 309259384 78602049 267056728 520535549 689125218 713122814 319598103 512981625 57222552 181158973 27426113 216228539 918179940 21503017 12157964 425575035 143843489 126798850 338392170 992550701 935186069 150023083 273627781 701784774 548270455 788485361 511407787 16915027 137188868 670304798 221094139 228263494 335195349 164930022 200182427 853006431 525992107 784057180 61125553 8481194 946953779 677678888 715985001 198345663 355532669 631411548 278909934 839667304 732672533 504094380 650962373 965184524 17326326 562256749 568180435 727898051 277903534 250858578 489273872 534032489 693150670 535064076 710836496 294471467 377980482 747013558 227183315 16446829 876604254 820118749 866630631 185716613 186571736 500009682 100332771 271464417 541979264 950211246 91842846 426421084 608181989 881772955 124549686 781145887 113231300 683295923 825822588 876957538 424020784 926025933 23392811 154870861 35320443 663002471 392004299 638345567 561870651 488153868 201536748 490595735 564353138 97485197 993299308 652634892 430605270 416051300 975392176 571760826 535354163 438333541 950497701 536781862 763338751 325325980 904968541 126427357 340492871 78777650 118154176 281985564 345188006 730853999 931625531 567552380 531307109 982085205 164550821 188326130 329786869 704933844 426490165 791864307 550273237 481278225 883284718 36980731 448195972 924962424 747625224 245922907 626941480 359023036 116720381 389176685 993271993 822943791 939462569 507905853 11227616 29341281 756122360 482087316 232500948 523375996 198704703 887812719 595794812 313451940 713357370 89908417 581008844 14542003 184334436 795661115 327331880 359869569 906330310 806703873 282091573 606520736 157995812 113904367 684764185 411657452 526145328 736049333 96430835 172725459 896519257 283408113 194356511 826872616 825138039 973480723 232482940 571221990 425329175 333229276 339787523 412497527 379750082 252370760 282746905 257065293 781903693 757128485 637741467 145474924 886068991 623138063 314284102 368105961 889130919 506994533 783275146 797337526 292645308 193826464 545040037 594288408 198297380 106359532 68663913 456827214 268499566 22930698 274080359 831702753 799506803 337894884 933429742 181117676 806643316 906850298 966937957 567164316 412008949 797635017 684237646 684040940 982277983 768358902 819230744 151097887 56280887 898688835 325077350 408476680 709154198 500958508 410134407 308878297 812030516 881541394 61303412 411212960 850266742 422179692 581234310 933607569 410419210 518124916 458581514 489486746 908689669 240790151 197412111 99116894 202995959 28626953 932069473 963701130 897446295 227077538 462853815 483575265 396077879 167189405 782114960 431528797 444451258 178307378 197180423 330903107 886907816 408232660 492367436 830689447 574765815 613552213 533776363 300128386 137106015 383528608 732492270 906009176 482638751 910528576 902751168 724311142 240827250 795538955 592206514 837628704 544443237 409588084 581888739 897789261 991862813 496915115 224940703 181584642 998190594 34311506 916521061 192174879 441058422 643425677 863898852 519700438 510519996 651213740 258551376 693048907 665494492 986681796 958624617 637696621 94211610 847743764 611799391 949649207 84499028 884564437 677697809 377853319 884980165 401472511 647709749 313314853 467268677 73743377 516364678 596271159 381741844 32226560 192983031 437981690 271153404 154224004 55805252 516897982 427345862 569047907 857705550 754922473 611599568 89089771 455966788 13354429 327771376 822171085 183294947 638556484 453340587 202565916 935523701 765263821 753401984 496609871 59855821 630831630 491843926 892582918 579862901 256349576 272911908 85297821 382190217 180952401 962894283 572236114 82429087 159796784 96225243 362253200 468534046 529861863 935211588 308941449 153570222 795003362 329294159 652005279 235676752 480906764 855363985 593087895 742752999 748562073 449390053 718526026 776637316 37901052 240736028 876870909 306768279 326890840 953255745 922782609 695637973 404999274 629377224 849376557 711930290 593169421 260342040 152695757 209375647 767339298 443227921 643839203 353565181 546172785 247101877 831982829 877615134 903797981 58258424 839162161 116984166 111921404 373426174 934965571 405159672 885546431 795680952 383668490 78996880 88822104 441740947 34112992 243409973 331458830 638517438 650122902 748230764 889278963 899283233 555520994 134410206 599333426 638863587 942212086 251572119 249021572 329137783 429978501 760257346 614405079 878157595 530260252 53955368 255226655 659735833 592175735 849888461 102812975 770981751 91793349 307228584 345812298 351753349 419679492 815130041 805963777 20123502 564266270 105889556 112055593 814174415 347031607 573729765 427006847 307033224 408499486 643614963 155633278 269768689 294809539 117171058 859817886 328978985 854989847 365287140 108286324 905817987 893173368 103470882 978365726 729583071 203098331 18692163 73473133 50605994 598408344 362993712 975903624 999398630 7666327 511273152 731626149 147825015 686145957 94773184 759389822 493281033 580034739 446498654 439060170 471007616 914359470 289721979 256692455 353443344 754062097 442790526 586848336 216929394 496137866 694295133 57167354 998657780 983286404 508205962 440281670 931508103 929124451 296884254 18238802 622349004 268323036 793331247 356502908 139495434 63110006 578768799 450997147 720383134 503429685 313552946 958962009 205095506 166316377 604631477 930171855 455289592 905697513 121063664 587085999 344939407 135755664 412228008 301958856 60993890 230801081 612621391 792141045 647007882 901674285 431886330 903191218 995937537 656327655 961599174 846149697 886580686 686021193 415041687 487926211 244277054 516043474 537709541 652483909 404971615 143741679 324422022 377906723 519562213 124215517 501588884 823145710 900753760 409371583 461696977 435135664 815815398 261369303 387586965 81031808 168122351 760106299 573975041 331977006 119325753 124173856 96033935 906092467 678592559 625480286 510737109 398751901 478623608 309067537 293705972 273072758 603983703 467947779 851148017 2468897 627510110 641265915 157409215 405301418 908261361 749747982 859676367 578058445 293991552 828089021 959675124 960476085 476457182 478557345 121470337 984543588 372993124 893281592 100972814 918802421 497017861 587660841 375093560 377770192 351763094 846052215 483574128 363721386 49441668 800893155 893331289 350585040 438690336 691684438 527442764 714852343 456062480 25241086 997290835 451247110 488533454 184208868 585332516 882823442 615476920 948822415 434853336 482832442 750010787 230188209 204263717 81058944 507956796 717715033 795261212 676257710 739595902 814507676 519964203 103048826 886033251 471105898 865952863 73903036 864062054 897209134 151166901 431997621 806502586 930623468 645303436 222091839 733492271 819662329 77675301 850474319 60313835 246417208 868516376 593724643 627049791 826053232 56463980 446277278 464791424 883839872 930850561 122513128 179037095 854123213 994286338 327044928 988646266 482149248 679672818 124543228 679246511 925970744 159330077 522462670 786107820 534033089 838675288 333015024 810962127 313194182 615006595 977883234 800099225 129526278 536904119 617278917 167787213 974418031 540456683 866116219 289709223 767091684 112319872 662385138 589748506 193019225 382431549 220596817 108962194 726987028 99949115 172173249 536343562 816898175 39961051 782353700 265395969 55054635 524787920 200094628 2054145 42014027 618930177 662646329 592628135 461815727 498003759 110464948 992020982 865119096 284946438 472507358 675222092 574208364 33946042 283264372 705862453 228245343 671365417 298114808 498197830 115872491 427700626 542545806 562017158 214434751 431119159 135994743 786245753 759593055 493175905 98332846 372124312 148511828 901903401 515375166 869286427 498197874 861103735 150703636 737241973 29991710 11927388 501890922 360933408 441310382 637624564 986942310 882778293 755875870 543533778 94890322 743053764 928504451 315423740 269288881 471703139 845327044 309200082 64976929 432916037 426754965 424141271 404801117 447038573 510929767 37835942 652776532 683711784 78740554 335593923 802259892 754749170 46809555 506241179 99262503 24918687 809906378 342874473 871195204 449573681 328309270 239250093 768599251 432552173 378452613 812318377 485445819 844795471 159627586 146914857 101189788 358362418 150269499 977776829 209392500 902658805 872530483 122311634 23434617 683327541 185267919 306776081 323351094 483722260 411619172 145968021 397073422 39635922 824700348 377696627 340254637 318064540 379119214 880996898 40443843 903271832 842595403 200997430 573187504 980151998 797084872 446949704 267495577 753203017 184287779 914676256 26958153 943237388 637808781 163165790 502218772 216381812 321213982 786761663 64125640 960108696 756257251 249651052 382167643 471181049 399401197 709148291 149192279 107204281 883238345 308889942 221421724 758672062 81747797 946624117 897246864 602723793 385016639 347627074 428378160 397842959 747124257 412239780 225891175 854418870 697256701 828798998 18892316 685522509 56626643 28651980 308555377 216169633 874815092 42707234 412181276 626173048 660690228 241191788 378381788 309952901 313889902 850505510 905793736 194806494 916462395 24348412 167643259 944120272 559694255 74358743 897502589 907984447 204058108 356830778 386692743 375394569 709194928 278028398 521179675 236778265 718478333 113345134 81836031 398944827 773907175 186671972 565758464 668119864 698212054 302135373 884112065 451868060 116073504 146890125 181787417 569230941 956216145 428781743 281328500 879187640 214715738 182253681 511372651 75242360 114074640 79215681 968174866 683198410 471888981 716581531 818233266 30316149 907370426 120786063 363375389 192260927 78646570 105858674 126376648 70822106 578274885 853314682 697329886 931457432 279974908 423096093 319171469 300591172 43344033 814545882 846219893 229569195 650807444 444443638 752241200 943650751 447407884 796926742 972652507 625944943 531105536 115580821 354632467 388292755 594289510 747356602 490296667 850806647 309143010 589440351 314406570 107933845 996075200 686858306 732666247 309948334 910091203 38098179 7378361 99647453 801460943 136642565 701676390 595925534 166767600 529082992 796421958 748840774 759076717 229681133 747527812 118139884 545420473 626828800 196702039 806548773 510113167 882631928 533322505 149649094 527721086 296489282 789361112 921941786 850687242 757715368 388203445 293616252 974500635 340013674 44602502 721461397 549950113 710912869 490147850 309298630 527634321 874179877 174424387 624983900 649139235 179390727 412813602 722641752 716804089 379468708 866371387 637316415 344736112 612375501 73400053 551686756 431115055 733982880 501386144 6086847 332475856 366303859 688677336 771591100 470543750 502700829 174992879 448327740 299623845 724272259 583418082 554369317 128218067 335922877 510679444 706031619 62659228 370252913 692942653 523283680 702985729 902430331 51281248 921543381 509951638 553217598 798997828 609514883 739159786 564274879 670869937 539962171 396014744 253237041 313543095 196579099 951059953 713056861 347958429 770608111 96056240 757291898 791859750 390153026 909050756 338810406 365238509 704137989 15877255 62197353 746621939 763524145 657114972 692371506 176526173 538482177 328251334 35411497 482964062 716112200 383008237 405995924 443781674 996919187 915927642 484817131 732391426 496848442 411922862 344536053 566251618 599616630 964001035 122939852 983336135 937803128 562579372 839086140 505773558 112257557 879332015 749071430 226572489 169013648 586053733 198690498 597193397 500845396 912410211 489948713 699244040 183143862 382964669 42359799 606564172 967334935 466348351 150871604 467853788 671224910 733645450 939279791 532764479 3840008 836853477 321608828 443616507 460908827 609988098 768925560 298226304 635346542 673641626 582683798 220292149 782713702 637721144 787906337 108743078 72135774 895715992 909492827 961061146 361685776 574346770 697484546 631523913 146984267 780969268 873500423 186634270 632155562 667610860 897427910 773628828 622835468 267049845 324902527 277123342 453255015 181475093 891832631 7736189 109871093 997800214 380709427 827224919 718025723 44030212 304356176 847181224 585377968 53924566 913080189 835579580 23604161 182054678 647357024 590530009 825627938 249388743 223942693 688762533 421187713 14205746 696223240 292926621 966182497 700603674 106129576 261810708 907961042 699914667 438592992 151573096 62032410 187596687 277806403 602008505 904321687 277528595 115099002 736521089 440401897 92681482 586331338 695082549 808921223 175064784 402783330 53444587 807977499 455422694 35205395 914809807 135883706 338883672 957493470 654652938 633898314 742016265 303491490 732209858 771008599 487712326 719107712 932577055 360894712 486174294 642709769 979699334 105586074 153466228 709621177 823214286 22490290 566311876 383854392 658301335 476609209 175461747 862870271 394631990 664130449 409656088 827413200 399613246 42465117 706695610 277843499 80904380 3440081 631898661 519321392 528043857 613514079 210606914 248737941 172133873 523580622 112493760 483086611 237384935 22962128 212456895 138920167 274990595 545453957 37304093 231517307 647566504 343166600 998401399 398067907 496964957 110129923 426944948 23109455 286972984 377796436 419338317 87857593 453160555 682049570 167306510 755724577 900442075 176135877 310279393 698824393 39188353 829685085 83198736 616993976 508651102 816433718 459694714 502103573 680891519 953102041 384824854 402100717 689091335 837938002 905650912 451215544 532652908 884213699 7177663 714920633 131383766 989816460 229764336 703379781 134945670 653006572 926143613 972673827 398245526 51100773 874550548 372390726 664397375 241071624 96485072 424254109 569548123 488501302 986638400 326332342 627667991 116323232 912604299 780953282 851444246 128916447 924124224 498936185 865847778 889791037 430875733 872181876 945914288 903104159 542214447 694024371 221740592 297162801 654692508 21348144 62995367 264416109 60670699 742585249 356219928 218161370 695140413 507980304 166582142 656565253 702942635 769152426 786632109 868144770 124437036 7864200 682268002 199826152 587750251 838583794 311818988 122953038 585254400 163053185 207269354 995985525 912354683 527711532 976815854 25076662 844642409 476455265 285506485 767526985 892763864 793154092 86936803 392262195 230006911 172654920 554319182 511730679 525358263 130650879 94748782 863033923 686902335 56964282 98861453 334603213 63046850 378978337 950068143 348418721 945628223 43053815 860882030 939796453 364666283 834924910 330541664 467724319 76374460 559249135 315127364 50760210 136101799 302003496 792664353 187760327 953590507 350130895 264224 57853835 634024353 736832667 396447033 320888626 127001145 610631110 538331713 431810022 965513294 229283932 905779162 629266282 903940675 780094971 809277440 792806625 250476280 116480422 51731165 346473436 720596449 205681478 226358791 944100180 257982137 225228351 337623762 703679330 705956604 190474742 483825801 615375211 699795498 888154187 162738699 189995126 467120879 74520022 666146073 519021859 283423416 647096200 883735208 439819236 635314936 228227811 79398643 588903683 845681515 332021740 476992249 753515220 424932274 200136939 999838144 966281601 251883362 736641936 398176 679351836 907967059 115054566 918921216 557969913 716478359 214943931 489597922 257410558 559218527 503955407 566993494 273662755 443711082 459960390 89133544 422607656 199936664 574304290 241748146 795896504 517389948 986204960 886737574 613352042 496140435 599724507 318533014 372786176 545452209 307189112 379384778 264760650 66084019 136187137 521182737 399361261 795046326 756294472 425852723 81152700 757375732 108565029 510138232 921623591 401429250 512474720 475034287 521639896 23731128 152122441 967038300 445617764 540604177 104470378 436301380 266952072 304788882 271894647 907820098 629809182 580972508 124170828 192705068 245941200 294178711 129485921 406895405 823867679 15904393 593425126 449560034 390838790 454293774 683355034 737251298 787185888 733188550 39265657 320390781 480807579 838508182 463536500 68478046 758757216 981038936 857688034 496584177 45387733 520920173 309079722 561876069 756884803 616614527 173205556 720677916 832445901 931171929 832711838 677495785 774799760 855884495 12452150 830998654 897744515 407621054 296007849 47217842 707907238 458045603 236974181 55786167 663233879 174197545 405692748 290153212 926103514 696810345 987795250 789820447 478200692 490708351 225635662 938417349 554865438 461659087 41861214 286893231 127779858 274461660 362574922 89172181 811866707 73199854 28410124 933829868 270526597 48755070 505465925 798799735 253144726 489190138 133433126 149233357 245785447 566080500 654547787 780188707 103077759 183150636 14961238 869710096 322345743 659783666 349308044 729740574 446183937 158088836 822432369 327496591 19897593 761769932 533563760 988542714 867438268 362223403 95281651 134579068 818122499 919812909 367037585 321844966 488651588 860528537 902736507 357077290 62203545 41489054 542336748 894033681 224982769 594158444 635404803 627857954 443830458 584541278 877453583 829320842 837281859 257702382 439287747 964329675 648562363 77021474 279668698 182311150 804960464 825696609 13129900 617112320 262337537 782019178 750239951 992453267 66511743 807544962 90172258 147192661 164006943 952082407 272627661 51365963 46688292 257604295 518555660 851272870 303915743 904522025 328321992 822949210 852090375 166707401 147839678 176838755 291291435 445314903 756921234 17466042 710289603 811105297 135026028 181540400 258627500 236073613 929526846 675703007 50001497 748338025 363698432 901188909 255834812 156074010 377660300 872875928 743978711 521782436 951504070 296691044 146663990 14136537 566636166 836735218 389466366 410138137 284050718 902668672 5025913 480437779 651605197 866644096 5569343 536680241 88769571 170017764 825466948 931942766 198511087 48950832 436037696 565379600 294386845 853641688 275407530 524306613 662284608 511615472 306432324 840277326 297782504 546338690 569528362 11040600 150652852 879070724 702636574 716964786 143809198 930294405 574326550 358698012 214915938 918508402 611415083 863175658 959426821 818935582 186804889 551143135 545518748 175637729 163860145 3818696 800227402 994121422 228271869 116891819 141069873 88043783 932882676 406410502 19643276 247926119 269928507 652406005 486230309 603931742 487393223 618940885 844411324 556974858 917035626 114559356 37159503 864945662 457430839 336285007 888253786 394122333 454715724 127524184 37011806 315638656 580786668 750236896 688378016 667951015 225622978 59018985 237767838 814895482 687253651 246557928 107347172 598353774 217618915 87039807 365857202 717111110 670021312 272332090 707403785 644279120 194327278 350674784 547207472 920618426 148256012 45636838 366630189 754482526 190424317 26097142 819972100 741154722 925664358 867813329 262664312 702123469 201822306 238105237 502433467 63108839 580258303 930872082 29163219 810535108 758131308 386038475 326627874 559779542 757337425 829628269 890537844 395890612 814987776 826051442 48562087 931329894 971070675 440693407 684654865 963960195 936619210 192712133 40510002 77702697 593628724 676176265 610565861 720349819 492750728 551136084 433846978 691643259 183154900 599887070 852847935 598296551 894748882 984040312 8770576 108301913 417720950 70008398 874795412 337442745 568957875 491210446 728752756 49081541 551470987 742314107 208155762 575914764 176191098 200881194 391702373 483489275 78890275 881636198 460523564 198653738 602175659 893123952 286686127 35927478 411776466 653914649 409199350 31406294 217211466 748011030 561829507 737614580 153622782 296805093 689620275 717109453 46113769 457433497 368777563 841752067 472067253 929057288 484415918 228051435 736500387 209553080 872205446 901037509 363725027 737044410 699020725 995298700 105444282 208085808 897829168 708074683 168313564 911633684 509155606 388274866 516096580 554771461 386764405 574934747 693249953 991905497 794611159 959874398 546282023 135958816 418549425 119038670 593404518 856682277 285022202 485001685 17916681 889988080 136328409 259130933 489941101 533820278 398601435 39762660 285627549 94056191 760833579 695039894 316268248 549688131 362376974 96610878 812972563 817585110 68502823 665551639 411601830 776879251 665835263 549193499 83729960 742667822 198907086 79927906 607009610 808456193 609483129 295601228 141207193 917531646 350385528 254389765 94205626 740962969 83127705 940093432 102295841 152883243 547287636 488210359 49123452 486115100 61744820 276230551 419224232 474267899 801820579 561478983 167081273 651774991 443553481 742092509 684671333 607027217 795506278 115090786 488579267 481697293 406702444 887278096 210991300 775621202 24593255 390525375 378144764 433586830 126450467 750065553 178159379 433880805 352625572 564223909 748919883 581795875 907089993 777398043 822947006 9166134 121158244 58089095 851030358 515652040 739780430 782939269 396144980 802801541 161045897 969469847 358959021 660536889 961017474 902503510 735633867 38117882 775384460 853253748 707424568 591474190 593514452 812134441 111410879 931823174 497362174 467279804 370078451 115015095 689295332 634422222 132949167 451205817 90123568 973500773 150363305 216517924 311055109 156723667 519727609 605141947 236023099 361961574 796847681 276752973 950712334 346049569 794431555 785590090 97353389 124348026 590175124 133910743 371864087 848215242 673017748 34867716 703791599 435553533 243296847 321910404 395109575 947513548 784453127 17146704 501922242 243635240 886939761 90550707 248298456 219956532 997929126 97258845 874872604 489509397 159417072 321051900 131158850 391199324 429413158 964292384 203019465 546648478 266811834 817581118 376414119 497185515 639786156 443265387 104981163 107392213 137248731 623771311 249477924 746361703 250294614 62894157 862039948 507549291 468557599 260077071 972828224 930953768 22695678 751412345 367479387 538014370 627079754 276160596 572857663 363032266 165855441 702957412 210153842 201964789 988435004 663304901 962720703 294672385 482882085 136099767 385819928 355894680 682664875 217046739 261120409 852251807 246502924 456220203 843780182 673626987 102931535 657050967 804812764 194978741 158979801 928493072 520055338 629491592 655796951 639036061 843186315 213965987 645361857 590655339 905976254 734390464 902150271 176802742 297604289 815824996 919300472 631449721 144990624 783004835 695010788 840774156 899656366 397853572 809484488 950785279 139688610 864226623 951888671 99111663 382128758 631307594 227865687 458447309 932753168 589015837 176708482 32519918 919889813 975485922 361971276 521251342 186867309 480312453 806873415 255543694 108005303 458011167 183782391 252774684 344657037 884415585 967292572 371511452 44997148 769440913 791363526 551363524 97653027 602645022 753508954 218255793 175041126 949526708 637676290 984413805 748300747 292546455 957743608 116546135 868489575 336443402 172118529 120340681 25251722 936307245 826985907 384313050 793285151 451182693 870989773 82994619 740132803 772306455 151197797 527826298 415372365 351464338 794518781 680409034 101218512 474296659 302086526 737332905 934469860 219653638 557790287 916934228 891931785 999477681 786439142 190479003 381892227 838252773 966932320 924479294 766920847 911083345 703755003 467279828 539721672 443822221 945365419 367675107 777707910 687281382 131504740 561698748 612601697 428065301 721718618 154848398 142404586 765637559 38699228 804026468 723470955 982112626 582843915 686448897 419696242 569636796 341361271 56097893 2469144 293013700 759090455 260486138 663739472 786427446 640167372 650317509 347602343 57522585 44616525 62099869 578273972 767842584 729674510 84774210 85825408 760539564 816627962 836866980 402532214 120050041 744102424 53323159 271565085 727847694 402901128 313939453 894663246 362597907 568245330 294785968 509982584 437078336 338530609 780537053 447455765 588938223 720967660 367568575 298909889 870123872 515515821 8449323 633412715 399617720 792706283 436258379 113848140 782635525 399333235 807148497 463442364 318573924 161252202 631781314 470176305 184297707 303956048 199103068 220808770 223638312 239182833 924873370 864474734 949402573 928640406 342948656 88999487 361237369 20514906 110156622 589549893 203211783 764566689 528144525 744821083 45252690 248833272 21415239 228495545 802596179 460871817 658585360 240939384 98998942 933368873 60345400 450964143 713950844 59202573 726431294 723406320 687212713 483048869 332958855 173688355 786602583 444037277 511375607 617961592 925633689 460849031 54400997 589677323 409084923 683624429 715517566 55636882 798932852 92625456 142962848 538718987 287798461 979884020 354741316 74782672 604101276 73308248 140128846 133153073 489402750 980847781 79962952 75539273 520688137 252930866 778205909 24753626 936004965 369022198 907508627 325963677 92564247 475934455 48095192 188038474 577727490 967799699 148987667 124158384 622767961 925505493 935210126 354612315 345427720 342518458 363361610 445349335 945607532 172784068 495477675 634484977 510430435 95662349 870607834 459472061 542729276 181772146 82580558 576426530 512952112 658101451 249063005 217217505 994841537 877645153 352655814 80350496 960392851 610286861 179681819 746370259 610075667 398783058 148943027 635458623 245248055 896836985 358916583 86968007 299616386 419933169 978572826 476972553 215331541 663504845 90754339 657498068 593933098 47347170 959447252 101485039 638062811 819092762 360148396 152276676 994200869 719872450 261021668 919851208 321801171 226770171 493808278 380862329 651334934 661799459 182882359 371914436 299124692 895252270 700333388 229228584 996437090 834677756 633441763 322413077 443409800 185216843 216890227 185703929 888435193 316859889 154143865 609383000 697818374 828280738 529006694 393220487 756935703 181186654 822485913 999576546 27553816 691578248 3311244 801666972 461200859 862441673 314467130 653022532 352832189 864906093 72329998 48550955 753951235 822292136 720585806 735492825 636853311 747822281 187612529 794067064 781962642 224038421 619091635 320871390 388309243 115637689 292896030 607343545 947758262 583645073 277880877 357785963 527841850 212388893 631812256 441821882 233729411 856432170 254141237 255924371 626533938 253839239 302560034 469654205 502258026 873739508 708512509 957552832 743970538 957912458 104235613 619460854 30954779 870209182 218305950 116127350 453501117 262300744 574135131 638922849 907270795 245082077 226691390 88575600 90269353 436673325 407578069 960184476 985756249 88157513 386436888 28865260 695672551 729672321 760367679 834453754 420401591 621234218 968610770 366391320 634229295 677988282 518763767 220178569 147662704 553053969 71460196 959631204 390127781 928116671 366512855 759444332 632778067 44888530 445202758 644501583 133528293 823397207 606993578 724062575 504164482 797437229 415706695 564750136 568515069 803437871 81056604 738672088 825860166 299154178 447107952 115341943 706937185 976033779 912046446 21498154 962308743 742170216 709536175 560446084 796664955 285367100 751494083 232045857 663127848 857627819 93137356 238214483 117983716 538051399 520675736 690273655 977366647 912344263 339930511 947665446 250667842 218738980 23839733 146890934 153957567 72900375 351170424 912659540 909127409 773296562 65498388 562289898 364665248 500516109 659930200 144761525 86427852 336177355 877163947 804649397 654438396 517953431 603737419 200291190 155327129 528829202 583119382 298959854 245459189 191106727 141467808 710077351 80093362 299990419 579677304 760449046 625806010 996267155 857329767 390822288 618570928 558170881 190521580 319393177 122541822 735485807 241415830 853130091 893304738 288746500 351878680 382344617 676476867 653152001 241700911 719276025 853503047 911793873 780183656 80776402 563379611 10889441 725585892 538956701 448508504 405736109 647205261 288045920 114465788 802243627 445789108 796139968 837157890 940117856 160033571 495579322 618507271 157046951 585682755 509144798 987229096 375565861 630743313 202931507 844937768 706166877 647185596 32953282 7948421 450388235 797983960 502407962 688757113 811933522 175850511 741835605 383283854 740703174 23029636 904895002 962300597 554896018 427102372 164569271 101178028 581826617 750471327 438223990 707954226 216490079 209275337 616911981 159948966 648729737 374046809 555383139 195591841 34057672 777164085 190894040 338252120 502785591 766209571 440984656 38237529 39723390 366121233 828009367 360307708 540870160 274483075 7643769 961198052 777401454 222739649 927796341 425123574 637778712 414628048 135208846 948714476 657628785 731949894 843744268 77854665 235510742 690318815 443757708 217939550 845698623 410601655 80813332 735527180 604050109 269704815 769974488 714769312 272916242 901926561 387737794 393613132 412986574 400850990 608731592 995462339 830758735 240176948 330642477 983754071 820795760 402051872 561810098 299775100 228684517 132779107 549369851 743907892 630591525 483581946 943645106 518719071 240301233 103255565 591593253 24482940 516855760 89534348 208826364 167806138 735593527 36600078 865350682 620620963 241160253 392683761 868052524 975038639 923973633 791105479 53001949 459637976 201240894 392751150 915519615 985469325 369335294 346012760 99115669 477985685 861471340 388217619 850732991 550420827 632488732 209574578 426606452 350850297 503289466 234162897 553355674 421020589 91693856 380689042 596684550 200322967 111643449 853117630 139947211 886105326 652040515 340384770 415613013 920433279 535473240 387925767 174253793 619022704 560838247 491477446 965419873 885589483 823729272 401212873 152266019 840516807 286829253 754532466 118257661 799156909 835845993 331799704 223476859 134108052 137116281 31783287 403349132 98289989 611810929 408354299 77134896 314746028 707852877 927679942 93985015 206576620 21006730 732364506 900964946 636601319 852115462 777505020 976390057 390808070 210287350 475475054 953817384 990159692 200923464 776036924 698502899 765572473 579272464 213812201 904472764 344923434 326444294 6491440 85943579 598793502 792446153 512984903 631091930 647796578 708610635 143888923 269560850 835763994 427029441 911546670 452819067 154848219 538020726 43464668 615437851 653694484 307519973 158246366 82163862 406240062 130215462 679103480 939035751 347610079 30159849 473986430 604091763 261937247 804697536 262392658 101505313 914714903 505661381 828617177 331740916 6659347 52290227 213735461 526633376 489575892 386858887 709792843 787095927 6887921 366208810 259770327 687145624 481330662 953059147 405833152 297857658 543221483 399598505 489480359 330965335 119022749 276209684 383970976 576576457 265934898 748011816 109067803 29630232 688093214 535589425 302599066 195718821 716453515 363221343 104970399 425630864 291434678 727003127 584364091 920813414 431599238 265974612 200663234 287100170 69400499 195319229 723582106 685074370 73356673 692711971 98989050 101721131 757640120 780395315 530049639 803858953 427622924 997948009 825083091 375074736 127057520 135841121 795950247 808421454 750527543 388090619 170405147 464865835 667767265 408333711 884275630 697345253 33808392 637167047 848257806 497794870 742049199 458544692 521809394 941397439 147120943 110716806 604875525 577906380 696661008 632918518 889049651 71451913 54679498 320273433 937451847 561994421 884284727 241625001 138040698 909834611 895290568 363541499 76084950 320215884 702191883 734275548 257577096 892916183 555630972 894132023 911450506 45016843 809288977 520033882 580814657 681927790 923882351 20711384 328882537 703175002 732749565 828713233 666889233 226926727 43041436 49164357 945864486 56249056 222232098 950643939 518723239 501602603 63093998 790131459 696485202 535380997 87466816 511264740 421202979 223935522 206143906 909959894 196890442 786517531 596372387 558213943 654192892 400953340 641972416 60564273 436650743 538853616 510103284 153433746 223011912 750149834 134380960 923559766 117459467 360393425 955862771 984867526 319670181 909215006 578911865 989404544 711319049 284414650 463330310 840828904 111993943 627163169 703007570 91710889 121198788 253149134 928903631 174643076 359568861 967168016 588618332 153961203 252763174 629256336 609555905 207360404 375170649 387862025 955743543 260136540 31080333 678924378 897745560 824579104 49830062 294674186 536255536 645560393 196306772 56286471 531134901 498747422 847719143 683511512 172958779 663120767 508741568 803528253 225692288 797381430 291459756 633620037 975915275 660955789 916796596 941628428 166722146 341756941 467017266 614618716 572882827 830034957 45665256 916927306 192192891 594952661 413966445 400245255 513997578 709971180 56740326 154813550 70149806 727668781 207316191 462653534 949395648 848672830 6599137 64113578 594104346 759843847 837663173 725862777 929573778 101599854 237472787 257146055 601893674 216620611 940089706 129030106 12448634 275666261 417613495 608765169 330522430 556517237 978623525 948746835 492377508 384939864 74001741 283927057 427094294 526330323 656252814 652343230 450283914 429634127 679388553 585855003 326149803 487872765 930121954 536790271 580298617 344595394 605803804 896220002 999485940 634163097 287888716 441349264 475049476 765660644 840227250 748678784 75392173 879307072 213146664 211381477 391170474 958273718 355733890 981628000 13106517 539684523 943306170 178708616 605166678 534699529 626392701 588463917 607821146 705157098 183390510 724014914 494742117 144352942 755499832 264370603 457117904 830725166 362846992 603164926 116238235 657650660 273912365 140368573 740753994 389913944 21443082 626163734 222776843 417976281 269701141 222542456 422612134 983111745 861764542 914562517 988029200 744291124 371339972 60404347 523535502 530332776 141567935 574977976 953451009 688073435 387793544 500695314 840046341 425566609 134969030 822668260 565924449 154219611 681746317 752234193 670738714 82480151 466888355 632542567 687816102 819847574 432210598 390066440 361380524 167009974 313116993 446666245 351378851 747964168 808969942 835378170 166618209 279246998 412944233 293840404 878944064 11224689 818528108 138700438 943053670 36711530 426596032 767603514 935368300 414020749 179833601 954414863 918999415 623471302 665550109 975431889 34219788 411262446 253104202 933505423 660312260 693674956 46061526 446531660 455602417 365468410 70370700 706953485 266068611 323141501 841898003 797816373 656906924 31763251 991071844 897516046 37264531 741835596 327794730 848378822 501267081 134651775 440326600 633110507 256901046 229744735 284092342 179911692 552423208 483164870 199877872 224202206 390367591 984679012 922667185 426314643 476528394 521679040 621973098 133069007 283039032 731179658 906890994 580954668 959476591 875258449 264020857 101797773 507516566 502418779 45529289 546840111 292304169 777672482 180837073 919168689 459843870 579750044 497336152 759407219 339964831 797915540 163435918 931011747 500876792 186234214 88788737 983324327 594389805 561010267 705915631 293882773 357009673 773203265 622100224 626021514 902449801 82836109 867748594 172131366 858398272 875771364 615754484 86841637 549373383 821689513 874293554 412297171 97506716 974707073 569717417 991142725 923279258 533489209 170612335 838146968 220329636 836153036 998968688 68220378 102469555 405501119 268588490 661687556 370792024 919301694 849770304 870343059 256071601 518084959 279553506 872479243 388706741 735181802 453734289 472554584 331198334 435883126 303450156 459979578 745991647 19528516 839816577 187470688 688691709 796895593 2907929 147498851 86995256 764446559 882181407 315881857 568653405 780180716 847651933 326395166 867521272 745381125 380379554 489041917 673684319 750863344 637569155 350680307 60756798 716733886 598314452 938257090 678978207 64755757 729764113 170092552 340831741 473858203 954657058 854637471 601923214 635540379 204497803 46824296 822369778 365487010 548358089 881404566 95890062 880625466 597643909 187525250 925501880 761399369 241118441 98817941 739384568 367682372 358617499 759994818 45479451 518252642 299861135 904067993 218026457 268066714 842435230 53014120 80171338 638060204 472784937 502382571 733220022 632585943 218398771 711091116 982891478 693808418 773956678 595381489 751202703 965700891 437122103 750062513 805073517 736468716 488245571 307163375 893595272 651405235 557320310 411359667 272776409 645448273 148123039 419025947 260462253 701859195 5709206 337796531 84481033 720235366 231846874 539308532 401242294 225963458 134900141 980534289 628930460 237576518 912976139 246406400 566549676 784794430 860704561 779702673 811154875 838031496 585870059 728720867 233892903 573786042 487792357 74275997 556645271 121067622 619905044 704884546 877325983 325785683 917502910 801587213 457414738 343108678 105363124 83207208 132275849 733873841 556475037 777102258 415385679 149492063 385859022 656828182 198456781 726990435 873082883 29395266 465203332 284070355 524131298 526939869 235912332 89553624 254532498 287076422 945689196 115249827 833162985 548124802 823489738 861641178 607947936 54685465 309916427 169855260 958522368 373662144 660848283 668974830 171216021 93473350 794198736 634757923 124131714 6505965 636062708 778976178 933565772 554840373 481264305 829846730 850071703 115085958 391972192 612862898 66527131 899735679 486174710 669366233 388730203 229320630 362769966 151240968 882496443 938827617 535101209 188375409 822142363 413988698 623968821 260643 497153702 626010573 194094042 344270233 317302005 601210121 562855623 968985376 397956830 524643644 64470804 18606318 881170084 506183314 859425456 730131809 495583934 679786306 593674502 408090770 512222582 411713682 879844110 260551668 722837625 507421248 556016455 851766354 208593930 886572821 987664423 273516029 591277592 168322913 673089081 216369348 680614201 967090985 972230167 175819134 941997532 412219117 806681517 398420419 66982046 778491068 312811199 57193150 138393135 722816739 369196685 172060471 104382404 75693199 372663271 802719630 900006989 292671693 508414765 923300556 160067219 575202984 463002658 985790206 63494257 169302864 106317472 917187027 197005723 882682219 739375555 727989270 246712314 913320816 767192048 974904374 899785943 861733098 291323866 535347603 444941343 800516409 80388234 315814252 464090869 742446880 876617022 312857819 995107632 346473615 754900739 853696533 237776692 466561825 89988825 182023067 139542400 685051993 94873826 334652708 31363283 423901904 957299438 133157467 504082875 915062139 195322572 606478115 196104471 219979778 727313257 783881618 54803357 221574795 352686870 4848787 120710704 260246949 477008283 26004848 958337658 418641019 117463392 113339569 722541202 70923834 790995105 192568067 720961552 631261962 870326928 695359113 337765253 792164084 615377629 12724689 448440176 965116888 597254174 301866864 425913083 236013 959940754 557743490 58730668 810991679 784270631 838361706 896536377 629837266 457988636 577737952 467317139 212599325 572370560 660250933 622052782 190735956 266751025 461422702 364470632 755323249 47644616 208217960 600090548 282594462 259439558 613745473 300967196 759173881 56002271 188290192 132765066 110710677 106645641 227994373 798086566 586408153 126294570 689170418 720015338 146311754 975568681 27705624 810386671 977719523 761038558 593521533 430977551 425956564 32160972 895460176 256949393 663096080 622724688 655473890 168493213 612741125 488025422 690064992 244630311 402700768 549058888 893881608 437530328 84562991 397787857 236019812 135134243 823651063 409371173 818660957 74099498 788895286 252301859 697630482 445872819 644645813 764043212 881066241 566471934 688763440 171688829 969519644 174989014 277304911 333005025 925167372 823447606 835144980 655940755 645164650 968157504 818104157 343093456 669157992 882764417 759313602 728492415 163539159 419793013 760812207 363302861 488296999 440368437 595922765 501101739 246681957 433562578 235702497 300634223 652482052 973799434 234932254 371162893 314320804 6863997 426777277 480443081 424236193 390247420 691493256 119893060 520204735 201052826 461897440 498107757 805961807 412027047 245112119 394993813 158884715 486215862 378341220 113061200 735150821 541000041 326073569 868134238 89698769 617468464 947891759 816478192 737019742 217293333 895374865 197176710 865442889 670229978 878002833 842178807 912987312 563487623 634369553 611371874 788922856 908758131 526625482 28015242 27714979 510148925 243485795 591099809 694513435 542981906 778681106 196366102 701537248 676258881 128216407 707093840 692801422 174189015 552823267 81485165 994587218 832632889 543427314 207288380 39689636 137835024 188902011 140088420 40001431 548493373 268114392 745785380 556888435 567189305 668891140 144245323 606144387 67857834 568628311 853637807 517923223 282590764 373766409 786388604 899428952 647080762 85633944 308344056 706999375 478694614 360423156 822001018 453497973 930855853 64595305 253592597 60991004 804794885 766240214 281822949 849164049 231837962 93771642 525739868 118344128 264822962 637610318 869247331 985475061 19862862 482990878 197159238 797401958 591551939 611173722 575680838 133733073 229792096 915981604 775336296 339813170 113660265 502364767 539789138 242855233 603352956 630976261 341331710 160408579 694829290 769920060 109926966 43731397 964113897 569117279 169130984 99803175 285855720 736404047 892896142 164968818 911557381 949555392 747607538 14763131 194189924 182399136 365134512 44594644 651464794 145916739 718457983 7369542 661150994 764874685 508138156 401998824 599895137 883112195 847176046 839429729 641073925 423439416 22236693 259366929 138210369 629840979 510409313 120067013 474650710 508688691 932441155 45694458 860383316 29780544 443117734 170344745 888879145 145771694 973310023 300130951 878070445 339300761 173988803 393805480 717641541 748872839 160490925 113456044 595800844 274554957 853894436 61769347 400263343 492251988 692621420 699107226 711520757 201908268 627526668 76946082 12376338 913605464 736231146 373354023 150835409 197242008 310004169 328337466 437001535 451742844 477654657 871433873 602824926 552114827 655823407 791803124 4196780 365197616 94871842 483467705 849620676 108230408 56909022 684059694 348765845 410751846 869381019 977967560 751240816 160091211 49982865 162236857 604834220 558797439 811115817 20181837 423126019 453321113 400962044 86061612 57853520 698072225 904565445 171096788 341762731 207943593 712945882 645832151 345937528 390001219 750173082 965234601 764747629 192371810 675475211 909802356 611267163 718048277 464118553 125793509 175422992 6023193 689540148 182974225 570676499 675917501 657375285 946240632 75215326 6309755 701680019 291801230 198417203 779810183 604248859 337964109 581611746 825658844 158518746 240929758 693432565 391550191 778835384 986095573 774046651 379811457 277212851 975090876 220905037 357669216 730573792 307729655 795855762 191065991 10696994 10136911 89411736 627418649 644202324 652765428 300904328 45758376 306858252 690403163 633865735 286699724 143208629 193973330 926165104 350005475 908391505 333184803 344567417 80430212 210905937 863149592 697144669 572836309 945107022 338486641 852844099 838001572 225988971 557356030 895308751 521102467 347807418 232437936 282907013 376360947 983396167 152042301 459825552 917216759 572762859 803252222 602199977 897266322 572509833 640856311 5881798 845961726 956983670 769455757 807396780 783448294 336964290 708892685 115384350 343977848 168483627 266855314 985852172 251651616 770921792 398564135 65104962 870382329 167518305 582551847 267353646 756300860 446821697 558715560 348751391 711011006 461225612 496240743 868176963 837910395 77245177 327181298 66164975 740207072 229861597 770988438 734229509 655691330 930710959 681533535 586767428 781244017 542310075 316750371 901557959 369968116 96557108 813645851 910582470 768784670 767905606 473176804 386703453 831682192 751386897 78907295 830249063 988147980 406007788 823392109 750129737 776634551 909764859 570681108 188333492 324102215 145258074 200129664 264717760 969079062 133162687 556905575 177839286 497307031 385064653 22615033 209315523 905847423 988875374 326752940 660764207 608892454 944952043 447122616 676923517 407489636 153131410 718763989 966711158 672773226 959158110 935968296 630338517 489529763 347038064 106849047 468966853 783394544 935346206 279904006 133971737 636812423 951167740 923129066 588127511 690080640 215589868 592011176 389972516 325745057 861351475 177192306 366585781 716211500 66591514 390072591 54895648 426944628 85086231 454915381 191508602 737357083 818703849 527446108 177323695 881174936 642967148 244691303 545738947 932137832 377640967 993414931 331462381 813983685 572427317 335422200 404455261 763904923 134213372 194878729 373811366 455769283 832145385 152961952 591938668 193933346 119102171 105933447 60825461 405505284 322919792 437875170 470608653 495340844 482756629 676212658 7256054 867892444 554990614 257038060 987465967 263375867 131237929 277033218 703598815 528649195 134655626 356743610 458093725 989738848 609347417 779855955 583836345 125337162 86303072 500336506 538071034 331897535 252582264 615867537 204914133 634899101 799443768 761212490 357183452 676062255 212909419 843424811 509380479 949448933 446343305 746412419 284374561 493659549 295477757 111895686 978932718 770585007 491916528 708850413 42854289 375171713 799356854 390608133 738912731 549433580 435400423 646320702 535647203 133772742 879498203 364724110 92733742 97927065 551419353 465330494 286324123 980128331 792846457 750137805 623354583 535926296 670631720 145638637 172636421 592122226 845130708 595817487 689704409 330239233 692355631 789728114 11793634 126136088 893191768 376621155 819670640 639054046 31450122 586847125 853323621 667288212 819638957 400832385 678372912 960351212 706754474 112203251 304186684 922654435 202115225 533773108 123440280 741193316 988176609 934803770 488470909 361507278 553822287 60584109 931676022 271183071 200825164 875678850 98683704 699173846 577398546 565771683 751512381 520433296 243495258 718360976 646541859 534423216 268001859 771287846 222328733 931522829 69732546 509585418 561727545 430740664 519562762 222186783 192955604 900352421 250701684 486369764 608563665 763477002 353561766 732570374 866973474 683433584 157419721 964565399 30855749 268498148 698902528 758716065 957032296 112780244 347378349 196729345 917797005 615764660 435635932 495803222 627760700 42079622 969269529 341083597 136679776 255681497 59365578 148511670 716564337 62740935 200717800 705934704 511102302 337298862 905542346 227680268 677491198 582690374 839239989 838356715 645198476 819294088 329841779 233979933 116619959 30421745 230158504 674922520 799522025 382933128 377781781 938660203 170630523 366161009 131256837 623885873 909111980 702553600 572136273 649043702 87736250 171929543 758350868 916979294 212996963 793485775 729295076 726447506 812832808 699800541 645475818 773536692 822279428 378923085 773536277 782573286 401763775 685836589 303449180 116693554 620416524 726779303 244007506 816153056 10664893 636414998 283624635 355865290 92206386 517382045 856123701 661861126 680318705 320068857 332522727 672089125 588486128 752146926 632706821 307772675 359507361 927200192 236903429 872086432 999865593 348314064 950538121 412502536 375509673 763462819 247061649 537096946 320255743 567956021 47280044 145111282 274863288 483629353 291446069 742430377 152922752 557225645 58366644 594207678 660431027 153375765 201110955 735335264 981481387 280653388 609313063 568028072 411057414 686646720 553531024 178905747 328361233 429590755 810657347 201122124 3591039 187281259 577786836 425056036 856450219 96396378 927660794 371234295 662060752 361222865 692642435 894680587 729652029 290234900 146917774 155163496 572667398 531256177 836511729 561300706 716430743 824232422 83305592 903976063 568906146 146697090 51539889 45041367 202775155 127782899 871360397 700554341 759355579 624714511 63181344 989440684 536248144 438851703 765448560 740588032 894459915 308731494 53344840 632589001 496974984 984282350 724984995 500330419 937376710 164958661 965788838 603256225 776033716 90255853 824408003 806702165 751667314 500963591 696004474 244100755 516661588 990478965 358081705 216246425 648803236 991182124 78049883 960978362 845589724 164920173 452693677 647848173 788146361 447318399 43131244 922691637 1019593 750772586 690270997 283148552 901799566 150722730 565507685 52913344 44423265 842454380 934444423 452593127 188925452 557576355 999968220 72530366 359396415 930912990 795067694 385627200 497463258 47114674 270369878 280089101 566670168 114746891 947407433 479857168 460346805 816344014 390256858 246281792 635015349 251208740 724260596 960258288 128733717 661066971 92439191 482035043 361216031 569656645 360990980 371923994 271672829 968853662 374384380 969742887 619215193 375743611 546553049 659717454 942573658 192198712 71637852 319301260 174373456 518761840 305773866 985203241 482114121 131980600 315444134 167318140 908433339 279170797 674074252 192802485 720089631 701984071 670216210 313684236 491561517 319967528 208077416 659753642 926138845 531247095 259810926 765403894 223212955 246232522 154707318 526374169 44496033 857823074 604716375 25692499 272056942 341584199 872492748 957076001 55823225 938080905 937558244 21682374 475197323 809465752 924643149 626993605 423976259 469400099 876075104 77476611 679031844 71488531 473206294 647389361 447373794 904780393 394169657 314167814 182888689 836779065 765284563 891486582 877395878 25376866 479276970 459593500 430267925 171217954 754978648 950090687 91506564 485084835 351871067 310291268 860509852 781277786 770866681 331467784 970610481 28553900 113352797 583794550 958164491 367308310 590766944 740265383 116627383 488382323 40202741 101370059 233480574 339197493 880299600 964760414 108385934 240376805 196011353 818410018 294666712 190485438 814527591 996111867 907060281 86229710 436318679 509522721 80661601 512558511 922758991 551843245 245681249 361127193 70668755 639887955 649299161 471643051 406782583 801160883 268886365 483684905 37218931 879003213 37780514 410828576 430201938 37800585 396064428 572375694 173531238 87721110 994238092 865291691 387209916 30818723 110495132 997886009 559376359 719203287 554230023 560577919 302193994 512328890 924589756 6162396 890849002 88429366 498699046 89720114 766361949 705798278 194458132 350513101 423320434 993277099 619969776 315632999 692151686 499225803 503499745 842717439 114054384 815549635 1129034 8982813 255833209 62384247 818061582 680275386 122275438 534341380 649360203 215805556 779408261 672178805 272231179 204018414 792774477 838615706 942232375 868393125 364769569 692640701 435968871 660236066 349938078 206783280 833401282 494443183 764925447 712328571 145459506 730232038 176694886 679017470 474331332 800545334 334191585 737016699 354803832 693162953 197551663 50754745 445965640 38787559 824040389 282072871 469430407 296129347 339719356 563404773 46510603 774554675 238609915 44457623 738229231 88668631 64620955 394808372 381741417 858836202 844345046 61752756 599846353 197875692 271564175 292524428 348266890 971296235 904584704 58284765 431801935 378304112 809411433 380385715 397552466 778522779 809129772 945947255 30604241 379073803 811214453 5572501 446790374 598987777 539925056 176238231 263420331 447064606 404496369 360166290 127602252 296485746 761073193 175159417 315765828 606050817 771585444 774936657 507416896 989115156 347823883 758353453 401787618 822561288 724791946 605098991 437673424 643047455 496737509 536504892 335906565 714188118 563099482 753437613 390150231 172385891 628372023 721620442 162470824 241896667 505679332 246812112 553732726 151524739 983449225 542978140 839670487 886376993 593054478 623268852 8347483 606672319 492422357 134868604 2078454 910738803 421733666 137318714 324636038 93047966 66604122 330441778 558760637 811105498 728416967 84387801 58074665 691296680 2334797 541120697 861083591 172411383 521756020 482892780 749699197 23292432 418107247 109618669 306463999 892113263 932988233 323425170 55109603 159528601 885104195 824761476 607699922 533233398 775462748 836759390 591578688 236321755 998556923 357208067 382255532 955971019 607326941 179711436 86238487 128520152 416401992 58356567 477864949 647235191 627825442 465125591 208261643 12414758 333168573 292094963 945211123 344062579 543479155 502181499 937328122 911175239 501949222 638724733 278588447 513999946 518587988 31988240 754415978 398730323 389165023 366560142 668149705 413082974 886464348 792778599 924312991 483629120 63183993 359912800 510666400 771220627 990742091 770728271 491922225 49927012 19781682 119989896 694997139 825526631 880909674 477141903 185681099 483983860 741533557 371969036 93254592 717024155 580196403 831330908 812615848 135356212 622589494 459618601 435034260 35318226 672418679 635761789 532559957 6341958 909922166 244212124 392118681 194921996 836943275 936379086 259234202 142062525 607376370 119638081 177446909 112952104 643001865 585629417 420811192 696773961 173142136 10371479 677647046 655083153 101225619 747780143 997944475 437398278 636621080 51300341 622407785 507024473 338084078 136808724 77037423 656540848 229854954 851406914 855339948 126986685 494176779 434241961 842114116 725900243 285470708 382651183 149025505 646955989 2010149 196616025 982496104 880719383 931950114 302706992 610436043 415004718 298340151 398818897 311006949 9426906 799041824 685451405 641166668 857944096 487602340 377945270 885255917 894338310 329605460 806713447 115662595 20507249 192897252 464813368 490492081 484306744 586702372 444102982 709058221 164562491 908491042 875253188 383329945 42288730 723286292 384704927 478502626 982333645 959935203 363555950 195130376 546682228 818574662 779598131 166819690 43840022 532534082 141570549 971276503 327777128 375640644 812062833 787436766 367646078 336026235 78917814 730160930 11536623 793176928 845157647 978469547 624841399 724286269 263238385 685434859 612907798 859759612 549871959 360560422 852865685 714805229 226445901 707893602 869034044 548522607 854357170 633059217 208967912 727974641 748745551 883002751 994415186 937976640 961829187 538924062 682172559 679573913 648918423 520285142 890895846 688882441 223454097 331566030 478088815 269595079 716938076 343488580 907945632 228278859 503173409 353754931 366119160 321014772 843777611 846637672 472263150 642461404 652009460 56688377 57810458 618460934 23814688 838148544 578879260 25870298 559494828 472860381 513165647 450061422 470516087 989948242 988775221 826087125 497265756 282353860 185622674 23849161 494627542 358078325 480873417 64951886 350986603 593890557 600116382 886831087 752058913 230487797 243438474 169592035 315230912 333955264 807343356 59689746 462582347 787202497 201455892 991576401 474999494 588613977 190318457 60143731 321849061 684993647 191878865 774515335 384710710 262503245 990222052 347717621 704799892 133801884 657065979 674167279 516264971 7133830 469741832 222419448 141648891 748336478 362589359 822077830 496785572 996181637 953037015 860494227 32857031 142861070 894413652 920710996 45195401 558482365 10693863 167574516 412090205 75134746 535518925 197638655 258245364 437083052 706090678 859917660 790089499 518816831 223213558 306391635 558301361 815335388 264042653 672110014 103944613 994593763 820985857 657753940 503344478 871350029 558833652 479699242 177342557 722584980 505503051 753326444 101076648 118923025 10660320 163915186 321335051 528801945 239777526 870490167 856168016 598843045 911837846 882447410 5583271 729068808 803015694 465223308 202433062 427464078 66046573 43317625 394158341 433727956 412260597 978065649 713053122 248027229 319650883 289481941 855353457 810475851 345186659 685629980 942388049 889126188 522444280 495077369 91932283 488328254 984790728 474180876 47402032 899425158 940874567 882435691 515995928 205265533 27922522 890062606 643520830 587202085 959076251 753921194 286826586 698961286 168627962 705556401 586340718 886217261 915574353 203698515 468299734 602360068 893280021 101325830 549668226 675991071 484493813 629907146 717158252 317684096 440652740 197110484 555790135 432844374 600725406 302500344 729971376 550018419 998318488 741498758 100019665 273914164 122095770 310327366 46169318 391326324 94177567 210964339 658246837 66218912 198764840 583112028 883587178 859897120 418708282 315832646 186833354 135185499 662751806 41523894 103275765 992969816 285321754 890675981 491546845 470955997 621877984 775920755 74679026 222530794 623869670 801951499 658295332 245839021 995718626 487470627 361545523 157544825 672068753 263040947 166823370 388325881 584438760 48703999 977036656 160479527 686370250 542948608 302134201 638487128 674287992 688838391 479078626 664735297 672833926 745276370 231483672 143999666 140054 445179497 722737493 539541280 817000645 977061275 628246661 280705820 145467362 778099110 233884831 490867583 853787218 799208593 860834635 361970612 778775035 907081910 973594528 82451083 239985183 221387309 166779697 155289572 101340702 37740755 182823952 405134441 706104020 765992514 272403820 186579640 221366327 469746107 26938846 864923120 574895235 376216051 411384901 323475037 539370297 6503673 664967538 577977662 369180675 399744115 784431157 407533357 49049270 944234915 481355401 245049033 433391044 505173658 425806109 766640148 454773883 591125261 165318584 548266274 79911703 625656546 466708943 202640246 58947338 694207087 838710803 819848082 584739005 213117857 907538229 498270574 863272387 363172132 814050304 384075302 851474188 154865775 691463817 680960839 606382624 192871835 75558065 546990264 808271501 241878262 136419775 136004905 401210610 270934942 735573129 414346698 840269600 160673235 666480076 984361739 779897544 991849575 917094671 414729713 177320221 424760382 591161722 621057852 247808262 824133371 537082648 868079076 645574245 763130704 266230380 879513905 431542879 454349881 370060465 831418381 935446508 633154930 570775341 186150668 752183160 117503967 103919388 975158099 632394323 907089993 80745081 182039977 808301298 497983958 765559840 585723970 457707384 97260780 63563985 866812666 519441281 152854419 184801859 593314543 134106041 507860840 491308517 21627938 358419352 132844019 835603889 752136823 894949453 143355490 817054086 808218578 962625497 167723879 118759050 785534920 660687594 675272266 186837342 177378426 526449966 595698293 584958768 139995387 492540374 427261163 46111815 87753558 464993654 838923603 476382538 647464652 740112238 935374391 769896113 588375721 109012128 587797957 745579551 513163048 92746631 391439834 728415387 752701 804183825 746947031 866113668 746856417 525317698 777625765 667115462 580611722 959575537 818456425 126359851 827792293 417674901 946090848 693257838 127925250 231776801 551981923 935225248 219021809 477064452 402444352 678557057 902734997 904930263 719144655 889970040 196004325 279265070 897595921 251856947 730356499 311565902 609173381 959799157 85351434 75620853 742773937 575502544 333508973 116810744 176438301 503000510 706667217 238552504 568923037 81823321 721054845 600051130 155317848 821640988 480413210 149687610 21291977 779480547 498416687 262483541 421243006 578262184 564125810 586010689 309699427 470168051 814553219 939011138 37826915 434964328 243100889 266634364 891403217 785524826 590688162 634300059 103792465 639743964 409245294 691185968 114469354 888137196 333891258 171307506 114039718 336049818 401401468 652128050 314198996 658934013 498973288 733450767 479347357 761794591 585196339 617323575 2862127 107371528 523498190 443223283 662058959 781445972 229557431 202466287 396302734 154195153 48331715 80291305 757236439 140248679 539739884 683035185 618183454 732098393 699201012 109173209 20567931 470933868 32828327 675929970 863229322 931046311 18148171 5129278 192653813 472960406 868712577 60169275 159812779 481224338 29671833 730465250 213031420 423342437 941659682 822016568 858747170 622905060 479816347 829523841 293097437 525336839 597712114 676861147 696899234 3358210 256620722 301960633 735173502 911972243 288963854 723093917 644854692 835613378 420679218 988702835 757967642 795576129 946547940 842641291 329816782 756963864 427178638 511322465 478609639 427383400 748712954 447603225 976575828 365471989 871416112 248701735 931861979 654652637 153116920 180046894 605559092 452119501 507405831 966462408 72265266 400155560 283473301 318730651 387248135 668948354 291068379 883738626 381016072 422527062 260607018 591727182 698611412 577011455 495617768 617383760 262783117 728170922 461539183 67154277 931078292 427713162 333541270 229319654 421955338 5764941 297248245 981351401 73186469 413051875 303994005 454074247 411149384 867957569 933750027 617634459 848117832 959066454 495399826 680134482 463931235 441983190 395353481 165876995 97571810 31662227 563425140 232988981 81986848 12610278 585298636 503879367 463034005 628802801 378756450 733815945 868604385 258682322 181280926 829365686 802389540 8311887 989766037 907582958 699636655 592990760 568049448 413894569 836957375 827237828 333395782 713469686 609212386 232914310 854605677 787468210 311775753 433015766 680165748 831871727 888862123 361414191 377977647 381190396 768102425 635723219 144431163 218659117 891677049 267586974 889013577 331776310 898654130 494146491 821759134 964958215 267574429 329184703 648649675 250519487 473543907 39009311 924100734 195314102 497429915 303710638 830433581 795926718 993453136 117768146 813662533 194911444 524974358 664502353 668232940 502105467 616136810 743504509 645366332 133707756 277276054 557951965 747293562 334486647 138068740 860296021 895153049 556624417 524092823 25523506 882627353 208399875 549511280 36142840 873669672 936346978 667396817 785818690 900124088 678713703 732053984 917807033 314534924 158989813 90296450 666786922 790045394 692078809 79409133 787909230 450744317 574600356 160233810 682912085 233298454 553666921 100400566 994823127 977685483 695583592 385814629 531476777 372528437 623870013 885297859 618460156 518609334 329235318 795180244 687364076 892724037 643318526 568571277 93814691 989170323 729140632 87412390 181686113 474487089 82500982 604222015 296267358 490663166 879223854 823323190 345167998 343254564 932177691 778677448 512295855 545672639 267529024 254782712 313809963 386034123 74598309 192370034 189039351 434609028 996789082 947132103 172479333 262294979 141159178 594500201 783695828 650809798 959369039 554773679 156952109 405783087 552940512 542432802 41499141 74200683 889835161 227444177 131470914 638086006 351999226 235235788 90555686 780400273 549648294 160181628 33524969 859989567 36110447 420890393 730102196 896456556 810230575 197223318 52813879 515277463 539810803 432811639 119722321 927480648 107618232 273085368 866270979 477809961 517890636 931667291 21094947 477616674 512575238 832240122 805830569 259987870 658939146 961244550 195258312 378490622 840663753 582139905 448592426 899777665 822898699 753884495 196681493 391350681 13703422 352745326 568465156 412978098 125132856 920337435 495112616 583917435 158219474 31982098 297788129 803890629 882192645 538372873 514159588 781777909 185184756 711360986 213804298 28800068 4114508 348092534 771875700 476654144 485565333 831936420 65407221 550843791 251882150 3476291 724594892 746327603 82353071 806425790 793026549 290582901 794217009 514351859 453626208 131039066 738156412 804357501 700675475 450314976 910694859 871463938 369075050 598965906 516564550 794502055 146653060 209147252 233413174 450171529 87008670 920597186 79051690 467742542 680048587 445435841 994889798 587481951 373057823 550066457 418959671 752732651 128294045 157869147 275735358 848499100 724869870 676276324 594079403 829509561 496069408 283287793 412635772 863683673 317584483 41217410 408520001 920214112 59273167 969240766 657496225 268674789 836553593 266369122 379086177 172665897 792903312 368490157 440266596 921607164 621305751 994864 974970297 657766720 281623454 112517516 332695954 718028292 519157657 353275445 694620142 526003115 110138633 540968577 364655265 58485651 304190312 391609651 548574609 807681649 799867262 903430710 626519094 940166719 836232492 809566562 727194095 510244484 103492288 702631485 967605148 125455512 306467793 670101110 867289114 921885619 700382698 381576107 538824492 417479621 939205415 532819405 841239541 747863769 483891802 486780546 109828667 816405153 653609669 498557323 271305162 253376304 936116459 346800028