94 100 511261669 859662978 336370074 515040863 937434654 258369983 354163362 194110033 980425562 851177542 180356332 187943194 990313803 225205583 160021993 177416699 367234706 923018239 477088335 465695183 581986385 866157414 925600252 451249636 132034286 396139868 683786784 167788566 981611785 816003089 886421953 326275277 533815339 463040516 316885636 997537359 787480194 837544290 964171775 565305029 432338228 496808071 644418839 221628212 46197316 226413419 318947524 233175030 238022333 673988236 869458313 393012355 133402158 429995018 419914511 966509290 716394354 46580540 951229948 792975675 219618928 453484736 272068430 68758967 97858864 654066611 970040248 13274699 498448718 102155164 598188248 496664413 54265501 122824172 284647004 881373352 456610018 176101394 987848467 966112197 619483098 770343033 598011657 735509417 436176878 102158081 535932898 492168569 754756555 629973448 226870884 607142468 836022737 46635958 66144047 376374208 189174230 360363022 959448748 989596334 100 869902432 510696696 635190660 759308388 851343680 191812126 999248313 401466830 172518565 341196033 153449811 495081229 449935701 410347314 210867106 693409401 786399067 697482718 161127537 389115404 199897598 480052125 976976868 870179215 141916216 690867578 255620152 222244870 344726865 835027558 959915518 77107780 675940960 21789213 743436894 524461350 884501269 873233766 635034636 659503328 842369309 196188738 351646541 184251060 523490493 661965972 355127564 426643249 205827204 833772669 172834574 553757277 453689056 446166987 282462524 943969700 678359366 492974373 237258057 742568412 586016884 18153962 789574247 950799032 781077996 271274336 261213359 466310427 787843279 245661735 933202057 2834254 504536521 610174698 963713867 884614676 751450165 169902323 739091031 733086652 787208627 771361080 81526010 241756159 412203811 399542401 445975945 202236963 754942688 11771276 812695923 350344242 191368749 633921781 657492052 118201624 389009764 390568723 401951092 832922530 100 386173799 931595784 361041983 393679999 988701790 284490682 169177577 299522975 431422963 275870566 833112732 709735040 184520603 295737986 590857715 979806605 41969849 184186824 319179621 831263640 24770742 828839984 118989575 109633804 851518084 470201531 385083183 77074350 264592824 317675073 555886006 189024067 550445337 380624226 608105081 495239145 990827355 290716769 97278558 149511619 812790931 439459478 109379029 543342933 613672759 189383826 558712102 122408173 822616276 650173407 68226466 125432570 584209079 953948442 7247897 703821948 606529390 385802337 998599582 122867664 925378287 542451044 973221281 718641577 643773517 419879605 27327679 633337429 500396343 918180620 577265340 554630860 511672338 967216573 445024896 591907551 2097343 84270228 361440449 903484011 197792262 253837615 682799545 938769029 119854048 64689360 742054353 887307532 714782012 204577110 40069025 327425597 590497420 784150155 842911177 803901877 22171052 522564138 601041527 105594638 100 813671316 486091028 687835599 377123342 193434265 32260416 13728032 642551889 317496428 2471881 598412834 882223966 885480183 244901823 995914049 752016304 94754049 422695663 865542514 517825780 576409050 598960803 799683701 674562579 803507783 413382330 240418250 66179543 388822135 335099107 849307095 846297622 723898978 49276812 809393999 913160169 464779931 415567441 942311879 948648735 866250623 788208281 327197232 428357919 597569145 998681938 625807532 316569602 490825323 320563468 841874574 972390184 443399463 51267279 582072020 632955649 546667947 194334913 653649435 318981280 180666477 663598958 374124200 368184589 693877466 646034437 913947053 368371471 793271951 942296939 391211137 463565791 318558308 543355747 500745245 290854110 942221224 155124711 797325194 972873704 721937344 118715552 556874903 232546207 654757850 156352553 199890418 302034841 110173895 900138434 481384061 33443606 718850689 18111672 214243189 479383885 534180745 928488232 254920982 687996804 100 179650397 36652400 361869489 108471654 670868175 466162459 782531200 596312018 171153044 2358926 13870175 147570999 655117585 749901176 334414107 431138945 432766707 591814934 855116066 789057740 28467195 605314716 392912074 623590564 247810067 98392746 231574633 363659380 762122827 450794005 101916100 756297727 839820305 544663365 781021185 436791394 989954030 387247220 447612875 187134687 725473943 42596870 656693561 449026603 357057309 602629595 880957053 250453684 956536337 148912620 692223649 752014220 494681826 125460009 408886986 371926128 905946261 777970482 974522783 253287475 787193929 599617699 743963457 446592182 109650954 709489861 526322728 751466649 268517386 170341949 78726936 765067449 368707471 299589405 978454542 242001053 82765728 117562276 841220070 102952612 978261802 459755452 428428311 432048043 992629846 986638968 233471581 852585888 148844316 391431770 979139824 428100906 216558886 405660001 380531115 722119129 323264329 703370975 598853734 676677745 100 262002195 554783765 392572194 348883988 272655234 202894593 730816256 620532482 307695003 651827711 938443004 129005287 571088803 811107453 311221156 987647593 691179640 944108918 477032312 494131102 855324743 169342323 853602525 709524296 684685880 756711000 131094047 104589320 198105422 103756394 976680749 783192104 42932707 119150069 248689491 185714866 491250765 817620327 744825001 392420220 452413923 267855807 84532877 459679315 253580123 651059562 555876215 18605518 128314783 878918479 132082087 5083832 652153940 926510447 565022343 447081523 798951441 482448873 499570632 126725099 374072478 22485708 886711054 7697579 342289713 281847459 928726339 12052565 193195547 511152986 793502389 642701744 965850580 686306968 96999093 455534836 647940842 972326718 812623536 314273331 703927601 711833945 217291634 68248668 798890008 905217745 711660213 930020378 83552544 697820649 25997798 428129059 557321778 970110946 42232931 341759729 679622085 784968276 250762987 611050299 100 933627143 746860252 744804598 150772412 736449828 934372355 526125617 236896712 236035881 301370608 6849647 929266438 474605897 697322972 396774876 923800276 461418060 315129054 923566625 783811245 851579045 77826949 582878299 201800473 845923186 596867362 9035759 979851508 172960904 356194791 955014799 380789260 454199685 755926638 544899211 698584714 860851344 971874338 395034277 164308839 501127387 555917705 795658438 69125696 685450296 908812230 942993339 330913897 884553346 986927451 385012021 660634641 375114468 122084283 601533491 246299461 777017673 513839930 736475384 654728317 998035241 43621673 387981157 613330251 311196793 440980022 215153103 150717059 15028103 469155747 738679111 429977206 828901764 760370188 798354728 657814841 862848738 951578740 711755960 786315169 7636395 128299759 524955401 578161254 103346089 546032880 918174411 95610892 637084168 153816829 659981980 795595444 839501080 493995514 386294310 817234200 386488890 544434997 277893512 524051197 100 839730148 743556236 871929226 996617687 652199908 345783546 333272426 666065612 426438063 479957449 402787045 826498304 787813630 380628761 159985282 713412737 548874979 901812227 195746459 224130164 965588515 653483738 764075426 667830939 766596156 461359030 921806795 849701087 976276025 634295455 813672152 853246193 312536648 175851146 186522186 614048916 250728311 761222465 91875568 187117091 813529250 847665765 244956110 1946610 81734781 623595786 369748961 281719338 360711514 200912455 190767701 455342537 45894291 971253407 930084618 86927456 694941862 105502891 799956210 116137542 591422340 279733803 926612478 332875883 213665211 684312657 79271642 76299101 345873282 732569246 318002568 835823520 22213704 342177945 508122644 317960943 951603668 800698792 593337538 725142700 190324203 735612017 165225292 759861043 833371612 697412624 755872590 677836603 347082407 944141271 590432869 160896781 952375434 831067210 713331086 970558672 278379555 341984617 167521917 353903702 100 166465035 512813750 383030386 904137400 2913798 137438087 442589642 98000133 887808464 614278114 364809959 594913829 343571347 221416280 322326984 872677384 222557885 661971290 24102860 297717628 996694845 142994857 485090106 190862718 689426344 557769594 662495266 698439708 293581317 663360148 367414764 699731893 938548118 523737408 126054223 213050991 988993279 402000459 837177980 279220922 797482218 214265854 938207034 192428795 206609853 219439221 243981808 755487254 928650561 844075946 125784175 548921076 319712946 330662863 826143751 321475145 33297942 339915531 407069728 367470067 789621326 889838509 538209715 849445888 711192711 426254637 312417942 276966288 903774765 552425454 272996419 295318056 943777805 656471174 891727136 274562542 339229851 618946178 610021294 489385738 49280676 179207942 663265304 543809775 286964999 544504220 424583771 908862821 832531157 352126772 210085953 54628731 352139432 347666415 440726024 317969498 784248919 150039416 593980139 718997421 100 392453136 71129371 191842272 422798906 613482336 403519881 500150532 653091092 27345463 566346976 188124648 960462462 118169237 193109759 527066023 785971126 320366117 872111304 293559509 464700052 517596862 769148497 848921826 304876504 599499528 918103517 155466263 950975355 541458656 465752952 674714854 532869451 636713709 396342704 799815314 866316932 613445489 896836706 705045489 319362907 805103145 236955093 524267215 415038949 853002792 639143212 182747678 884226128 942342943 578064009 534888493 816084003 146380245 890679729 854337107 57423977 643518261 855050892 270467798 722190481 708329624 302913271 434069179 550401718 117049985 156081100 619353407 255992177 663449632 7517955 854552426 981368429 772313973 556676826 857938623 31399002 197101000 931459444 470141901 853086829 707099267 678268334 886051329 298034872 372029739 538599687 669841434 973311163 8855405 471002554 705951451 385891388 172373465 113120196 360834259 932677744 655652040 158256217 247607326 328284966 100 31419052 743372218 773714048 860463817 354395749 64106947 195826087 667276683 10740584 604063382 483663969 502869467 394618725 780389536 683708014 492886156 512705500 5981172 283368856 950911246 344139315 968206287 16326250 791261478 818469390 602473329 531016412 530740765 306062487 372132997 450390225 688277235 336692432 794536534 883792020 223034297 870089612 949196589 227049021 846542564 941558407 879348690 307024023 109930097 683383081 20973729 273930590 10342023 259899489 460140605 300662841 887256539 736413366 113633578 761483121 352041891 631867372 610511820 383731122 304471047 530365453 492872811 946471936 305119274 121048952 179110191 202250503 455587483 210110995 826144045 518454991 140741115 398240411 749303014 232703317 477337898 237541191 294817613 811318453 207626974 252120073 211069949 741756765 441823766 945872628 146924227 879968824 224324177 476964584 567729706 731208338 720140807 549187034 747735722 200074438 950192948 369574475 583037432 620558492 282907207 100 199578531 948508887 307947808 543067360 406407148 378885141 142830033 905553494 697383939 922347479 105762896 599304749 752411300 672942489 308513997 25542549 801704957 91700173 243977566 538255698 571042362 778377104 559132078 734558339 481768159 353594777 876144071 54484714 775311216 455071158 906519617 87378221 269731048 91620806 426388312 12925956 10294652 305491791 777532795 215695818 966220979 905028877 48364512 846310835 331428999 226536524 675845901 519092818 414641130 472722497 193541832 834997986 26185886 883328928 815353579 705484363 133331167 840566791 742354463 392355214 888016459 216529998 377288540 991486671 587192703 899943812 460213957 684310569 480120467 533062829 330385046 71050986 882992361 704198306 609214696 64857886 522637030 847069502 588114885 733830505 801025882 677309022 482785299 337428014 427372959 202688620 522395073 207560948 66090488 615947886 551683824 488560403 101760589 17856523 915731729 302940517 918074284 525835564 29621448 650432009 100 20161027 155107488 888775214 474803470 964095553 643043523 646415704 535111211 166933866 16501080 712268392 353847405 645758692 880241907 982351755 494666450 277272558 124434789 256080194 101336830 580185927 777524284 842180871 62502715 263194152 736344752 397374671 239743047 606006112 423255932 637530726 130204055 711796733 133900123 215017825 468805324 739982994 390521969 147032174 494422658 456027414 328729041 667441388 662247322 346477577 531520280 653480822 596648684 708062279 31830307 11590667 373284842 363257127 543985484 825427861 243808202 977417865 111743682 380491873 649538314 674337308 182351555 957650770 586886553 865419950 430736127 804761482 611629816 100173529 329576965 355935888 100010873 851008633 294988462 339322007 605671607 226219275 55057954 975032043 426273948 59482247 579822993 797723258 81877923 621677100 214995020 867941046 816591240 5886793 847601425 679628775 676642542 865052758 293214090 698599349 330058461 292955683 119070147 666999462 668723690 100 407235397 583402696 589030736 241352030 568003117 854693202 943932448 663155499 895477986 926247831 506081060 357114110 507473915 172982487 904903352 237814653 220965652 986428843 664827794 135262011 8982576 72625454 868274039 797837734 99530193 617337304 214516424 116315157 789701776 472946964 600112453 939283908 746885390 759990279 507919312 328493253 748585174 835432266 368781292 207301318 638175277 820423060 193250123 107992644 243459348 806058291 128547153 100450843 924272280 217227154 440964606 13494077 818674979 656776143 523082053 861171749 300242945 952769806 977733266 168585078 836573825 139526718 181396765 761425060 33446426 546141536 213590730 94049801 3975574 799388323 919802001 858952608 983108759 935349331 233438439 559926994 711173880 106781600 460606833 832987655 23338803 71435652 318724640 132215990 377448809 285116486 513680592 210238685 102333595 841209416 995473570 934964242 279595157 862273800 635567123 173066981 841087830 7722942 41990992 563354025 100 464451973 57100178 976613903 802604475 919107010 213761007 606325989 701241939 509337625 836178811 703706839 520675806 707541104 565823724 517579850 725078007 676212550 330880060 508483053 618227630 662713996 554895777 612354321 587621789 33039695 551737611 113079503 909795281 691059119 903763416 238005758 523549637 102429517 426232139 114632022 100810969 623369709 590405771 5258603 259208547 88815024 111740806 745140743 842100354 411113837 172428162 641942665 548926578 216384981 894647438 562828881 306394203 697029930 52984275 213160847 996987382 10833936 157204772 758293243 571158997 720011275 874185003 477818425 709312898 612134631 5890423 787135388 847248893 574766225 252538404 393651719 34076630 130002906 550980219 895235457 334813894 941461626 217489693 820375193 438181054 854292681 538860694 205432903 382113011 531549610 866304929 566372432 675228591 951031840 11546280 598777063 989740842 695964531 435934458 416616682 606184262 292480184 969354460 951495843 16451012 100 79369636 662134303 347421335 69349956 433595114 305740321 874235316 234389349 796340689 938725749 696365062 654663128 77818832 834689458 664322032 259248586 480142919 245576135 296942768 247741828 565342583 496634548 246969536 600130765 61406586 832263154 267731868 741865327 741176363 750506456 129225309 485069024 993380131 712694152 966910665 931834393 53585928 675813866 253701190 50291298 121676908 427378648 652557171 516686839 749546589 811170763 316756991 157385063 126727973 464548562 88031940 247435021 388202871 682614277 181662709 944360629 438220418 446195510 401198317 328813505 319152816 697642870 237390160 366171830 35373695 170118852 877239680 715208635 42387123 596174011 166740721 998769036 115503883 398950499 948016616 454803610 135396244 919285731 613442039 112497596 559464275 575962411 521961156 844205562 15079088 404312760 535483860 289218068 930649428 40633168 161571042 613345570 90238322 770777673 719587676 138162258 737356142 977215372 532661317 643143432 100 376650029 57794197 515365164 734101619 147976506 851809908 12827683 528510719 689260498 77735649 198917613 354098329 515553807 282865070 365749482 476938546 691656232 352111014 692259001 88362625 606671035 29793419 135692837 270269531 388430013 255511393 26435931 361998072 779346362 228885883 757742658 667946666 35162562 914476413 7917386 339860298 546942423 641623477 838690735 924695577 854756112 894772090 251772369 289439262 386904070 643294532 915712855 667638274 785328463 165484293 143723444 256977509 640922341 539694979 164738324 597072736 523204573 213169391 925890662 297236424 519877202 220394522 417562207 617071519 408214292 764758548 356873713 866737279 673195624 417351414 391256493 598660291 250837202 8598011 597546933 860915889 101881539 425115901 680690710 125732550 707881055 970708310 597928384 405695118 589205191 273655030 852502752 108536928 84489610 106430055 562722418 220322062 923020073 438532348 702904767 418884758 545286768 476412826 979531781 168224764 100 337368674 450813002 613207715 359377219 620671293 920535811 502003937 379713222 98936554 660332938 546375053 776779283 320269374 230261954 302955637 955265319 607888946 23518765 749047947 909747874 978366227 541944308 88564521 407936996 523671902 877610036 563473788 967432243 582016044 234699134 288598240 92672138 772617536 717877103 972003497 360268888 240441899 408677531 474310050 424225306 639789220 938917893 286891700 56195689 459721751 120876200 146202143 65079582 140117964 967713131 503818279 595241768 613921252 94840396 620892285 334429071 893932252 986291121 878015550 694195832 154363040 371743876 463966160 329064810 913514033 360999752 862025182 405856540 538391945 763554818 766061745 716432905 187945596 749353027 191351130 188193156 543326345 43857073 354771415 590068105 127679390 1877477 716910944 423981969 613294463 275057742 803295507 825968437 284419111 976157994 671193386 327212193 36644937 817159951 747998819 432875991 252654299 969047435 979755892 459399755 100 730749700 729039920 738063754 143654964 994239914 376473783 53072455 955627322 663231469 243738739 337294767 134230510 688837580 508622100 666326933 29325340 20989123 348788619 759817827 198938897 657397503 404527633 791844364 694974114 662536132 168165669 715559763 853217532 281075717 851246471 969532877 123346313 291937084 543862622 679771287 853716614 804245748 625041778 302724427 868653325 554974347 632396048 74106706 590622414 913407561 256473342 534660227 748766762 599339359 585312431 229485735 818712662 29821851 918490603 855660442 161364033 172799581 423034061 530629353 656660009 382425727 728791057 323956243 734035058 821777850 943563506 848044140 959735899 872026304 911447799 778305123 915587483 15580543 675370373 790899219 822476901 147221900 159609907 938672634 356746112 597941547 469352953 566589346 663419582 308560082 723214553 944590603 700781066 990673231 415063808 366784754 237059526 678178853 842352272 49726503 98907335 65018907 432643082 830702416 298822109 100 692606330 253765704 899235241 872470659 931418774 831200108 643486927 904651612 530559553 822749015 160401554 924633732 579111872 485533669 234115440 281130669 361273210 82383544 716594943 453550886 861931935 332386536 255371245 542414722 877933719 43922809 639760815 381564084 951078905 229011469 589308884 965263716 62256118 183027962 44025451 240640115 488883875 929779332 805489022 28728326 945020187 713017475 102980431 191215091 328284097 269046796 972858695 873020578 265145276 476929829 449870501 864168351 438616351 538122470 592263628 755820043 47684732 834848654 155564533 250651340 587154594 242892110 111908227 910690812 67205996 790428535 622901122 338069248 36466713 245591382 325326952 248347381 739481208 493891399 1360358 416361785 891353920 505961288 565707166 261047080 207716235 366808435 926840869 81657459 231265112 377506150 630289214 421163249 190826194 762145488 113329431 645113820 955513172 271747003 567821354 266395662 197742616 551155743 726982970 284414019 100 353069813 434810143 521317267 265620915 235691517 398132647 671481419 831730948 636403929 417692122 301628647 617086829 309037489 194708929 590315811 563469536 827608081 610152019 394891637 572243184 565470935 626175313 566563419 804273640 55443882 646501754 51163184 31811818 288941062 423663937 132604336 23860114 755565393 563582698 172819515 549601960 18007563 214797659 308942288 25083846 748903293 231451939 221782035 392543308 143987215 724653783 710872364 743291356 153508034 142891239 656639599 453157458 982553092 678270726 145839768 625078844 882658436 159259388 999441858 408012057 983349498 347003308 900073270 64285433 581300393 855345074 354002058 570910658 848874800 15357056 482541704 827191699 335596556 847223536 256122312 805132229 162347180 637198550 946824204 570672455 2701827 298192985 749827605 294282753 798230686 974500189 100734859 321462444 955920100 138914587 841016943 632962235 697993010 500376971 345349956 999826660 314849936 821671641 866768136 444641821 100 244501001 9792950 773482490 510082305 542735524 338354820 1907252 254793156 406091854 890083260 989444806 507056673 318739755 989215196 623532849 79334957 851056449 536402337 641119625 18087354 164569951 328545120 205079940 33664119 458945362 703442517 767806623 790982869 895276509 601684010 142345632 878737895 819387249 697966524 411111360 193103642 206859801 454426736 220426028 515590303 875890027 538882806 358600112 632438418 255859633 614490143 185820685 966551745 444424898 571797529 833208824 999352475 695148282 50061754 311929937 899187485 448528645 668348360 120011867 465486489 414776682 305322787 244512679 897738879 925783430 483603940 895632486 438743270 741887534 988780349 270928816 361483088 329899350 864739642 124256510 251068190 653271406 678801423 321997251 246392837 729869324 731176229 193002572 854386639 406765039 862638294 630393540 756725872 568197694 130115336 726939116 858230580 223840165 967982817 979700301 917449567 261211935 592824679 467529849 919834666 100 575016717 708506237 479090756 121540151 425657576 428065126 707192545 966459082 385497432 740345788 378531470 792468601 963571559 837003110 672188316 542275577 43179290 88553419 640799075 199514070 961764074 435025805 233010825 321265411 107168797 147150572 877591282 890903725 917860655 515178640 260004557 238777886 428761813 449786183 362049217 342096820 836067198 228184400 990892025 677697846 613814821 89150195 244732141 959309041 240856031 843013030 688515598 350041 637759922 67668354 746234775 453137640 224965661 766439934 71963970 618270346 658697164 836796215 427974973 750947185 294635120 457011520 569893008 330579576 487966575 599798788 552202381 341352552 599301271 678449739 341850564 264751392 242760623 465059570 345891086 792492195 646460323 832491388 400613316 761561514 917999855 691914442 404023073 326974250 443522681 132624901 183473237 343815812 638276108 751307939 298389860 581964291 49393580 488584688 443743828 196926220 484397102 372849531 364691066 692975913 100 427267511 666514265 343172505 441295720 341706567 267363356 601080155 507746209 152514100 311361658 970736849 314334478 743753887 249917785 434206711 175259341 464208149 827911888 974361649 618671557 787828277 997957104 91902681 134556697 562556452 962313993 778275638 5443338 824914628 997697159 328318677 186664574 591480862 513785776 675810648 909629978 40982579 17181509 447384 426336627 173262279 416144017 205658613 567012169 972122974 139115414 986916623 763079605 565487796 608356725 736575811 503991056 181519802 256983917 605736857 751611775 858131575 763187924 894212693 685841314 679205131 877599235 292223557 432462300 749546643 54672300 13447611 767588264 230056147 269793986 635857092 262742357 536810635 758201540 199438773 281148736 70385061 215234919 832710689 470603910 741988676 473608428 459707029 719639151 833799352 279044692 394446820 836771601 339813348 796203939 795291987 928947574 880715559 591643110 151181686 886360769 298093867 53789696 197317141 578145846 100 415605536 728298046 924573749 518681167 979702184 559419964 739560039 656088695 39988415 337662708 624579552 851562110 48900412 526243522 521623981 342584969 448653859 244260130 923797098 52630098 334732862 878744429 133404386 26362419 312487038 994441796 244987634 986507889 256138334 391091397 48972832 526351079 791472614 543925226 681858551 330666424 805555324 521103292 79915529 733070843 360309876 410660180 944538781 362292029 719571561 453541699 766032029 32299400 101926258 139503927 758089752 137569284 286654161 638200069 798020 112606899 645208048 158730582 539170291 326866375 902894193 104331186 461938329 513487895 583550024 624838663 625354640 793659842 551495022 395674786 375263158 117398748 922643394 83560710 732713235 883954123 339753769 886525816 648430217 17461999 845385790 241060640 110773876 34952815 612753201 974141902 153250488 156046454 959102570 909746850 265706613 390444964 287585455 876826912 117970614 328615986 54621969 963114993 150519848 925137549 100 266523837 219303223 770634486 312675987 590068185 132781198 28539991 208926276 34997163 451072358 168224707 261687216 740080417 612703916 420067897 804163415 541166677 152961575 558171970 953121814 21651033 188369025 962235990 898567694 259304528 395722597 174580845 45276455 401008929 464725427 982991538 139485453 392137545 650512205 137536516 202564990 63706314 761327498 325741632 744222841 456727366 679340929 602892067 775713415 774954470 327442566 348077571 922865952 596497440 722245029 812108818 793326329 850521672 381111977 566822260 866621058 568916151 786734845 723680569 659802109 188197711 906730108 739343733 685585704 221363435 357524205 754637602 34032501 52711177 900418701 464309667 554230232 632170310 151008467 350594502 644326674 265588035 320760361 477527340 797803266 773440368 495252779 568588549 970558557 338444439 246358689 257483249 15485388 554618577 517537147 200068998 399062623 627170164 335511323 6677458 108875972 169719236 470516081 462348756 956788827 100 291128262 181001691 357119983 247418699 590416692 873840910 176411727 278895347 555119001 776915 447799579 156751269 955753726 984637210 456481344 364756154 830268374 173801144 242540025 379964704 611712610 868807411 289634935 109054436 58923461 285787463 939994637 916730137 858700270 849934018 935127183 87840917 719068614 117218157 857013165 222324138 797388525 624423212 561148263 407533610 412819975 938466267 775877734 60263736 788816083 750245504 526137759 3459400 209514166 433039670 522900894 272903562 849502789 10503748 195860412 803867662 797148290 568070847 393679086 459815492 723672920 558968327 631833583 372432545 538530714 185289540 577460609 374710461 96164167 556117446 134649812 128729739 916566009 497569130 802408794 170306013 559945627 162646366 477515762 837544041 489508736 798681490 555369459 177626266 300518526 288846695 402870447 241969273 853044203 721870738 227676284 290166129 928830699 193663616 697734342 830615052 455664504 71348647 278229741 485746842 100 64878978 313728128 176686425 595359455 329412206 161489265 21002565 797045691 800172477 79760948 724123476 647110564 600977315 989855666 929035487 84654164 750145782 249035463 293531597 507215218 831134119 426246235 311560057 408799160 773880445 116252969 871262148 822760268 810969726 276202283 991945459 473275637 393067691 820587787 705847938 712964482 536861723 622943404 546019885 245032850 363494235 545518262 147460441 969791997 921746408 938827909 529724808 697270278 181380322 48112975 935144332 799327819 746109391 812877039 355985367 848873669 300143411 80114775 17389052 782802077 997368111 740034231 403766778 374439482 743532993 491995271 129147263 640976744 524153346 418023043 291190997 637057441 621668006 492514991 528440237 420774961 617180099 403418425 897736604 884653122 791283046 337967054 67949264 618175879 554172256 401507092 596298985 474227978 965900461 243577434 617276859 779799442 312703636 328456374 363049633 461689498 442008891 941188738 867843541 768387229 100 469433919 361157326 81959343 411862586 466724347 255855378 589982854 200742063 654627926 412415447 911247538 253930747 545938073 938035992 395177307 293213765 257475970 875335831 710276453 418034841 710285404 505262243 158033383 775789058 996139526 249466440 753488858 220242067 490168491 798816549 320744652 177808419 959125983 859780639 983386481 458099790 99590314 385415917 207773727 659207159 446993792 374718942 954539078 917363999 210364995 217914666 793488570 686095810 284840451 292185831 180574423 728157882 778457817 218569981 156126142 219304308 515400766 644787798 58561291 4446326 92468977 677975543 414693448 853630392 508360093 599242531 298394925 128955253 751940004 410377233 298359073 83293469 131705970 618918134 809816922 332493708 884389159 790231700 151791468 388666019 290331573 630560605 911723486 908918049 202213092 880265009 974813192 650317019 513312816 605531729 456876632 252108564 26446079 760482706 30087023 827054466 165464938 137406952 686869194 478828950 100 703087722 226365176 997731314 426312228 319864260 643475112 336518479 960995308 4866560 475886114 220577625 670959342 650117808 575198280 676036049 992129990 268027570 827146774 607103548 207187949 225738204 798597172 28986904 658722173 877043516 208407110 131778088 3160729 390419975 258256675 899973685 360225529 517275948 190173667 718622510 33187744 500788013 425793264 446040985 570237427 399688134 61988553 493358733 466782914 857953380 77603701 275967562 724089028 256695827 27566691 813414307 89751574 802189985 358225510 651871988 307655619 493854422 101164096 821496940 23155564 270910638 401117424 913209718 171354355 827770490 458802302 240265953 695959150 322203500 554763773 393519034 864780015 233114790 857954400 339802077 250080879 950578424 829485941 155302015 747733573 594466532 296482499 245442989 59868265 558359974 795117038 331807379 455247051 943919881 269172722 715030281 412614741 18068495 714935569 766545597 324356866 588108034 900517172 759893580 44160222 100 691988243 683622917 680680235 535631386 434315031 906988880 597121623 214680976 892219071 717228798 259488286 623565019 715674702 374316517 787627332 877838112 845279686 378339355 486702714 384064158 466999383 413035021 362549045 705345242 608533739 496534379 130043259 531260420 473596575 597647732 914065402 697584711 636222710 581878511 188874218 881829731 484931597 386179836 889326417 740528959 798738642 697362897 107906642 356037762 956007514 548564067 243753516 266245071 239941109 177646150 217433000 104013146 347039559 97239432 945530410 329892495 8897509 628816903 517113560 724777493 165162331 229001605 161221489 809679473 645058438 28472398 102577406 599712534 391723505 68440490 302425566 159200955 537163521 261948264 981805385 245620092 281889376 306053952 16484004 386542610 727773971 127951284 850175438 509417802 792718843 629001070 296361787 575029376 373544095 409382861 724324418 678378463 722148038 938341532 176640301 431059054 320011188 962957201 980972353 92950187 100 736651800 567524493 492954874 330241719 91943135 258007531 625947925 215248201 96286916 579230005 292243916 375038657 331190690 854507219 54607995 623444076 223068531 822178058 66759239 100646489 495860146 259755701 187772414 761580751 112792569 341084019 970183236 464452150 632963295 431838801 160463015 815547294 359400434 46079620 143035957 68264901 292344012 422987 348435511 373669241 290172678 121444371 767741242 457554778 147954200 657274908 894072788 429359096 143986257 421515347 81314194 919775180 756112355 859822920 2768648 86622052 946154112 5266541 229708854 945136840 686320250 877166637 423994641 883753825 149958296 610780074 614419160 319457638 125112441 542889413 37524779 834387341 30269010 66717731 619722675 433659665 906739613 197012556 718281497 344735646 807948102 954168642 911395794 761305740 602771424 435337998 343023582 162883272 370069744 44356663 88070576 876647170 488035141 910011366 909041809 913579178 944846538 978454055 524790288 506069372 100 420400805 974001053 963400294 997859141 599512594 738488990 271776100 3907429 737007037 124003762 637234820 855243992 703789677 75046145 972662319 265025855 700740532 202514318 254543927 483716584 191078456 18161952 224893339 599598581 81051400 658587276 35607081 248196953 736042523 66326681 32169617 289270058 738053272 198217769 741938110 219653437 910415339 312363287 843760523 526588284 544066838 246671331 258297403 423960534 159438281 50962251 252105997 1025466 896900656 720270021 610633772 559846868 170580814 510224474 961327397 718344518 941372096 255905458 303474144 981935834 658233794 653031448 726257931 325014218 624956361 504576308 479790031 804371123 353576268 895671176 597486202 531465426 445600742 682897674 621037975 282531399 638407936 899053372 365302671 286567059 361958906 889872220 139245544 192293606 582059789 756138955 369269526 72407907 482936776 837473893 584294180 70184761 543014827 137107956 967183540 677586425 759898232 754618228 241806510 102824079 100 557624252 421480022 161257955 759278883 631123316 802530166 182252345 937977753 274435452 940984836 690664412 934522511 202234397 790933512 368936889 329117082 996328646 586808251 74726897 60818504 738227080 472266018 599782903 742150231 515704313 109789224 249018726 956466820 785691536 747793802 514803327 77950701 148836007 654068594 975482434 899693165 198108299 850559461 869435047 341731405 237469176 296091226 90419518 798178768 286845963 660867978 252821507 863685288 210451226 534888442 639801532 457001137 811500529 497172918 833641330 926993208 334930818 482955988 444523694 341158910 885738976 150921878 573818417 371634491 544875471 631411409 785206757 534081476 201637698 520003230 506797787 395601234 913634803 109476403 54315853 938989990 123621251 616623881 33037172 376255630 222400977 468665915 951112889 7749184 677991204 564420086 440658452 397633565 397165583 472398931 160234441 737314626 218460988 644932940 808151528 539027733 811469323 810539754 407248068 499652502 100 58587381 185663552 888061561 691382782 654459681 294202475 563049242 137086062 599318658 87320703 662498724 508960237 819828871 70597026 779259129 981220598 236832589 398964095 411362299 984900111 26452917 481793672 65873509 695223126 948203479 305353128 840180508 110311938 90869424 938522906 425444131 10007519 187385020 183242748 388991880 892482141 500479609 153176134 794253611 430871940 416696326 94181709 100560038 154945927 321843547 882431492 267673212 291539816 618430039 58844221 356314967 314850127 53962466 785018298 770826992 112691463 272464942 675687522 511904868 849390244 119380201 274606482 346424952 411619602 495898816 987112409 27805381 512335133 474199340 284648133 237313428 189254285 512840520 509761370 846062798 265586111 232852340 645980777 829379212 760691568 195612103 702323367 757876750 618897434 871625951 977572074 573142628 580028155 257648007 309034965 780036282 923097552 416664785 83458527 781637105 250877599 717529660 843333422 977314123 253262192 100 161742412 35766070 45863686 141582424 817335820 337796979 565355566 913963708 790829655 482227985 969962254 886009185 148143377 443691767 963868356 334370382 295642451 799823975 362099270 690364109 76102385 986499108 51560244 897372395 536869286 42785448 324397285 762356825 293047839 818506530 949417775 446131811 690533082 935011316 714633411 940933685 83841815 122548439 658910722 394521832 680271806 583543363 557291483 424428297 526090324 409431926 322895867 390433652 938290388 400043614 673832479 956298689 262283465 510084195 981557661 65983499 944583008 989043271 348385651 6719359 384878353 685227014 670554184 37727346 381187845 543951124 922101038 487901854 489707988 598443625 909102673 123064491 751675173 996010832 483256685 585728906 873249493 153239676 882452885 940951344 802505289 222573506 130519879 856801562 616632967 414814697 462435443 405605200 169591352 955417577 120656453 642125215 537162640 271244325 518214387 934227768 677958663 552477207 529927753 522484363 100 850215765 288045688 774152020 24904955 550656544 916257760 267756932 169225004 952995678 936093387 683355360 661483029 674002181 850531843 808316406 354333867 79807663 974775178 72089336 673403585 172012885 726641179 775196567 242543347 712332890 945612855 119251643 765630319 675698225 535165642 978532166 864121422 118496647 471273725 608027489 217974874 86462351 364370885 800437654 588030943 845794575 154394613 624750152 100361217 119059614 504768074 862596750 593508356 498719246 847688406 220589357 608720653 804146805 913615306 416526556 992678920 905617435 687511301 833494205 166985482 145314736 169291754 38072164 177320487 219462201 715474167 134984720 961806991 104555446 325012922 373789714 200784817 265112667 898786535 888218659 320625223 644878937 996003391 797028106 996063742 561736009 322980648 233222631 161274504 70939979 297614095 874818812 656609699 629156073 290583692 953839257 982244493 320624134 158196104 458954973 600033682 478383599 652542728 718611905 56179882 100 739328633 218478233 637018224 810246577 778330625 840984387 941917470 152780407 136508354 903816864 74005981 538441117 678202403 705626689 652134240 898891577 526996601 205177163 96737937 738755626 595115044 112268303 732902141 235792393 409401587 286977722 705406165 98035394 672503388 989888527 463060889 900785207 714354400 519564495 166543146 46362787 686822752 520504523 999951162 448371878 972222154 205133632 946221952 353892230 735253104 676635595 252608256 810653886 751390414 539614387 697925528 399066550 316864996 202729903 338318763 445676626 927374282 150971341 237905421 924108207 517495823 758548175 77969152 458152554 689749005 322422355 643950199 754870986 457177454 143232087 933404789 695031132 393685166 132948584 641179570 601141165 139909381 667911741 363769585 799978447 36821219 622781781 94645215 700902847 46452991 35188767 900220586 830222473 387427652 861018434 990342778 759234943 54818368 573967597 668507790 82004561 442451335 213767768 833430547 371722589 100 353025833 978968744 880632597 294482264 167178170 343510582 779420470 442796393 160184455 503004289 612229989 312166728 6927918 85982330 851539176 956012513 631198296 280765374 580765645 769355954 266640250 263845912 290900691 113511560 856418314 837923874 109406050 808830600 101802001 719988189 387957807 468182524 859849917 746665890 210186399 259702918 746888517 162153711 32879589 63033255 591202406 182612309 466461254 974610073 48715856 563047957 574301092 895401388 323537362 331162068 446588642 626316452 660780619 145044228 8722380 360373308 659236546 370013746 163780393 298602995 620212696 838996137 556478369 12669603 911324053 937597999 948482043 46018753 915523933 616384213 975678434 959121254 23421935 368069494 832336374 124866998 176673374 417040223 415545849 961691506 556452326 345084658 902792523 693257553 561406899 671582261 288529729 297953187 507995556 83265868 761479159 459392420 516206542 555987591 71185663 805163719 752874194 708235073 597854207 743710933 100 115833467 754839822 772126612 276762439 580215922 962748615 89802975 16140111 672175603 623414315 140451686 887456397 794084972 552532751 413239064 287102371 163156894 198517016 241983468 85942937 878496860 118237596 555640338 588144683 414946055 235191849 157104712 70272983 448119529 513801841 63009386 12975718 751666020 260344089 252427179 681818378 412671848 98581957 449103455 38729355 998829929 667800374 183547227 845778223 555052240 271253952 870681620 638115694 205826651 576356740 753223979 692171652 416737841 58969887 12749930 942945285 215516062 42667054 960636560 797543403 92174273 929669657 891682840 999625374 89539530 922755954 649689471 919442470 190698658 641766575 646219644 765386912 17896010 537189191 689348562 30767197 338137399 80661452 38370476 548448580 118629015 394082752 11245541 41840497 731939486 707594957 1686955 193686860 694649494 654332841 727899412 464306458 80751380 145445310 296536127 212573489 40523290 759562083 889334572 696960644 100 808415296 685361335 599181149 85818373 517289415 266503539 783590314 337387175 784790364 445112034 700346187 638510671 82154522 150075704 269795854 203410508 433420858 686552895 142073953 642425011 237624939 414976507 370448282 89405378 841265378 527884028 174462598 202166744 125356267 718491192 740188077 761804396 501451640 457301823 16576809 495806359 875612109 372798807 217964839 235413301 993971846 225238551 590866754 853399613 230758757 604991723 262983354 971537877 890592973 964865862 350694818 746967733 747077234 948999823 791464056 154200441 483538191 272404526 230075215 298233373 420613139 143496616 901952995 645770441 929876281 842382340 147759962 636865482 882968202 613924171 122572591 224783117 185397873 123316942 686552532 144430577 936809829 373870740 390673701 822740104 320162291 194597411 402670606 385892258 943286 838439778 359241915 52842285 702679727 933725663 234107219 581138171 824006509 835950353 163046696 70333279 958894314 943904950 902624362 616653630 100 37242111 896367644 174009315 980386519 612984389 707717396 265704606 315925481 770550684 169321456 38530752 896610149 193751214 490059235 618841275 42565676 483370939 109947843 653464755 674983294 384739793 715602184 495255788 233622398 713637356 137036710 499361932 147741268 114234784 738122284 849013300 862267304 996066371 881499831 223357688 250553923 991791934 560557311 295292203 888987215 776893492 199429712 703566793 996980312 900655492 796209916 273088369 495910260 140530388 643766160 864295114 801843044 993738614 473519880 643203402 813464275 136235814 247297405 889081199 659125537 632307588 167747529 719325956 817964339 30081726 20093499 516739966 853550915 533444258 106075316 702355084 505936855 375886388 125851797 450411166 320043985 354833397 734469411 991260669 99400862 76614558 163972770 732314827 851200503 47723463 409292764 937503928 512797760 335577132 108447761 777230370 918068098 797774746 212854870 926081032 633771271 995074717 574960387 820312771 928343550 100 275834249 864676456 993616141 288837677 588480615 237618824 452826838 637895047 611574251 621268858 347976472 738916625 786024709 412028507 859990036 985053213 933018580 578012899 93161080 902459895 585951349 439237855 52193663 689361052 282742126 340941920 308133222 940080495 171773589 996897436 204310327 196376495 138553017 253755194 245648344 714518199 762746704 58444227 352202788 120921125 932224394 384190387 540686066 341247505 471018834 872353755 204316161 71865795 984337137 654737301 405171088 453741768 359509127 817269666 93271916 132288093 752748415 378348459 720726043 64121687 979192668 885029055 166617584 415605512 518616776 702687359 383624251 143720817 802933660 490261321 682392066 452123813 990162458 899871401 820694627 566958403 386818802 572798133 394965435 322255073 778230807 399795195 105328441 99177928 740358430 429056623 526959348 656464496 589713932 834677922 670055116 919831035 299439751 351881920 188802617 632097980 194146892 769002538 746467531 270069271 100 319006655 829962809 537601668 848517274 368502120 192205177 323931944 710255127 998510689 556878600 667545338 345669147 252738745 907378112 892333973 564925047 887939399 501942923 985948746 619740305 485136824 172033767 36307923 724372685 46822256 562155992 542548671 667650909 77845046 575686558 636547661 866404114 150892699 9073042 365573587 927427734 914453543 502900330 339804645 623406253 466173304 574417253 542722159 163052019 483512317 969631813 944308994 891951890 404473925 655109567 168766744 625391846 700688483 527961689 267843562 460208295 236403248 923243719 781137446 803902183 665845059 772347597 8415759 722083966 787359997 977403579 568981363 483579345 599045950 8070117 551741132 666225463 419470079 514265397 591475972 326939621 959613210 83939697 513597839 783583434 662527280 194765675 657679968 237979149 364491799 703036168 940403061 915390557 154148700 674409839 780574338 256996204 523272326 100890674 906472643 361434354 990478290 126878901 581433538 194557115 100 444247429 770806054 24143148 218758058 231910057 227345518 378767651 117424203 244816345 645232551 300346813 136452931 396089331 168418158 53121075 159719986 407643896 213058779 771604673 142423355 245735328 850756573 230126279 946442562 582507345 287547034 839759209 54655357 266674857 146016877 836361240 299754871 109261720 23344675 79657337 890049792 329039293 4194686 168540455 868105089 952192214 540808716 507675230 365599089 877538057 239708095 274602911 629332898 774615064 429564023 554378411 80138050 800075385 326219032 713524502 831046546 753027946 189566296 45128276 347307245 211189276 772566823 972182056 520895389 899470876 386868530 209745023 27456064 285103777 780217047 150167954 342049860 909672124 916184558 635027838 991828098 504032607 334732289 845391326 731085027 180875751 298042292 343145798 599367402 494349349 752239758 971988852 626060692 132359086 777644269 815422405 698614190 837819435 447797956 243777815 764012190 971544530 929559862 831134881 29847949 100 42521662 732501246 721640753 799618656 1940030 195138290 142588067 251615064 633139203 126874837 786351128 828973340 90004560 886798926 247758749 164144040 265911297 93335893 388669825 452523061 783186752 361332954 327197915 893472591 881593370 387754932 292068873 827894105 736742941 586543901 884593877 927646465 927131582 782340807 231935686 146714682 726932412 884442448 455473613 594650388 90971599 589098880 237431104 258973997 610316606 309515700 312705105 545005027 749293874 220347790 945501059 962768122 212111403 437701378 36223343 428486377 103991961 213585682 2200656 509841964 375993607 504524985 73304800 868963169 362167500 341736350 77549109 565062400 337848227 487530280 4717852 172964541 295141998 310235169 499802351 814052405 7502082 865533414 183629867 710232131 578115479 202158581 210629432 785824147 392405319 640844326 342009684 608373458 872542952 669469846 46812202 349056392 657819646 824864802 234550922 562042370 873582787 979908059 774494439 895225749 100 374269373 596172077 85193740 313387121 43277397 714114618 350483381 907138298 500907368 58296865 443049432 529671490 504028440 989363651 396144209 962998164 743852256 811892521 555940963 94269757 506574950 719612049 344459590 633151106 893184364 219301907 418979721 52645455 502933297 682258963 340683898 157453871 675359089 737414942 599178809 956909083 629226297 310755648 380348744 682440140 351129415 956523604 919510903 856856621 864096085 130483883 973277936 612167353 705171776 297688631 928087731 103503840 1426004 433117772 811320001 761062229 589462449 791752850 406741950 197707467 498579681 669228582 109567530 930368579 842992168 545310468 405789185 606856703 241064964 760614197 448879614 876886008 403234765 287401798 622214906 767666503 120519378 382359280 33442027 954064624 988262203 710649485 338684645 707205049 419048591 369371759 658646191 262188094 354402831 396210844 352736979 98585690 566384208 231089605 238300138 642603173 516653924 127725722 635240654 489650001 100 784840439 50052037 680935806 169065754 64582821 507160246 447343315 111752430 37211035 256629565 903061149 264164174 155391855 304307880 998245085 130044686 894163045 743127073 964897746 144365455 253450198 748144955 44971415 918646299 160619350 829803618 708919110 2676870 169329322 386391094 22305971 587004777 285403487 76925351 372613936 339222377 911069672 295881683 944653435 770471263 628546662 553079393 423667890 579807459 136497336 597780015 810435489 568544617 5264948 312329280 395641298 197219787 1482310 259867748 85446084 229690054 828743650 504468362 715160744 501525974 367324789 867254286 493720503 634833387 446769016 618123848 868744710 197475425 619017616 617295954 747965408 158923486 858532876 949211793 539870135 938773944 847600552 922836119 775482299 847133250 567622489 848382281 300878090 165756598 548825137 837070564 193734724 18071517 104927207 345921808 857613773 910029598 906802711 53623562 511853276 235022613 542393620 721702688 943748675 935292745 100 473841870 147478966 111835410 736541067 138251392 370900591 817624459 885986677 661827793 914330883 119079094 770024042 466493473 895453128 389392758 203066982 637823113 699259538 172904052 472950768 309456633 141294673 232467538 921186506 226660502 767617777 27184236 575530398 301434118 175280397 938311494 622582413 859954412 803027719 665964568 596709456 460853873 725697476 903157479 568736111 717854530 15272790 256599517 49910801 301546699 351916370 92065760 981573013 191221784 419392527 307633658 465188151 736415080 679002160 133215219 917812812 779692592 918201972 234094186 555787024 193326585 679460296 487112471 743858451 138459565 449624008 691567092 666544851 477355415 852876126 105139089 950798282 798220800 720851452 906481714 465194756 572049666 97749958 803624453 536717109 593484520 76401222 452191668 528150852 480886069 678416504 67942252 843613590 844626365 97776242 413815102 627344304 706492385 770297487 351702292 518268563 373322024 646680814 667669122 328975328 100 374234182 627058499 840555721 635136412 149117412 163469562 392415763 884722114 563438676 721423027 547049101 526759594 55909266 237012774 942506814 860169235 319079103 389883724 356229973 599912420 377499275 328068872 559467606 853224955 665751765 572554613 368625314 158543283 297822393 691746564 610362683 636005136 816871231 44427408 829580081 161469480 635921886 48431527 601397584 186675075 595509591 380648406 616448225 330450584 519722085 666743223 540049439 511745180 500897397 839389006 888282542 326089929 467017754 904750868 662134419 571886363 941117344 556759109 829193425 335043834 707807403 478154261 25627500 766060771 953498991 5827596 420100365 30403476 341224458 920841120 228556228 874844109 189827658 687142693 442832559 644653967 890578959 590339962 469166772 193429912 595435256 993389689 431213905 115404404 526949628 378852688 260763379 324990532 542103607 587162634 471944487 734829528 544687977 877096236 192699007 252108446 426101981 977986557 804000917 674355959 100 703666035 740188628 573755900 21638260 384857590 413219705 584102633 633187808 510974508 857301121 688151891 396792541 243066344 784650084 661325726 652287501 642950289 211820075 679831062 959363647 734940134 724466843 924901210 76419430 844115967 567609614 997733466 624835884 553932575 807549529 250075099 691217030 735860304 887555610 458166539 783454272 694349275 823683894 237892356 365266779 123995668 243785544 358415884 326530607 232843741 719154190 89008440 994391733 817725642 665062313 704253543 420171905 109257461 704278863 840557021 26676240 635938996 568497837 300078831 187960277 437994841 930130463 142258742 383684543 845597811 372188863 952263954 145525256 306182184 199915117 132693952 521473487 66149116 381562666 531443710 199356238 717166444 785956426 889446800 732343210 929400104 180417915 683521186 843067844 609753008 344223247 836207034 310932525 47174901 82917312 931505903 349429707 65738901 273427417 792685407 599630627 877858055 372115170 938897604 555315170 100 783950006 755430482 473910186 193758621 975302090 706005584 423510615 510719548 768452256 884685885 301352209 215001178 777392198 437984682 781359458 708674213 260072145 287036522 710101783 686159787 444380962 561883439 751050734 13362550 246027628 379324162 312162200 238706813 657208545 472123456 15035910 709104851 962736857 689852137 113353652 861101437 208022196 394202000 862918887 940283801 851397849 414198534 356536667 917326849 596069744 744059477 222423565 484907060 946622326 162935001 87229300 411902902 917006967 489971122 371464584 866892710 865355488 311304079 461736625 640438844 656569932 62838103 486744435 547428095 866151825 854015690 128213894 391652173 479777557 21481168 208126763 112552129 150963126 934461642 560779072 367416027 985772311 25410999 11962343 711961903 47046684 688278630 936412573 32652499 727747147 782162972 350170850 62032824 61481529 612124973 744265993 46004641 521778662 818609056 589073068 767584039 591292785 740179224 43617369 599322234 100 693085128 883116813 758697379 759272237 219860194 366766161 41947457 547861179 20684045 519798977 65505401 746549874 919737270 472826732 372491347 522966242 849307973 408958936 221023640 767462243 608942093 205955097 130969814 892943872 755462739 242097904 358220381 404501005 911174965 420221989 797512281 36909982 281482229 796480821 498606027 465406633 99899987 475082382 589635225 622636905 560478139 504240146 422139897 483513529 28871723 891745256 439072645 905161840 593872546 953929168 135459411 462416675 585505805 243598260 640695636 545373068 45610088 884373142 311299056 241116984 565814413 544381253 42241966 615895616 86134719 958038487 902994474 430884258 811106988 394767877 989919149 356749984 343833690 504822600 491109169 617027994 51085097 748634105 183400346 633179323 221735588 142084724 556754207 118264155 469116677 108760509 707189554 897512333 108969428 550622431 55366507 813039234 174756441 539462095 328465803 998000816 171076104 20589304 756207773 555065590 100 576615827 932441958 955281945 241953216 837845862 808082190 453073048 496915993 183409828 974506452 90669186 532307856 669995972 197595963 766657856 630707157 556192917 411886526 681133582 629933117 929934620 776032918 578284187 899801272 982973342 174385405 799887623 920427913 368621137 960240933 211349849 660770092 287326163 765984722 553620803 363653584 129715772 190498251 694139004 176229769 467661009 602051763 354618043 965570597 674856027 854745917 405377239 44790145 560346087 277405168 377119964 248591840 122344998 203521178 180937237 976687650 751105226 981372760 51671128 59242895 300864017 40322053 455439167 777550428 94831131 928191106 431311237 438055600 215446614 333867732 178226351 424536784 707694809 436741575 905708006 964703510 989332899 699769307 248869578 657384579 202673660 160371853 700272759 684361742 125005429 526388303 472689503 939973533 479486094 357236415 991736056 420285644 260408110 568817657 267800246 430035649 82834839 479965988 926268129 294064348 100 134069507 57279020 657458082 334882775 469718835 838179346 63040560 306961643 338521559 561348750 63660614 23181333 891793875 726514254 87970967 796079913 632840596 954835730 223487363 760983745 299076627 348674615 509927301 915301540 318997297 730839900 861472253 754747155 223259632 345571249 659153930 857095967 345245938 847241458 589976924 678644013 211343213 597662741 255340100 950064086 852547895 118964493 304870177 740670708 163755846 243354199 429990039 735882091 778406671 11773586 840427041 504481742 353285084 730105515 731652371 397198698 805341113 585911366 238140293 333998923 337447379 814470793 312029583 178061472 482704059 136006233 854610595 887864896 471535189 936180164 997719854 157386312 714228220 14947829 491189165 955030896 620853498 441931304 118081877 474879780 415748214 163189344 290475100 736548078 595675467 199060385 379898799 429032848 377854505 579403552 945893927 345449097 878567816 493770779 519980557 15838623 656986505 497170347 816088723 737562584 100 559826827 421574746 640846120 386500245 215985287 486918695 757340773 402318498 200901686 848544559 579678499 27153404 26988154 637349957 313552285 191388297 867567690 745710082 905539612 955466531 337170155 673147649 424277627 362793530 522850119 66892851 92283071 427181459 188099601 7951147 744000837 839604002 863129407 111441710 15922854 612101070 265078180 422347760 213563199 66437857 665975310 191901797 288095496 782673472 409656172 754897618 570232971 27361183 565701561 349891382 682418832 990947139 15152675 559190314 869771791 416358438 491358154 682175660 160670075 83981984 126708049 928903945 114200355 953227805 750433141 983438212 427522014 212651977 547708069 18675250 672357621 407413677 186575803 560306400 276871640 180383892 595380206 352425100 806984311 162190298 236455260 325427991 109791553 369932833 320467770 66079390 103475221 371383197 819590562 382118237 952751023 476011516 47099273 204859033 852464277 229264043 201621937 391963609 180811542 10517205 100 663641285 322854240 368705804 490281486 684200707 822227673 490080515 283885330 243077347 577994154 789294876 125657761 758012597 394059860 105968549 426321693 139198955 166892064 314409544 516586485 142317993 440022549 748370005 100861041 563849988 224269262 11780845 574270775 694497785 294756641 650301000 787303438 213377451 260005812 247184629 790470914 669627787 28147443 580203578 785974578 876362108 708585361 222945579 410865806 909450213 63099220 732609857 277969055 350457182 902063679 168316751 197554126 979481683 537153253 871868916 978457555 212368524 730184559 938708920 902991685 32902023 158739271 469492797 840066862 138699912 867190227 611480641 893694823 614002890 737905570 22675690 392730124 309326255 155637663 669378915 328644063 518497171 105510029 636376462 739109728 495483656 275909357 993269096 493939071 200261529 122813171 809750499 535463736 483730653 627576917 501012912 403674809 970138048 131984453 570612496 933821330 863668785 252396047 496851924 652626572 100 245806788 388578008 999981488 305114342 33373677 499093177 767565717 778738174 314770126 253455945 929097123 321288071 494870042 776405741 365228553 508549609 33945450 21665028 37615212 802396634 657627009 638305631 395285739 474780319 877567851 70747390 485461895 899703552 575641462 229998438 337572214 478705634 997538072 376231957 943125190 896033232 54831411 270792488 838571461 372108269 224995192 118928549 297149013 189146504 688411124 175382367 953849712 216191912 578436136 861298855 81266335 323142083 226691139 325700835 541555346 439175351 276324515 619936475 954430744 65322633 431511055 753300058 115588393 30730327 468203237 441177203 703619816 25655365 57021437 378520995 300695489 543059418 853420850 31107614 710954331 731498964 99101283 528536656 704222028 384518001 176725249 213342069 204811029 271385674 685763253 922084218 511022786 198096053 723996144 703916915 457771766 515485315 481117523 70325124 974177017 15834772 679720595 239109037 283246954 822605661 100 849391154 709512223 789544179 648768929 724102716 919032332 286589064 976649901 480500740 570656926 476192777 432671080 659179210 427068874 79389958 474700839 194145472 46409145 426338781 997005515 594472848 39754403 440789043 835124413 379367229 961652776 529517096 858971617 878698750 491615440 979927020 782512986 197320581 646898595 162420214 195093866 867055969 203763078 850231801 361381419 396689291 415762110 941416619 341080959 956614428 323634574 692534252 705005504 362298047 168979220 212860109 270669027 585868316 846040146 877064695 551033725 837769516 235797727 98049844 959063562 336449527 674737347 46850195 371639622 863978630 241342586 986295813 149232066 904650636 197873108 465890067 237974298 553558566 640538747 605748099 751135466 910530638 215777891 47037529 498095893 819495747 956732453 229112807 177129042 815873991 47343803 755220071 272171767 80088678 164032088 469398267 577196479 330568467 545235072 435754205 89231185 865761968 626107990 817355062 948620099 100 993674803 424802632 23059978 719007592 112391378 64667693 241752400 292404285 130159163 425460119 80650454 152860750 190483536 227842503 334904983 387008762 814082334 787864504 972582241 756031099 388391663 308726079 888711943 927932320 803353811 972252258 721999504 724050363 956937271 76783890 672333827 532123490 578090001 521115384 498706054 527926451 376386312 231876881 232938338 709542830 180136209 400582971 3754954 579046079 847963938 226588925 550115483 606591013 797161065 568838222 952315987 342386771 799648577 218514066 779544094 641221830 10976174 650532790 83319062 104735976 918799510 606723591 603304032 621351700 287309928 133704019 752947566 106144909 911254643 326462937 632701669 819813726 268461020 377675159 162468391 332653866 58650679 187202437 697577238 664859845 543101986 460019198 954279458 728912920 535172420 470296456 336331338 576343717 706435064 707375625 847717134 84289946 391916818 729098360 87725244 359542573 707433227 753715687 395307748 750673046 100 882530842 109948694 264792095 148213411 326469019 826815122 658170875 69320454 497533523 343902909 315849054 458971470 637425323 59643701 836981205 856545075 467952258 345599162 991292313 61258706 458544209 764851454 602806305 647912486 613294307 788779892 887127012 696088279 919471797 889276799 822895598 556610245 976399157 176385278 495964938 581798438 790177993 439667992 319219814 22569459 858716416 195883094 83930097 278402884 472063356 762344356 591653298 34405398 546786324 126570654 975351808 878793700 474119052 356357705 829928735 244677198 343038862 130037814 865286163 806629023 597644218 385212659 652755599 943694674 890165510 8061740 807624408 286973854 809303223 61119105 645498029 320803107 994491655 303447936 971067338 468230879 707485529 867770612 309991280 433189886 52325963 869088062 664773072 655966681 84829444 901091629 87845618 279521629 763128167 47382001 603247130 178617768 75751623 124512236 511280115 233275094 481280230 977767749 859558663 610978043 100 202680843 35264566 426034950 205960861 527654373 656568194 683317783 90941582 891265348 675514744 953859658 44965193 728336702 877232701 76244939 184527255 656864277 240593656 814921500 311129066 646526871 319533380 631008412 223816454 821381623 134411991 726081261 391026436 821362688 72933426 491182763 650653903 641918953 478962416 133006989 2720716 832723569 782707839 11922575 131414331 667318351 415432470 733616869 853681737 163314917 462530223 900236491 405802620 987550690 381652388 524290975 226658861 435451831 56250536 688718198 280866900 532791324 395485231 247535677 599190132 714052230 851363818 14844478 42634534 531241829 471383033 796265293 342962837 808686087 418032050 980608436 748481486 234173658 618074977 534642049 180631622 126939071 655216161 365528229 935007466 289710560 276166062 397574818 133126838 608547279 110887763 438227699 102326368 63623635 577882123 992552065 265208672 47720227 656354977 272389588 345639030 99203919 36015125 429595317 617884575 100 195391883 643030778 462903878 588788261 785086616 287974429 594531757 566968920 631806904 307016068 431006669 313279198 906314915 110330375 501765644 436903728 395381880 910541064 463742968 144107908 961248306 111923188 694006616 945370731 273795058 162600786 855914339 708004116 141821315 697749599 175938303 110307600 799607590 816417304 839671264 657468816 755488650 324694360 419621291 893648408 141344909 5403653 741610161 644879402 733789698 596461372 94224569 201469718 788149079 911840200 423053365 827258078 265924470 541210211 145978134 690699912 999653319 629699871 788567473 733536272 889283641 489002001 164810091 546964980 20164609 230695239 676709640 3814503 509586311 812183707 925390711 978889612 14113345 637479509 978430391 392289889 303894106 702112898 218028865 427463442 181398900 474364094 802314432 555384072 212552430 917890724 406885033 535613245 727189929 790553018 348592211 284691264 902699981 783998690 541157240 822222720 386207283 558943793 54077664 440852056 100 31180605 897004245 77765612 862424415 410101028 656943458 228980286 371641369 933103489 888849795 143595057 811641839 998704950 390296563 245347699 769084066 943599162 42281482 336696720 240023733 76197169 974777556 755869766 489025358 795477757 996791051 112432072 791264972 877486539 483775067 977560697 687081823 868190368 805022892 874703476 248513020 502136379 306542811 357602845 789218693 492785674 459738647 462352457 531229335 853997470 813530078 725276587 260787079 513451743 136395387 405454863 453878232 861685351 447680330 81189825 104624794 834899134 522423869 185649357 935059697 984893523 150033434 562236665 958181512 388304493 851315152 856130251 559609281 78142356 916219056 480691576 902287131 584937202 927143117 819230411 489600824 229775346 86358580 177106837 426822341 399028140 68752339 15275802 611245842 787755014 359561786 439525336 755182564 781807449 835721309 175581471 520009114 477555771 2747817 44796558 724098434 829417831 817358588 601592992 127008242 100 500619884 227629642 178300389 489464281 918618081 626936253 831250252 377031196 700081 275519843 135336707 492469549 906275279 595155513 532879868 289152131 381764884 317394328 818816621 855949946 647118561 589270240 914023039 285010207 661159152 975933149 199597575 104404761 827929295 198602542 356899477 828925319 529502784 630745437 75343332 691782172 730208581 438144838 664982776 801226631 668347219 835999710 529053075 953270338 799172692 32269554 265249802 512170665 687631624 276552215 647840069 742003912 163928582 244011351 122393568 887487656 393852439 968794203 890923253 729382132 385951825 999759213 478252722 831569202 27815632 828637326 679950904 202160310 15492417 450252391 622723316 941473697 773893147 487507774 645059761 868413422 495742873 73640490 801047968 948723298 382567305 720880746 141138400 329029554 414337586 270337096 69852178 701775468 156110868 795053448 140618510 656637354 373329147 328185915 172795744 351621296 964484147 227189350 179587210 146118960 100 852673254 491748749 832288034 556541417 279248530 89470140 278230828 119057437 526159210 276199783 216713450 473151621 7982111 508263795 659192026 356697906 648447742 716263150 526375847 933649577 516906820 503634454 900422662 584447114 10148791 499093286 254568791 172119414 535176528 460112293 684812163 271714184 525484713 218845461 516403080 544101737 562297472 140770121 430469837 665421377 86432011 629201544 92441048 919414058 439278301 812822895 558089384 788893639 818767393 679626696 737632069 735808166 3119340 906655310 183286220 302363371 917945729 741411926 252803584 394634282 301515883 976435264 456596092 994371689 37362334 959404367 264064119 624344270 457401582 225201022 820549608 394383296 703124220 243025015 197711236 43247962 685169937 42531909 488520260 847594195 105260195 669465723 757488857 412032963 197949030 770198268 988883592 489975267 973015777 512276667 782182793 97945663 52702157 728169419 87850452 363717101 806557039 611110648 42206583 305055249 100 611365878 720619752 821320359 889077561 724584057 584367313 52307590 677288250 209822992 203852516 424232045 516179504 420362759 718532514 276400138 146820231 370437990 435640288 317461164 78340581 798956941 951012578 208662372 923876657 26975789 312324239 394901518 395933472 732543876 102990044 936573763 750526316 380021687 990510980 312345612 610650662 767908246 824731729 918275824 296860434 34923997 690771579 627345471 366771944 215129822 225506402 93507995 306500976 312092907 63429331 819493700 531413225 926114119 720395102 898878016 235941228 802456163 109243938 71454177 301039696 995499289 533047674 438606445 686493163 625351974 180136369 410786587 57079982 563076743 215218518 47368908 336449414 668598623 625385026 225407832 840135793 753551021 82333354 451147341 261568132 51467820 43302066 521962241 924471980 942359579 518609056 936669385 349161690 90552909 947242049 929450854 111207267 424195098 784275090 446248601 275073032 405129979 127412627 522654995 796707455 100 488445682 58678923 503906050 351008326 551426830 549908939 800109323 841379334 990956096 192994880 444490057 769441827 586652658 701043343 907448145 278868712 878466308 283056494 573469690 592585329 319604218 376395421 958684407 478687466 371171407 587951061 715048410 509275203 68065001 105422353 946061593 928619334 108460463 409564811 447241126 846413196 288653348 676400261 786744914 955054680 595606531 692104927 135729750 282401290 86341306 822113070 637941570 514966498 30970775 109237153 180298485 400137996 798125245 399564519 671022646 158579107 362976136 484662664 941032162 924697511 58801845 582256524 362003381 714239965 494837397 180833383 747681819 498047645 703014886 255462194 1553830 895599157 313502537 911507451 969274419 58186879 874736500 660536748 492826479 485080050 905153599 368649412 737614822 579269869 363333063 263071114 571574926 879989273 833460273 717400539 699868035 870254365 175681833 438137227 234436313 714026329 444648275 740001241 248846424 122296525 100 815067219 825639949 22156725 551755468 265751663 577632166 500491007 197499709 6918800 419028331 866079339 191025979 691031316 844229770 21007496 391720823 607735323 594296579 281365885 932582364 919630984 447345839 117936653 408891357 744865090 222285619 515803272 300145410 894645114 192328334 257459083 414523816 257459478 833132017 995138259 750041779 340612026 265115445 325292732 955031523 820312273 124241664 597362980 255963109 500476724 601037052 577693389 805740893 483938545 706088405 443741475 455352567 725556449 857661398 532551423 395468684 661230103 56553199 142697294 701683673 971493684 274982147 772680448 353372850 190718909 658824411 468202721 187229322 594091382 745569145 159521896 593471143 294221128 347178821 979711332 3295165 314532520 500291564 498070925 587063193 159654627 662268238 997716661 768344306 817598320 692985081 377730130 887748488 790744728 621939452 697628757 983890918 946551273 931359573 641175574 411695875 571153155 73723446 245886807 237263961 100 490065700 872212661 91036524 294920881 84808185 988717008 877655818 59449615 394540555 362760643 96225949 15512855 598655638 492218781 625754077 857194925 842971530 745511014 160229550 34778103 710828345 139960414 625292654 952757748 748878964 487065985 983990541 258294525 281953487 48306691 981270277 727606186 419339074 388560204 985029982 56880473 986774113 379584390 952061042 940697400 769306244 582566091 675934107 135898527 236351757 253568703 803014184 337822161 93680148 931800922 487154867 234553717 704823075 625407272 656912747 871323457 68603188 884017782 27601667 735687082 536774457 84092029 722314652 163918685 968949363 78672886 511710756 179965707 546708317 454480044 970055086 822495076 507861493 91876145 876071983 935578805 586427530 660176131 895895854 565777098 981293874 420570808 10524485 316066765 551578115 137503243 498932880 506977715 440484133 125561173 742857290 641489304 500841029 63476158 719561278 111997153 916199580 199180627 770831833 415547453 100 463638509 893987584 749437883 54302347 834727998 565954181 581053524 732201332 517415812 569680902 584371661 506373037 456315764 556915633 437139961 457476475 583832808 176025724 434799788 262346774 8892652 184937953 355951085 974611087 707260784 16720185 343709253 596789850 257910505 503880007 820754465 741942337 311811130 263411940 237836267 619633843 810211607 914002510 580463400 448807127 777332038 725887337 406345402 968671164 963060290 549650376 905754210 949626384 445858229 171849824 356287650 58977456 504217128 52892157 520965411 60174045 654108931 476154067 274813904 373738387 957657899 551399635 597954544 995462628 852624455 784952711 432174416 818261150 921990616 154957311 96996420 586379442 341918684 300235615 295620751 352072098 984259979 681279331 799517740 359431288 559600090 596700600 597194344 57973807 317444345 899311223 416814220 263556175 6321457 780839949 516513349 945171561 720451058 34551895 525571525 582469212 66375488 1576025 851586527 892081969 100 285699045 944600460 269201298 131941658 78790020 861130952 155207402 551935123 448178055 513391653 200357573 626828614 179503147 749604161 716451020 448968167 760535430 132933036 202328192 788218071 191535320 541821276 947459039 826419436 342708709 655540979 917604603 625756097 391918300 789631191 254751738 932262260 874784222 611453772 715908800 679604153 500161757 46381039 658971882 455828221 640691338 188933064 738189189 490885978 264960721 261944140 590234076 808838949 910494102 887839761 538345443 575284753 825229482 181361181 575095330 533091194 648713731 321440259 801034344 665011351 233544636 529200678 512470026 361360470 71262771 868630061 813977759 194243245 429361951 784438141 434457595 518976571 247130037 431349403 893857225 575254664 900900415 835783564 756678710 973405427 768128315 79222957 826070042 725098089 410690483 362291669 138292950 405310710 207745032 92417342 340519656 973354996 395169422 272445419 163757021 522972627 908883654 969863194 917583863 923877026 100 481057918 597477283 539949985 215813284 857299715 912015028 242352325 487507032 532490141 479882217 355292299 580090191 208026292 839303309 194478864 891060819 659784989 163019209 257633806 34227119 594779177 330324662 603227401 467667170 619358946 290116875 202168987 350379004 199425068 928671201 282105172 750075324 463626102 74327042 669120719 108834962 636464376 563778752 757332095 178192200 918309412 600772134 255902568 845575067 164059796 585437686 403226331 737947766 295282944 892312382 818765722 448648835 501981117 444296076 876683063 353280601 7342299 640022376 925914401 107168897 185900374 473303599 280273177 131133940 660483438 183886269 661239253 251895850 575720593 337798024 158460010 584487831 895301505 662381380 709014437 109215989 246888151 446137061 644356115 278742669 346517170 136944484 519511402 520769019 668385694 225585138 827392229 85590664 928904300 265926589 8901793 320926030 631094587 718800867 237383431 431296106 136529802 729912215 146070166 696871022 100 892562673 580345356 242888741 680706675 60333748 441132592 314549816 788145575 3942383 433196706 988254886 162628388 984774551 512224710 719645839 5537295 173244103 37532415 10533082 604641899 35497872 372640500 754333273 847989281 912731841 445140784 221560148 228838319 638915275 395449073 85778826 220273749 668774682 205762211 133435462 384669541 867319330 958703417 394025112 436562993 834695483 615896204 53561475 822791588 522611479 350767039 870675996 686047163 470990735 885363680 88713326 176141151 898518531 121294474 820022732 963307809 827158356 34917267 102132302 194804768 157362936 840801610 948002105 72024779 995718282 199025187 476977979 688776391 153039050 474014074 248007523 419693831 855712176 552803546 150092290 945324637 675275901 546705256 405028636 654312045 112657360 382156912 36323903 449786677 199197161 307326991 462398744 71214162 496393905 472085045 132653361 209563425 723764308 621330736 396435538 629100411 439306874 820830677 769950765 832745238 100 198400760 88133676 638566853 516594806 847921067 318876561 101924501 649436185 147275124 939025504 440540042 366491735 264917928 486385820 20448948 67878985 581913228 882744192 511810915 606948287 963871667 316467587 451287087 452515862 795252627 249912722 154376807 959580062 608742245 852376727 936566544 340196596 62930852 891201483 511019539 387300142 710286990 276815872 943330935 730605342 573134117 723917811 779744439 423715279 384587212 164119577 512277909 738539051 290040005 111097744 674947786 168588359 140369521 86029653 274215911 934367079 355172849 519796463 654460647 628837212 350872350 260472696 988184236 322515910 663781957 262246632 750284523 364504690 21179697 694095096 27193864 526553016 869045022 549692985 581867024 737873777 803458355 137881484 173616502 294677985 266861200 621678352 89756228 199565806 629524653 176632818 364802640 643261644 58157832 716607264 640811796 174830846 155901402 297672013 453361379 96189060 944610522 396216598 701118921 884094285 100 828687002 474938352 592182451 180839035 596357535 718916117 321735956 650867205 727370576 566126643 69776884 279603063 914002273 623001057 139570027 812506852 853986416 815085827 111136168 34271580 827542012 916702144 447067948 147636834 743268981 234975133 262822818 715637705 213387144 548499588 40006460 158819765 791202468 972493797 364176998 108631706 877979979 392466693 378471954 211298536 752511260 444801953 82556021 47449970 15498368 355982407 128840171 881316903 795267129 794331165 90022053 320468882 619853443 582146168 289865880 616303055 78055465 622938645 621079507 959720327 999305004 117174761 516551295 776123122 527989755 308919362 588404949 126098483 419396315 343861508 319865598 324997448 17920473 784881933 286418244 703742450 962441196 473665177 797928189 967948789 969800222 198130025 108811536 131747018 390446251 41631149 610706256 680361015 220623875 326963039 877045812 996112453 165239230 519994232 366485496 777983759 784964281 959217 306352267 733731413 100 861743880 978616843 333587610 201120076 455116045 643687094 764862983 535346423 583079631 236860077 117688441 857854125 774924446 107924932 570036595 686878175 225382926 690154075 351375044 169033927 844004680 238760402 549212963 838074095 968463396 991797632 974224817 200834953 24670266 93622871 569296266 474626855 378508569 170905231 19522740 692125595 531172221 610928871 291961554 658758423 521383135 391224205 549870925 515753500 237794867 888476093 955144148 291509447 160056310 515296013 763294121 705296756 991419296 978553762 166917054 563274209 646979389 580283512 831891036 954628246 506524383 323484823 71532139 236951563 283164848 634671639 820818149 275935324 827927416 726883501 109680162 85148700 917242562 296286754 32607725 927736712 813964955 736509094 744872142 869422732 380728218 297428961 972998216 248344679 939968982 218962764 85570896 794018761 524713650 586095677 637013059 44059741 37487814 526290356 870022632 429266821 27091561 312907822 390321070 463045636 100 789043664 360543611 312310917 114582966 848856593 197404839 964088044 645791734 926091495 876580776 945311419 347664958 912597377 669791121 20168390 963115321 277191189 34390208 978086542 696771301 13438717 769756705 515678219 341108368 75454691 762375689 87902247 844202075 121027899 979415976 196887249 963429537 391353174 503350346 992021663 966513369 316682003 891723178 451703544 764905770 881902687 605010577 445147011 406263949 858827316 233265934 974853585 924870886 811210399 339182703 910835153 241312905 284250429 74325279 542488649 181652965 13679728 355917326 104954413 59855505 190192917 845655722 721315568 548304040 195034101 101313088 832515519 535513863 338450007 905991355 17410965 366710720 322966057 348004361 846287877 616632812 708667733 159615325 949550355 144178671 492031361 344025770 453282357 550393133 630310885 424665780 36449901 383727478 676484830 496620642 215555476 957064332 873467035 236993294 87771641 216054978 581173939 172924702 873965961 600875308 100 176061885 836813341 454013418 249500304 200722433 383343419 9536148 870417691 332240904 142662684 840601004 586402906 217441306 753517801 972454804 833053112 985357839 811234869 375022601 812212601 333970964 435853663 483807700 76144328 354640973 438924401 430948333 269969439 68838173 209110892 650025843 747579427 546793825 675449526 942797262 921661510 786474638 289757874 992006781 739280403 992127484 268696209 645961296 611669453 467773200 141879958 740452381 894861816 313219398 403536337 726391576 907678514 109713177 786472460 316392208 63134137 200067364 101991389 450309648 437223810 257583955 623881458 582180658 419260640 620493154 556661249 681968773 883834939 450785005 273016708 807633727 293236153 76882234 501628997 556477570 449492672 943007346 199217394 410354326 193475873 477511251 335454279 369760798 465804282 471584785 818803173 719179635 556036522 341294980 490230968 979777054 71345969 801570414 573932991 184353182 333086292 237949765 373645504 41009045 145126515 100 896743756 944444307 410267263 37668095 853008652 470506208 353271189 505216511 621307771 502780827 79228773 541075247 943357292 633729992 405459805 821861717 891353252 999972755 301942682 475810841 993440605 180215838 662320542 155938304 61529299 524722202 790068902 433124590 509741972 914354907 286464173 866809577 535286455 932594524 265897168 282359139 202282329 425042953 481047674 727539170 745181085 73642438 390787753 189290430 547029885 238130174 215601726 800441172 660444945 774855303 867261059 980685556 663694077 109636736 147935193 482239771 164009122 30126861 427535536 812085285 743445178 706051665 103161679 906489386 588964528 334356339 687021163 704065131 30816978 465593102 6008578 369684169 769557648 159080028 317188852 703078352 57249217 262396592 706754939 161531290 683936099 678504692 527691824 581801381 372247311 712836628 675847747 364036291 617661200 348828193 585200570 921139806 936365048 719699833 638555971 565596990 519405836 493777033 324307421 65759177 100 126066509 182404811 510448809 932922508 94444337 97431712 126095913 148602183 790802775 792298915 662324136 38401475 252632904 321561237 290088455 162668951 865970808 463697284 885251684 472784978 742430182 240425392 677992273 258180929 25339206 967872297 20420190 896964086 237261697 976272058 377992618 951356868 63466699 46843870 736138987 664672747 249733995 498570939 834080446 976315889 68607204 258128844 690169316 805585045 531739297 268037990 488388714 722283650 595906374 161215303 166531736 668182509 918784840 32413083 111975181 142371325 610327437 650972579 416470146 195708413 632646057 376891126 509679644 544253223 553524877 305656035 925497230 179605949 177504413 344351206 392052821 280903372 920136985 733394136 250289694 826478128 719428933 471537980 542258224 629191128 171885874 902217911 236475192 256504867 321513558 829892110 615607889 459433616 285770158 896239058 172827873 126018772 171175627 503332040 665912369 504854358 363636755 825343695 342388105 898206910 100 222682901 997659858 335600747 512318645 836780638 255328672 687732096 886587432 276231388 411653301 297937671 506447958 384343303 833475681 263163965 170724052 31114762 431032124 85334107 921273119 740310997 329572738 4563506 928589872 999250748 324303251 990736100 444603134 838884940 381397315 428757341 292439288 675998015 181016212 219602574 378697124 61534393 821498989 306547096 76740952 242121351 237258030 933389695 22491082 228905185 609103164 560414106 3373910 532597911 389298988 453889873 455798824 73837107 161502760 290890619 738296445 425146978 226270771 519124166 778669143 539145479 762054784 370722670 198362297 316860937 179803022 533007078 567180627 819998541 714804920 35448260 400692374 277021341 309533235 445375600 539591708 406821015 12065907 373105790 284147905 284850021 620474069 975177206 886120756 178810756 682530755 200992247 348925196 549557679 250712534 436982383 625600345 668832984 148127472 914603646 33153617 991612717 896448409 890821806 435929678 100 470826601 133167883 450477102 326957699 706799226 461517513 355207637 525966708 943075753 781185945 929731723 846613827 639159658 639378660 897999646 582928111 453625073 112300574 544809052 605374621 596466746 841226277 432217423 803905990 436765073 4976754 829988872 295519924 418955155 765936404 227848341 245145181 449566233 370795745 246633883 373105063 288861153 18843849 892965672 926571594 790704400 640324582 534419013 805341212 771784515 1886571 822103747 718483830 250908761 550583646 12675518 468214438 307500533 793237210 817124898 326093392 140666557 63012819 33034092 805248724 378531451 74484222 792735287 493242821 105997230 371192970 415434792 531409211 631850961 541101367 338642911 77061503 793220297 532726619 125342662 237682550 85131351 111966069 219895686 452153701 349966588 914703777 431204368 135735767 612468988 427274712 419297611 998723864 440706727 373693760 621468760 698026600 869758799 137356934 762999662 446715375 646332037 983583868 121114621 735808597 100 923198622 553786984 544083615 552357778 993960624 946535175 737644024 691400930 991820520 281060775 287532319 728590227 748910279 132701420 92263952 286406804 772152741 417695820 639819002 923386590 463475266 409839368 480719250 438651912 635928677 205387643 40186998 178704123 852326022 212112708 357374824 549934360 157097902 751772776 251703593 46046523 640087970 854890985 614163014 127745530 344025916 298453308 473169732 464629654 702401005 240671117 818585528 875007855 25595519 671154263 216895521 554460739 836136195 595549491 570933931 997386256 412766734 990149434 295144965 785849734 856687100 696892689 874577104 132456474 722899546 176961230 475237647 50877867 275790094 223148501 387761907 841177136 623057442 717273610 824057014 865204263 970106426 866037159 301249989 186322160 950143981 171902698 23699901 249611518 523946296 710708444 827108032 616266444 880160989 488771369 139019064 408620654 392752989 277106033 652734579 491296688 574260589 525493408 262112645 849629768 100 241842250 9672979 913604966 81372132 682495009 942037667 889931701 553856514 288955782 968674274 454698793 810342176 907483535 719018253 634539331 186543831 264576185 505496829 901921109 441452086 128243373 103609527 770058110 478459359 976435216 37233552 550598909 912472694 287441634 751091511 125746834 510008324 904247626 980324915 944966993 786613446 133916806 918861795 145596266 789930869 644510145 701685805 799590390 210656881 198355855 480716859 3337437 53918696 458153183 324652056 814580036 485334424 839662070 598879501 703763839 522829425 264195960 388293783 538005075 638159253 685362734 783237502 659925618 75203335 697034547 882228431 529634546 793088080 565734446 142245570 258981392 335090676 691338293 505477489 959980415 784667946 275074285 775878798 3885845 971897491 384704801 970273648 489291725 217840038 593969562 93644512 269536175 85097342 480526009 155690092 151373115 273095321 878032419 301785398 18146083 876371365 79660 974131278 151024852 679609290 100 246812505 77570799 148834506 230668509 326104038 967024633 84487817 33842180 783903780 954172041 455443326 337533488 250783691 401376965 201147569 680911316 920416590 618030687 991711630 707499084 753028558 331690118 689919385 16831518 589392123 719944186 100031350 283186918 112382882 198091900 161364425 103482264 477675117 984164350 28530794 328176135 799103434 64450612 167879394 172419869 712391060 470278752 534755542 460584128 475958298 728983597 551296527 880806122 830781113 308297399 348819677 706372867 659216600 191768844 347005540 812945286 868092899 980956580 253757801 308091267 534338422 888494858 541612107 48286295 582740307 463820114 454691035 757535301 380072597 634856882 290465102 600693625 418130053 792178662 482060507 106242150 464664163 960511984 426117558 688433537 284846710 491470655 846737337 460252558 892885123 165014689 575094067 824742609 109310714 678573905 437257946 817946672 744733934 218523440 46689349 304538865 780099584 803302777 8389372 337080909 100 881434369 49608620 81617432 160574651 876422370 755076114 624640381 694430014 258665796 549230127 859128045 253981013 305500292 745374962 652438064 572273195 807317284 651280084 379132592 235480743 694614490 567602743 690357838 89588304 187014970 798941752 918961251 419490046 54912127 570207553 705658285 300335908 684099719 964568439 977593308 415279868 128880388 8065214 669464577 690782651 607394245 361751502 741308775 686291596 198734803 133922889 504479516 89201895 397345576 264718172 700512729 776069002 542452572 675638870 40820103 487555630 528024379 88313251 4343916 807493954 59695898 230267515 610226684 588505698 744461504 149104252 535500772 285176134 648454319 411502598 253749674 572702255 803170871 180009120 918822043 495517498 473512271 531822594 186671785 777339649 905046121 711597695 722665908 654395829 786945181 908410931 920734056 729361938 801012402 618710074 173087802 769187753 517121 999487356 564681614 463871371 293429363 599089015 914109088 910947226 100 189300775 327167389 323421952 620086400 517947994 365857403 619031400 625410209 235234245 643811940 440695580 36226309 70760436 424222806 20626947 72446686 856972753 207983921 572395555 4401312 19683927 751987213 9049969 291833791 883150530 724335000 683472699 300322409 275348992 675696454 120284751 9435704 345929081 590283995 765694529 144828894 773329002 15004164 731066827 512483925 565688454 156230958 404317161 421258863 571648293 784810637 281688651 829243559 216746916 890310095 484163884 93624404 843336975 460863484 794953796 469101844 124084739 747165573 105040309 694213070 790451498 748538745 337568345 170387480 626774241 86554793 428229235 700966761 959500787 147038928 261817922 31323056 59342980 153281071 123951494 792288418 925996327 487704511 769009233 111881926 333763705 158374092 584448290 688919180 411526403 786368728 438603813 983183633 250515102 5866594 509742117 681367796 460131933 495942370 620054076 198357618 59042357 258452594 766735487 905921680 100 510104472 702258830 913047207 984245997 858937434 873416362 260967766 946555871 369558897 410343552 595377261 856175461 352231871 2852008 866235543 622640001 522124457 178924897 728729891 813483900 395414933 142383553 483681356 364359252 5961350 685984336 235845127 811578370 213713405 482129927 521228393 897759227 753772015 806469529 720027787 389654004 680557198 386262948 909942752 66884054 908129247 976524405 566523161 677369290 414410097 838097181 738743517 462516573 669600380 854029854 937645880 850698150 197171380 132768415 607403401 621824468 285206346 33307847 400675635 415705500 979300002 569680877 100104073 361871611 338131507 274389833 14320492 894686629 368729051 219646262 658483322 951346490 528328348 456007901 608615760 141714361 405313564 788326090 486254145 929795491 433955101 652124588 496289910 89942829 837292597 466462891 659607236 417838219 150577931 483882836 918006380 44611942 174009553 716031165 153850702 745227871 678444753 967363535 736987558 34531062 100 686166718 402317516 106158786 992559971 304839110 418218864 340784222 766095170 137089234 10529895 624658559 936506787 539663766 148188812 664959688 170892168 604604299 657487300 154160915 575545680 3051948 879873769 879732764 132665198 414890966 893538032 236247695 882713611 394950850 383259423 234591908 495930815 317846971 862289943 898423586 224964461 877547888 695201103 990896429 550964598 694266499 135244977 841988753 601756180 331513195 242874465 819365320 387469448 36143033 355078605 691843616 715227545 965283387 958829614 107247124 168930743 470045226 230011431 443405376 32721541 15809682 92907932 440182124 223670820 618306325 421726976 887025374 635248918 917197545 468879778 828661766 383382379 540048084 78211137 936130448 778785516 551358155 420870418 398519076 491032295 945901536 618913265 427813537 464935076 842373011 598545195 535235554 199592663 296284988 602868236 350560793 876622987 390389017 719908824 606055437 331929135 338643103 66931938 596619144 806314958 100 282696413 435709060 175769771 658423226 245045794 603093398 849056931 329355712 108370218 382443568 984009245 760491508 930376302 618054351 503228512 266430438 980849815 704609376 981628136 613412564 256798240 386653170 358920591 974224941 632941093 276919130 44472207 528358376 478313894 99935022 705752252 210278177 901596563 741665791 586927096 958187620 930389512 289323523 340724108 752473098 73434218 186969039 152802443 904383335 56301703 961772137 502057199 135884504 832451371 689252730 340776675 827630204 399912799 558208962 540594974 848628775 36537126 891868239 293361628 480562435 657950656 893692555 399341190 826335634 415497016 443459016 326939124 930055717 914668420 126877352 442846053 94098201 198743379 257042724 619249740 30237820 865562662 783382398 924991640 857684138 345049032 754998550 656137743 118935211 706449909 476727721 145109226 882474819 462310758 595644786 383493127 220725365 417234463 778966654 88854816 804384353 468163152 417067964 96863054 348019359 100 518574342 336243374 761296812 378120641 806125360 39444170 478710637 225323070 23490360 1794793 678778011 776565083 652179857 79259699 809501736 324268837 288996917 882234688 258742409 658386850 815311859 560838998 101532714 196479192 677345734 52222174 11655192 840200729 206031143 827673108 841682240 602336647 894912410 379655316 374285385 885665117 434532125 926382110 180679924 938333543 386859823 190870511 986779377 7652001 230808808 53899255 902929567 666750950 795205256 229431406 319549460 943888974 469659055 89375953 899416663 530622206 649441084 852203962 955973113 608001833 348711917 552556261 625601448 292735992 43276520 914939371 826439410 168205265 266375615 167173207 714602242 521527973 793585082 486132687 714524359 322651452 304575001 431124769 423640150 504886315 63951486 615104460 448933686 995026611 298063052 688231934 135219227 995466931 394895959 253089342 615099058 500150197 382434059 616944799 920335412 61557270 566908544 388698549 647367787 475784711 100 875757749 247991336 632795279 862055960 798285406 610911674 583532572 178016880 134007657 780675476 475348818 553731278 985568002 218514922 408557725 681114041 198576671 417102184 136995674 745381853 375920554 875989681 860260925 284517483 767369085 836419813 889601918 904527908 436274703 612364368 399830233 265387903 188171165 132298232 908349523 208111612 398712476 579557079 571912852 924117791 464686420 858800207 360835829 512266563 686135688 219506015 833670685 672414068 767089241 239573994 165834624 8235997 844083606 276701994 546854834 585370813 199261253 755716109 889454531 23019400 255854532 567900012 510860963 93044563 532741434 950604180 557235359 992245422 166663288 682128704 769371770 747928609 430002356 554784395 21193555 562718916 417348425 665368481 719297236 420203566 372319573 33986115 268991070 502101468 171949291 637279448 758648324 769548591 622637818 459641282 89471104 175296012 418209702 70697905 379704274 226707303 867427065 416044392 788403999 871061965 100 25791794 848019890 973621260 713073334 979877889 192139488 488118953 590071321 115038312 893244652 325870001 174458599 969029995 979238126 125166436 888153360 879009612 730710976 767832349 923473250 426101879 313139864 270900397 973488870 240080381 877527842 708031380 401651979 783304346 959555113 42962335 416253525 225104257 447150443 14147476 266782336 734832054 971544621 196046189 23924686 423923805 239317559 521781452 872825146 210529189 455494294 709550135 845565892 124065648 122963057 224249945 633756177 237233474 188781516 782442304 178146136 680392269 327809762 625582640 232458930 198644468 531394447 766233626 662618949 663768666 584944580 878756514 83894914 240946549 41368090 39597953 131010801 493099747 839474539 945653463 890206885 191156676 698615946 963142063 442047280 680148677 217884186 557134385 261939628 785887743 656149669 629420000 716440762 809002009 967574121 985668170 740248754 219044156 562964458 592961641 142436245 930813266 199799973 95388955 179270450