18681
530206336 238294298 665359970 145891556 790047111 441702854 55250442 971944522 661519040 443786388 41899075 914685731 788723437 994055465 256330802 601221704 981621729 17818293 166669363 223595186 690383865 149470809 228806922 674885528 221052466 244115574 881394190 82904711 825734739 303104074 945348777 149877653 157126209 458824278 50368040 170201507 844704834 212297534 127347816 199732895 336851715 152067528 857830282 908215590 623928565 639113177 973398425 946735448 137808557 433436248 456232794 648724448 677583772 755081017 917244632 249643314 912080903 868411936 98121433 53103736 985806912 642209998 971254416 97334229 745001837 65279388 715797226 632187037 788995615 582569586 853458620 705106955 246935215 24247644 857568761 380107402 59179980 664212305 993096175 184164003 984699148 995073080 778398927 817068599 30329846 200478159 831753882 187627340 365385170 883493485 993915783 179246196 113544021 773350103 815589458 967074542 676387396 936854749 683453107 863689104 102217227 714200223 387197354 127281022 609428324 79442394 187309085 757290296 236949879 68354499 667771345 542533146 660635848 732221827 239352648 288624614 100957131 430310999 413863582 959280026 150632272 633596987 775880952 27857227 783274745 233984176 840998387 863462237 912831301 356205050 467931490 240332535 441044148 674919685 753996282 806714133 949063734 505259029 433256924 402111509 49884409 195909724 391294789 25717092 512111855 270114120 729457836 590827862 936042645 91656046 337632509 318988097 607739132 621101069 904335034 830724340 633542481 561713145 171218254 833459431 222343413 677620333 754115865 54128524 344733790 961488831 69510103 423325795 860641650 271933615 991501947 241710712 110560094 95263369 479944204 764537351 378647683 270130023 936526055 439108920 254674936 960815467 406980045 720357358 699886785 85785086 514335275 763737375 550836326 42020649 454242812 286247488 156049154 884767281 287235727 316338837 932780352 890024324 324183148 135457382 995327883 384335981 712380607 443311727 165437984 31483417 831821781 319071218 915928525 241623207 547128768 87880204 659655980 440365891 410070291 79039853 207967016 866617715 283148000 172795293 877479647 302190796 419863486 627104502 286919874 861525283 125192873 671787281 901975519 958853575 145650471 411889264 537800257 780926437 341565182 979344780 742304118 338800445 879738782 580669309 747045535 120950143 84307352 457226317 607766399 488843355 151155139 523288308 647888991 256157365 327846698 79160276 300296733 737662492 663434200 138365442 413900170 35473559 435850485 570771673 98006546 248001318 468287448 511994298 264081879 802097592 559552593 33855634 854425023 243523946 733234861 138830958 617809461 76964005 403261673 670647383 806681830 564618550 487826976 653019895 624187561 871188723 616209414 852801465 535296829 582723595 814194812 135679563 340713088 858785057 269277281 259987815 401960795 315763534 558170970 766795080 692702378 962027734 628481915 643066919 643468829 154833611 230987180 192622650 765290393 276385995 909714460 144710278 431221547 278209804 600332468 214457150 57192403 568802915 791602373 904811637 739447782 639006439 390096091 739101869 90542953 946455142 599000759 82823591 551273588 321671232 465053763 476650889 955797471 568970175 108653423 210752370 405551252 426945682 266862855 427025339 952088811 556862141 251127579 433778617 178648231 589329915 158362822 885971891 368794739 951158830 800445184 962567892 16477405 37862083 196720893 207077417 883204699 149271483 881379734 906831006 575571598 63898326 956606492 227802465 34675392 493951847 157093201 582358960 382249316 386125924 628635199 693006389 963815258 161708620 562958636 697062676 26536867 824278314 997193838 57690840 184615013 67433399 443148279 404429465 531396065 286005539 861061107 888611281 8078915 88534278 72546051 755332456 206909071 546117024 309092824 646612089 756507324 705758470 12285444 694964267 543208660 755566758 126985426 121711466 912488091 924031976 276936246 948192516 135658320 123092543 614965602 294857860 41287115 511912337 261863636 676794585 895975601 163361916 817818847 477370553 579635899 470769715 616179791 215759106 862049348 638309967 797120138 820492606 346037271 303526843 710817544 591104489 648101173 405513774 588675318 81846560 823732767 230607450 507414620 335624117 684191446 330985328 172895807 895582177 967775709 593976103 590446396 62048708 33822811 602653508 432616901 567572480 454241234 643848771 481403516 980268324 78520735 628352271 967102566 946474145 546523743 222434400 317666898 744067388 187446979 139563616 772620862 536994178 822153679 581699520 526958430 564219473 502495132 772087820 890431648 376413786 895414462 712726565 653133514 294730781 138880431 550060852 869091208 678341914 937662957 257090388 973609891 588362108 365277192 924571867 700001614 924197135 593264017 511213203 403377643 881730668 691088296 453472123 665436075 427948817 753063691 254188709 933972736 6153525 550469239 933392788 557349983 237777545 219640288 828297389 929051798 468534771 196959523 540834803 154906966 560035531 326527782 4600948 794364004 178445832 312594519 690346591 55360206 713714365 147007098 694953176 810120332 453393817 430110482 844259949 609546085 895270072 338524776 916877602 531386026 171460612 935145844 418146777 469824251 148774076 61832169 784728325 490603173 744895799 650652682 484751540 570335690 953283866 343620311 781204741 452811977 685131144 865730458 696955045 411309772 471323088 875343464 227160800 710205407 773289457 513952013 139199477 443634432 456011346 9255545 18232612 758529152 69237605 725643657 694360003 913145838 428251347 903577650 705173584 770524542 990322660 389176304 397535861 966017236 969924655 185808466 759735088 34580892 801135615 533308450 45859640 486338903 963140411 315302710 938858880 633586739 947436041 661485593 499229100 411414208 803043180 779679782 191985836 58283885 705402664 120070449 492442700 51807221 605369353 163707025 215993640 237006532 41958084 773806107 203757334 351810681 603261327 350937697 387874714 186310055 518079453 387071625 558123626 222236067 458897478 876582434 352554227 761675651 128617690 672895038 329021690 303325655 605787852 397436523 443699854 612223018 16386097 847111815 462760598 962491552 809749144 115082099 840892888 322933902 241587696 371695291 558921170 117258704 395243107 302624581 435955703 718596154 832653771 255602249 248348665 399642362 268142629 322728211 966234529 647713833 892698896 140107425 274319246 261765277 754461935 715237242 829653095 72794461 161942132 540922830 521658744 921540462 520207687 782976445 15580220 617331174 488723371 168066551 490006394 826135127 391733521 116383455 418966678 375899594 944160263 628489454 562193925 466316176 221894448 788150553 321536375 940783161 376569722 457266825 121169060 368886667 139525427 881893393 842886012 474368332 359276856 129291921 777028233 788500234 21961841 180548204 431312279 695429270 502649976 491039839 828859146 734120434 92570337 827098446 146712516 934970717 922970428 217750713 893850826 518952217 685982049 822174275 982056815 497042841 118447658 114122958 856729104 101719728 272180236 594775340 267147276 354302513 116254968 295060087 874959527 618857696 830319682 894231282 808460995 667216806 956860664 853129468 758730142 741573321 649190694 773296872 658219519 987291636 956205254 24884894 383030521 665667380 531609819 642791749 855054674 323877026 765642364 865041792 884329500 894837376 710620139 46030633 323482334 638339644 534516746 55453104 785328321 448098316 795229164 311762946 403313607 612460056 47856901 65600593 406865804 472555581 836460772 563300000 862230791 422399965 462862819 673490407 995375179 115066079 581592966 463150368 653373399 844102100 793785778 250082090 233938025 490189297 56164856 134694705 897610710 461016490 912855836 785249693 923281920 868910897 183235777 793712384 425750656 396172045 813679713 690762009 210157861 966696278 65332899 313461896 253903105 787220914 451751238 533668939 815855885 996156205 752625494 689640660 341502875 316537220 807172352 688491333 463646719 429546815 405691996 889035846 314531358 392433393 929865955 732347841 40685549 902083713 405689203 364601922 897928037 406357674 612838444 69610455 966040929 59274098 670267470 33546709 605026174 858611061 844326148 146146919 155619635 568653989 697759079 289992552 662611242 9310533 107437688 481097150 181077333 506836140 694840633 986170975 710200072 373438568 937829678 134494436 495395145 580939735 871986186 530482837 988222083 240822550 300940351 689931597 663021463 27017424 865239124 324945576 542598285 781165552 549457414 671460805 981423577 49714002 792358632 225102207 869025276 673104786 766124639 325105198 311713325 974224929 114268293 861175272 966597592 47491744 618438913 998711328 646836799 246785569 604055236 183646053 631685407 893687687 843759427 502415197 679699095 746302238 88763805 891214491 370769964 672339796 343110311 361376554 101060540 587607334 368656247 675474550 682182930 664709046 614042858 356458909 864126186 866723450 238116911 364594969 990535238 673002055 102808014 374320205 774479515 665732347 30663658 706416770 958113705 320822443 77982110 525912840 298743963 675267484 325252725 978889984 985894921 34943689 256436225 186186064 456455586 513852666 394322175 562464334 27056124 576143214 381905076 831632568 894721434 799211100 595408966 695942703 23592236 298712949 343790527 363476650 284006925 640596139 273598597 286819232 262712238 467280900 107812515 835233474 918009413 349042587 329690169 318524663 54842119 780270436 5820184 362669071 943942061 522354925 58276837 109153109 835163365 384286382 240901839 551007683 317788530 383404021 387239142 815124126 769039673 802377149 599510130 549871200 245011828 24952804 378287502 160617482 650520313 914196266 936487291 991875393 297233336 122109486 71040067 735994169 366332756 764344342 139963453 419921712 516794853 323266229 334309389 589539416 964798768 773643141 477066857 940674423 939679858 575389588 988279083 999476460 575858188 210816699 762923255 572027951 323365690 602846827 984469774 176774859 972503120 746328483 424222920 386046304 949809466 625946956 505939744 82634614 553230349 127909666 85548170 413078249 743562130 693158382 409486838 796461890 61808767 115885339 133428851 899277994 668465852 669658651 647938103 96223766 883121271 294970614 65644323 431199805 43744596 970644194 477590724 707120368 780207251 798501812 151156399 155523977 967697302 570107652 860841960 899039361 435382352 189317707 739507290 434212892 95591732 994000854 723398939 431465331 356720621 879883152 537863339 682099594 747585822 108029298 810073739 722332758 649817979 714690394 977011311 794865847 782126470 612254881 447300687 920609164 83702285 36517143 595468771 209058053 510633459 258703785 710319075 382660233 103121730 680059408 376643277 679931793 257568738 346385367 771173813 202306952 52060051 726759801 840495678 181664005 226495399 397340859 210696385 536984735 220985527 796282248 764545548 589512237 489909540 842865980 987019133 304533566 160263838 781038743 190258717 147961440 476204085 552494830 967342893 453221867 611983416 633395693 396098339 990329295 891418999 843057720 153111180 903036876 494671078 761641441 170861894 539292938 519362359 986669355 224996367 973643262 748046106 73375916 867565352 616732828 517482391 315927611 5880038 354720780 309809640 158048246 419862257 45523736 583989445 728088533 184608559 230931715 211694454 643844952 273842284 264016191 856878473 143971632 637209718 573389043 729028337 233392905 850702358 964827162 498324660 981638248 499352181 220722690 665364667 435219119 617016924 412704425 539258478 896626678 503924973 941992292 224145558 823793947 767915867 521400881 708691811 389442352 792219301 864604734 531199683 591098560 113439433 382943675 857919428 696368535 834362106 236433686 207946267 844431404 919253819 543132709 440434144 627942791 345117264 891621928 952643014 15220016 748705430 991239288 386276140 413000788 552449686 173888168 528029798 388837229 440492089 972910873 991602885 252015941 222829241 915164802 495859208 418165490 276547561 838047090 866926926 451085795 568539140 216602126 194963171 984490828 114425630 691299277 178718996 466623430 53359324 86664873 841034291 818238514 835859468 284053363 961648416 938218234 306486228 440839359 172603074 265057636 359024385 42932193 928288356 496209798 273706329 613380167 248285515 809790642 842950095 227176799 793895535 951066171 210043243 338219949 822406693 487210716 878166554 510596926 191218342 474645765 641842812 135859767 339633505 3666811 436760234 781847498 247983916 795165321 583710472 561399079 941396378 5401237 419634040 547481961 640306311 528244088 955097692 521194351 738644430 161430517 802229278 552021063 378568134 967294536 794650617 326486850 499138603 750322975 278400668 745373289 513017656 498315105 799094544 354654257 628873268 781440331 635687262 783967367 326619721 737594205 200231990 453630438 604182531 863127940 325833698 809621579 609365404 369982489 627173270 491224091 330990362 408798625 854529976 891410615 836371052 793426342 424926033 330339627 452450601 895848212 704772308 937503297 516876936 163224866 588467302 517832534 859583776 576368878 12877866 913058166 786043234 777694487 597790881 646202573 868323029 690364468 404425110 90712242 149833593 121788131 786593529 541763170 636025993 624204747 808495531 871309577 725686776 684161586 528046968 570540975 341691442 991120298 374691098 277387321 685228297 906826335 646386551 60324778 194845506 723320384 998498303 153318678 35217970 355427745 674727625 875601207 275527016 523920090 931541344 768596831 956285508 998250409 136416467 705700669 974345151 484010960 480230379 173695739 105701994 53093595 740433911 507003424 298122376 445166497 11081373 276788774 973844829 969460412 798604347 974096971 545356311 439536681 470530074 855910693 978346996 951342166 188430576 497939011 806549710 49419526 913869958 313016058 956334463 152552320 773641972 364282982 905291369 411382768 516094060 947244798 814543135 881006356 485894211 456230065 908939412 728668327 246993728 175494202 50396930 661474186 95939805 975911798 981850229 302115050 125539580 305736357 569387300 151341745 767215422 317297917 282704232 896109606 313269050 122208774 189106882 169304246 418683257 483822549 26702354 417609086 229007903 367206431 718972621 662415716 489803773 501831279 752798969 501481803 43079893 592975023 328498180 158138983 356671662 966647734 561440984 12311822 470117550 241030906 586036801 344251357 884790231 433728496 263037893 322468146 27006014 903740513 457774336 814644785 516022995 880598076 330592236 49565138 817974676 353757326 361022887 14913845 495548373 384215601 399369807 873534450 147979377 787408070 639264496 793289646 641017181 119954754 268788876 161166447 784393863 676496169 492018556 489467592 311756178 279370970 43624704 85021078 426884577 367280832 107154207 711672994 555247409 767712180 89880053 954460313 564615745 575182593 860316625 539135738 399873745 572885967 453026441 255811857 761622423 896528729 635207743 518242576 251583018 220844325 264341917 95832993 241643200 817896517 938799441 888791714 315541982 41817297 416614996 591945480 294124111 610012542 426451439 208320569 359778026 946903093 361544405 847570256 800581362 820187202 202437407 168832774 726755719 265546810 719500927 621933949 252051546 238490352 662694251 331189014 174020149 681759758 597135376 818609180 665026265 481310579 23913854 455186848 50354190 872403726 842648129 420941371 804388543 274844799 409299495 661094367 632939614 983046155 770148187 976785995 833692360 226228741 772175702 796824620 470027204 867805940 211474532 601164473 402433092 967050480 330923423 844938493 981216841 605480419 240621537 591122170 216063157 489214202 266916390 156357173 472218104 197483133 340379978 784726214 678661942 396299793 49836612 30301150 317265858 958733086 395247384 481351313 272813997 135923452 497257301 191650969 861575715 385410124 496772472 451519683 57746540 239762347 387758660 157047018 614951462 205626714 237000554 609188240 15576248 340834600 552249655 796837644 601651195 179972537 242034202 156578238 784026656 587398757 751852638 482776152 723583610 82288617 515971687 963598847 804168953 400334907 604409997 637049505 520881218 127660913 4048806 456874310 930890569 121514855 798307029 422655236 137341285 163550841 125289508 807811461 128458149 679747243 158382949 143039930 978639973 487895975 300651429 362820028 177857265 776070039 306444773 469373921 483593727 710473270 519375611 90962258 934017292 231063659 601576384 641030935 612449305 480521290 915148812 373076148 107227954 33610463 196380317 893118806 697593234 956783153 487411534 822873010 564576265 557111187 688865438 372353777 300385222 66492823 302237972 876986190 975885357 91460653 306627299 727577746 176107045 791694334 698629601 854093657 539842778 698855951 745346542 703799937 639400867 785840192 804425826 510598223 684071711 735884443 489820705 16971716 964974973 959990890 116040927 543961190 998140685 356223799 728871712 679743179 194280217 548284838 690565941 535195565 204436507 545549446 612034369 667145783 386144220 576217202 101067376 533505010 269461009 675041085 314086874 592873121 18894321 489895734 225087015 208759110 437730173 311567311 689834310 518826977 859418786 294911664 126626481 829437626 128600880 578449439 236857527 295491272 92984461 854782342 793361660 750042471 160136255 717953957 76863137 516988123 937253358 123072175 897259165 508970234 922110538 316427931 9116125 648178986 244118050 415961512 148757553 605393583 293493473 272364883 420937379 902632001 423479259 789673895 231595528 308429480 189564956 769508068 197198060 565556632 568472117 740918547 343417790 432608009 453601566 582904955 876924679 817790560 816032350 470609715 977708391 177160872 300407538 332003077 690907613 841975356 62951989 898836009 488675519 856642710 179954094 399438417 167797732 270570185 555879417 515231660 92635115 158246764 733511916 65501658 968759098 745059249 147912576 387558993 161124518 214092315 282529689 216828618 125695039 852598379 991843268 29854294 375109958 227073461 795442931 498436516 936052872 766743216 852234496 440983875 958491443 360202517 13436681 360892856 972009740 831898881 186158871 866332672 740848846 386508166 567564073 781640207 314216270 101939915 424474826 226400254 974679441 530093791 810384187 211160129 81146820 949249832 525642179 606601766 156657987 872678701 618253869 903910539 19320484 735187587 692602809 653580378 955685927 51289935 203682283 17683567 727000846 909089150 187546871 60695232 854788692 978321343 927426134 351785154 933183048 841688100 197624609 910997479 82951777 770048049 470359392 19719708 659617639 916443451 107114262 146790039 439789873 206240413 818360502 511745114 567474289 983439044 287769717 370810004 243156728 980144848 123172705 155747883 849571352 123244199 649877331 630884039 578658080 137505699 959019461 5423041 226356430 559094143 769345145 40094582 221543455 663172720 236552624 691766770 246166033 312822862 397828726 1557468 194232492 441162650 552167569 603867661 498052496 551099523 895224310 360460185 591577133 895890034 223781806 913325863 295071336 655885659 701591594 577703471 994675376 16264458 443181310 939067374 323680894 480697436 920305174 171333819 406434150 791842303 14480431 712755839 956627819 405825527 195701645 274578728 721249767 675152391 139887764 251844167 519931397 879278095 86054466 360777366 81278178 218390746 590633205 340038477 406745314 956811712 564943028 15280984 870011907 792308654 81224199 232817045 93568907 914017394 97538838 154980890 872896029 87134023 908494232 176621980 120183780 840573252 660829306 197140462 474632998 245412477 117293868 525016836 227758619 688240417 199082131 802983647 316372522 159456846 192814819 731714388 139150687 193967887 557824965 290707092 766110235 321655972 743153730 674574210 39301476 962937221 682690358 217038565 196723238 525422173 748904303 835605246 237096643 79847036 383785199 458374503 72080055 776208598 114836649 583571962 69750994 457318690 523324723 823846179 95954824 886429407 853354668 363338072 980756694 392462088 422646814 678033284 959513806 671383374 802568025 389377811 597069570 169920265 541123988 162088760 709559898 272419526 410015336 500865744 458058698 102328224 444401062 619250421 869596254 904396662 129462661 232401785 826013262 425703870 380923512 240916012 601548992 537856285 854063826 579739537 407947770 266200840 461891001 143293013 423187580 95266456 202164578 419891722 244527245 285459542 258662507 740763621 12400921 613918638 70378403 844670630 201938925 368551699 615677653 624815864 791499662 892053952 984242971 876539624 854017725 632327321 262488760 707524565 940437945 333024996 320451078 881235930 932697285 801409559 911964464 768963411 259648877 515367373 295039366 662977664 380572760 268493691 140054666 948892706 562984723 843139811 222164309 404452851 36742541 964893250 922979916 696140779 974972158 978481088 541005901 385372348 831212280 128742205 570572789 115369893 193517879 68648951 182986868 835010083 591024788 56969547 227532795 746085451 107877511 931723016 566921205 669858330 15053001 550110633 824431065 56234985 322548058 375633791 984603741 60615975 596768641 801558149 656549874 958452556 771956357 866122688 970469087 715821317 929158605 870028255 774934191 18891807 194423988 699581165 739968612 61072007 547712167 887172906 507342036 268972002 952111672 732637841 685804667 389488194 364570181 50550068 574320960 752980902 951213543 302767023 123154584 604171780 954506360 344414519 424957944 304586663 558670721 733094453 218832566 42709560 371119496 18080030 659765837 746101407 401415651 749716546 417201866 358135753 933475984 742449861 988441723 439791084 227612740 422501632 287418244 453719622 635357289 208731637 468968978 667670126 73567877 968235364 917506110 409824037 853037752 911227278 28096974 608502493 965155468 545769111 577020974 543763227 156024600 76016566 644447835 489381452 318888073 465345257 638352181 400694234 260580823 377858041 345572234 419579487 916892460 666268879 520142362 90317401 395737463 116025105 168866982 32106774 145124722 20988356 565191019 117322105 373156983 906334125 164938906 71397837 270565730 346180522 610604016 784424388 733843299 355824413 536719002 329170222 870683791 636239288 944796196 42696604 95956714 204416476 393568818 6377461 489594596 477395132 989906407 312806240 620365259 683547877 305466228 224028674 389553509 415956932 480438777 393721551 406769805 722853028 51355814 777464711 684545418 912498828 288039711 218480531 847793015 62848108 812736889 342186678 900401729 237432550 97334767 370600633 506332225 389817682 894462704 235110365 237998139 234602667 286013529 307122810 399703131 337597682 631646828 114553666 287062137 69753232 957089040 461696311 938996856 772294575 663418636 865138690 751928784 585488957 421308982 942573668 895625739 605716538 279087173 476690285 111090793 928386709 656785359 560793287 486959794 755218322 858030935 584887673 361391916 236762845 793681705 926508869 991025917 951572699 123816211 415036066 52656038 650660486 369504500 454126912 872386780 161573407 201098654 457279933 259014764 981648839 3127264 120206175 270466642 964880664 972214426 224317520 354062730 536696526 32899306 640270897 242507078 167816428 109326211 654642071 819527500 830695227 409858884 183708869 731461443 143108120 114907056 993731244 170051705 624112185 358990471 370592844 417750268 549621386 714119107 653050003 227230495 996855679 841720071 587273386 88607024 763526514 455102681 884623331 480789717 634910677 516440908 519326340 203591291 253135870 487795841 455053333 637926769 746067932 536148924 775464192 441903014 250683260 284998089 18343258 158491168 641850477 380580828 256047225 726047455 617065430 42247573 757547483 987710480 300864570 309529919 160758357 46029687 938042100 952427934 20672668 609284148 626876710 661869694 590512786 933600836 214771500 580802843 617370774 539396269 553081558 422226687 65161072 540972034 339297834 506011914 228451119 202165658 554478647 756288444 129232609 485450892 797123144 591847081 87342848 798862255 579955790 889461958 477082799 696358910 237850507 718410534 220318401 165085267 855089932 974431477 70719151 268734098 886803313 482322081 283293025 723368719 611344659 397667331 823419442 228265006 87162145 778895776 290214429 310483649 2111275 717629019 308283224 300322615 111781951 584313486 635202973 976303168 362068973 817550968 941670369 567357011 519773773 933444321 671540146 503555915 807604871 554899589 129520205 740727881 456017728 900752404 477795882 124309738 244598427 717729254 518541229 287171387 208855071 644047198 690604180 420746654 489326034 236425071 830504231 725284299 637427826 514761000 480301313 962148886 343561834 284287251 559555840 547464464 50145443 986481074 671729696 933780400 217143678 472325856 100952622 406553109 959709206 575360250 32579203 431247096 916339636 39389517 940884898 445006225 898756459 456385196 456365248 325592476 972942639 145308991 563466272 419806488 977739490 120196071 736866417 89940061 600321443 321020733 808167787 869150848 328034377 467489977 863767417 209726775 188586686 527003643 530301854 121667749 718514536 114418931 22363802 562093217 17966815 231159525 345834511 226668155 359266858 729135573 777965454 943872756 205810863 167780069 73435741 492456870 727189402 778260803 450633894 404114137 317670346 188396189 832466049 156356697 584094781 711903680 106110735 75678993 64250203 541875148 955453475 472217450 44023377 98698679 506746300 96666757 748509960 687570700 127261556 980373222 252417785 286289130 27830270 584226915 183397513 599743466 840017949 185398716 284986619 917898532 703223124 483841714 531056183 874662510 778960352 580020822 419885031 432406814 392223877 783841059 612890097 223938136 440347195 740389744 951275964 481782501 781008487 135820532 283806790 818482576 57764131 64860585 328097311 541347046 283029671 135713499 67649706 829742158 268335097 477832472 907908018 243745514 127398543 279243763 496739094 174820122 700023533 171866010 146097415 479341480 540884581 243064788 497924550 747178629 379339368 559839998 167485253 40141182 536281653 619847131 554537952 48635111 255501914 524437870 405876006 303973640 142752377 630815396 433087914 963756965 429088485 615794645 896443071 306812295 791226599 592292295 117541085 947517121 248669063 831598895 886740672 688452960 766722051 657061826 601927473 692327246 305000200 421629034 285430500 864738440 740990660 577515584 882199941 688904456 229256501 955285801 843328481 303313045 346594045 865630530 316193173 34331500 994766397 551133390 124611645 393885279 479512441 421426135 831696190 876149696 442268190 513959383 75084081 38945817 419721583 726543778 281622201 493144175 600155118 63752640 212236652 103259518 650008027 787769866 287178258 416394181 104415292 658996431 743418047 907798009 715643099 97489819 614047318 180611712 432083456 738375397 183851681 758019043 28256677 270489575 426929008 570546050 980387263 628569245 165092388 746423975 519319674 106226983 155689852 463374363 174119579 393943892 150056227 353786002 779990625 260666146 597513862 547701002 535871451 539046776 507621014 874828119 779806975 77439006 793373629 162104289 272953623 858888793 171402347 85212056 147204845 175724741 872457268 496789359 841422410 619322939 878870740 288489643 370962128 755060600 542381989 563983869 652805654 983895298 326029168 325747302 743605901 774681135 845149387 907393226 477372838 271638605 134568712 116875825 238845822 454217302 278589418 339309736 720572177 14074871 510770979 524366241 126858968 673207476 144064520 31007008 883329661 861540927 367392101 454015256 901511604 48925181 258004455 482312296 753855970 166273874 119668094 151025815 935997828 60367709 730068603 440701872 793614280 876966119 789421821 348817512 770081615 830565450 82945865 298232013 433933900 413897331 507720 942727061 852913807 948211681 486244104 319248209 150636103 628730484 158812380 325044793 794086321 128008990 558990413 332501522 285348975 228840774 527755953 485613495 571217219 633650213 179517833 92890711 17930690 571058193 643841634 17576355 387668900 818875361 771660118 416309893 816614617 256715031 654472715 653599035 279593968 114834453 607207027 749623114 287308606 358379520 204493888 114912223 877617726 28523883 523004255 547875393 727938552 246914902 467755618 450261462 692278208 292422864 448685788 856306846 244282111 432204303 582991660 291449803 903094839 554435479 846628290 442339024 586143588 393304297 839383523 716097301 942991610 874947048 846135984 392273150 135877639 318352503 418082674 458480440 418024306 710345964 926070597 927868939 636164147 701152614 244974539 151184104 909800954 531884195 914447554 235171913 206925125 911862158 660238460 281262705 710394240 160750225 306220346 751700265 477902356 251526850 312522430 318939649 678646083 717052909 350049526 122343254 679558648 530473420 305509514 67983200 31441131 372475507 746404054 742256283 255557533 215874302 298963229 703114627 979751059 396657353 791908051 882602460 519756180 686954220 608267499 906920956 936357109 343962082 630310383 839528222 115263322 759841357 490704566 61544307 407906124 709251831 406946871 253368745 241913029 348152886 880766912 621160516 351391787 240989989 423642122 62100123 577604664 217225159 475351292 636448842 713940745 411689532 213718228 218490588 642649594 643392967 969063828 538057971 801898044 507241098 189177470 963761115 107983407 702480410 498645679 104153989 605450735 866368017 916508203 887872650 44954005 51676665 307685930 255139218 994211807 281904105 805693829 221733248 793647794 636112261 496498484 799666101 457488082 478512366 306390642 771846649 824695851 342553232 189986180 946557940 453751421 910898797 693486884 493375816 167680192 691470107 561706018 181283449 563606177 352685336 797997211 890711212 539333403 985521140 49488481 373158323 426102932 697555379 57668781 170145156 798100821 354966606 743826875 755596237 962538909 887496902 223054649 291264270 445455158 584930794 636849470 110533096 839196271 517848571 501800283 968379669 641383883 132426858 163551206 990298257 734941416 921000743 181564437 70280156 691157475 900690518 382508468 63647782 307443374 527695402 523606981 802642574 914342286 937556279 490117381 71945522 224121131 434268642 597584826 642869507 568689755 911738442 915312210 279548097 249474637 557453437 904567527 524794512 177693335 228418348 391041990 294860555 199053393 891886412 666466180 364680306 280701538 872979562 551425548 258303043 827553561 138643280 812201680 298618457 623288163 386290308 430993929 711659070 919671099 912464889 848563381 15417654 881769699 900677457 77102705 94352097 736012274 214551279 902922233 205166066 201674749 107958864 879551028 224862591 484603581 810155579 945138514 180292386 351316431 269908486 267168368 664207080 545620693 361728029 415468081 60549487 972738135 758673683 347284053 479036204 334599543 573043750 932806654 863201108 572840441 793051585 659211224 111849322 893133270 423402132 454759645 629107634 71442582 129813369 76856839 150265052 66919440 108150727 286922026 839084956 967375408 648963357 577233130 123788105 348601167 785763617 687319399 664285702 145240307 508259704 551013090 525135582 797144513 774211865 627008070 208601962 502498218 734064024 78879601 994523442 454670395 356727981 334793087 679748513 301802858 199127533 440372304 472375928 966946110 523066061 623395093 701384777 802952894 565144255 679094421 590890845 177549694 874530561 843026321 525082255 444716392 514754672 860766073 132221058 801330980 124730309 104444346 345946085 643126296 693829324 495208726 377777637 714146217 398476619 542399555 467808273 510831491 813383719 376378547 148477910 638746924 532137505 141545983 16067771 344119550 742390020 755011413 381121500 483148709 767618525 532658796 395501753 74768984 424124272 45855851 571636315 403659219 234084308 484380363 147387132 793045798 595615827 510796781 254557321 505208470 664905095 290148721 858933575 926946221 526193781 947498239 745786915 809481848 433850301 780493212 872608267 647194612 702812419 338787229 443988546 256419429 27681546 114339033 596579025 645703872 638975629 477011989 384579468 537672684 659802318 787309698 725526258 842911582 868412729 703782554 651883739 820858128 239432922 438579143 516874606 419454077 223102237 95829417 328942140 289516589 816975370 232101753 592571793 71432268 154464000 373565350 936801651 943536937 921363489 825832588 615162626 824909068 676919967 340044802 17709298 882526304 875263789 451626540 671576197 888464131 628397192 495592018 357897861 537020852 949684207 919742909 321660961 867995649 260082872 73228560 291983452 438286925 500366252 52936104 148722351 238983543 541484162 881746765 753696310 616992044 167933234 272797609 801858875 288892290 693676335 60018391 179248354 645360164 659964343 28862338 573088117 633085009 258213183 42881047 504319269 632601797 797186122 415071735 513347662 238391513 744050390 452074529 172791731 94437303 400240781 87805505 817622071 446759152 519264913 454858688 712369638 409768498 672545645 983813938 648958772 571599569 870539915 963774975 341186183 131950735 572383155 357701898 454367638 824604856 224897650 580760652 408264459 376356252 523642611 898712468 431894124 571375512 761103922 850931830 969828914 977503561 273413100 714949257 398045467 798037904 859634362 317861657 223560189 760556191 299153074 144138003 240963689 686220642 411619972 472098061 659778223 332781462 661599250 832177080 125724582 301077717 132874927 340414913 173871971 207671486 35417461 708624628 979568417 417651086 909119993 960852416 325467160 301366269 450664948 382875906 149090010 245497382 619848166 365138181 703295997 693268133 604471719 401309393 502433914 601688317 557476003 989497982 754769408 313151202 22605709 355331595 625778047 174390767 974411987 209192595 844229048 181765543 616412036 402848887 187029093 505251862 389173508 67654927 400473611 351652033 225604711 233540758 779400151 167514595 463968892 412793637 838372125 280380289 785515658 618642372 497148654 601709926 526834068 879064930 128524352 103967001 704176143 242400160 435463801 935841158 970351702 322286380 700347098 612538118 392245582 200389740 542224742 36136144 611650136 813479268 77996284 225360595 391843352 144320963 990334853 221219199 51889270 253644605 366263342 34447244 617745027 975107305 901812807 828237311 764369529 609218029 985449572 884514224 785287852 620574907 473802517 514525563 309949249 414986859 783519821 6984086 698027159 289432354 981836589 768320403 546256821 662588190 539504105 530790794 550202693 833483743 357483900 525470069 20929803 433370078 165950957 608705235 303970458 443177092 479677390 269292815 233718487 837819169 377161620 379690555 587889523 528121285 990015780 24006910 170226687 69416468 585090198 731425749 259916387 42256740 494325505 308786123 411246512 374340514 706409475 965421599 96233123 608287048 443340564 244903988 619046053 470598549 511810689 177272955 182838101 766410836 823538206 114613665 766385710 772378476 862778033 257254134 278280342 96348217 188594289 88492007 847403874 571781537 241763602 717564687 661736017 103990173 470737204 193059511 202837490 955117470 125928944 156722247 692928667 449850677 655535394 986632390 836403696 158732614 996281165 598419300 723928059 397050593 667397792 618752374 363725035 239992307 349269176 294105454 780849138 976192886 663837359 527851802 991523077 601266723 792743580 643485815 454064876 143479407 832303164 406426055 2054512 826520063 55933145 605768297 104683689 728978709 158722639 624268447 884509559 893799212 116081379 316359700 252309982 115574550 460203273 895465991 406697993 620036543 825776454 323165658 775721015 493741728 345027508 516971558 956186655 738225503 621157197 192040378 714914916 308386646 898116834 789695486 335049245 909911560 677994509 572648054 555139677 150815134 35594612 665854162 698583852 794029808 417147925 787427593 822572300 291368672 606545415 883963712 375261416 351845484 92970579 837545438 38764408 786448759 704511188 385364676 196834414 752166206 560441756 825365374 902302114 107261248 648814264 650435934 701968723 633463666 98646854 222233367 672265798 379162789 899293921 185898295 322496983 646470698 435599623 434223359 86370612 301830323 326714777 593778402 233482745 566404131 105316049 189197124 489545426 128471291 735233738 382278730 703650515 819846631 247111429 479579292 73436045 279470366 466511013 36746489 720259965 490035367 446362535 855664586 730142675 306580285 363707148 687754290 346635305 820796319 654054537 254067523 247097902 759694709 814687151 64097620 103147870 19880567 82998650 63843804 818945690 624364838 58246377 622898899 409292631 771821220 684420307 47147121 586632935 344440966 785856596 113664868 984761955 794279536 361471304 941756159 58583805 586421574 694588486 322723136 348996370 413272841 846088205 528603281 956683345 613046918 654437104 808931194 138043546 441542985 973246339 484317398 183679435 269987389 792851240 359643927 618671317 220847546 383079068 545047159 100483496 297829296 674795573 953023925 465014998 921188866 55080247 588374405 701603552 579564508 665641504 522242896 799769390 4812708 141399882 467513884 769543686 138996904 782482017 85768829 713514056 706724450 959365290 213256333 606937805 820634912 4830303 865168440 574797726 653688637 26462532 135954751 177066671 280318110 152202065 527304576 963465336 107905136 815133625 728009326 287974721 878379806 125632577 862280075 639743540 243701923 673814638 98808401 504237354 846658475 943078840 544259387 722602659 799424950 198548930 638338335 346687938 251226750 160088782 2756743 168681860 98538227 242228379 906802844 96105210 193986770 905163058 527755115 936518034 102084881 55802015 584849635 762299685 752441407 249734122 219674577 602744739 836242158 673487092 580684886 825900262 691324472 528692116 945346046 338695965 844234424 956597665 727326471 918256950 249063887 973753707 769189329 668842304 748657844 968635283 775307457 662336308 166723720 489830 993387383 940239605 375748027 531125088 612458510 859261979 614972095 216573119 245550136 502402686 705716803 189079055 783463689 627213995 335953187 336158450 176532338 108671959 759744418 79341131 706188556 958583100 744518624 889370391 60126193 332556722 75674773 543639054 494036073 17587634 800010739 768213826 454725579 691390923 280334009 444599027 602269703 370346480 102756865 612234613 829226402 26057644 26974023 632551627 434347776 938359635 902775788 300330369 686688184 733980289 439954221 815980787 293819168 809336654 26971574 217473619 497294512 500893167 776973127 961397591 674673494 840500034 353163307 364403140 403994341 768364033 923944837 86680273 992054205 464930880 771909805 645314402 713812692 173854277 937435193 778123899 349900905 411797509 407975329 367706110 866729051 720202560 921212263 678151625 165652454 571905526 307403917 880669476 750652403 479256022 368905032 223105021 995118355 962988334 154832358 788701078 463631724 717325231 900282599 523563831 475313770 26626123 902152978 524644196 942953647 660137430 109698177 775141076 510536563 42260628 93447298 527154145 962782218 80996733 794422705 591899315 298355838 331599216 751088671 888132870 750823530 710582613 958737821 685004541 56203349 514675441 868166101 323200536 281464561 523585617 551972137 649840703 198221287 631084646 203496735 953657286 63935664 335284503 686827878 971811565 949205714 908078656 536122657 438909804 877421579 942877044 299392764 860892925 363942719 660759371 694539360 136639102 741190912 825773686 464662823 288815694 423936460 644995898 928898472 20411682 126753795 184960917 887792644 277149132 244774534 632347452 298491045 883986894 34520796 158712561 800081017 637602974 165030950 437305795 356731835 277674587 296763088 94133673 163708307 866179770 585711226 843229404 676095674 261074882 260275680 898107765 464842653 711858255 553110042 795983590 82561116 328168741 222031292 781909781 925171075 618017751 283181690 168225265 37585703 1483349 949269128 29561145 133668128 619578581 876003456 195480349 122957742 361296084 113959056 70921707 623599668 41543913 98531599 761115035 896655663 595721956 478684270 218653371 909886997 69537370 487055785 927954024 31180040 827068717 959477263 812211534 884484072 435843224 13992615 413300041 611735874 726821756 208272378 859078780 978907004 853640204 305680064 741814993 188710328 287464534 245002680 571364493 618960028 84020707 804710123 490321408 395169581 748774455 277228550 176272096 908056739 374482463 544069892 275358267 83582736 714869698 717089043 202896372 548968305 461545180 329083111 376729863 83803690 151055701 995421042 617761147 251997472 403261486 110456131 165640658 879507531 505042425 187680494 848884185 908836353 608187277 207176513 315055277 837123117 739784754 319917510 447428915 793808528 999554264 892811481 240695236 352460835 590142777 975748252 560142383 443901174 881103217 73273348 340288763 533562954 281040107 92048658 393010357 664812593 486143515 484866698 485123762 335283635 709916931 945003343 567042308 639988065 10616275 5230712 170120665 631272604 613410004 362085540 33852312 529822196 908792672 401687132 942251474 105116560 820609246 635934681 272327764 560101220 350724479 533713857 692741964 757268370 779816520 545431918 749784363 828810518 745844316 237629097 640041802 376402513 994739309 374764949 970359383 149227669 470132985 33680445 151472305 940747532 186806261 924180569 470198035 886099760 545245771 153285629 872798569 712606920 632193548 153839604 310455593 143826453 792889495 50040346 853782483 408357505 861873227 837484266 521394139 571379992 860225462 866561026 855253549 895253782 407823101 338171167 860878036 414753796 237206671 458061074 860363994 530341478 464701340 488606540 735559276 215086805 930444493 84555727 445040981 981643841 172996155 910221699 85341552 865373374 957059745 807621296 768205671 89183281 42917662 454694960 661217203 723898669 826726898 251385117 143358839 180576030 583124246 854306143 331414779 672223169 12064402 697996890 301958928 18589468 570213150 447137546 754892205 769509149 467795294 109128441 260956135 284221457 117305222 963952145 691385895 15189771 955878893 155982768 170662938 723579816 89637749 185888369 755137436 125629803 393679162 210469824 271488362 364926351 363207999 954608091 107568927 621915551 867182228 224825399 724330803 950804278 3526210 43419853 274609875 114354261 641235483 485273400 352958613 691227287 737666323 796093896 598081119 288047832 363102140 386411272 593732861 213284510 207492056 954985106 274441852 436007405 136797648 628939450 265562564 275227301 826536929 80436554 573918751 230660812 411972592 638247799 749001490 66724452 468910343 91379861 552374927 609804906 228517894 453255106 261114378 535785264 573544458 905912974 656911908 787594700 12092722 590583612 233369508 171693075 107783140 706825540 604908170 330804986 939655676 271181084 301776145 925942087 252378292 131322671 697965912 851433806 142692193 977479173 173863933 725819449 139417445 742067042 839055807 233339361 305592741 767081967 150900085 136352169 316420428 105545025 250763068 598033362 905650189 134314454 181944123 732677614 970644922 400571992 467665817 694220796 945165138 819451064 691932751 431335028 308093344 46349723 462941674 543081357 999499694 487586675 619520518 304394526 786693261 768109838 688555788 318829818 78587590 550748048 492977622 432444982 485762862 767895083 927467617 127722263 256561692 480977522 839825632 252519147 651488309 737914815 431820970 140484440 439042474 750237898 511314139 647319266 169604089 336836216 909621910 374346597 798387230 312329910 29715037 301737014 867187136 909924487 55823926 688296309 400237359 836077190 740634465 435292951 568812341 380244644 499902143 435255651 374082134 168388928 66540720 193808150 378080507 88700292 472310324 211898727 877290102 447173227 892011971 110168739 777302535 243232821 508595422 539797727 522091895 902307148 246636374 465404202 185038094 321450319 222174560 17526387 659169201 589141168 540673741 258129192 135138515 569148824 392173289 203040462 351813841 876087705 391724775 266052018 484074923 39031522 643128219 757667664 652601970 898026908 313818776 49568677 96078976 715792343 321863376 792965758 28227406 952299122 166034377 102078091 460510739 923772986 802532205 458620596 367882989 186676088 100880325 507897956 181851308 831955396 656851268 601019241 303852327 130056330 244342890 398793630 503113039 919812756 393101378 543564607 787365462 600527460 574003858 260293278 765771753 842142031 784850590 849995214 35570988 388017762 151399473 360460274 282808477 766251951 475380325 560077559 69440868 295904074 624835155 864342997 69604819 243023077 504897866 979494944 243324679 435413225 851310105 121967355 481506931 885230390 902238366 549649037 473745667 509925826 144457882 464570177 855840223 860947224 951593134 840126796 649272405 342562035 123373645 23195323 625556142 394322492 498355016 105744921 194359311 438339384 847627015 42541297 655090991 791853853 975250188 849751555 59569486 727915277 885254993 660101479 996768341 638020227 175227969 703987530 719277588 162703273 960406215 792754744 881530820 130227086 145862234 504323671 474447527 357487907 202122453 724078836 591090479 919162889 166172086 641440297 74264312 707826640 954373948 778565286 228657648 557165557 893313952 69651192 785911298 102017006 137244223 863886502 588359552 385513533 483501867 290971180 787060186 755771006 606877949 125515055 148546433 220464333 606619424 160137591 779864185 589874612 775849880 166687936 680985498 956629217 410999897 289810752 135908954 476437507 418281546 52232117 828501979 425193028 598233443 476987458 902745166 871910227 779217055 899936389 271888502 508383343 190656727 514400219 915229700 373484406 275383811 294744200 9438037 308676394 74477605 182524454 411769267 775115585 438134113 472553811 928487939 832281710 152240517 540511766 262853960 183611066 21049192 955599462 895108284 566925150 672149214 396855092 541833660 119106082 951691959 672062631 853684240 159523089 560371265 693077260 869394570 931321805 517564053 464231960 197955350 140190152 599400520 973584789 757189468 863922210 602973375 242979949 336880931 431485064 467880302 317923351 326381892 309913380 966507849 73289820 557228864 691832173 372615859 452692001 420835099 588295224 712935597 992629994 130581095 153893640 118262259 583568 538948175 377010762 630127915 930650251 227635877 846064734 601151214 642385252 510567629 4852046 240067741 402103437 808015552 657665535 974099601 980699964 757542925 155853134 960838787 919088204 698124975 848756677 923912072 636016287 656320469 285472152 311629190 930047805 301416848 748456338 766383370 891033 533076537 883995095 394232093 865314005 149416416 760082519 330763343 920924627 235462999 135262239 146510353 114363670 305245540 450344266 664885070 687167482 340141920 7939277 180152969 275786980 348667597 711983551 577959587 617697719 561710747 865888724 870698080 514937515 178021957 293998862 165710660 846618040 486587884 556516308 131059266 596603000 546437612 850604089 588960715 850741380 517135194 447438138 88674410 877711373 271036302 378211018 607323060 180797240 547559106 934055474 508173961 962030116 469063574 437029929 694019271 259348460 968814544 651466742 9317383 903051808 536024691 533619738 292330977 60717587 910988611 704577102 511475981 138314737 735407474 14235225 883421580 883233911 199146054 76730947 629857451 272444026 390285079 417163417 492814747 892925954 143692940 889754489 157403270 758121672 607863880 388596137 920760569 114576025 841206902 418922877 387430895 648199727 423973398 557559415 143121138 292708989 2970456 598751982 952293137 957061343 560723273 57681915 336253883 750317748 872736321 566132890 676999638 380365398 917343651 168564576 83907567 434752277 602985295 544064559 733113260 831545886 201278642 286782432 796206955 717284271 30383799 810843529 84906968 209580971 498321217 559988979 387957803 427115857 933068644 826486267 516197863 508897700 112895141 149849996 262317003 101234605 591829206 368789019 369354500 763186418 920645203 448681673 116417349 43529468 273006049 385852126 217482511 943873044 331984522 260704868 330814769 510762065 772538194 585307850 884517484 725976998 925143 709855780 765597860 632924240 852371408 957873455 322643507 216480654 893695606 639823675 525587412 620404097 560900848 122447531 699275722 232298534 564942785 741135009 373668372 335378058 888753125 654461902 916160881 901456547 219367303 934151820 572526537 819041440 292343362 860708160 341150110 503584422 975076292 47498582 599982269 330265551 882355456 565611334 223318954 333520731 675414325 959576739 706875829 454672269 343545004 204653359 693673264 190311957 619390413 351524946 428634888 903117904 838708772 645376749 130522948 148957226 124068618 116563194 29308912 594919209 778309900 409893110 900567383 886347435 567679694 618769418 570305782 643987013 562379330 187187702 697951186 498170070 673493204 758075007 567187187 449605796 911210650 170020481 199236380 340786970 347831633 358379871 577839549 345337456 361654648 967506890 97724130 405067281 454183895 492404851 602290412 796090727 666744510 357314674 976913015 258368707 878801799 910236622 774916733 437698863 755613068 994831765 660967473 366723114 275406372 72225300 411010120 692892584 51512985 962398098 729880577 978800823 873289497 41485161 883747693 996403986 353935011 297585821 393036297 264796917 837503806 774924694 156475454 508121710 262297058 631532201 512160873 553423345 414039054 742771568 246429160 583947308 419376642 787208374 770537585 988856644 784502183 913434660 387491230 915212035 509654010 836778773 64205003 189359385 533961987 195872003 371173741 364297239 135298839 790903441 101013839 282197965 887834594 497052608 732472738 59838448 309970803 271527827 984464923 346099522 46391842 925369354 761761651 228919376 353437207 208332303 939533219 47133266 101698727 251067773 32947384 792096228 668210634 207159562 457005360 89188202 627540762 583430984 576254707 761862948 978992468 549740167 705563448 459051407 922528312 679060446 594427747 983554222 175159597 949460868 573447618 683075297 186758690 932191171 329926929 858339650 829079624 890020278 463635836 151397488 295839989 615035067 442939431 409840218 43497647 498531928 696240279 978093702 140444936 855956664 225927443 997657659 924681834 936315457 580844822 522169141 964559429 398556916 997184091 920473522 800647483 244756817 296847019 745447207 656185543 554879530 269342389 56548126 538570369 236748208 313320479 625270249 177014235 601059482 80058099 884405211 783390737 738849808 380994891 131223132 179879530 535004368 206228876 763993694 552915239 577597484 429428332 925276829 595443853 303860651 979821172 966831183 76771024 138266768 330317900 755891347 767661535 219134408 687926032 214591257 189861442 569307246 744816217 799268489 848450932 205798902 411431656 784438371 665852513 604914160 199232015 671050825 737728162 456437384 390828827 455302237 157368389 720212055 475654558 978211452 554859308 971857203 151762645 138123332 560647996 844654532 688411111 183566922 522833230 317030100 865178036 181764687 506345884 495255500 745709835 663638913 76841439 205329072 12051109 42598195 919246419 183701477 3282933 433932294 350772060 686658812 244338642 102234237 580020932 790915782 600934807 84510149 808172564 469029391 563136578 338102061 12507728 813784608 45414374 500368628 419221736 869262052 758469749 75923983 517061406 228851175 805411154 756686790 346682129 131627300 357051136 31453079 55208294 527210763 400904233 695131853 458855837 319507506 702787318 364398438 918104582 734457352 776176569 889288434 810097962 788897478 593481664 149054804 97789434 590000918 265677034 295938433 893199505 802704675 968999711 124239909 323889509 638850049 565279944 188173605 162343015 937300172 404430865 726443753 880507435 951376433 963903236 943396832 399204952 42471723 621064316 606292243 484800426 48959639 509647687 697850401 12839936 925195892 3831564 114359683 237375270 701526869 96227337 298976157 785930214 214887156 273765838 47670242 618371942 331854814 416543703 74014498 289270351 540870400 384623884 159878574 687273061 343860173 890076058 229671927 200167528 758637452 591325425 986335256 293424392 848549368 367200184 923764221 419034688 359517388 503955299 650671094 748368134 831457745 216635358 461298785 231907569 812181000 842426573 79409846 167995604 247557363 383733074 302944995 836985560 640766667 940271255 488438695 128604926 901036163 160838792 140663188 426751177 513403509 938148762 220760002 672371274 507583547 366140060 568044586 830837831 117882873 477254101 924933007 767527320 400393654 186567736 998958712 610837789 266461397 642635686 905565603 442803161 76362406 490785573 41399250 64902108 459491676 756169220 31902170 468540915 483707020 941362252 802487687 174236968 504058330 59411113 161900647 670944132 680979829 448964049 278551976 294396841 112501637 368812647 781413489 960026765 854850611 914858783 314237869 791594824 853152569 768567905 696773634 672383974 330486303 940552962 4951795 415115939 15713551 588851662 384127351 137338973 972446624 972164429 432846597 150674902 556256548 549346058 666314351 272118754 376247018 50271886 673629595 229837924 915188876 702631424 262469725 804188872 620727403 766599918 523204487 846353408 859801426 529913206 239169441 45752904 987764167 855529429 514316044 255100005 691066776 475859441 975427225 435781880 437513668 433476369 483879273 16674283 572829366 522129415 419594659 687898445 289747274 215758148 250983065 526953797 518099005 445389121 606576213 237669110 79046058 324365093 213845560 474353350 3469688 641930153 824738986 846582705 594240854 177480918 580670977 756113959 602942611 712534978 214857826 984695717 145812345 943553070 265124287 709847085 84729219 693404603 295661456 98721285 770993014 785390459 415195165 356390370 376550675 940827450 908761090 391287034 46020486 299315640 538887036 316543735 335518508 113764183 249026310 237798622 537438758 772706481 833832194 525818522 519450400 813079505 153757667 922094322 213239175 584019810 515821188 159399230 749951630 546513201 686086896 874551797 205254004 993949077 513884017 295826784 616265299 743965070 957598663 905877113 307116383 143543053 706536050 978852116 83970212 318208446 267578051 389315970 47181888 350537734 509589020 181576905 654327767 451451990 794371896 394969899 385225236 625133628 607625790 37877057 922962115 790647424 85721236 766200676 723449394 252688883 681900800 825202784 772337838 543405228 66803970 354839459 863510793 54387442 833972610 711269577 685291428 170637776 621233081 256310286 133305625 249603684 6062361 678588185 689542809 125516110 566711704 499839528 837541283 185852483 636097972 944413843 237160420 919530564 700097678 94329594 399647862 641970262 603307542 265215906 853538053 538189458 695494880 256678814 692524300 674600767 501282455 618743326 227049357 103971651 355937039 794691747 59900440 513555690 802289686 857695845 295359180 227824873 30964132 565832596 121362812 433857317 472943274 889461729 455292383 230226250 978531429 719986262 844312585 745312101 712519612 347818103 214713816 331476114 588441136 696109285 291551036 408216890 511460636 902791022 323923380 439240105 57195657 734636631 332636725 374230636 915391141 273244948 56840555 350826688 526557054 55870124 158712650 548596186 305180693 65975903 947584323 191756923 736736325 493134756 526378495 256375228 86429218 507402539 660314714 336465284 448030125 475901896 268019635 988472032 78666409 450259802 618224852 795068597 453287777 282004171 206834723 70398862 829993565 883619824 381452659 833189787 956706237 617231072 615036278 150432171 299057464 915654812 356239429 892625827 308525742 283627376 293421420 256132346 116118753 840942283 815809194 558308322 240404076 548182498 69777577 359445953 667876913 376791148 353994008 946445461 260153414 447461810 48226504 707159682 988498021 648487828 227706727 783576099 498225555 414502439 536319518 826761062 693047906 947388006 366468724 299747007 701850788 812480264 896750730 454527766 181361117 672285493 862851766 471964596 316420338 193249417 364347535 102772193 897804114 901758144 561480872 409369131 463188233 644937246 564132915 877833558 171200667 648104693 26577683 645052336 918681839 224834745 615788335 52098372 648122826 22328672 181473030 874687001 622452302 2513596 932790653 530289436 179689077 266029100 324972113 526542225 807462507 292615939 401111899 217837024 246009240 4668892 812170450 216318718 591579233 442967636 808899591 489319918 657560678 294896643 49176791 497929282 10385327 969987043 849422945 782913410 483774564 590715721 79233407 306768607 923255073 104366452 148771267 932898490 371686638 491679382 227094811 566673764 507004521 796909617 824818425 725432318 910221357 730083278 687275060 664737234 578594212 884255344 318683125 852685817 621011639 105355277 798265663 467023412 507469607 841377506 543260116 495455163 751505532 457558433 561537053 114391424 871669896 7274824 575881599 568022510 543302656 937746955 66478721 68940836 684275682 248360517 365867710 642860008 920570810 882644690 671501405 343096016 875525744 34277254 536454676 434731590 711226283 202416252 764815895 39307035 459745644 57253069 367424859 530614115 653734530 53707483 767322176 11774193 97890260 799788241 279528644 289052440 797044962 668884767 600232496 123785465 995571794 922194012 859347801 526992328 712614293 771800863 785598023 670366880 468997746 801128395 874017175 763002464 174779721 329641478 230601706 166931236 282393761 94836685 874841806 270508502 167908502 94306350 112957891 193902356 316405389 69070738 181869797 160757839 656798041 702914328 794414014 937816818 467281447 480660971 597296525 209723185 628772804 558886334 31146068 879361174 94322941 34538981 714741297 783208831 235889214 667767731 294157549 47984492 550648897 292714179 960138477 427740086 983098092 457791582 767767790 282566938 676845255 50657369 857562800 788801965 222132280 555747657 927766289 805646199 255400525 251992110 982864678 320425700 375766441 671859090 355317805 148859602 458602690 109526402 801490199 171348209 431212825 168663393 52208635 872283735 208161612 593098269 927646746 951056690 960725809 600035108 591815615 900578718 298100359 344985693 194335908 679130572 388782355 366919703 618848989 64778520 684297886 414201185 714744257 685469256 237395832 650493647 710195991 533942501 838865829 599269421 929342692 927340211 265876230 720224758 405283246 99661092 97631009 178268925 642207020 63624405 320636312 6918101 162506244 883894103 572991875 482257116 210268612 825362881 695878319 517904684 467351836 196109667 483021742 424149725 83029864 917103852 269201839 65999229 968793066 465038151 70181927 277669005 61057392 854719941 765717621 779062229 123812175 448499714 380823926 248485330 971063902 217681285 277618343 521596445 637411369 132397125 699306966 450648867 975931683 103721775 397286948 703619028 832057144 420115717 654729554 799348616 231881657 712501384 604653603 623547632 678340595 300847274 881565328 844395959 390658896 277672517 327469393 578982224 6317955 935136218 909432864 126800115 295304541 565963172 806834973 832648737 962448385 140785591 66266733 102803620 315139049 976334666 551915336 851691614 924183895 308278191 529216848 319684592 111638967 303563240 284717461 773482571 130377548 427598730 44568097 875397844 553139006 134130758 385100773 792618977 740659350 286881872 255739496 524841406 793629669 513254333 739915610 691417456 664675393 854005155 140389790 865124940 359084922 892551800 314501652 268645741 814348082 323183239 987130733 502394568 136223925 792928238 767233766 643899698 84762708 89429282 752087679 2522780 710428266 706290176 111837119 940480555 970692958 866149256 376445274 745424039 891884777 907607309 570238387 528258356 858807339 14749490 542518593 193187669 279053771 544134973 191041348 442383354 97824149 178348894 111079214 666198646 459971751 853992608 766618112 12668387 653328564 987599600 541212716 580561132 470531903 615677744 323846058 227841176 611945958 676056778 772591394 154202124 599771451 932628887 408531533 535187412 839120117 674764811 248386082 589544833 281669943 971080763 309054932 995592270 711896913 272617627 811305195 33215266 686160180 269805832 280157637 414602097 415798029 102048800 944499917 966479309 11831497 417766247 699625055 603933043 103774041 627857342 445883535 161092500 275621097 930051295 705922819 424210025 272477547 327441100 569085788 111490773 921402105 807543810 539940923 554188202 846102956 898356409 355183152 720010499 564460522 247117972 443002741 356646991 755035668 345507290 722640970 135546292 296637759 419374999 745334835 385353292 633358477 402620195 147455605 357553182 729487211 983928154 56961745 583339686 103117721 537743606 651208983 606933691 368086691 958729078 181383695 396387429 110998796 223246113 938476927 942211390 646538936 77308869 568431759 793197896 794631237 153218111 839835845 566735093 946219962 402893658 353340342 387625049 504306007 474102597 244090838 833982744 982683776 657694985 998927185 718387879 56167521 128849054 787759258 985473248 855277494 83609012 341562071 41465788 356147589 484641996 727066983 282761087 416142279 679232061 590522127 319764098 619461912 894106370 799384404 919978383 563304846 984567414 401853228 496856021 348184908 457477017 81470075 965290708 935578780 17381862 411963259 34934661 664076658 670561902 640625821 857834386 217676871 398768451 898231505 338293322 883453170 179436481 344337048 672158286 916683013 227641336 476611120 586818613 333299396 207905174 648699954 846511427 604221231 898156313 707646970 811543406 218727744 456075595 145085755 572832140 813865682 184736631 660590106 78426667 977847160 119632169 713767254 52621338 538619735 985737460 681752430 88542643 112587821 573197178 996609478 36510348 658970120 71366106 411007055 722009709 864450677 51877116 123153380 489773169 975801306 561296960 637111362 844624925 315354644 843795513 760588637 823004993 282987754 852947139 484894383 651017198 296957773 528621805 199863569 937370863 843775083 118394406 41702503 548756147 582796135 604035269 660514129 19165432 860785691 328903795 517641620 282894399 600986420 456477162 73872446 327467088 496778987 335804930 696323235 465655476 780013379 635766524 996331958 96141607 351648017 129038008 843153335 120146678 674735829 877919186 928719129 342194913 496253541 254312176 540240813 634092565 110509592 75473615 571012236 718603550 762724172 328883788 124655704 577978764 448083315 994832623 580437014 796458258 693621197 219050341 642264969 292422642 788122724 695278775 560944048 34396623 747171562 754885642 82233396 820610996 418583465 167581271 105464059 489025402 343390107 882259491 190019851 914438571 909901672 709413962 208363813 598799931 165465362 221582411 214409091 293910200 371124116 323229232 539924021 956489026 436736319 924092379 410752041 652003723 656779384 32652354 126337431 406005635 169736394 324372304 864451755 716275223 176562510 834899510 50519111 74602210 622247917 264538689 698419062 802922892 71021988 745634024 972914109 127614049 105434707 408283726 960590717 269666832 218165143 747867165 240143005 152847125 190205824 385731275 439151607 849168299 950303183 320695446 816497462 696142605 901557927 920767684 361749553 125776937 967595741 555674761 75888211 713886555 965673304 730031623 498107811 136610043 19518413 594265870 875390423 272771717 747481651 638278989 250328231 771293231 794865301 626646270 498452086 615240059 726272388 156898364 363991390 660021016 136617146 133718043 784751177 486098357 263148100 569729081 999237046 390433262 722278963 669080333 346360874 594119508 106838766 560863443 131007667 556703530 906169116 988924636 618372158 129755292 504695442 446229419 922984498 733947375 488719723 905048230 337516328 932954759 743007869 438702937 274574737 225962998 241703413 220234009 549584754 972525399 487380336 289376026 263295330 851938203 870688762 143300593 30858292 668113673 780309005 102478897 772044753 196156112 268328105 159427016 650260500 475043172 853407934 607429588 427080002 244674983 199912726 832206365 272714476 55696966 553877946 651263814 756781841 702961248 811531067 386999832 800699574 76675832 403927119 104824667 222168348 832342794 186707225 184790420 881019877 663117487 620523980 931008548 406193338 148373759 882824259 746364898 139958861 991562254 47297996 371928304 48000861 249109274 65555120 165812240 179423915 638581033 960672911 348186204 905820774 676723396 449620437 26871853 254036178 671491696 571750004 285025897 932379963 912242325 603278769 927082070 37589668 770350490 199134469 140593318 405844931 784147025 50217613 45020521 578562479 960782706 4904154 326134026 45128191 417559924 172700657 590196786 454960837 492833022 133167290 474505991 169703255 898440733 196856266 733528703 878555187 565234350 499131080 332320558 693341293 889551749 740084587 275457319 829629715 693010867 850920358 798617562 604864583 200166735 359539912 103464353 790732491 613678451 225642024 145806396 593878604 981197486 736655623 782679341 166645158 590922922 598652975 620048274 270750067 414089796 58754711 922720246 811853110 349392059 79937205 573100769 386656404 597712785 878041962 280623333 864206424 886398674 328568254 925745871 411358528 901297554 713551016 514323133 362947833 978197643 355073457 680227483 911024124 571960435 407768973 120046587 639188530 371419899 797011653 85240995 449930619 313506364 158683523 193397442 871202603 795059966 956608009 21342359 74348305 908010158 344836278 712701020 422239242 338568716 85343915 747319371 352659634 592368395 567964381 237556413 706846360 389914001 766539981 976275573 6483659 735492716 714794130 830119167 706981429 448362441 89292673 613337631 246758745 526571743 872255000 259888625 245074810 967634496 590078755 420011517 922335320 879132020 389411464 624801084 297776354 556478248 36558041 263882779 611988088 911817461 626063429 409197725 176174691 986660557 962833742 978772575 520819342 975523488 152247657 58796768 582956876 321345555 265027094 969992750 724436349 477946289 764281453 638499739 710392749 735474474 682515249 668359461 47012812 71077235 875343604 710857714 541264407 550751844 752646549 922177764 417074753 599444456 949712291 191462802 252719596 361186245 683125355 626277076 254600598 991107770 372953654 794871894 613664796 736097871 363760888 495279438 160965423 88527257 203325053 437534097 646359369 715578221 328170350 448720796 466598269 661212040 215326595 448796732 280756683 707854403 995836487 501552299 697734089 970955690 355576500 630472900 510356684 745932141 100291772 644028934 911333138 198062344 529970342 124580266 374535830 902983298 199341483 489154436 773704019 754803196 287353500 193376780 189447894 196516678 471400979 526787951 48296775 449914056 983427493 691295955 962622794 925926237 462700272 556057346 619613209 446637591 130162728 185042336 546753267 209374390 884555842 621611692 520644712 566574732 580891430 91844798 795100838 219684765 861295206 806381747 971179920 577438688 644521823 237823004 73734518 944726835 567287259 119468567 333442531 766240624 418718801 60409532 320015357 994456038 186329587 732777607 250825470 743174023 635533275 817848650 941285855 782304923 826798544 432191156 298316929 514549641 801615485 561896351 525612088 54407451 243151478 550409025 598290796 516025619 474545458 253807400 774358243 10184579 919385024 930856928 153005081 650043724 485382805 794531791 291967417 145661865 168357807 38745921 229175671 300466295 732882081 93531685 97228910 804413183 503001141 558664063 930179614 99345101 912069154 260209194 178715523 697075720 905121313 924637467 748408949 349558116 472312072 825510614 965497280 292989506 842047727 996441072 112679588 227824469 31448263 998585249 611423959 737813660 66375515 496080748 835211774 854533207 949062407 334111632 776974658 409848071 836518021 321593116 629553095 487430328 168277777 693569593 834072362 260411867 709967860 616081279 855513130 187280870 14561619 609517123 877325756 79670768 382363784 614761532 933826297 131672793 372548508 57585967 86177191 705774916 801742889 237283644 465827815 640337151 28865419 494566808 250138392 395279578 463284225 118875693 284622658 647271485 895211435 145617649 750838247 915318056 316087510 120938053 891492470 6477100 643795345 477646586 524072153 138105748 74110551 982325025 587316791 681523070 141539401 675292547 206893936 273938528 732949330 582147069 185471161 105337866 538169726 932123070 67870254 921600201 804509065 828607793 34675055 351947999 363221476 363614531 899576246 19879200 856843985 202332012 408057019 334182190 104708374 553611506 370794775 790479500 989734303 993903911 623455793 490153571 291079805 847990338 890806251 233526844 821416283 970890956 134788847 340478441 568141859 13543879 915096994 580552531 417676012 943832887 864343201 142515008 958057149 824716436 76440556 321734934 506431786 131282939 234977828 125200242 887326869 725953208 197508170 905663600 929825433 779881819 400681947 832310341 85880295 189818843 432465943 875247573 370435811 955566439 88480433 100527922 85919637 885544036 887349670 259810418 903856956 794847671 86721532 959394657 10981049 804898079 531012881 891503336 367338704 418607665 702449314 816125184 818161987 879007044 372219484 893815555 978678048 519220540 181225139 595486116 790535850 544365799 16267137 594690999 715713622 740849842 196926445 852759068 652505277 23191241 129251460 825621674 236340479 880016806 382823319 823742245 445023215 344804614 554502718 335211697 879846702 971441999 991820731 252544314 990581295 914660073 348795412 298238061 14653273 515656034 673679012 726273631 440380922 281453901 572107218 67680338 647994759 161677289 937418200 66719378 873563798 523065608 864975798 931242402 163777641 969584571 439052972 50476405 284434591 542587109 878762478 947991592 997282747 804001062 668134460 862448243 783889439 909076770 185068791 227391557 758528459 854722569 263170507 87819095 678179210 989359077 945668482 834119075 348233029 892069088 224127980 993146399 888569718 719975057 718986386 980002063 593170856 529477627 316211308 623905640 351129629 382828092 311421552 49004140 35354181 866188575 169452360 842102574 786781858 487921619 735787456 241145973 379180718 206070211 570996639 688287055 752586350 475391452 860389544 540266975 627815674 517806032 460035046 12683621 139963666 972604135 854699369 587510554 684793168 641268989 293636392 483086701 68319769 972257451 793268356 785417544 740974059 535171186 919125176 677592127 317504849 100458976 434505154 885625571 117590882 314556228 162994693 62802250 862503409 85045864 901299826 866458992 841300627 716000560 802801965 174308910 345514940 212341079 749206812 234224635 917052901 908264323 103014155 455045572 95165018 145625779 996423088 225336717 98889202 307949892 14741249 443810836 175748048 806978254 203893375 574075199 715588454 215228808 951652774 675865650 603429433 93337492 845243347 462868746 661768669 413662828 336136909 364369719 189927951 294738475 778873290 700142512 798437503 333136948 518445530 23285172 160754955 763765280 313454310 537779919 419196934 575146447 954038087 325798629 302800946 498125431 124673080 323088595 189301799 680310215 791867312 348408670 429654450 182069896 44483237 604897268 442557515 940139919 233724242 2178872 371449767 989542202 885879064 49878025 126903145 545198344 411120592 230605729 185320911 425906439 821090465 937267352 410892733 961254354 524702566 758776651 11848686 973591737 746772560 783792093 766468538 97076991 698832580 445012031 707891596 939629035 930491318 714480989 137406678 678422291 659274414 791426275 136642272 683359586 846932629 632007632 137381296 654445672 658294356 274720737 964235537 159628206 726299412 671639313 965682907 639403605 507970504 27124556 133457501 87851919 530569399 621365321 789780558 943309822 224249129 87778537 438008275 674892003 170773016 420090238 169783885 562172746 852968226 235289459 272232354 407426455 246210884 751928604 473810877 531253818 316506995 151428866 538582405 51221256 935931521 858191612 672523268 890052334 106547554 243820195 536018095 878490838 165727740 21467134 179461428 436664598 25751478 429906918 705307620 201133292 708651645 799074917 799110832 800857428 334320321 187762459 435105187 203103016 938577980 368747443 337120285 542340132 916092964 342877924 165998691 687344254 656808076 648605705 814303024 483195889 979379671 445310687 182739596 727756436 618094293 308514465 186415041 379016658 919262414 468483429 253247508 284686642 826136645 985883945 609412930 497307541 857466478 934455142 321406016 93383001 566606742 812743427 324453515 779781490 866850045 338144481 62938032 716936652 439298579 903853388 229958460 806295621 657115746 605857784 824341436 333117552 836924584 563144312 710868569 670112027 867889628 92956356 839910266 776108219 111136634 831692821 231035311 207497651 628029162 431683780 870052521 285523769 288996853 558789622 722237394 994109169 834490679 891677486 652612346 283261686 776310120 619444215 839836368 81742039 747654047 30928909 583775859 768263977 640997329 846863294 827351699 685502779 752417827 459297364 3174157 888031512 272072327 300822359 97216179 84262914 394484596 296293727 746355967 131181063 184981478 607330958 468599805 382965595 751606445 247270909 345285769 873719102 281411866 879400088 649663426 753547993 734398057 634909083 35840294 336553691 17187160 639988187 755282997 650845841 503329116 663216405 813495845 163317270 770316002 189092275 936046049 785081351 65836436 147830497 112232346 22782006 586777033 40508746 414616879 991162363 330645502 908393939 368888941 357415485 66671396 632671356 146672427 662099439 838655621 163963175 799432644 941046151 347928994 784046996 182148946 17937425 71602966 356236888 51324401 593171201 337541075 797306350 258931347 901952393 969542455 891486562 758481309 793467039 517878041 222923087 466781865 287599858 995101861 59526996 870495691 365125089 247160091 703349777 987179092 825992316 150414461 364119395 906468217 126029631 393809220 847895963 106064995 619392348 122497327 706521449 737931702 482046706 593920009 6644543 582628538 313848913 827503965 20581514 313956993 757478938 315703111 712700414 109444288 46769947 785510514 182347541 360703039 879433786 597344610 944785035 949444795 973492614 6150476 436047757 274552601 587233230 13747661 844880075 875885228 138880200 550610706 857836636 511346422 164428083 659890338 989107239 255166592 333026737 276855773 949330034 701125933 703493615 309509409 938076487 746742854 281724127 340220588 886901404 789316622 219523088 311654614 602995097 971259071 900934447 946548382 777542313 164022374 136565969 440407455 455141278 564663785 679184597 228607082 563017141 502684566 380121664 861854064 632851744 980017062 963525410 626955107 468995246 239573575 972210816 316535483 929947769 192378736 495983816 69108654 104532936 380711771 471511958 999980623 367215847 1836404 453690550 821585585 858502261 973187836 103836907 985277600 889013329 50891088 900537046 532958603 577823810 105651120 789707800 346798434 133403251 819799727 537480976 168685259 32093718 254969033 530509500 890493615 754573782 487849149 78334879 965997362 529709969 108808126 221409534 757150198 63921366 789723586 980262357 711671521 533566872 758153668 717827026 709161288 400980442 966844285 651099501 736928672 403436316 385651559 560074787 143858116 99581909 150214639 549464334 978434499 999461920 901441547 34037913 821821182 138094740 89543296 990756107 674134670 996313423 338436463 313560467 477700660 163286215 728258239 983008522 461675881 825799006 756220300 428286365 389800567 110244166 469262118 542275577 500155005 969990928 286324708 77851084 239975812 88882736 87711246 548809276 357351167 601066503 647687274 481907831 790692015 109524497 681511224 383205623 441321666 802128013 507011393 474502904 148601334 338250667 844226687 915385496 590608089 881989208 645170741 863229948 722111571 475662590 572381623 54800352 727441290 524377140 802974037 133598428 374487200 416204257 848444115 903780435 80223853 920115009 561269729 12331221 373048122 467725094 818575022 751016528 873704469 513779186 928523251 797247740 472464145 177570207 197210696 139686085 422391244 572604496 201730124 807375720 327386593 574458436 501237619 439437043 937160324 900961169 322251324 178472284 387697917 359443231 638370220 74878536 453045155 768865295 506769195 929545332 316104603 625256718 491261672 323837793 752486892 920545927 642175383 917658947 733023184 838227758 71296839 491323891 190518530 690754777 350820472 798069010 806127351 75876361 203723915 161863672 958087328 337387101 245576492 760171271 810536426 797555371 860681286 566402169 822727443 332475906 543272324 672962967 746726166 639306238 127258791 878792950 39753204 37575189 35678730 83722170 280228638 569629320 567324478 626941691 647173808 793956502 663234620 622802347 937924335 997826476 897467964 439599860 585154183 770109381 694015406 798130705 365743098 218874253 881774082 443037484 529597415 468318593 43425391 388147311 844691917 263126859 254235944 681118987 663100901 248793709 694673430 639724510 404432768 452374141 832675711 920466507 649335688 953390190 399514890 543919654 759965779 125580953 411807561 986595728 38580635 49730911 424422415 98562769 30892770 195345092 875383072 87109035 758504354 313863516 321933154 619209297 552969945 562011914 841630244 893497751 118375295 501193186 312097746 436460899 345046784 130853871 962951292 713405412 996163817 663479324 906738177 988586172 339742344 647441590 249920013 362273181 510682513 472977884 336663824 656377190 349765367 752922716 599224202 261934327 640779510 9372001 9745282 825284929 719033295 265430796 188305191 714148881 307698873 598899829 472149107 118855585 858288247 65048159 105143720 321888511 362983062 855981094 215217869 525976338 464206483 900969676 594066772 90780236 766039165 881681209 45831591 583515488 431061566 875850159 945505552 44363890 713203478 406706459 81884408 20586771 476373421 347235007 596907225 472959183 971960262 795357241 785767106 703031673 176564882 466407755 986531097 1848050 641668799 869153431 54079820 745553485 414655120 601666297 179263027 339381493 770258579 771724169 226951075 75550894 827681961 433298270 99436091 771128367 692629709 433556212 271788634 339131205 618853013 329146973 86198042 460892805 128202013 382646938 599550395 615872796 932555313 475427374 282274178 15244365 945198516 113878202 420518876 898512722 701641276 347429594 43033394 602900431 813175748 785697793 780763839 266469550 13351751 776993432 476503087 158682904 398644931 423504084 895996346 426412473 74718037 261846856 938178662 370714152 139581115 416918378 777809923 538321164 227369928 982889347 843594987 715289373 470515946 190619969 699473281 816006587 158542690 411421600 533472227 66849229 855608996 101118807 797605376 163473324 589155336 796809114 422306146 547643470 345525949 192702181 183635224 937018619 805783886 32516593 214993441 101157955 169654274 965166498 664912402 502535780 763091168 517801978 487762455 375186207 180692492 561024677 913771541 490709500 697304777 245309050 738465091 879852482 797535215 800827752 432007793 78780263 336524664 864259709 358930065 119269316 252633990 73841881 479847901 928978936 119300915 967967489 599990325 682653406 446254414 370554721 923482043 647346161 102121833 770968699 360943822 210762371 544244594 453007970 595903507 235708251 883399061 380523216 429478660 209032305 350569081 864614853 395525956 61389142 315050416 869100506 771915063 555392594 285909926 200677156 156253072 561494118 608970301 36927903 810010230 810032175 203579795 170919886 311154132 562310959 839148774 362158025 417578321 450820161 888034852 825748381 162869345 178378428 554910024 189139669 659883455 856803751 830389541 101242601 50932790 678484589 950050966 160210759 724305565 96100672 394138918 781380512 293877552 525401605 363006640 181828835 577884768 745249832 764008643 627863047 326670560 962407786 5534789 214379058 490119738 250218983 562955607 547559154 996603220 672111956 262790997 309601602 352827162 776874323 10805124 735834966 174028273 85849509 417891412 100920364 793013835 255641381 83286688 476664063 422026684 787063464 379121130 182323088 237898783 955544755 818909539 995811883 695702756 459061152 188456819 381904796 508032227 924452442 840849677 440104584 665360723 94921735 718365445 593796054 429657694 708277049 699552466 250729377 324142810 48592514 257973092 144346774 460032077 373553634 82154064 493178849 611859875 586964951 971327604 958617521 74143895 839082449 541433365 98719272 265355194 533674297 67510839 986679000 601418499 591690352 98541717 718722633 623243887 740305459 853786793 54626225 583007680 190375640 954825119 511772729 913433333 191823062 99728026 86847875 264153296 466502659 877623227 810233104 390662830 666423472 343224985 80289169 254365052 395996897 670773641 713177728 588950557 57405355 524218596 91941192 981945000 286022653 959363545 114279601 771635793 991177040 264875902 850656129 82163172 340300743 452702476 247769093 711192613 18458725 993046908 303753709 715063329 304051825 134634660 936776966 783357383 712487612 925750216 675094140 122958909 72032276 633003365 720288778 369294795 632014165 298716654 167070079 152243802 95852156 372613856 857873537 963465908 60664234 934739590 357854964 345468006 299046629 280869114 519515706 419945884 317061825 956028037 14901121 663212620 149883911 149061425 82231837 718447931 21451432 652605584 441432953 743628283 393405179 624002537 377597893 522359048 510286772 266973531 563607964 695122120 810036818 846187703 299356646 16780194 886073514 514662221 560630404 974735243 648341653 866241979 996197846 252133472 88763803 373861623 317821545 810933889 463778885 268859906 137304691 331737271 674253751 592307763 122628064 41691954 128177526 415281939 737958304 880456697 598850250 96152181 773261055 161774847 588079334 102859371 290409258 682297789 756827257 1567757 938915441 342830647 384794117 455047900 281722443 376555649 765465096 661268857 281150826 844282971 361676191 994775823 2634810 957516952 828139757 666156693 982274545 205087872 565397811 153605246 966000570 864521711 888709049 252968203 255855682 69544166 178833427 744051866 315952215 732821323 606574149 166045449 11487075 110827035 744716777 159977299 406060885 64925917 858068370 296639986 317723897 897974626 126023060 564914122 167236114 770879507 289144630 736170493 540207169 425157484 535838728 453881338 305020464 786700626 819794378 605798453 710808201 152857014 781110457 477590015 327431363 928971177 71222906 801552286 697675855 538472825 95891482 462318470 362758682 942067511 400078272 457901047 112969441 126291245 621412129 429000441 495230898 707660385 450631160 171792252 452923659 8529438 365606842 848780363 347031628 438040841 238515616 859783207 315940425 489684939 718020168 831565875 490009885 539823940 310023258 742857789 887492476 961300076 897551657 668143691 834353020 237861262 579953994 223645829 633910422 390457133 310978321 661690039 653415975 422688664 257352848 508878254 266316240 251926070 216301122 280716271 413121524 274873704 864406608 728621217 598932620 788365913 819215923 337523646 496451961 446342835 821998751 165925863 580686961 970335639 262271043 824094359 211576002 622032033 770341553 499247329 54332494 800520808 852876178 296014814 956796737 29313096 782517953 546885287 726031026 450324698 833943513 920275741 622115081 736333992 902419762 630393067 755111421 25598900 378904782 208441741 330803802 566140616 492946791 622836011 479884311 990569029 75195056 741838887 357938652 597327492 203376360 26011888 665539271 131055443 260270068 449319361 123974527 462225109 873033248 476499384 93852864 77955174 919015584 353928810 68680205 610905469 958941932 649615884 442154131 648412318 91140066 101677398 31485271 487083911 677848820 441336888 184619899 612418687 640191283 786432918 353961327 183485531 428824429 827594079 624212799 652347178 807909466 385050102 269944286 585377900 412616311 8312381 753718461 635326534 840282531 309716559 628064931 356472983 281746627 579748955 809613181 889554790 322775193 788602087 739323742 468525979 26440852 389580392 612314837 854176839 925858565 36654564 879596752 311294762 680181884 499898163 405225122 10592809 370696616 881847448 458747142 832941265 147498927 439311640 639167622 552520752 440075699 868626722 807904696 418072423 881869004 508243247 14215401 555474456 965371203 510387630 753291052 409720468 379315443 66923235 260547145 807628498 996342638 634802061 665199591 585435060 358186435 303627822 803547186 490965458 839283283 326762073 504986901 194187924 386395743 53786986 921096657 718373139 640677285 673946468 761993593 910767786 914772204 449931971 592366787 823006702 303243061 129759294 130114545 154613110 138988505 613230954 785139458 695586780 874214318 60376699 825424494 30641808 766753339 628694822 712935551 461866188 605226650 611489015 987317651 747522372 229904570 614249543 110893199 150416749 825940494 384332806 1109246 561981354 873263913 292613559 886165451 329245575 427741320 297009063 680903029 204945615 422486033 898978537 231867327 78262857 565003919 526214976 500641388 476322558 136747236 990453328 675361762 56098903 370436895 659676087 622704883 965801574 255187140 587153647 980114035 480294624 204195247 150320164 35618185 511800233 530882913 343414609 223404149 423022943 501486172 214977648 253886383 475223 108288202 813194536 865429528 517088164 953050978 994113748 797706351 686903192 479618758 134152447 550779632 883549057 616384089 910063896 319803435 833256584 109474587 899461809 717577966 194047033 425085911 456849022 340092411 610960503 228331370 687627895 121871559 759171717 864060019 309223050 936602948 164422126 429255665 566240819 371526016 91348303 791096509 166675129 176455469 362185234 45973759 975827467 796878381 574875893 843189109 134119427 71462552 522228733 976846881 947159102 111684593 416479007 362101144 708344435 479610916 106637362 352807455 293424108 765528637 671696365 357591984 962061317 822974440 832980530 54334375 295713330 683423557 404049819 660431155 648379253 941536646 850526426 149020471 472267221 337180406 386910599 920506675 854013437 800309182 970270577 103567026 143617833 370440076 718984932 828830842 678946110 462850099 895212166 301575204 82760829 69468439 968117469 97976186 398153129 639293142 359600028 226469482 476939851 135296063 790523595 477286585 165999656 726874442 685252849 499599070 916671011 179932943 324964061 416453732 837111165 249552982 821868166 604438248 361019829 688782832 46809723 801788539 938135214 425714190 559010919 640287166 130827625 144150759 482801768 382589354 166111971 846988489 269162000 895699372 524418601 724883346 791149898 199655556 778946489 969843913 604267491 493259593 406739375 320129145 576559901 650827333 449372523 634805737 226035984 620942998 327976166 261283292 236764822 944896204 241037995 321242895 917834599 626209853 714306600 400640721 846209362 765995994 741720118 411026217 283525158 819067788 927144891 24683738 783265898 929139453 703585750 891891130 336869969 891184772 595076706 621477194 667152562 643924748 876594722 423507367 437671744 718462474 258325606 911131254 232477503 546531455 98952602 489905348 396384157 704827658 198843830 594879298 682166307 165409480 126219778 389912595 507227775 112984226 65744596 381907079 635160907 826870279 706300787 693154425 542383568 394346503 171864570 457662316 283201250 21787894 503278837 196272138 876389118 606765826 495483733 624400661 300475797 412120553 749566760 941563783 939730578 341392851 299262021 973808639 872129353 413533338 726706048 992233541 210584085 703243393 954140312 511899346 781416229 914970481 857669576 665769505 617321375 436458223 168614743 330912121 560763502 194605182 249767318 589323279 379576846 802253591 671585237 192850857 278331201 133139781 932893727 772470438 576547420 411049499 500328863 806811951 738347164 627272583 394018747 726506 479709378 752306189 789252083 598739591 952604831 769339349 51231753 485080410 595837157 571700904 805763508 608424632 451774208 981692225 217507712 713290791 773923093 56714056 990311456 982934512 143287692 812323193 411201642 984094735 150607703 679382385 771804660 955319700 826667091 869494402 740985247 828499 247938735 503247281 657859238 797823186 288076502 935736232 887660873 749507381 172078357 990255980 594482101 704382941 826008231 823288811 636183403 95458114 215805925 115952454 448251135 259202205 442941227 953379210 874251001 946094272 113654438 778963139 333160076 670783446 866530978 514844905 397365614 939852934 616966351 681065395 595403529 484015414 723980890 489731062 25705990 69159676 725494214 101787015 941085405 917458331 407792032 905064146 893098789 864735853 284409245 368379900 257677664 855285667 58644652 686207832 656756902 594779160 40314578 809397469 515587746 806167090 410735016 989016002 764441365 545925050 325209456 953314455 61208631 474163208 923650029 57411822 965110156 998281266 787288993 59529514 452747952 602929611 109762244 270437773 279259792 705099211 159321522 909715624 246083599 649929179 132850413 865625580 139754555 646960725 939880129 569783579 628203501 844838872 648245253 802335237 930011837 669734962 540241461 408647835 105648429 299999006 169177435 369387957 728314288 495137868 455686378 754000457 538521106 945859233 789001413 53127254 345516180 421222046 657327867 173432596 47315280 781384103 512998389 268055901 783840721 897549998 672482393 862753867 264728454 445319855 502464180 812339660 768419775 703478911 56832503 521177511 291739925 825505654 806789651 327476031 583119204 486601405 305198504 758801058 195213309 277292762 622243874 702420621 538343602 82165728 295420091 1429207 835295210 861677764 306858870 665656687 766774453 444439320 578745827 321313257 854380724 547650006 217242898 752953019 914065683 794238771 989522255 730897306 443534885 1413135 453619085 778675676 7004948 863540735 601810760 128578988 350493265 168268000 176116614 997026008 172331605 958759264 898068996 629923386 357584985 485850121 379555370 12332609 589693478 93550378 559424436 433466630 626704063 719636667 172922342 292810511 530193018 579631439 443920349 39367269 169840008 491763400 35700381 958736198 520078356 25265719 725313256 401784860 983671159 952966814 218630321 960303432 612728692 314874479 100095882 782719676 990080517 771933312 999867745 267015024 72796366 718924748 286011062 663758322 626018408 380373328 302317575 808333246 985637636 323847770 369941595 402377773 110871042 711164693 54249632 314640958 397040468 741273562 294866328 866570467 226447209 684589013 21412265 149017632 804632178 540453296 999326170 232882927 129770279 971646751 44031029 629975633 219197717 800615865 608371501 308965517 154948034 888950700 627556822 66548930 807291830 208125093 294250231 929543425 595598634 402564736 908254039 803292022 750509422 832215931 833217172 639104063 517416858 62848168 489926346 351436668 573218223 437549773 479546995 554849088 736983310 203394197 876686885 916966315 155836830 683255518 824224264 511820372 775927256 669360820 179203254 606261450 565254110 89914099 207300836 336831500 122932044 284835757 148988504 541814259 938267316 337161372 137221641 762362395 725669902 86701431 762479244 31888349 381186358 850189616 263287182 838833696 849445401 894058903 918460084 453324853 199071844 822093486 462988967 959697527 453485981 689922699 605511069 483935638 857240276 353454572 585213476 104077640 637842694 641690247 935518285 237846889 591753594 274677263 197086782 672872464 639100780 141418937 326268876 677259717 950269307 345089725 90566624 984133394 327999191 279863839 362418914 213033614 843932672 927692126 415189605 170858528 961159195 522516721 903016267 454817691 971222249 918516600 137125592 33387458 397119818 73459951 277946917 633169617 674245958 77662385 78196342 956000274 852210551 670411761 989353149 698409390 826137156 567974299 463556917 93287410 808748141 875472642 839184018 367173851 712833746 861505703 668219903 942623818 492608189 950683443 700944781 270971181 744174517 503443045 229561082 322641222 629024341 715779541 1021710 778026687 24753377 788453919 523342707 957797321 575843953 476646311 346297517 624811905 230816126 983232801 97661395 302415549 306800205 119322496 201873886 967108263 495769703 431697711 587924041 908324788 205075699 265260659 676576508 886676986 338425620 722894560 657753553 213941499 763369940 198797720 97270904 479338847 547602658 363419278 261159223 129427602 439297074 98654055 156823726 182458603 574272184 286559418 731006851 904527114 332861211 460992598 547149437 784131555 766032786 372453332 597132920 907895967 928040093 54503460 864107703 954927878 566172392 113555821 367652218 580876356 201585375 853907408 286071508 56595195 765945843 44285755 215911207 113010214 250434266 968024301 638525168 167723794 9940456 56888406 383033935 564432182 621885730 681219457 317543278 533362182 818067888 336263446 745930961 685544848 794702797 679723300 759728065 27858608 477570593 453081461 226862345 470990600 355388232 254489604 113109403 952644945 632002791 906782739 115960681 428332940 479764406 587921793 895051254 606868771 285979597 41464418 983011218 273569138 432957389 70903516 935941543 353756064 128605965 739569780 598757816 918130555 463417810 868797650 46204184 867946022 364570036 114461270 37474874 500970228 178303801 216757845 762525628 974846057 845943905 499615913 577862394 825744841 77257670 620429875 930917856 626334295 462491554 585090360 335993191 209181015 976457807 873503043 62605336 494241802 910203814 915596449 954556539 852692926 797851017 2385104 136575648 204425013 97486188 78078835 697018830 205359803 497651848 823088620 799001011 139519491 520056562 12293450 853320987 138210981 3698860 116126485 16042346 845705311 978056114 909061377 158357881 92725529 430291906 323029119 552431951 133384452 578659187 236998 179074271 143615562 106654789 511318490 681262859 65559038 695628226 449721530 134053877 648209059 633508512 105778154 368173078 171007992 425874904 997567554 235179797 750415347 253562645 298975642 632727472 599411019 422626414 399054666 287872946 11934101 273545300 453270885 109955889 880920864 678768559 488270885 448580961 631311826 557625237 415920742 841591638 438377312 144675656 884285337 179690583 923173007 815265340 263627114 382703904 335719140 405896519 245985384 883668349 222337549 780461380 425416860 161618513 683597452 917856022 618770534 730760185 850243475 166284893 201120604 739477927 707281288 129842513 664404014 946702860 129310187 215255161 219514774 774471085 696328487 968460534 561184359 771303566 449703021 380708587 397938475 440244722 280774989 760098644 487289887 768679700 237489298 932722554 214668126 478554373 324052031 273677285 736608422 820134936 819187728 495228509 583042745 787059146 621860878 431393059 934673720 243254895 103471559 219407293 195976857 928980317 885359634 514299406 856641345 993935525 272765602 963879711 110751051 560587285 541796913 807736230 195524453 897756549 678115105 376779190 775037113 745236162 610701045 684927596 355270344 399235324 175136213 186742996 668294329 989758328 226387328 26699133 451528883 260649285 403367574 760789874 576052886 12017049 573975454 986448086 784285126 131034108 775299807 549327701 861876893 60604874 696977100 650550192 998973583 613457640 653032853 443939508 619839605 389900774 60715395 701242105 734662506 167349819 932920 884608940 784958339 991685138 608627002 727548626 525774344 115217329 184116535 394842006 40033894 664399203 242031433 269086897 316991582 463134848 5373562 172781224 477642989 32915440 625962689 628249922 884463456 708612164 21344764 485416782 473738865 397031707 750046772 710890082 219607163 659556691 996622776 588224016 659244406 308600797 238170557 684172506 179346346 257991354 741702208 343976173 970132207 558999958 110625147 689032471 718857945 964148557 951561440 597299628 588243502 90942722 913873876 381395576 25124894 641390395 546642837 673652785 702218145 642279460 163073961 56625554 508815670 284584493 871060620 369242072 236228814 308428623 214895867 308060827 92151087 653545820 32533871 591786899 909627322 547045563 161788094 45677194 540530985 697320669 438385850 759996459 814640421 541323446 195078156 199220539 889718950 802169995 555224224 194152519 235855658 107057991 31469384 688079730 17621785 610030976 322586641 311205179 415702629 972176646 249852344 165735626 532753589 926547407 502715073 94172231 366067921 608190870 2634525 900520304 373022889 134417561 513069925 896945634 398000299 327655975 826298924 773299888 972847417 793835344 17499584 10206615 978775240 12476878 382326127 924864386 836505970 25318826 279612415 773949912 202717145 222721791 338047702 821812464 649295346 131860854 431438696 350769416 395806583 449261383 115488666 288366394 865271645 920084919 839928538 66572313 572571003 162423926 203806545 572792581 867534447 577907926 992581691 367159489 767872867 859658890 601365750 541503537 547182901 507737065 802407334 263041795 691783735 731449132 478711426 774337071 140554194 43587821 827207338 315506189 520654995 648481659 53118716 828620489 637611493 134338314 692201037 987591450 735668549 263899303 531652161 299674299 454284545 544934709 78899878 745414910 184951771 613824377 489705538 331225268 922581042 334279491 534659232 812090792 900759580 835961708 852135254 370773136 278862949 419951274 255468530 183267235 115420868 456617015 181013811 202142266 614550783 910223191 704134954 651281829 810374171 558834071 46319239 839912162 160027771 366517115 933717236 312989704 215230476 964093169 809926805 452998938 435245018 4371538 959615737 286475829 913973916 201274506 159019547 467821406 69943011 612352272 931581834 692384634 941541023 993360661 23825322 609344057 856331983 419569223 619042813 883722431 309687278 953530832 619022077 454703323 319731164 840200247 361459835 716057125 677331818 863564684 167893145 958709498 565069481 458943942 264583715 254971834 870094280 241084809 426228863 655536482 394350050 993437765 723120198 93102830 512932847 387338899 194647205 260859104 751775629 396844998 886332443 138886636 570097367 960157561 128284240 678238771 455301858 367734064 833058161 696730250 870996019 734682420 764911023 655597965 423970382 714501067 843749465 309570239 136350861 598044266 229483211 964277643 506187330 58584214 730393228 257738734 980428809 254748220 845667723 46578212 710027085 460997276 810471590 14475201 709171771 878891353 247725824 125598426 434505315 758415951 993722091 445366997 553726385 828957288 944645605 897842141 516839168 565501982 972081739 264672952 165058488 889456803 238574517 924205514 934946804 930658892 814315647 498186084 951762784 254700573 58933115 83720958 584228507 905303447 244100701 815302413 835188158 570346268 289099725 785413873 232359491 457757311 863264788 324759089 156861810 484199574 435267558 120180007 934621939 127686859 684603551 346527001 131494710 330982993 397122209 902407813 784648460 914082638 651088684 805472102 379703817 738611528 69231423 93366113 435267280 661416028 410856184 150295321 65544415 102612756 944262077 577850076 162186351 281193360 424791509 189185316 963998633 36831277 639797407 451910260 442365786 578119330 345285815 970786971 582481236 871390557 843815972 270160467 213404997 166559683 422826875 58762680 133402910 317421328 114370946 826777465 306380926 648992259 648207306 601386927 658812909 702651776 763184626 27751143 9114477 783814760 156008357 241366651 489263261 139548212 742789378 94659068 856526821 542638166 217661552 179432708 335489497 23487922 56555816 967999757 711095828 944085997 854953339 167610085 979646435 559551846 59941309 37097093 690957600 104013088 249381681 90399776 61317129 686955528 426560299 596130454 50255707 487953252 796389856 286943378 499945991 600488270 951065154 52055224 833098621 723965913 362772383 280402037 178289926 185362162 189893901 451385467 649977416 498395081 431157176 249181377 9334883 725613179 312716572 653580496 693672100 450701651 382112644 268602814 5004088 317625736 446245264 857845182 90679374 981019441 17852549 855518159 815919408 854399338 842453766 994949270 943834968 166708792 774904349 682274820 51533830 708199519 337338558 645067752 755918204 516530150 31889706 9649233 918163219 344725021 545175126 255795364 892828320 635325543 341924995 672050905 602623436 894949615 103425357 955272620 679361201 914241536 415354940 3610749 184725858 223345149 596140134 429696561 789538788 431894571 737250449 678030609 170683979 273350172 583870469 690125488 942061793 216788955 786224267 137082832 197323737 968715895 632797135 947186952 699484466 874449793 476196262 969085224 750818334 702131808 467478944 729219195 125663696 482214329 837095564 437298955 959137411 519803268 64565199 358275250 146058900 811662170 530589071 243190484 823183284 982763747 758715232 265169615 334760117 432456474 894933027 288779736 384554670 508918045 747464469 65409968 785005733 78116976 511774232 492925977 43419986 167758420 185697747 506055026 422141044 900265554 753887596 438057021 257493095 358944479 395341616 197559088 340589266 860325902 22185969 167950827 243351427 815046441 423394938 991005339 892311056 894341259 468530435 30254078 720279214 789356125 734298437 379554960 984287733 31487587 376525138 862134130 569788903 941079466 101470642 880500671 804998650 865270066 91086706 518811563 779777147 483271852 328529913 904406514 999385321 852185231 755443893 31181973 844702754 241098739 561811904 115750989 936745316 509878377 109454939 329161987 763074980 558489538 342341787 47240022 957223131 59644858 772288767 894604498 555843223 419076932 913981528 433339192 160482679 642487248 702418882 156989856 761899817 991668222 306469845 602439298 29490978 108694759 228216472 24586189 378446014 375664633 709182569 166999309 516038570 196785667 243873971 935457025 839618795 495970099 637862339 720557207 854263345 490868951 342707127 121553910 877540204 670292297 609158946 385731813 560535008 974533432 223173638 457656495 107728449 365558385 438813638 579977088 789379398 451708717 375439521 928709000 440492922 230311740 841722582 969434077 721867040 131053327 131275936 901720395 514312303 354636511 111910373 753597648 183397469 290569201 880390385 154010451 757024533 790997527 95091357 164225983 350152848 577474979 7974826 375535270 243852144 364413617 552260065 560222508 46748981 700327355 153206441 317424775 427669503 723727537 100464792 253957989 472498629 132224280 648967399 60235993 205923093 300338687 221370042 134228033 815092197 888459031 369160035 934462715 372268373 551410827 427576177 908284468 232483942 779471287 969065581 865969413 521199829 422821145 167176287 906947971 927183204 675234982 518872654 911042824 566224831 327707181 185324010 103997063 908111692 869801515 36877049 330104815 171806221 869749093 189752382 309239924 192337012 72013243 545375083 60292211 801164353 821219194 842751447 556054952 32689302 771288918 667732860 656399366 688658844 369445489 294406054 586149486 621603481 987139632 816603853 793859790 241926855 133132134 272275164 165356245 918648345 123501064 916376173 488903974 793421088 673935168 196524376 931111931 994977869 735927697 31499325 143855801 623410701 87266484 484552221 60241617 901979842 844313330 130968688 904026199 74315932 642413733 695181360 686156636 59091682 984596778 621984464 165821748 694619466 770358180 165100924 244907673 317602830 676770667 31319261 645264959 635529751 107777868 691716778 454555333 487050258 156340562 678169436 995424820 341054101 537468569 963218606 635322350 402345850 928516896 849092421 993600235 579623476 825282418 311976516 630743889 449413606 253424760 787513988 951959958 958085697 873967409 670528553 730096315 274649722 344012368 8459747 927911143 34099001 550732992 595461989 946835229 84427853 611196416 866760940 799258594 197573109 731639194 388089753 881023664 931854661 23845121 994521327 125146883 975279487 816717133 821262291 435834414 96286826 476839885 89915879 548349900 49136285 753723557 401467386 241497088 157966075 247433253 3722439 901961584 884338416 69031258 602093146 234321200 926009913 272474780 637927927 403989782 723222506 729589960 530535054 254185040 688387710 254108840 450860632 10951224 19985392 198982953 571342712 329270622 738207073 652723223 789282243 106914396 347798927 556016096 558154939 578469547 988601204 817872763 576993576 197194947 97109482 863245661 345519692 271159705 103602102 998637506 268354420 46503278 588364505 66246020 496828899 754614139 215975168 269215887 624116088 462040900 394928744 614068534 284275996 151923543 330651686 932303157 151197827 586310066 155965810 615853147 911147571 753168747 24579565 706316547 566750225 80510377 732504567 716775171 493857660 964559539 594611257 990825692 926613889 734366232 479555176 518560916 205212240 598540150 218765406 374204893 662798890 441525007 76516530 310068519 8645523 643802993 723687389 745696257 102908042 883940559 846802862 543028886 848034796 368842785 151801461 974889005 817221122 277405003 516305383 575216706 488019854 82259464 65153440 73081446 912691101 46710287 711828662 319837710 12467052 801596451 128959034 501931161 200517450 269563638 215845427 462656475 427510703 839188178 995250461 520471551 133119988 273084971 176046069 685310400 296371178 352169450 724858765 591041832 968780735 386577116 822484736 82899455 564180790 149268111 641378578 973581169 830994910 293038061 358280 916497107 406236604 384813622 25976773 522337069 865109094 443529565 739999021 513768381 342636706 785173792 23756214 362366716 136640519 273821807 870472911 205225808 235183229 885130305 349725997 891120268 779631458 87849088 305872262 272743035 767997184 112277032 53317117 167916970 673876560 615249850 829801183 16146142 267829167 192127993 652942998 95752532 943058862 453856424 474845085 416863438 609695437 569893750 168411528 865315802 252577551 381849877 913604077 843024941 191665659 457679664 779135592 687227339 408524750 158347272 862953181 470027140 464872347 659127384 24229011 873685518 563721423 664637502 502820919 778521221 74998992 121248 905261119 164077846 13326611 443570639 192311824 368648148 201411797 557936431 120157436 577361576 550632856 474906407 515225771 964253292 505230352 449537520 847907174 186971023 518051543 534732118 591904652 963711720 1009859 93424112 805378113 989095778 795193849 481670901 145583914 462324041 698001227 433890372 59226767 694698547 257149214 240589122 972474447 822840511 78019316 142787008 453745207 78647369 597968516 63572277 958171881 781243171 343837803 579618742 83516525 976211116 881821350 293840052 329056352 939512934 237891502 777028038 443307088 45251180 819072441 146168124 610899339 545820853 829263104 961176629 675481989 188685940 101776715 174813248 160859 556035074 89581833 572193799 790083318 419499213 191709646 714555588 538523136 966873679 743289985 697129696 631224617 962499735 988673580 670964069 856178739 332599147 988982650 453239225 622706179 162648981 441896428 931080757 717325323 272052458 175209773 809765517 981825746 602497219 257653174 542277133 179977044 709950171 856073348 849535383 967401370 721949586 941429989 588460095 312851746 399198384 293604030 438746542 958069772 707795667 418892462 146140715 656644556 395729425 987587726 2251757 968549765 358202146 352830608 857540798 359451923 68643864 492958617 17378297 921114831 633797262 644065907 887078687 391020047 915131308 73531080 31192840 19161131 670197721 542116693 950946841 357720844 405531684 277304385 264611998 681297182 328295741 222063631 698835529 142334451 476009290 408300122 5019702 101971663 148787653 430817010 145507651 799605540 619134566 577804382 767757066 663087232 609261235 963160021 485977657 374123276 588643744 348212988 54900683 266272395 446069763 390677882 572177164 304851731 75107308 371402639 371391011 252459157 639094775 67943548 971804553 614761598 344785754 745513237 24344773 824552925 747251775 629215761 807523476 530901461 208318467 809390166 315755838 239271865 571881525 953740631 28638345 352251842 654196412 586792217 985190420 414612216 158658450 521322372 50283171 77972383 700418869 380992416 26272962 219329094 963237400 665065076 805616720 201830051 519927128 687953045 891742866 594954493 674629897 132075823 303317394 599609953 354891821 658127707 650730333 584139612 844786246 734087214 786090302 327592623 307824518 647942872 69381661 382153760 496305842 317538235 753492747 16617702 318004089 648842511 792942229 86535203 427792695 2474025 391816408 519742305 440523771 617701579 821372311 334705726 197947702 981795011 912823329 684044285 870232686 771526598 109710268 682558083 512416744 962476145 586271982 388172775 502209433 151691814 317037177 156507687 405288618 455677410 898686463 815216450 853285593 460868002 588845067 699784735 743598610 282174514 702867299 642544520 910562071 22024190 907265998 364984012 789286840 133941965 900385276 403957900 180884476 970350026 620055577 969810294 728264995 982685312 597382371 822218949 455411483 256072995 168824921 709753008 290852128 819737677 182840642 352957991 603920411 436195562 782341483 860544169 683080409 268397583 58814172 316239171 467921884 186236785 645994776 143831018 374181163 143227415 582996120 912027909 438744993 304986710 41571734 584489862 510638902 134860565 872357932 383031816 423196193 591547168 486655453 599002913 386139456 675194349 770363808 248802186 728544344 266663017 912327586 652116824 502936886 891539824 840001587 642733670 459771885 84577875 26065387 951830030 370978649 477102718 457688279 107535811 258239567 497754874 935881987 617154117 226811064 993458697 847239000 497478792 205394952 152840676 52440073 35878690 227551840 783937559 44175088 93192403 131464951 770384413 53712798 58087379 595367703 88234792 775076147 585440699 968102120 128375462 903758419 210172722 543693931 103132176 78801945 859992176 163370454 862266931 863202760 308961586 739447142 333329115 546068258 34072198 265614914 256514574 288192921 711625672 128288968 791735407 761414011 807484363 340857932 971702006 764333428 886099615 250848864 85645165 659315874 88227102 975760381 32107466 268797130 241876652 953389660 914482782 597911427 316134041 44927220 754767656 413215760 417323451 884776726 187548776 278834799 963827340 333360524 111709802 491621256 195811617 715820564 368906300 296009793 17044013 670688333 315270249 266506405 612470447 70742351 128126030 646111332 901377519 533713717 924911278 917341339 292937367 172121925 697324795 363732079 574591714 958725756 554570975 931140297 415820441 362801810 977575264 464486163 388244599 47125560 395951711 182844681 777720898 27308593 296940596 20336200 785553991 198452225 679653197 329240593 426004507 249262649 606395167 569960262 659634205 527375040 44305305 684208148 875597718 689944215 838169024 361599081 840143906 496212457 11103390 905149492 403716916 606961175 836289353 103318481 140810942 306869664 393784289 830337345 584924596 56811698 624888125 386241618 615460328 606526493 677459806 724357547 700125872 635664178 924668278 55817173 904364448 967144092 568823364 874595404 585311113 294277810 555565954 661129450 228800859 570017532 917216920 813682706 147977506 381938223 730108065 812009088 124944603 965842151 636320525 495937836 222354477 817373818 801545195 354400697 708938606 272192253 318769628 365174537 152315030 932206276 949001788 511802337 994919854 269287130 210596950 474207001 707890639 912160986 216550842 655720283 843556140 48865324 738991481 705426335 632369720 884689661 572817518 933878383 99621553 946129959 129919233 647793778 383550727 104868774 252594918 290504205 945559532 953313861 333034648 24901603 14245587 570973452 513080512 424053648 592950005 459750342 756544462 334223065 383474297 733385422 918699765 294870166 167004566 684234871 366371934 121422680 742770970 927779963 370783656 701981078 627505534 567446038 719768888 288826263 697364275 367135789 711368612 603241009 791091340 528086672 787273272 215977286 18189746 142032732 66618088 402743316 354204774 971207263 766530021 337630589 433157779 541416818 527447505 826095888 292521825 71720305 40844069 800286791 249866811 937895428 548629312 598433820 499117319 391063254 742125670 112651265 38994311 188127754 997255511 253596937 48395462 842097102 449716795 180116760 199502454 586350767 848371925 716318985 794756856 176487500 926512837 70911726 476294900 741174032 181836041 515730328 413014645 498594233 404470894 150311007 149554453 134153158 237549069 504564855 290155407 663024488 768111578 298543520 21950899 214719936 728065084 145646560 93392524 597302554 855316399 299340049 982097744 385797081 273729691 176932363 885002733 669474779 638638864 568964103 838376318 904251116 497427809 778901217 845999998 649980140 706078019 573328957 506177485 36868679 853120512 334723006 606493597 584026645 859949721 200152066 965020350 67405800 194983010 751252627 273367577 281649254 980438084 387372072 701631363 907461063 568096479 409735730 756055322 916055151 182785777 171012715 514519390 306160818 768488959 691668626 118507595 718142158 542406471 412864799 572733842 449618210 851901082 270115359 630953993 424393146 759971378 370697306 871911415 567398532 50907693 514492235 275759026 512888207 373479742 799467462 532247054 791190578 277870982 554492043 327368553 357416846 163131087 656807773 972517423 390185858 998973410 301633896 103676326 190113839 113766313 487527482 348438047 985043845 317442236 565717654 720309705 99986503 452515329 411347462 362252792 995339558 439962084 116162764 911239886 848758450 713759850 804443871 279062189 732876783 113022634 274843202 238959038 574240403 679510251 107749100 510123765 757395831 356537414 678221799 822075447 478043863 465076711 836288492 742659399 425252628 141100058 71244395 591357445 866518165 538878098 372023040 153207251 617349555 25370655 646835548 5138656 422116949 206564692 503107342 573713333 314368406 281634522 889083413 861171464 801584478 987226371 789891353 113983528 205376099 190629581 981351619 875060833 980701635 39277044 924483625 874669794 64706962 530047443 356314640 885669940 378009217 357989526 558662218 330133978 395623354 151252717 996260535 616945589 944102165 226614813 421210931 219381011 782331081 470447164 739490586 987535831 516764017 791555665 968937255 895537373 888473655 802500196 854986768 821938650 74579527 549203710 995982190 134035972 824374901 177184044 813521789 132815366 241855382 627340587 277976768 743361872 795810117 606385160 633876948 609843871 386568809 458667245 24649071 600817306 903326170 199892435 974791251 13656424 11603637 628791774 439680433 892799110 576174377 5110825 81182746 981441783 813601953 60655131 300785856 524143813 592211253 90341140 301760199 110317484 256400251 192307358 141383244 115865240 697287380 633832773 339610909 79791151 962240437 738319114 920206415 458083583 133508739 200904214 86585828 952414403 674179039 606995709 281294819 120815402 56889688 395612241 50143578 720105429 521750558 624624840 784826752 84833270 869346787 162364660 442001218 204052604 797219387 309636363 454718043 488362421 387597940 618121301 303755747 387340112 815088223 953773429 602823245 871444970 487371228 434366651 79416377 234196050 170055997 415501797 174727131 777542735 343348277 74423254 374800611 164757021 907764843 100830239 389060270 934207419 854504212 272530632 403892501 15667289 520643639 830894933 211487893 623863835 656565295 562579352 594899071 182489538 48922150 927533694 443840574 26227917 204166362 758223322 709386538 346787207 395487492 185782341 440655757 805530619 462923389 615797696 303207319 371139389 791717868 131422023 440248111 442594724 158988633 412390419 832974163 927709299 774619597 594210696 418028474 740668006 425458535 850244919 635357170 312666458 816552601 777397674 567429453 699682934 623944954 147884687 971374391 848838183 371624220 213847054 620143646 252331738 232272170 314484291 107015461 868465146 239677591 257640112 629070120 100220179 463646343 370575245 502582978 204058317 980861059 985798501 488362347 71163982 446669487 669275286 806264573 423314869 117587094 107109686 433223003 62885319 515658099 448147565 848383154 688509812 931901014 553277453 661120824 831465122 97826704 787380690 508310721 242288406 905847733 315067190 25851561 76913123 3806584 230973287 322608631 708316175 614799885 278259862 821988497 178039903 671837659 504567003 705516804 256469924 217383413 904901837 141464357 896125257 417227076 864695042 920503579 935740443 254687289 771149710 901522875 220461688 997633803 861054424 868934696 521846465 343395765 353060276 370591498 384051407 897087748 304080230 995531354 876324490 601132551 916609691 951497035 895422023 112580821 580201591 268469272 350389512 149608816 262868261 723570708 266657905 268109124 254447970 413485520 260385442 115553821 958417381 465389536 377002855 624648174 494999514 261937743 319336150 577895220 293509397 723415125 351737501 863418553 837767975 31036187 490193430 177569646 240133215 600175955 728102801 975176275 403016652 980116330 273067726 882676047 123783817 736640812 780700795 585065764 15502763 456206137 747236842 329278544 261115927 832406965 348376513 591480319 394543976 389639762 592590072 286916730 196552755 913892545 66194967 312729742 439059035 124794845 850968970 100622319 951118762 776632070 964730030 168066264 308607542 397137663 93268558 836678932 839529396 240313417 524858238 257655633 39629734 212401953 954628139 743650521 503330260 614584941 192704770 1936935 13970578 226174139 151978119 357754577 61585597 768564226 727015215 978378850 541477354 307733997 127167353 67983972 856047980 463158584 667191026 997144774 813540100 91274290 501061979 584342416 888243766 14743836 360133162 219531135 518716124 835313038 911528368 615318858 76000919 920789133 347638610 232652233 478234215 302072495 82117158 711521301 941593684 437635071 86929305 536755857 394192197 902322380 295872720 172093078 970385140 769433431 459791197 881499541 699778000 418886187 45550161 542369840 588775402 967300655 160423864 330568081 611086512 480366913 916063640 731618176 85946655 522424461 316417811 792428805 961947871 651242058 430952256 941132624 769587394 881679890 142105728 577154116 866263881 602521721 430889080 333408949 788219011 22050969 589042267 633298313 483502379 676244892 185070844 210745498 892047535 288094387 925915873 680077392 347223319 416488166 930430811 100729663 468497945 459962537 20581563 183859514 234233314 789789904 742298043 250614504 629502951 171146011 291615973 157739108 637379641 481185270 326119126 21060422 179693100 876827498 940626766 366946269 166645433 730572386 592209074 601145615 494761008 399177573 707388478 620663877 926433805 926071571 785663115 937541687 823608938 77929968 429746061 651146041 108292507 182482421 278531878 237573326 749704722 76779482 950599208 904695254 174870554 890281783 804242950 877293137 763170633 297506585 108335905 568155079 828132716 509008151 738307674 890038604 157093663 700541664 936643351 677883928 34336719 378597644 335076336 20779378 750781383 793605090 544915674 766355707 965996069 260448587 486859771 305928822 111221051 432238041 980536462 750793322 307924353 502188541 418075814 248818477 696661254 454953386 730853545 189239989 356320079 633109865 825527258 426171102 680211805 603799219 87757473 530618395 51346167 238992836 789441017 834509191 91938958 669852431 787330033 593715364 569266700 448268112 262081759 107398658 972059608 235756836 41681387 801819235 96816547 892161752 379972172 820835402 909460489 407756042 80292628 182168842 418544063 401166276 905193357 51665421 637113602 29590128 411149637 953684649 772972131 495606476 355066852 811414968 350436100 10608252 351196947 420267061 293115415 905324433 278378492 807846750 569329486 381939078 385944763 27051052 472894648 950893218 202669319 579894152 165172418 912443969 16819349 781397511 205574075 868272091 987053508 162444629 317082855 33407152 614892143 133359606 535443213 536359280 884881593 524306939 820037156 255581043 22688193 67930274 876099036 561310997 11146063 498650214 388782829 719440900 322538709 39732152 504282924 560228375 810153970 464056025 79793812 383889060 634830620 585431480 347369946 483620690 952575082 343219997 396048807 3646396 56977174 511172964 298377985 711042571 863201159 497979248 679512385 802807101 893906301 896486748 868554453 434698069 748296450 760574241 452647603 590490679 483369801 323299044 26373655 109507668 923659772 81038391 438048624 446352025 437709788 4831384 820869300 27541460 526153503 629033138 965335854 351920836 484355254 747166363 976505102 611927713 106231781 214564295 152811016 442618285 645277454 728678874 50185460 264564314 847043189 260116144 455222183 377037459 355399164 836495813 953238174 506386599 800940088 77380686 624532410 68583967 88967163 520530797 717101851 665062221 503326791 103677242 963396147 106328265 134385490 787066781 335579615 343164720 824593134 627798251 833996579 62352945 795025460 444474705 891600571 738271942 844644685 360829964 119864783 815789346 992863423 444946950 888562359 450116597 24844492 981411908 629887581 964014378 761063809 990735958 869485679 977356435 874269655 873113925 105241748 940127598 626422438 929283073 914677201 467534372 828312944 186692578 401096050 635124093 862187377 656656947 690220291 338301652 474884132 323714054 51580872 451374402 957969927 112283536 783908428 536620654 999942165 39701359 663961915 937682586 737212309 170394889 688026372 381461958 386874474 412541494 339619734 361658514 426346187 625453719 494390853 187977123 677469027 553021349 981739891 28601879 497691847 304866820 987942425 184813210 552660735 54130173 239129507 502988358 548335802 864271827 109895044 525953575 691134238 8766797 137824597 60635386 947275291 322806505 114070686 970240549 783151678 108532211 161288663 557899503 189605348 927002679 417595347 244538888 258490526 62660331 429812763 877144628 474661255 716478492 263009906 698904073 961662078 147116223 27815471 26466575 223818679 679103509 697651066 813106289 93740641 678497022 881228621 439779941 593785137 385899528 606611767 154971284 40000016 801466040 824398966 315202607 716933508 513900960 858797417 828161159 976623268 690931114 791110659 851053012 12047019 356449167 33779520 902571743 568107901 778400662 567174392 160235419 502454931 308145018 609473816 301994632 798879845 464489300 788941539 258397136 874893962 465372325 201626525 483199142 466701295 16516796 118877338 420340075 728336826 571268700 136725800 685450264 523734918 153610669 934794085 145436450 764782693 754669245 155332655 356548293 911213355 433095692 195079750 683147876 613485137 588936679 868708192 443240332 383023430 854301840 589049286 933815714 476890939 29610768 160654677 145247195 497306918 587408024 293711324 823306480 86874343 786454477 614202586 5268763 742272643 965341686 566252725 838378849 290361951 678383951 463737247 366734122 32214790 244971576 881688049 833289707 45017456 556304434 432015314 24435635 872464640 115151203 63489552 408378248 701821422 331455610 739901058 149149610 427949333 547434235 861346671 461339826 479703562 826713220 151128402 532947976 419735045 496701217 41566765 144005397 265693298 756397691 585708582 539670386 405294110 984847090 352801172 317453332 733951713 125560189 424654154 436637379 84866422 929178755 661520387 127895384 586889707 506685679 206100055 74337310 269741091 229045727 414960180 481573629 11565568 586507459 171318273 329413884 88750289 421167194 658630887 305875168 415252002 495197825 201538532 623212297 641748224 390208655 997341368 29041536 108459560 937015076 406109843 538559576 371946265 867251722 700166519 585825449 163653869 596864169 345799944 815641208 471746295 877808149 739901069 724551270 158938538 224243822 80177091 813562750 195526716 97694981 954853148 603116504 552565592 222744797 306074651 482509405 246681181 176132638 610567575 71685635 500474435 480513603 397510533 981460257 231832123 545492574 828300370 955004179 550641916 424403006 496228156 594995732 276974565 262724492 405961144 445839009 493475490 515866258 803647122 245559690 169560981 827989811 603528956 744396768 102006006 486733563 688510274 709126643 181457850 361024445 95990775 514853067 217581700 121460008 458580915 718545494 127057890 356294930 470092899 659893062 827375067 501539158 774858647 596478905 977355640 747505666 494164490 492813964 331366762 553468777 548100211 215747176 692432740 53587473 214308285 614494440 93586950 614979794 523751879 969050834 804654864 238071569 81501060 76616396 839776912 102151999 831167672 189853192 585144504 789033277 990229794 463915710 149134119 141346030 542995584 417699358 251865818 52480839 869850867 363035793 579836348 441124796 867310289 501425785 536905301 672068846 365988310 814645810 971026317 589600865 933915289 196072783 108134526 571793875 646673203 797874518 935713980 107178735 963291420 999086860 640570634 241275586 988876999 345191923 971366362 829118306 442073833 550783589 470297528 293375970 211707886 51660350 21746333 427424151 79817719 614714144 631922046 686647926 548519132 630169009 120098021 375931167 391140951 675576811 738598089 896597983 58425504 115930385 497781134 254684543 360127625 69486007 50360452 517288442 911119360 534862567 875480708 393292155 92645081 237165350 980435612 666320068 5694946 621663503 501547321 879348596 845155943 746806468 865104568 482824001 994574002 145794500 572436669 369113329 589972218 873779900 722814673 366057713 768832372 450771992 764554913 241398742 298339703 851567281 668469824 941491958 599150385 17867703 632022822 873342076 269555851 670859278 75519277 451505807 154657734 697303392 530425096 751728280 843963366 646609737 564582906 116419470 887801642 930893664 561335940 309965569 337011379 412065258 528997479 192254790 198007478 287106479 840736697 1451348 958029491 697509031 504749875 101123859 697080885 561833250 37474910 303167072 21805971 862322182 98699700 957217429 310848084 987433084 502409181 98765768 965636314 979795496 188407314 854190782 149756851 826722534 125937218 935459109 416790812 270623460 321667717 434378278 117085620 250059505 63997780 171200485 953149917 31325231 34449496 22635634 120391563 663065898 644724390 443016783 221523724 553547108 561970569 700572638 466184779 337863280 354880150 771012677 786890420 728300744 242165844 876467060 600257270 473709771 770788343 627546004 928250785 732998157 642961824 112977323 807667375 190705543 245761248 921497601 781106194 252461886 458133130 202850766 107904389 148692783 812766707 640311686 593032921 679217146 941837041 137109607 741289397 156331556 773651073 615042038 673905954 917950240 269600069 925176350 435743375 204539198 729950999 533067713 17883094 245884984 221360186 28371593 819678484 820062150 538430254 682655374 865153667 587106014 591564388 518832038 875315377 488206457 73236255 487202852 704877869 697148928 60141810 851648616 591607580 38591959 277747928 99712349 586390227 12472445 428541763 603591761 303455130 358565033 393338760 763504199 27219719 589431242 284232036 399742609 362393939 34123142 459739761 500107799 115276795 465326475 122101473 211326674 466134809 967522733 383828708 514363805 407433409 856058313 816854461 934264220 565416676 850925940 128413632 751222555 68727598 196829981 677339293 558885825 329071332 549448497 223298984 320698939 32280124 268849852 159243424 474594735 736745664 800254580 353130844 947904776 704351633 804160499 601191316 207038573 544776119 206634976 683500664 229499345 465040693 672064022 746643074 252276642 706967742 495995626 337136456 206506131 188487078 576790663 914925473 368708993 77475311 47597405 879053482 9352770 353089191 457503842 729140622 256327165 97017560 300813580 131715372 881627108 397435947 532876755 158342332 594076603 254711394 889750552 189447243 228014261 533892729 33109661 737831927 413695834 945941281 865681772 896042012 853670145 361975802 760410692 771911407 242744082 18480297 418108415 638319083 581968795 288729968 867420802 353608368 335050197 365149256 733262599 403907640 934149061 387640574 629313165 811193633 855430614 141100611 10313436 699821809 358997416 780976976 997619095 433133831 433690785 369701975 669977631 737170282 7331361 957869006 725792757 218563552 962329932 394867102 262346453 356239088 422837211 427906617 687920657 992212646 553992011 436332505 82658176 927415944 647403427 648681428 339112372 989593417 655665 245718698 44022838 223967305 431196295 260857232 125763474 481674058 344835130 589770611 636759122 385364513 931161861 830555363 222362850 155209910 804766854 874626649 826347335 686846308 539300840 178991387 539213629 908272734 266961829 518690202 286915367 548877934 814785690 977671072 661671554 306484857 483828800 837776172 3506825 795859171 541632107 724068929 207465630 657068803 27634847 965760586 814083231 459305445 440879310 20421472 847241649 372759384 430565819 329632451 639059663 243873608 262582899 39983096 385539807 136842362 63277825 724581126 785804887 401324148 650545172 996108695 954809084 165247334 691851197 123684326 374900448 16850500 413338521 723120436 602188379 433786098 194915877 360581202 188065728 570100338 978865226 903537354 499551748 730928061 522439874 77670917 591137568 949347040 341168980 780357651 934950281 584490674 979830244 598931883 397640442 734234901 32171491 607022666 793307976 449215449 513799319 653554094 844618792 481179181 910594092 163830601 472599812 262179919 50279787 343799752 257633732 818653243 672334674 865436228 30816205 150555966 445856305 189514618 447950702 95488132 54146545 418341545 451361128 578400414 10211021 108925389 920715907 464200219 267394422 263222433 108494898 297576570 625082981 195906535 278672279 674033471 70918536 448158977 404687828 410493899 702776797 315297712 654819236 995987032 251981788 732775200 544762292 353840957 574812629 179138211 909812810 536328394 235227602 123472686 675189607 346150697 875190835 225276134 717927671 575281697 568709806 66846821 566586052 841746434 632806835 432449014 67210341 380940023 453771836 17226154 507127386 732496512 754225771 129755403 18489341 718409136 551463269 747555433 623012630 170707441 78019320 797974409 157689220 764541804 252836095 12585391 858262377 810917313 979406018 365704654 679017474 225345797 775653491 663805382 519525712 240115607 1334592 790676967 325071532 166171187 306108594 317855186 607512367 294304825 87460532 582075184 383323420 919518114 980009201 695118254 536036290 640618184 63014717 899615913 655048861 459600961 676358519 945803484 183851247 115381199 310394518 71353012 341447158 134131125 286153132 44767606 256178170 10834343 329483105 444547577 655009128 312502984 281677583 861411059 356728774 88494738 939478041 134227379 784092714 878251325 544033827 601015075 334798209 403383579 930744086 27847894 608675651 977983881 582964344 485174374 167803930 28215482 459354313 500622555 475740693 603618627 717247379 249213393 958024391 257307388 799507977 685778126 599484548 173515874 142483988 911181893 875206255 93055450 688219279 504731530 751760244 997512318 745512625 202353641 361560325 791838417 175979735 40988597 405460565 931177129 291683746 995104999 213610173 558758005 403329000 314452907 803317066 324601011 49671517 558319673 549454804 820022063 576784360 896444543 842525244 991542779 25333464 709549351 798075767 77606331 450076396 810841364 159864518 378111266 659859109 818341869 971734263 710824764 253118238 994401757 613135705 770538972 320429377 15049177 890182446 919437720 954025052 424914114 474922980 473349618 115330626 299101704 993230720 99126869 294449011 66494420 207297060 454725515 631176854 437085838 200165054 637053466 598977093 26319474 726236210 22137234 857203937 786881796 463779983 225464236 954525333 939206917 60900451 678292702 113817109 8664523 830560070 354652957 600537489 623628725 944982712 368243869 6437676 746093680 139856904 64562045 556983089 312493411 279910032 131234611 452568980 751539563 300773697 884184452 495385272 22628259 804845637 159790590 462893908 4453962 103085810 550561841 686249378 178776899 622110550 22064780 927428922 325792823 602590516 927872422 694057500 499054726 780738170 734704350 80844939 455261889 517860025 922004552 63321883 449721267 589248692 68940409 403254064 16276253 103817078 699947764 983954696 800267650 820101079 918006637 186834095 113387320 245220460 891105576 178008239 517748437 928696132 176924865 702465161 340669010 889420101 911459183 682952038 216238573 626811590 487253388 178478769 330668932 946303591 116943512 145046346 591738331 841709694 936328118 42312065 480108647 846580896 103495057 760493778 565459019 795356239 847738834 433490237 583382155 752553803 171672761 351982462 428166179 874964690 815575710 997749710 924393900 872910847 227676624 658135797 298457294 792090745 810242807 253566448 579994599 98659048 455506523 846373788 688493314 987112512 995557783 776947755 534409915 163426336 31082607 958230427 432355214 280423010 196275201 159706627 977512522 322988722 10306782 133088399 928455373 718182953 316226484 585884186 51132611 440631210 456578212 128993153 836246746 129108400 786730816 743731975 138934407 435849325 731820067 562059954 592369824 205673855 393958964 873603235 823737015 815531721 506547346 813497710 112366074 941909311 832542237 173491592 922281627 773338682 994977420 664272610 955732751 415752158 553357523 476140575 722196653 375176142 43867275 479129317 79898041 31059874 727046856 110710515 742876761 812181816 491112639 5088783 40064006 167798074 170148183 586218500 830051959 484930178 201996 603106343 877033271 378505242 952090386 496807248 642372229 718609451 879304328 358895113 150939032 681882753 121246416 446076893 561939030 439734849 649787867 30974844 213887888 590602374 462903020 395056690 310752441 798557380 814842389 916028301 122171786 98515285 176475645 638286665 364437628 502717445 420451867 204458355 964120920 23702514 900447156 307535975 59675178 50725399 945102270 346299234 337406052 748518274 307033052 527268405 240816984 855230346 479585699 451040297 993191344 956308343 862258008 520913564 498671979 992583962 703268427 316386864 299238411 656451450 456782288 460876593 173117173 446366303 684590120 748678806 380405124 745722522 360298850 473301687 629443859 933611739 492717744 2340559 231595912 56539906 875494521 426914125 64681371 281984053 379999744 16464844 232079190 507393329 832554247 544594268 619299666 694469336 904352039 898625446 581296517 563175239 223472216 564437518 138526505 229507735 797110028 896570689 554697148 782174052 232303571 442569597 126985909 111790399 752934343 709380800 121591613 478633636 990268771 479620359 489750177 726604327 851100949 70046140 391163181 116456786 776563035 729102915 233494001 834835593 765513152 988563067 423462445 26645077 518948793 281525145 362386726 234977329 176763892 885369040 169140804 668149473 853876487 34420795 282930672 112883313 950931844 882981249 936293862 675403718 974803882 805629094 483482938 847724219 744177626 987626439 825655710 492550686 328202953 641653032 584202403 347437909 478435121 236515834 224923041 111648010 800797453 335597947 798370044 755418297 835001082 258109973 728867362 291854960 852651916 669289393 93382805 734067315 291358907 64531363 937884850 958796318 416214901 373299937 6208804 809827741 974518244 579933911 919813845 75059122 732382707 496876689 793740357 894143885 894513575 608571194 791370429 376339122 854294581 422372304 251402900 214116145 822730709 754387988 567827367 328243153 361452775 42932418 811676514 877187474 250634310 785155889 837827234 342861283 281252697 516547462 56045585 709821431 158440531 817923402 439289806 11750613 849394275 273661557 190791410 872879223 33416721 580066911 858806061 704289246 192845495 282629371 421167956 806388627 256226114 903244130 730480221 2052621 568477645 732344954 371221549 383741239 135077161 839086911 678827557 664322378 945019618 329963718 46432762 197457653 345760765 805073130 830012986 302325195 447508670 466893539 578554009 333025376 724259734 858497866 64269633 202846257 882638714 428822845 557505831 10185524 999104731 553865859 910199979 111620546 862684842 587279510 469645747 271414929 888139982 665532249 981368401 869434867 463253925 186125815 59799234 703980441 758886008 921615561 514546576 792665963 883405286 491535883 113251023 485739164 592559877 159012005 693480871 789878729 369001837 920283837 302562685 859590012 462631946 150426654 707743556 387657965 153101832 750243934 877507475 287322508 673394505 734811785 677772262 664465085 22547156 56036695 152324998 777695471 313040608 170303476 872204537 409985333 844165442 896266741 663988029 528795571 722560063 497898205 482203173 858985301 627602247 477620088 208313574 671993581 372819768 663881517 771894046 979456184 686232805 218229493 528382593 145502831 202201589 757003372 459741256 249646048 158419164 131738445 548485054 143083219 888177475 960689551 151210245 114835964 786743653 16910668 308035761 609308228 195372452 864370655 491354444 527880426 935857037 848590772 860274 172806601 958132825 462779564 789218257 886963790 214373605 719570662 724238551 91025492 452458478 552026896 920012089 663485473 262413605 465198445 653856333 160094185 864260339 584653989 690178585 31340471 342589552 831231307 929961848 85241566 439597182 111720397 966323312 205552859 274555139 164989174 578393130 646205121 658317014 504056766 821774347 150537332 139422181 849003611 357577077 650937667 830862058 725145368 135812264 387174688 390011965 310829596 115071747 273500471 459610585 962044001 339328189 235666608 874505698 552851686 957838327 234074199 51194469 313680434 487906197 605133596 120201515 770287218 806944930 992044366 496539909 812209941 379099400 486270972 832149665 717380071 993734874 622848480 299321062 664616065 796957974 592838482 373022762 426878786 925855212 217886918 946038505 138432780 133452617 740708769 780442746 914169602 46627221 301515385 665983254 82276542 953590894 616231916 525734769 8553495 741333484 967164897 569265030 250427995 654162239 838071627 794441197 809700065 261667266 156181619 569760806 189007559 966454517 279176401 345721057 709766306 532185362 548473354 517813497 597322357 156962499 946133582 253989478 687641698 755770801 994656382 674388273 377296707 438669791 579446481 696932718 534668993 107356716 663083681 243656114 273836189 340755569 600623334 466496191 443674079 37821111 101356853 410758253 214620246 288903119 422192385 421385696 523601499 39453828 151151028 661580797 275876346 122730422 166434071 594598370 773901794 485339806 591905329 273602207 311616872 680635857 92401061 47737298 938410486 663640285 379043753 198526891 559422510 113706537 461379954 485822403 570732624 652518842 177722685 943037787 161323171 805097922 349873316 113113776 957786073 455511007 934682625 296750507 890069578 88305330 193181094 95035914 476834182 764592437 430584268 461402927 244018763 154580504 23501121 443420095 426144847 183231705 117717465 994088262 839845704 393655650 437450486 646922227 888923441 16324140 753791690 80137654 800827739 650756556 824520535 386702390 423572272 118887105 91296369 605668241 659605237 474339727 90804861 219631122 400159783 528687048 981054265 475043457 939209249 765075493 964222590 206431266 697039797 726792282 124551123 415629753 708592514 396345310 789750839 472602042 135578939 939699621 410865043 787990700 274192829 123828791 425641405 577595500 472051971 573846050 668566438 366585293 192152654 74204343 364171631 364636917 441649201 855759208 221721958 585070823 592701405 623761575 927307249 764946036 98138049 350877054 889533088 905455496 916416641 971278032 608378708 896347721 983152445 273424463 697005201 577351358 728166633 936504108 738461838 310486281 626504124 145637595 599343554 760568722 963629174 684346047 470135086 160977222 182123745 425877845 960994652 647947670 548646950 445529004 286606610 363852516 7727901 828951747 198845598 320286766 461543231 706335938 911888101 378489998 534836085 866099340 600445056 875381284 130121588 497633983 274634298 494954416 320023234 958217649 435071532 741882145 282387146 781292116 305646351 434359501 980317915 298242464 147069118 192803821 695730940 996416830 578341978 676976471 806891019 861909245 494253197 765379189 539317281 447645536 20081888 456809815 456804310 951819165 454097701 202527427 202067093 592568050 726365639 550884026 442903409 351480074 531282391 32613934 110282784 557233233 32814161 380484227 54153665 860392794 855399108 255385552 632324656 405253683 982818274 330958890 575656854 318452289 39790876 752556753 184142386 587769818 739168650 680849076 288399528 599841060 338801916 990702313 854396811 138629270 560299678 208944253 395404545 555020839 687231311 482377502 967013747 939135772 385386716 340759998 324258683 7659708 316772901 834193667 116838956 533857706 790086190 893668883 710318115 37088693 274278875 709557161 922138336 90983492 149908582 795824125 686672675 871428295 647172565 126111942 502768967 632158631 232444809 891517337 135793914 459806454 566862533 396529009 757833100 105881985 520426741 720412970 707744482 340028454 328751979 425925536 934875489 592108302 65949191 960898514 619741613 909207109 491412420 993244429 683860962 908778294 304110655 673685971 460839110 532752703 590383379 407592481 201030555 977924809 293649366 188996259 152841989 352248913 152724313 938692861 765834190 798799101 477168182 306556008 168049873 437063983 852490172 709274951 189914699 38332174 693696441 703884511 272336744 227350385 550890337 724639797 154478123 289560147 105760233 167994920 970122606 496503026 347708814 411993149 223898903 872263695 22277647 482504267 547773846 596154602 627724508 681226298 823976861 108422828 508375089 932856689 820281112 839685948 559426066 271837336 360505808 991140995 892870856 110161617 383811486 291562539 692906797 323796706 610004275 672949946 271530492 829565965 18716138 925023319 537530835 526701406 14545079 848156069 808457794 851160297 541502112 670265266 41112415 843128681 847404718 535457320 336475062 970449079 125288149 23457614 554117434 764422569 967816911 620397621 829045306 299592489 155658969 254727190 709542848 348315228 479738556 943184969 915497903 954648326 561935276 127978483 45888699 562078332 673638481 923562004 362311672 564262567 889300745 829406651 376937902 682029208 238257677 322292884 638713647 262131701 528829438 157981506 150755309 346929671 817130310 392858228 585127559 732784498 562064518 883957437 636070039 669307761 250668707 325098378 272656448 236914468 3030335 142274944 424322313 682698171 607523943 897573870 525538076 393610416 527450857 325133032 888646063 886093300 277959462 471260648 442880914 899888056 513259337 831878029 345795395 384999917 697175083 1533215 766091728 750238211 384889487 769554798 998025390 877121609 24849260 87216264 585823298 953240797 423699561 435631312 985037259 648875341 594733589 34487254 386305881 124689402 181636563 170201661 169524743 244848217 552978796 49572491 180142268 177469525 829966680 151962675 716950168 455999452 559852938 464770338 771094915 983463148 811713925 128539591 110256525 841658946 904034388 82933589 627163014 243241132 837197950 661163248 535020058 66108611 453396365 229508571 234802893 991420910 587446335 420410607 961767311 559355509 590261559 947753347 475308639 700751045 616284312 608982322 223432728 975358590 598703591 581069544 978140633 460940143 73924557 319544536 625672487 689666730 188536019 698931724 498750498 105897284 751135925 78438759 814026553 809831926 332146000 893465805 967786969 370604058 18079685 41959222 673499511 73265551 11467169 656909930 899910818 450191664 508301660 788661449 351217310 237406981 858455430 186197488 215127545 886977358 299723448 572738989 626861230 834116318 195706596 509091110 25362455 882333006 376106655 63572991 690544729 19738873 563061274 771703883 390559853 60649628 88191163 427970343 852197322 915647166 211348083 986623888 506634522 413505882 750605477 733234161 795812726 285343546 374188299 834514644 226193816 368269310 770296089 146499922 171822135 981744417 485226389 3147024 799834338 307355614 549167938 641062591 757610042 543237659 205956412 674842358 271892105 152770448 489736287 512809716 304713801 325085174 723884871 827022509 45110014 475062004 424491191 888494230 216185966 586092405 935462261 485073270 407740449 55439473 799983638 376762530 174679689 957141178 537728480 629727538 83615124 495738257 541466016 422394844 905624766 681278447 406664716 128640200 319587637 918794728 688376464 859309297 334608777 637541409 541625752 929297480 370689171 377791113 310415098 471932064 219098311 106917964 426033675 479810948 18018776 163091848 670768728 772663265 150486845 821021810 267495019 823201134 652485995 289182061 947516861 39857709 423425601 451191204 678937544 413888396 596932544 480223733 929094056 880913190 34978057 382528308 384173621 37290958 864835661 285659859 525988029 967860445 423080050 735166974 942265071 730728601 499016592 963762199 912963487 866511550 242291930 637029100 136618491 678756992 322276967 507949778 6953114 935164156 767766810 794726797 492809866 432036928 757093720 689739677 463577691 637424860 906785769 595680888 909924950 394703847 830033770 542257560 575478815 172410274 795763664 156829170 180642787 708984393 508428315 718372136 278687501 822943811 996796966 98326244 462414642 976611900 683621250 78576058 236404089 157227316 135887056 5106525 128444006 140349452 920772240 525209784 386507874 696202206 925095304 126412386 644007974 888192791 175614228 746909192 972849818 850821004 596280840 400793666 945049274 863794947 552583156 780807867 249754034 114847901 430969167 121087319 894111561 17068173 204036141 133000571 348838031 79769186 758204258 609058686 230556698 574468183 893956892 907085594 435742628 501774249 65952095 700135324 578872965 924216469 611900839 905991917 291595424 52094207 12924033 688113382 453273016 444694771 817055065 566234847 611951695 859758977 813152817 608088888 365289010 768928892 302362161 513918470 926006775 334432967 761327122 14908303 969675233 901139231 96977332 359124785 558261885 67675251 862323044 200673221 657292949 512300060 325002344 31568076 23076389 747219638 760364066 708922860 600304504 345994633 196303650 824902110 715877182 599351501 780759397 949950872 641431177 70518420 18991294 684895208 468792890 903822905 499217526 754600709 113976641 427020782 866993898 745091197 658122260 115597103 297374265 758494775 244097104 182441434 658370524 240250829 318812271 992234492 394190479 482192925 258576762 393975431 471204101 868970587 415014185 968701482 651463974 307852607 202158079 640207429 633669920 732773015 921178736 465632286 174090115 700508277 458795749 468522998 800569900 674734129 69265149 159024592 316881948 181589402 524577950 132633393 618571351 443677249 41165724 63659626 143879901 740824440 443102666 896303228 153680706 321796343 495938905 762016740 933590128 995635757 393846916 493747517 966365212 717536489 968720487 85344445 426556626 198750637 449607028 776694184 111984928 982992400 553843471 770755842 192512480 308667982 212482068 974420588 595519412 890075174 439824753 446573245 902993973 690714183 791421740 582482449 879536970 613901188 752672735 941744139 429505165 396091562 286310742 232223582 235106317 493904609 810901189 345353458 974877683 763236788 166402254 238746456 933856307 756232278 536566046 117527606 477045312 949834843 453876432 178241381 824872889 468931876 628418659 718946712 717926702 567053131 474102879 226689181 100311592 195754810 437274763 187152882 577009680 777006322 965639439 401198420 271485428 465028222 602466795 936992926 249836383 836206473 822797702 938917532 681736495 149438189 13979831 311650351 433757326 764154073 402688010 595838791 39981256 564402926 798275309 822264803 695849480 538141966 857067580 580766215 974869943 647598545 329477286 80165449 570438374 740885298 555953708 249430345 412121687 467094471 746963423 845444061 845818438 164469961 313503864 337080960 20697136 471963987 9539115 622565741 426763274 856322112 405017301 812264518 465082534 525335162 251764258 10762417 496893654 151416066 685159427 435015069 875458039 296451823 794058141 164348961 920192480 484690245 431723985 280991564 430721122 771935861 689136137 993553722 308900127 297225821 283245213 44725555 4985118 101470127 846054821 874360203 941328754 400385865 897841088 157753865 692828546 318855692 231511573 700384334 195717643 342887386 463162716 201991255 633517435 725560273 201053928 757766909 104044556 756704453 153110997 900256648 731092584 247756264 160023929 985937518 402901745 779271851 68914265 537431705 586505046 324736206 906169750 922165965 899068392 725348420 269365105 325091891 177147877 687922712 773160217 685466958 294247937 249778113 45110327 338647547 74086201 297304157 218216401 780833472 227401909 388896145 150596680 604205576 377159005 767924672 143723454 16929280 257974709 561968826 907200214 78452656 739764697 686702768 73414603 183473309 819914283 583661404 352490420 640895555 255200223 966006883 429167311 86297555 426001044 181508424 834788306 366539628 835435655 149007527 977294058 539410134 324447975 51943200 873942536 769901375 184900738 635428613 291548258 720436345 409189210 293942226 79921467 352418070 89636358 480404919 456578536 595738390 362709996 581055487 136859428 432487454 492255811 262512593 696247904 421489142 484274025 393078132 746666577 872765823 582467981 443882221 417459107 600571558 918921321 433843746 156680734 235702828 249566562 786624116 43901033 123287844 242237723 771598606 301167664 224208575 290325519 630055028 797083520 457686695 225919942 879586235 681657827 744683189 10135134 569634023 271109682 750266437 575614460 434810091 641252940 441265954 790431107 845105667 987869890 382890235 642616517 47770674 728181419 582711042 261091444 299949787 837537686 950554726 169135859 588808057 228190506 657534531 816883618 655473641 484572911 895663495 243891179 143919669 820926419 781731821 297586274 775238094 368568507 656228803 189015300 445261120 32861172 141404575 708065461 675488911 104806825 279405919 185566270 162815706 327239754 151465574 292515510 414620686 581265564 229742882 5793943 356165465 564904021 617558452 624078963 215506880 685559752 433436084 543747069 549598154 957154978 444388673 571860352 400975860 301115196 409692456 670737363 449571507 137597829 934419711 390458821 49252135 522859646 570126822 969246024 270212971 793106078 332391581 187192099 182396406 292085463 712958642 524083412 841241964 226601801 744743435 108659595 593167362 456919518 151851748 948888553 495432220 358118999 22086950 362336972 672910025 597434230 937620690 217735424 14880817 253248064 877598162 351430389 304882374 630531004 713463252 415488098 869039516 457940578 767952561 598623741 592353687 860548120 926692886 719530137 849831722 731154530 343622021 975333852 694518868 623489231 65164511 103408516 348933359 825349631 205819864 854230345 169523311 404841763 119172080 69670516 712616283 476335140 747108793 527766286 81751832 3983936 772227644 778300122 105592112 88740748 168731707 619170967 388040989 860221698 728625822 831010790 876105012 304483853 907474443 281943326 713569951 57223238 385551239 581332007 895965999 927282127 209046454 446952050 931184056 987338386 756084565 645200985 570379141 233666362 535908494 652307441 89429859 7789828 941543418 281963755 436074266 168710793 752070398 419844300 226331343 564045174 323391498 642267293 638410107 452602910 579597495 317213472 25820823 530146675 384716030 616423997 517413961 570041571 120491387 239915218 619446655 208879456 58618295 673152250 25466249 317178425 16205809 469725172 644213061 323543641 130779687 243985124 741218585 918298630 389155289 928687880 780519015 277301597 945516944 142802392 398592444 824110530 372992673 743491172 972843934 807542780 459881601 958730840 706359003 341633296 640950515 668579342 788670891 949880993 572005587 76093533 179404342 734378901 817936553 569391806 516774017 25480668 280040781 549361132 744108747 281202592 889504606 63034837 563308968 947417864 941297651 84833715 570703073 63705598 995151631 188488639 307411134 779143668 228550228 403888168 720311531 953481859 879166934 295483012 326295701 951622990 596133584 987858932 845730596 223314989 873024026 265952970 572971952 695203297 450403032 847852546 721527073 813759017 961396285 262310003 133932961 541022582 412998533 787162899 132507803 245149012 45554334 906500171 84788243 666033231 664381225 234047101 688911836 72215122 373507396 906110124 552274074 121963209 219572494 883590854 710981322 300003626 619153552 162750712 601319868 916792833 404571448 950480023 996170973 513781301 690353475 683374182 510340348 695993010 60188787 147345263 594475014 100412986 360439837 126262718 62810920 481191467 581944608 153569750 769830719 19250483 381841705 223759908 760672527 777766351 301365760 83069357 835858867 190030044 372454126 789494565 361476472 346204740 63975177 680917247 445277310 165763533 735644162 958821317 308361087 954749867 942799103 829057707 95888377 156486596 110498286 217215742 812258920 803343319 738581618 884196649 213217595 69424924 248932453 597779457 90940843 284674700 733207498 422491208 751974743 757126015 339410815 237311968 848913354 47483470 780225491 314943249 263425670 26095112 189251577 92542102 411093723 940668192 651691144 475763880 699226826 130841793 259326921 959838010 497545665 268354125 296368397 520358380 633763449 267412160 294727453 405198869 455538354 640161578 433829791 406977881 923378636 296495441 377506272 381402326 288440194 643389521 913664027 371987846 826117213 243910569 778723732 532238954 803161371 82095930 815433781 615797037 170519109 453096799 596186172 647673809 25684526 602168202 979070964 352868311 983728832 259978276 449494273 499491604 313051611 547136416 883546084 421636879 445240997 152279613 728498279 209422775 416164682 609913419 619604077 52188801 893509998 425024019 328164869 137559462 478729473 133900723 351590406 199201239 756344933 627726364 594333749 998481704 576695249 846809278 203648413 776349021 700159449 857407199 140861439 109854713 467123486 969531037 998139359 908076385 768434996 349894135 211963163 647268961 674110952 240147635 123913285 691857451 408500207 622751069 443163074 35185557 941069933 883483686 567873485 443132770 289651527 343266072 343341587 576219502 406790830 122545409 896388421 76634285 193322728 782573017 38609374 184600891 765717109 405889170 206494696 629982325 800883625 769245957 414222668 950372416 325741406 722632618 659096499 622598821 863148434 859030486 800627118 856839267 146021988 351873685 616436945 962656260 410068973 128835944 812576180 204726513 441323253 678417583 52393774 309524424 200176695 340849855 151523642 39110681 484280379 274505335 822413521 568528709 764860654 229244435 88067915 715061521 393635657 317694858 999623649 16959392 317576843 687651075 752310863 604734978 82199465 604997052 872838838 696251975 465059484 119229539 737029031 673157299 26406846 221547469 518109241 158556793 886786654 588163657 658483963 654125109 640929003 987119212 743801473 370522894 562142793 131205579 643077220 879328084 214432872 477421309 376512465 529228453 821698577 261012618 572127653 11989576 515023127 713933483 833826762 545663613 443711414 205350258 499076573 392372613 243702031 322875359 143718093 635498023 487195316 402172412 535375829 244396523 569064170 753971000 580578271 804828002 203130735 122204466 909680228 17997052 427779322 688060170 621929967 411526572 241439224 432555669 175341424 876739207 39086684 241614203 585205303 394157773 171054096 117720851 834372658 629841681 322736641 878338060 827744471 17338713 355340668 832060575 88575433 559695427 764526548 595417040 602438815 620825822 130895262 391888373 526197471 502795803 202422413 189659414 11856705 808678158 511314902 804410797 28193792 810660851 992997480 509072310 209292908 368001258 264760496 619756252 358031534 43943409 722409008 108218333 888464293 522787393 822997549 21934926 45012438 289583412 500181628 440431519 148437671 224141266 395359973 90672287 873455867 649223981 704361421 620556047 957287398 719841812 995598860 920442935 731161804 545910603 326597240 599747231 825674702 775814256 70918205 155926667 114678721 364914092 575334101 726025224 315761687 339093510 970239921 699869608 535075468 390094123 189330318 92345084 63496660 924959423 930378893 536924410 385785389 515104842 371846649 564385022 562550677 750319094 792114118 516727794 155017104 582312001 384612501 975111538 446252396 184109785 61609510 887941769 690452677 550651984 199239262 146008050 273387318 983456489 88703232 82381770 699245303 570951674 571553467 195971319 76560377 359347512 974544092 616494137 490582437 952024347 807783179 279568683 584222747 68688515 152921728 809685345 462961939 492864124 841610024 319330182 485933780 790632233 24500707 598156716 12891080 199319080 944746047 274980902 46953032 758488181 83228595 350917839 861188208 666221787 346315014 622327035 100969960 901180614 31863319 864118365 83269366 188834689 91595692 497692718 78461353 430142903 231967574 846898015 662416648 841612550 149236631 722867322 265530016 993912516 282601671 735226351 346962480 295313221 784811669 183576795 503753500 72183594 390086291 807887443 307592607 718654709 847153885 121345538 989588494 367204920 321649842 410288484 293529620 554402607 201118045 999346792 980968549 695951965 425971103 965808088 796249158 567052536 937904995 813506267 868407951 900958602 685851658 654689133 757570999 546602053 461749644 961783263 937045978 765173752 684900507 955354541 947793169 46506139 222891615 26377429 876848319 794259955 723516908 733583019 519021094 304890100 901390554 374964162 747512112 114638441 378725202 134619576 718250426 749252443 918969906 71464526 253632337 550692948 666403675 898750661 209211355 84271500 846138696 133061961 830031451 263160377 877333839 822631856 949187615 661697459 353228696 451813768 776350977 87539061 993303183 363354913 753945359 782979382 747460471 557127346 447248716 543869717 899782985 970429385 219112821 977402487 432902579 248940043 565742228 563306190 219086401 186145155 140390338 395295346 160643275 254995055 586564038 263741576 220712887 766290021 795419299 312052769 988086618 531063425 825225953 936937284 839349051 115577906 218334400 151228372 493469319 365734714 517935639 727178302 443577252 478230693 295246331 862451551 509643931 556981433 373674993 409260027 289554109 326821463 306631419 694259046 48736238 71950237 13794190 192990783 767981609 446324037 342456037 966192613 436463233 346192138 360264980 370043551 787187792 714221937 652143064 964128440 936314473 716298825 614167474 363594650 219425447 73159414 308769213 104644438 367964920 662860372 232743733 768634803 772313736 875236270 536340703 537445158 687613145 796451810 471997550 931595830 211295094 146305992 802772860 650210620 230250664 803036889 718622835 18956313 688456172 407413362 135800250 739819250 826815349 474970764 442279728 709439577 532837436 148007024 989466969 336799099 898265816 209404153 9096881 683773027 137345151 3562626 179731662 690449483 831255416 492531987 714583130 397550223 669031018 233385146 388119066 167473709 363932980 366986428 132604466 839547958 714335840 895579163 748643573 162277886 118184491 729126879 905401813 878625879 562258522 698459977 164918138 366783484 87257512 605403908 503860140 848345982 52370877 995873427 372516948 889896900 464704311 244282075 908246314 470706608 847952343 229346158 36978657 391448720 379146304 479534512 108848376 476524959 969805385 690971597 422340893 832923021 400004304 750819574 678385777 31271854 557827556 214424003 966553656 504878333 606069356 698796408 350240929 671093839 691871873 624760965 325611799 458966370 649354627 692479846 947168046 723681798 239718666 651653412 476123436 874020160 753593291 39966415 124323412 684783741 283000150 976882518 451666246 502363776 300239550 144248895 703496122 271922040 826577095 634701141 281718025 213590557 127055857 156039809 1888584 885597620 490525701 801609871 603624198 169719754 647877294 842677989 596511877 331947895 50284610 275810537 519500243 135831390 633548457 960902819 278488969 306638115 497345911 390410175 838239952 18251204 667622893 799282012 696644756 311574039 525277073 947849003 637904838 900208137 566786226 758409063 824408599 67754009 754026298 441909130 385418331 756146604 53896651 94822048 646665252 84492397 750817550 97999008 168091167 795882691 759886477 895505151 846537121 914673005 728148553 376346656 556910967 58454270 454980496 73982434 314916660 102268617 955495231 966886157 720488852 744723834 64251418 26754593 887968036 887283404 974485767 355263938 188599391 794133553 323514583 642702639 52962417 706363768 69693269 503129691 671294739 854480903 257790948 186213183 737048766 130350624 158024588 108057783 987959184 374997996 235449880 605294981 413878923 629219891 93055505 709104160 804128474 203611154 20164093 451130156 764758449 887105378 348109002 9710919 507370336 48704580 828598150 805782782 925139389 163555919 591953774 600834360 921489991 459042771 85706389 829479234 334225866 144392416 869601127 102808299 579375770 94366993 152720647 966923237 141373279 428050246 71493843 818909894 850929653 901081981 837780273 527059385 865199956 114227837 60552430 38952865 754482293 878877142 184396038 205998066 194775296 97350227 923548932 935571850 779753094 411415172 117630730 675065590 290886598 459888482 808405150 363565942 17628834 852015358 791748524 772037850 925825825 177273043 633860839 212730393 947245921 688299234 511636720 840531636 655399278 329991124 913576574 168995478 400881609 289252297 19371261 286674582 795971337 188971191 173121974 551740456 51387003 966738862 641023568 544964416 103856936 572894653 717749839 945222737 138697018 415277692 642770550 28083263 452873846 387142516 764942009 775488320 269738688 865209808 482536987 371181319 390810838 977721825 415188174 861336412 812933547 789688785 800712562 250752216 858434097 834540260 174788992 652141832 786315899 878667903 655433707 772975245 181728125 659589057 383661415 768216531 786817578 514725296 576673952 645547023 91294596 295551746 83564616 294990711 134826072 257174324 303344968 820084337 624189946 438502740 656953079 629324877 963379513 690863341 372337452 927423966 755747691 100875870 604332494 674663513 519500365 759488511 94274300 512966888 863614640 803858481 420282255 742588184 562452995 94178111 517972840 723135688 997970143 169694931 713673280 133024916 932900077 34038772 253679798 320643291 400933039 180183499 73318706 951491060 325732476 460134031 826413046 166845883 87682066 48883560 628947329 896457225 331117822 789701209 992410034 565074991 215370660 686412015 251914744 582234709 34811211 253203220 248846527 780226750 957506411 555936326 196666380 452024529 529977648 657511316 413115367 369259041 990330024 746660125 185272718 899275927 740805997 709337010 379736969 881450802 979416488 888633549 770686272 463909612 552448292 757269666 623276254 261911931 342293869 943781274 294580076 670313482 273839555 866319079 264779071 464883392 647751585 465963577 789591011 931901344 400834748 502482736 440643703 903435618 241946493 382653866 143018831 651562144 727958155 260200922 421940328 329121465 758380972 874785622 95225269 76024816 85098525 848638178 888003698 231110236 285052582 593395124 27566829 847031423 821558333 269866477 27617542 671572394 729208606 428331792 3085951 558192083 933169358 849183372 757537258 154234762 959292797 294642964 340816748 68941573 485672843 397552200 402090755 891380210 489127389 992652080 977897913 394925580 325929803 348312182 229503929 801380054 868274937 756560829 480884304 626323425 219238875 642029496 996520476 896925043 540094849 235340141 117839553 304799599 862999067 811231469 254855248 890404598 467118108 987452659 636162075 221979832 280337115 155258483 631619954 989196266 562741765 417897983 796264916 848894354 174379320 925135243 716205946 791395470 1353952 826582252 192187378 473811191 635460414 118932150 626036789 380189748 666644050 501257522 429591982 701376870 419339734 49676099 118837294 896638213 316102362 441402896 45188006 665622111 612099681 893863880 169349046 889594210 430862510 672195454 645728770 846264538 913254494 354211200 441365484 720632895 356734882 253998797 20466499 136393326 472160052 189924769 380645289 802577423 904869554 438418712 830754979 112875278 160744410 295195084 26458024 839909765 148244428 652458980 392247831 174946665 909773871 488356717 605454206 312981534 831733862 686897797 715634758 352257507 484007237 168458390 287123586 534437606 975340409 2703269 538639857 641515662 160713106 120000364 377624619 437471106 363292458 956242777 66790263 621744870 736789137 825983301 62402887 19486771 91303497 23596527 813675880 110209491 210510087 404545173 10558047 953563713 669458604 765466204 352176970 922408451 880706112 45410759 85728432 330462257 379309857 146733211 796976541 439581551 517675858 165056623 755774856 118631479 368170845 427966415 206999695 498236586 120238350 530304726 437812627 136811890 70873012 220612459 605110342 896033586 394924467 654237909 464393338 234211223 297788586 476166926 681494435 587350119 569747614 798976587 663910848 497501593 468374798 617042155 425538117 241262819 277489835 466938411 136126894 894557024 269896461 29999081 634966774 520149386 877991301 823780161 594327783 770067930 230131487 6541991 760003733 555868021 846687280 318560201 61230395 527693151 998660185 881224890 212467324 653938861 451388013 815640213 64479877 735336803 267888615 914701139 856586002 164429659 29890043 326875085 399619330 38320449 337317636 156512294 849604555 659658786 441159415 264932821 880457215 637898518 869810834 51783550 351962780 319755199 101207889 544164441 294284027 236123984 745064915 11744832 846165515 195101950 971452608 184016654 159099352 351032245 333184568 474785980 120826397 379937438 49550540 607618525 25382809 896135161 260778976 230087835 587400992 25511286 91941157 41182724 778057897 238070770 872382214 246515962 637919236 458339864 955046302 395786813 500883841 64473664 491696109 76770588 772969679 300025691 243276900 200250190 467301282 962313371 229740403 263231670 941475460 110716696 634807053 76665801 435113856 398605613 378291248 402629980 858890650 247964083 692585019 120602778 403131749 800490538 867345966 355661405 159145192 642303027 786769428 757379224 173672047 233683456 858608881 230602694 296674789 483016761 529765638 873882962 493674902 416792098 417309725 736456197 223214183 526351191 665759107 34097587 600550221 762294458 944789572 123550859 448953315 81502571 217474544 794551048 895301804 211712313 582877831 199241368 993371880 938080161 632528468 305817431 941700712 388066415 764577554 656498970 614993699 581273244 148787070 693092830 908635685 497832944 465000675 525711718 958088926 860274181 726792696 699965147 461271414 635356086 834115733 124175362 570112428 201356127 499670093 216231463 717562674 912038901 171496021 846275282 882406150 620839508 575907922 705759148 896600399 259501142 581761884 449724552 506918233 841390044 578799811 54511210 329990118 577509316 628803730 820026365 422930364 219170695 873076547 501953713 545489647 683489478 980049873 220760051 725933330 911976505 765778993 634653454 577548315 111010678 574150984 456011470 943446996 622922197 201372004 252532566 362971592 197878300 210806442 153486806 671934274 524616164 196048639 831525284 821204975 190094731 807677090 896061328 995309517 533052982 398635282 614482421 435075198 976741447 911062549 6810298 70728092 451443541 511151664 869550241 332105950 883693125 921471016 139937537 975916563 337452470 346727997 195730177 575733324 53993644 191689198 880227824 787430352 966627750 234243656 798179309 395578341 296965483 754840704 443772537 281163941 791389528 873282590 47380641 751025755 469828007 487855733 446625446 974380847 851077457 690984518 322400098 338544921 596870230 514078033 946243994 110450689 907923339 172535736 497059174 146403398 284238125 163168214 14360712 416533031 554302993 992985733 433647305 270699939 248515890 877266561 104712383 848050775 326097596 7887068 321551988 539050130 117078939 115885591 173177904 137037549 397256817 580196650 188846711 835866736 360967849 532565039 804616778 77850435 98340288 900215445 75813648 20977728 125811468 379628333 442187824 691710118 95375399 667871529 487265025 531753208 832140960 957737356 625057643 353110968 803230292 737462201 841701240 996529251 694500465 708928071 671069387 308149351 908657876 112892619 590450688 575793914 262334499 593089920 579318840 434925024 602708424 847513414 599676854 413300940 749621676 989431496 972320944 146932415 4824746 341033405 176251749 21522139 556013414 720947984 166054377 5058261 111631481 727154527 436040122 189672578 988544855 505048878 450325176 440474373 467246920 689765127 409881490 515869383 885315368 428170777 579743762 417768589 679222473 281721671 650854498 465296699 432849730 704049612 347824532 843343110 119671810 667412039 721883960 578685374 975994361 946511822 600244040 89273546 110668557 346149313 598691438 373223572 320339872 769511107 79362388 502444831 338093400 59681240 38899768 42086596 35524712 959630069 681810677 708715108 423099490 103458711 593610824 433288964 925925266 28407921 101602381 392783004 32464587 566566208 683817846 223054469 796873032 325016995 209770492 322941537 301166442 532516486 883453490 601132251 68295151 123646442 995125650 533128558 7318268 341925537 19896038 673072015 825257044 312830000 458247889 900577273 908285355 932944682 220750052 421533091 183082532 60310667 274265265 64648233 13050552 926589578 326804851 307062835 951462358 130837702 22253780 469359211 585592787 62445305 700466647 272975451 391817820 752990144 971494492 472869076 707436145 993201596 823543250 887366820 875077944 217948224 882980910 884812237 845224504 454631497 22159077 856086784 3583886 815229598 456450247 821378792 25131762 932042759 284067818 692309593 569331651 421739649 742863327 345093111 911892694 713889953 797768180 221358796 21247552 310519365 220678167 348266608 533618269 626808197 879506963 757031035 157865002 66799920 564541943 185929249 54844962 516854029 968921530 962042053 330129576 348737784 362333521 855257668 332441135 149979441 290209127 178002203 316192393 501108892 995580542 503935348 44630549 955844805 758125826 53448514 259343113 399967857 180274237 98951002 107948691 885736870 254492851 35116769 604170797 511987274 168579536 843073870 723664450 771607759 905383105 786729202 221859784 997741682 273815605 421206148 586557969 384099202 544943150 294968738 297751368 61966753 14557333 83285280 293630590 550094940 943353067 700230509 453704789 546490010 931040438 669916257 330434913 943205152 39205012 445092341 267157030 650503596 473571648 584162905 359292488 596394791 324985666 338990111 803241461 905892618 39434729 903466772 425677478 461711058 775865055 105260012 481895205 388412601 404158076 985303889 12029766 547230960 113920199 478979067 994174386 102439236 175076721 452322863 620934192 787239577 837778674 483302726 136825729 600218333 151568544 694409942 744439864 131762137 353203667 656878912 303691989 550189186 750120908 513811719 967979547 841371212 651962589 119589455 782310173 986277336 527329181 817509462 792162564 516675407 556443952 341643465 91430453 751125044 598999124 560724495 572076723 372306076 801076938 739555377 664473972 270492858 952507764 271792938 481431161 297490892 353613191 461694506 196589580 846873988 751888557 905979072 378815886 778971311 599766745 558281291 271000387 8573311 418018943 475543435 125685543 357981329 948755859 315300629 545211367 695027173 479511826 858060758 126205218 696339961 733836999 315590446 727790611 329860520 571011141 866926486 531152757 712350759 320414042 869306760 834258054 714666045 104905720 271233093 752379684 716312118 574314435 25016054 763091361 772647094 178295079 935491842 884207252 265744080 575191162 945551882 960965598 512567141 207741357 767827740 356873222 280663429 742016221 986664002 542710183 295633153 781337369 829959697 777136254 178889407 477816583 336120162 287169213 165336064 161270128 469232143 45597773 431845728 356798815 772237762 386679272 585509442 259777663 8209901 464712464 600122584 273080774 471525187 64039020 867357810 877607861 316556083 365791744 215322089 889114778 378362677 88882244 442550675 977900499 529916143 24936571 455736834 604161399 552175705 615512495 823587030 96800573 74185196 88948144 655577807 488118167 60861462 650827545 958518881 834222929 581071173 517545627 164167431 535732924 393137877 100690841 898364146 297102261 463720609 595368090 870060466 505818487 813228818 656875049 743458533 378183065 952576278 263363450 740743804 665142290 907924258 379892766 412158377 168522784 116049417 652434706 285933734 374526667 302532369 742931151 901309918 101376590 542470634 799925006 241874310 607467231 633901429 493831516 921533155 661671594 179496656 511365400 496114295 693242588 280512918 190882878 642277919 507556497 216170294 606152296 434401488 386485427 492538907 604807903 625570446 906853126 772487025 334355727 416615380 170288469 724711155 376136331 533538161 846501869 26225642 556893144 664780780 177257440 980650651 153475114 385546402 10983927 233983533 639370578 15812863 736238394 751694423 587195337 600638606 163113617 251874454 664230658 251013056 464730279 765743568 459901578 792616920 61622245 307466006 650064756 92171986 662942419 177917496 23656972 966211770 169577356 305801572 842654638 536885560 319148882 796034434 164324095 16944249 543984759 728256921 392545169 262546034 538231589 804447283 431801930 665936137 738129865 75092824 342353440 669293884 42264055 919358783 282772952 308179287 282267121 876218433 61351155 630235719 389466116 666483517 711303747 902147332 38261090 252762745 71443766 310706302 404622335 140448434 476210243 158537463 762877456 799728314 955803293 192819915 999804826 354261615 901977768 682628097 694675816 863492717 663959986 805172671 427428892 790486138 945716787 756295993 652735813 114423664 805790847 745897439 555630714 117502028 683705081 111674899 586322973 518812456 473071983 293648187 167183903 752071421 285840828 404917533 986341237 241591582 547536570 303258732 798696838 53196438 98915669 837028099 487536939 800137553 152665573 482292292 743281219 684914751 342750746 332255311 932334725 658886589 166762002 505280616 674729575 71424584 227817029 462712618 734695239 589155373 878005307 10983721 536451546 517726625 984180476 957458960 887650329 738325143 587060387 459353747 350222893 25086999 639291096 907116330 365997446 571524617 501370484 148227561 935239434 485064649 372774663 738328719 726275419 990406166 976404654 528015944 147358575 263981690 793762565 577966775 906741211 403429838 112878598 700815653 125321973 515382994 77190172 113507312 471831652 185279930 95527743 12276088 940569467 2538464 854321752 53305509 385846782 885447544 290574285 501347191 712945410 159236207 988240285 612729119 729677403 12809552 932785174 747248853 949636377 109937762 576050198 853599999 572366886 26600944 918458853 562575159 161454813 626086967 821712442 226444430 328457273 443278590 93641232 701501126 905873416 392524914 567254577 126518289 64216074 575022035 708444928 299749276 308730221 653868432 527103137 518869966 405286930 259347172 499022838 296230988 167561559 525283860 758002427 856628907 265721048 885370787 202972786 468152842 564932221 828088945 655350293 477085837 965553714 783467966 325169514 160833734 533342400 212855532 699684225 854018764 935925712 602500547 573516955 706572199 560886839 473183181 600372181 357527479 428107034 473885932 988737421 145665253 772839657 543588984 416091672 334015989 350152075 495425483 675488368 747482643 418455798 676756690 935988271 7746789 577364169 165710764 234773913 79228900 348084773 593900881 932803306 225979521 222914044 842739115 502235572 743624923 518456411 604085658 519238003 518877535 382553470 905615056 932940175 610768507 507969451 56949675 448243297 145872527 412075601 567764515 290679064 461086632 795021251 663238260 769047953 613857294 520040291 236507757 267768242 371960822 655648306 5879651 185483034 622227316 523650454 627522990 747647155 971657758 372663984 942624845 933649770 454081303 616923539 19942832 447413510 277873956 564051559 142439722 328037483 805167441 783221732 638833526 447500759 501716789 738047956 271669101 58707124 506246801 108488671 456378421 345852713 407532270 544370898 266740716 157580624 256922318 536268378 420122662 493930012 327178226 279613642 638016290 479360736 546028737 437181944 394194443 217805571 701087347 128344600 344895534 871504679 189160331 300592618 91351275 211119167 465154922 981559097 844372530 260318624 749157586 671023262 7762438 647946714 323163184 844611431 379779079 715344709 370233259 483703515 922649653 856509641 973299155 983609771 487941137 280953388 970586625 655222158 927466722 990980741 998762625 271291284 969250997 819855499 531764144 551263246 202893019 668663797 131638699 277944376 199958574 973772092 886156301 437906052 804579187 349756876 10339020 376748197 229835344 107877865 309885887 505219386 488196183 837589205 726429792 739302157 42182985 265933316 366194651 269152425 151687911 714586335 420100504 827424781 88708046 838718982 620301996 656232782 323713166 470594558 254275594 910903441 750666504 351873096 825622217 51815982 430144171 545488301 345739963 749156408 494219752 521511429 290080319 579565303 387428770 857959334 343377780 389280398 809932635 333225174 872227910 727692370 861182179 767802908 279903655 579737254 77826627 388540429 602882275 912551394 497144433 978710099 462889514 757832197 675677077 135414313 748766132 209117247 511786414 882977958 481043162 792765549 706189588 158733802 797288255 450233119 209357086 573611845 309408012 719584325 427401397 319875317 943884726 987746299 589834614 543051450 457051551 850358525 953963447 538073977 208154564 833376412 852431788 275311671 683254373 828436570 739381 665561472 70842879 622024853 639533823 693421216 461872489 726345200 88999324 365988545 841340753 165071076 178563895 23793921 928623200 997385165 944514053 954208516 304005513 184767377 192773244 676898956 417707584 831638174 782252944 982650477 235678315 197592720 154471164 212823365 920309917 294221188 10966354 307409749 773258132 76117396 447451891 915543202 9170497 190951556 901314499 55501295 165281546 67030609 992213014 486917893 122180721 326838188 950021452 102597458 132360595 623872297 309408864 875434442 777806395 831126148 8788476 445787336 957846476 250132440 329265272 458431183 281535622 314903113 993051652 33794923 585633742 255038871 324911994 412867162 46748117 413445705 315154355 281140451 265550968 525140080 994262011 792154305 884466222 909382807 360561232 407707349 89445998 176137271 53306875 743806937 529504280 73487442 149146179 523934025 911537365 997728698 585395424 221287431 214611924 973906272 874306699 311270595 716914143 951230917 475634334 857096667 343726640 303483469 878195246 82533131 279622006 153330987 114815859 608580151 970072579 583896576 33791878 650066574 189678045 664017140 822290408 566704929 520409049 531039154 994300814 367800508 583139663 220562493 621887758 900627974 521340227 899896165 697904386 841005945 425410513 71737025 525930551 210233038 202365813 380793794 594730120 304295217 592797521 637625042 433144144 121687454 600573600 417485387 987849533 916090933 321573681 316126271 684596292 819511027 620504294 207421987 958609038 933422364 946207023 396939161 857028505 425323035 17492857 212080726 519821072 534045098 41121573 505857171 232200127 861411945 784354910 162354720 960890567 923693680 711952377 898088732 777849582 296991060 41652492 167583136 680447778 787599991 763537412 203737878 686623412 226838450 367778425 255775832 637897502 302988280 295654454 813867135 807118654 915747780 424384892 979215768 259593060 223294730 783436126 151248984 983882610 845736206 679130703 19471570 609038410 405479254 815098075 44172749 859293789 548898064 559629560 976315615 118830339 913197948 901606456 670122210 135752403 485407687 193361911 325388206 622141854 5422218 807123124 283090233 954145517 163809562 786076329 204866656 790863384 490959034 926244843 714400403 424227089 499114436 124396358 765501673 250137279 643761504 278907663 31743461 700846649 38687567 855439531 619330922 221320173 674577382 91217671 414227376 28530945 961352279 128302301 458772324 556457409 98793937 415227003 916891028 442422637 832166742 55770269 999322886 602749619 619845950 814843898 405889890 129441943 437012249 220075714 89113753 871442927 465307120 346507364 958239531 970995431 964385570 466211606 640531919 154607607 389094462 580191155 988068192 487452843 216237307 537015633 303837287 770254985 806763673 539736625 394892603 130128599 962529271 747897572 738705344 491428418 387148865 895232310 878713419 382041120 25123716 116938060 235942357 11419503 892560505 565186458 9656366 920922836 11919905 649264314 485316528 308968559 659993235 397652024 46480487 952039962 447857321 854316999 477365715 90843743 270194780 384709120 189334892 664560756 787178472 590925921 635846965 80651043 354286795 449205264 962448041 5911603 352269305 400212222 98395043 793045022 383885503 395215674 168857607 321984753 450811204 958474441 190813422 737072531 871326977 685372806 942450258 356062016 390026264 118759451 67407223 936058325 928846306 544443465 400973693 850150340 715590140 70682118 154221507 993409311 507881396 664880614 386511976 425430923 903111078 823289107 604551781 459252793 833307665 859169907 808171876 416452965 923715672 339469321 783506072 476117289 219486283 631114366 314365215 819281837 975849923 777553574 605571227 977015657 40607307 988926841 997100461 934241133 345964817 871602495 519540748 250482642 9671996 922919406 49001121 2946463 927919082 583452880 50408046 49258037 519530282 97167054 939842675 901443060 763243382 432148567 847916081 521611461 982425070 45842532 305802148 503438866 365634701 666641940 675685604 987552162 238343392 419763015 105489295 707184225 723561174 399704293 897460834 516352499 986304062 917373855 264546172 215884514 8811889 105576981 579664843 261697420 806032933 557331146 845076401 7578652 288402169 323271855 592514564 522134592 230520989 665701662 747158383 294172416 614332413 729019941 991773238 188000355 721120190 566675206 39404862 716740054 599033931 958203848 631479140 78259083 764126113 507947070 866080305 928189575 283011424 371514465 836084631 811035206 197349075 327164574 770019733 981262708 492599549 905725741 492294725 798089666 981276657 611201556 851031288 68631157 506890733 570500841 166025764 359574449 359422436 64264016 86417447 490427572 125220791 855692765 818238246 642284824 23010479 300257211 789290038 120228025 508980227 480058573 495536355 978989487 882562190 535332107 578470259 944173866 133016029 206076092 377607567 386510525 543677384 536126810 90534139 916609402 362229460 771400426 930782271 909929442 681875256 862856150 608340744 796592258 495308515 565692342 15582692 87773903 339371433 785494519 431384135 262006218 716842080 343760460 928127461 965451954 760453246 744267 175554741 942885825 560448064 563370486 785588924 214450818 529440656 572757325 779076911 557344617 333228543 96439271 570961025 674409493 170596344 703081674 367662963 66594776 650355633 989411355 829528965 215186838 773797310 513195570 708839908 742746405 264867431 266844936 790465408 950733214 898836597 605848861 703913579 121479786 129029462 526974946 523590690 103450801 42032628 938348246 26815764 228002458 63154512 920590516 23011726 252196915 157806843 110366063 568336290 361518044 585723208 817295136 413188038 78999882 524354581 201952198 667153700 488046268 478558161 830150543 28374220 972299596 864986638 520996404 906817423 905850186 94099588 281843877 748498948 395821146 11575908 378270098 272317938 36659716 681037107 521664844 120213376 198871429 594782448 562429232 488067658 146321728 587695767 158512700 883078801 796230634 173887152 344942973 493264946 892998620 7209312 563764147 750339246 340602224 160862768 186402951 885292674 309757002 392364089 510551144 637864245 478844059 116400137 337055249 653591410 604846432 652463258 530367451 200119087 448652593 732634675 666801511 752292471 423993593 269781524 10082562 181714126 473069263 758882205 773353819 761133295 79141504 795580798 89572102 98419170 311185792 729660746 263798775 306902165 388551070 563818862 959178124 95252897 900662457 509305437 796817705 908696618 300549745 694685032 852786384 519631858 460431730 500145151 60653249 553439151 341247277 990377004 779714041 252997558 831092221 119470415 835608472 938967860 682002281 39292675 559634899 844074826 185339239 597001962 407626042 420382158 340237739 586381542 90078032 534883642 709971081 995079277 982080430 33533878 142855338 511680627 46156566 530139021 271529843 556514802 228254587 822568521 154035005 780467912 462793438 346218990 644207397 497821453 75436648 597620157 725452543 549794172 343085771 387761673 237388784 14970175 121311511 311019379 151020265 187236839 700955730 277079945 600001917 793567293 14378661 723848047 809476772 918615650 436265667 832480091 323860015 74096965 136841340 252456368 456777121 25990862