3746 12 0 689860776 389132681 762131838 602803917 139855491 8310470 42227915 122852627 829439646 188811230 844997756 951967806 801702497 702086877 726670666 26549466 157779703 328831728 509363697 80512727 186168782 497408746 558986163 851513865 953199897 862188992 680454356 368176808 750433873 487700749 938119455 508254673 345269424 981100431 106030175 236717570 924668340 748658600 952946919 889978274 919776162 626837982 485692427 123759991 473432065 785708379 342126245 590886190 213803035 537155181 446778257 809731030 216977791 444528391 224156720 932841573 430170242 357182783 62904041 609610290 667880121 437310926 19344292 930110841 103385984 74790035 403263053 262151642 567438454 111390480 587969879 986424539 13224959 687695595 950060086 289246817 45361089 779847279 105503204 142351675 826173735 194000136 939529053 495054231 842165217 763750859 436712994 32995211 784694882 545570795 403045050 404409229 697739361 901325125 207435053 895266555 3764056 197682389 729061767 937112213 553372936 417008959 691687515 539487486 599734771 71202119 92470077 79065918 586346465 994565721 758083911 445595459 439674972 412485890 196956565 976400475 590326067 160223604 487651785 423864251 797369595 811983366 881546887 264771835 855604105 943248818 451823098 489428120 991300729 771822742 312029774 967200369 435456427 98296435 3888179 573403211 925304256 453654833 835652961 311623757 399493793 872891225 396710158 124821892 507179513 409486489 550368889 668976224 907206582 892438084 371059043 674515765 675269260 627028432 459688081 859920572 140997233 626088790 308772940 802633871 63669026 121315861 452437728 120535984 928886941 101649134 365796640 824065795 888197029 869306601 316865248 920242127 850312770 333472176 556407162 368614977 335336510 36029967 902391370 163002856 397623720 233063034 716170546 356705338 882019669 122059655 334179095 36505358 257826650 200880751 283575393 400736032 917068691 354178962 141651327 210570385 840086560 405903088 283492705 882470244 507015651 49665712 21384700 374723074 953244931 140346781 718136010 604637111 174279531 944327587 688191303 179550002 274367307 655898711 491629941 264388361 83586454 403003245 745430105 708226611 775918723 295835967 515909756 811326604 438333965 68844365 845746282 739629908 761615987 848796855 642579254 399913904 831979704 494941893 107037940 858273576 214882084 254017376 40098110 813970472 562250689 621629334 79568304 24418943 795051742 452478489 97836652 190027234 283858320 234198977 700227735 697875562 187110444 746636806 846651610 279642386 275369167 749125510 900765154 438524474 789683670 810603653 227299040 765021735 142133350 303245672 144818697 584516480 445552357 86740281 687124759 41009618 167655807 634693670 7050182 558151694 276851874 887390722 295374936 278782726 101554562 768317635 436214802 676665331 106565782 455352066 813265340 569040114 929735193 662639230 319545893 454836610 280818826 615465625 855812253 959753479 943101740 597872857 83058042 608651595 497097351 299816809 516792467 653575928 316570341 42076053 303112136 232317470 677072598 415359058 782742392 345047731 429465516 399527091 34606857 670633743 528318975 149936245 457795939 582221420 461765163 996955764 753699701 780444524 704060621 900476723 538068655 186720914 812979018 680090969 747302279 510230215 115128392 836218414 57492980 980846039 315656243 193269282 229854198 7688434 763653049 227047751 515262476 36225323 696297038 508472786 793674684 865294332 601462441 869230750 405727246 491939264 328853829 293728680 605063697 872471096 71031521 32080020 536657237 954772231 500119809 317224743 724649072 783706678 136577131 945061323 430770042 330332337 340025258 791797774 381480080 729795271 646028174 656555299 152651860 408965806 297221033 115992671 988191339 712517884 707327188 836054973 564900862 472183087 909197736 292890203 601714234 224524839 225305350 764092667 800063696 986213542 185117840 25603715 139010677 556476887 561603885 938846333 318845283 615267268 164714889 759747992 187873750 69697503 260182162 426227237 397514897 624133498 849694716 237614234 686118743 19606606 863262910 323653138 39568241 673116920 790820243 769315020 420407342 822842743 446324602 985221800 423041374 107461040 47408695 48617389 619803095 820029930 651113167 246553222 932144113 160969555 469529616 9795327 686917129 932677753 803993863 303927949 167525633 862312913 813537159 966916804 894019262 600921139 471712425 203072990 712705193 38742875 856626502 590023483 421991983 147178602 578481279 267129307 830090561 312030820 473021494 398922470 753622229 667124912 444878738 833736740 842141539 13160347 559085439 550474886 876817256 913631445 727871788 529228955 990274534 547838962 723534987 541086491 833515746 47886570 563704532 20226912 716859877 900393625 580960002 386039272 49679484 192779584 495835220 260628181 71023289 269745410 111081166 287233645 21300655 332529256 977169845 862124954 587643385 293593822 183157783 887925866 40700979 472552243 30900545 349557392 114579328 556257821 927629638 273029089 71640067 349874355 46865791 131698904 591338854 889912049 825715462 166388499 848879958 525501495 836192569 270860756 998417412 625945034 895665725 349537922 850062501 231631698 766256505 837342501 129199091 933501786 681854487 950674157 722015403 653256660 15254406 101708971 629946381 222336658 765296122 178239829 662613087 584374222 155008746 668213895 747029866 18524323 958532498 962843901 149894907 818404753 924710255 711353627 304365412 350406909 398782149 745654117 971189752 810767278 784776476 227838727 30254482 805053266 320583103 462756941 734573327 115151607 242187324 23381804 78944207 11816850 166531302 80760248 2807864 663518331 750370646 325769388 78842419 169410031 281019622 634337253 63652781 639015821 899345205 749992167 387898136 415876826 436133030 456356182 906343399 139613629 88439520 936198014 615090965 678970115 220090703 687129805 973147551 405742300 617565090 43621971 335924485 975640412 483432011 365690185 217788877 907648763 44068098 62757255 526046720 912353045 588645698 778051084 534684075 848230507 803783883 854072697 270610272 763149217 960319006 21575318 331254962 532826046 642676484 25634508 600713916 670535855 667330312 284171946 579284635 33070019 452409336 675429473 89234415 526257200 470628968 100207688 361950559 973217165 33015854 816667480 994744594 30337622 664354023 387100592 470649654 209212524 17515633 755345170 145015932 563508114 297210223 364193124 261055130 507310065 205640649 79216945 80947912 27886228 299797801 295833638 665420868 723156973 422787454 241257365 546093774 501367886 477222269 454962421 200558892 521868401 249001243 411824223 232757671 775009777 687204372 62617875 930883212 280715215 299941479 754324977 40395949 549570798 263319768 826223617 988836829 312859286 59340653 932388587 7075704 28753653 21395954 442826624 251118808 767829401 81092213 909335599 63044065 501545975 969835466 147176336 90321782 446320104 978076168 265545437 561684993 822920742 716330249 506627700 646403055 126015188 39071982 121627223 365128242 352156659 532336281 3150507 862424765 565840878 13765170 256363068 46291212 207442959 201834403 554988280 723848345 536459527 915966748 500685936 147299176 512282986 947215759 160016986 550816380 540952624 513087796 85264657 52783711 675593526 690134535 463265299 987915166 216778171 776497733 661981826 223340875 961292003 857938675 871106468 891819898 543611960 682761303 216216419 974353860 231993892 367435389 593086670 112367047 313688183 588198835 84635286 516841891 807444199 12552461 601788818 668716670 267915147 242909410 366201659 714281218 731483488 630342477 927228977 951004634 691257028 81285805 955280564 507394104 659038718 924822053 564858155 285228626 174043572 546905116 915083937 992927712 141700978 501456063 858645315 954554016 552350762 5708922 35608803 800782035 436633775 586500739 115276152 76273597 486461497 111066447 236721052 340656168 586009828 435101979 805093644 513734881 858636336 14079076 315594540 113611066 99053442 961995887 446239617 203237767 379645090 20891074 810624564 206588833 337867836 147972265 975965334 640699238 699768415 604633522 784411542 746183478 323582720 61459505 611292237 880087160 199474296 618489021 577569907 295910419 153224194 879066545 788125926 367542005 741653566 246251948 47284266 220654224 424423345 998737425 611270884 369271640 351511363 156045192 145042014 946189638 583599295 499192955 637657863 374728280 466624342 583713178 799706352 947042062 652591644 414116439 543342159 213570799 108956810 838933867 681341952 228169986 955298042 541175631 88912895 534537301 971427119 649651908 974369775 494711930 853694154 107607372 943528342 57863173 454761941 77109678 726425438 580616463 672474941 818412150 216383702 924544438 48257360 431522418 978938159 31530651 742747715 704401206 796940224 1804642 126335662 305132441 352133251 512800565 805506061 824319542 700141717 728119106 815458113 645332460 160933050 203068728 232872205 944826462 482064342 796108238 90916507 990267508 48740213 509922621 879076852 581550296 394668612 542583233 32293515 889991290 939842197 636236315 329813427 2579725 782897375 328105490 702894372 384570247 59424828 636777197 766594938 69014181 719656682 770824186 916690102 538110309 911424715 49896715 960721595 354535818 88813028 336873716 394845138 634990107 404287201 256990222 903048487 396649956 896878992 774900407 566600009 811866611 207398241 497889232 608881326 623985180 362789869 289877309 740484652 231912310 573445996 835844713 28699009 207302364 585137981 73937599 421545933 500421997 169872994 223548466 227104275 94180621 642665985 709446070 66398652 276998882 861481956 376310212 608564499 164999127 189833466 173237466 486568905 909100316 238991316 318526969 198081907 426394788 311641897 304310054 252191239 868308901 633676370 65809385 309406819 216584988 384095694 141822416 725012678 887299142 526215615 422761709 867480917 57324840 230535276 258129492 966436503 329437961 318568125 480254111 200092154 54853875 414229698 153817706 511690828 744990773 621910061 756301014 854638658 368347875 323228371 499937802 467975412 678566484 843912494 283860909 819661407 164005795 172901598 570667886 807167458 658910256 770389795 465267069 590706881 475377692 267001189 173756175 565505189 992122576 992384429 432277213 525569562 582727542 125038889 993834917 554214160 779044734 523635883 80026792 594344283 862874907 593880875 751471146 924987187 376861636 546865217 199324662 3983285 569285299 638102700 227106775 219002719 282457961 453334733 282360352 455100056 184710184 841143596 966450725 538359846 371649144 444964594 318963392 847239606 478040483 968635502 230475981 985627735 477229368 24021393 187103662 88547583 645845899 915775089 756806087 938085125 898914356 747846089 270560515 738073253 570228876 409427832 778152269 954659712 413536819 550154494 833021720 90211609 903696781 30234626 956470232 47836504 105580608 983432398 833641607 574475531 668893111 186970321 403112481 700060768 182990242 426380572 716951080 491674989 303543412 23008998 223105824 650365609 400840676 230105096 765745428 97655151 919797100 510486914 525139984 231158402 787486413 983462900 553742500 567896196 894834313 471628326 743956071 115202685 603679848 117136256 246924402 276242523 896050164 945505938 971461601 955637100 457080572 878609294 303024726 939139813 856587796 828608201 365925494 419329630 827738900 378481982 629611113 751010900 22339989 313545482 701962334 725507238 517797239 790002673 262100229 198954265 111622494 806614488 207749139 247817684 256004400 181715273 206415042 987907556 389570712 288125426 868251726 542429113 313455495 254628134 516927609 815674280 797610669 640442970 853047303 481447527 102955524 749998505 153743171 613344147 684520774 864581713 525031033 915747885 75448434 983259444 582484601 149905177 170713163 642791768 450597147 260218782 239973593 571175527 662056885 227600873 552701414 673556784 346587046 985056649 270159233 931271204 451544783 196886516 745976447 198782426 707645461 23776513 840389365 971937675 548970465 759340908 392290495 11904918 607228575 552161110 337535485 367255037 954226498 344183490 269213584 607438055 564761023 126839833 902307233 647266588 771281805 469957287 743060507 661540492 328643115 490101532 498741036 343129288 419007898 358332939 13631944 87143815 361194207 308298862 329787430 242527011 456264323 62470176 752668737 967434009 541453075 217963617 162567768 636889229 176321951 278363222 126090606 709404867 144562239 547913095 772188106 741980583 168147593 811158112 951393145 802967110 13178397 172807344 380723911 970940243 32767258 791946796 701525706 574914467 592784037 283765997 683215319 704473265 697490793 331715566 333539338 634767131 90398738 301576591 949196739 898272035 912104913 274673685 114607140 428639022 728402139 261961255 467745172 501094985 579544298 418571602 754205758 212453023 37448122 890902151 556985491 970860036 223118221 760299672 699623876 522619501 187027368 755225790 511210057 29998710 962279124 461863702 537203804 265976283 749631454 151157023 504974462 584058367 923940887 206226493 354975730 482117224 941914068 541790266 548928829 226828096 879198447 565190080 875916973 122840534 436922692 994955487 460125902 293014299 958028597 972873613 67752694 384831014 323223079 950677538 638715834 69761200 159252739 400910808 255169911 364548505 188034741 372578641 816583370 817124705 461295280 619370256 149293848 633463471 203317609 862819838 890411783 837542606 928050392 189230567 566620419 631617579 160914682 638543867 507566522 15183064 727476305 754358093 32601760 526120205 207036002 124765527 681201772 238439329 571708982 8396404 655226777 101440149 825948378 344320613 843279590 7722890 381835231 844882125 916922839 580006981 282661338 807635381 812243249 863600434 364923621 848737801 614971266 948400094 742467868 223096344 679106966 872036732 380881185 243073048 341453059 548440929 896840345 421907615 656043678 512846729 39525037 823358763 888066820 898949903 538949258 434376348 165999379 792028344 939019233 434871733 658042989 496052073 547403623 364923294 979419644 972900013 565012822 31406692 710885992 858434864 394261995 261843320 215605411 668654918 956117990 297437228 624947806 711635813 693771533 619187769 253130385 837099174 129900713 459263548 428144119 656359752 728014855 455509044 662691727 532890413 623294712 647886854 288553756 819901020 430658129 100370425 637092774 767279997 206382188 239346491 183043575 540434528 748410790 116616794 211598623 534377078 172272863 179771851 931303665 150859606 43384829 334159974 871373956 557020474 449425513 895616487 595289266 708609407 547848591 247924079 565983900 359302953 520040291 272669186 374495268 298186588 832542935 317906695 269400177 657250788 879259238 407976139 611363439 497385390 761953421 885900030 368209228 987127117 142051916 933705524 433756924 983423350 316190633 353775461 724509879 679466372 69118509 682478701 691597686 212224500 710695781 39008397 264156281 202862314 849770850 192206824 71946179 762350763 568844089 782881543 216118940 79007777 651026820 211327830 750401038 171918682 412350688 421532068 95866217 831425545 835917933 541308071 454679232 80001028 874119249 76282742 478085994 551989700 911810613 302875661 896958593 929259752 326310854 510496204 673357158 130698930 186880821 897459704 581540923 137713288 560863160 317472825 530947175 593333876 596570119 871425818 20702486 742438309 707530463 201694349 568204727 203132140 540201859 772319332 712359036 540868928 575670838 560250585 503499485 812133946 827990210 182380295 246543381 937701530 905224436 493845870 348607908 882997952 634972957 387049587 612024779 840630067 385003154 398221021 446908435 28184862 758271021 538017882 603650502 125343950 216577739 742617592 729270388 717236277 623738316 275005612 621390960 413772650 972541334 506694606 776814417 381647655 306772498 541421467 861084786 515446090 218292526 172085682 322435441 315891028 675319129 525217176 896529587 781536493 148066825 158490932 321111519 968075358 610077752 357657427 911111775 879344405 504908515 692107813 951529442 377919525 363865994 880643006 443941085 244594371 200736947 288518294 412702981 946966730 352293992 774262281 89171414 506026808 985414324 490767576 608754447 778689711 331644969 921930151 470234420 388191733 286620765 703089021 590054411 625797748 849061480 234880583 805925151 57318587 543836519 640774484 143995457 776054011 776327933 114983386 39984641 49516938 244983757 841642352 181817401 897076579 410702337 871661202 602846851 982940325 750144454 349268769 611852478 156368656 149639117 455646432 466545549 188112523 321170380 547903992 118424279 936805792 519329531 874174836 127901256 222714366 767314072 901007302 125816271 394267382 550344803 821805889 33634334 270618623 677086498 525120668 990504238 804613427 95301406 575679349 695672504 403872207 703090853 31327436 827329724 232623287 80946310 608676740 730394622 461534959 811292312 834489061 715716228 346580515 882528819 692405533 157444633 419520288 816249013 492048314 672642254 635116121 126787070 915123249 613086068 244580963 139990260 992687707 844392994 649036921 593515520 590840050 201470133 76459256 396239760 77276185 173643595 572065764 917931155 734763473 278781127 154966882 111315712 233107589 773975377 689880636 382359119 311520127 501910739 519783008 589220350 300414320 186686844 740185953 735676941 167539436 297425985 417099508 184049026 261363435 801440599 962093941 642700006 920311626 503442619 232681056 162313415 619061576 254363306 72808664 517827636 944594953 484423209 917988899 862668612 368816919 539156350 377629739 584985487 768954588 480281268 122782719 977138355 559387432 647578652 653459024 813629648 806687665 66807495 566332404 529041677 194642574 5429004 120900199 332107793 71041724 373969672 967952453 553709706 612834969 709296409 244550609 931991466 358321260 880975459 102397810 341000100 778740955 275535179 436453936 123969588 947072882 943243774 977865787 89929492 148636451 677424363 510766949 354398344 775411905 183485253 437920675 634093011 510228356 525417858 474709391 627964351 665325448 221456350 462245609 16156954 108581965 286330073 165200145 161238323 210720568 852261301 648645519 399262305 668385297 420464377 565407884 655745148 308117892 694018288 538944854 245493602 270764960 472078891 108155616 38879604 151348314 632022523 163369023 138052630 983317515 968632568 276750126 181459506 96675310 196476285 468446859 628646070 467650211 224189993 405248216 463459089 443871407 461591647 130171579 778681274 584486650 258885319 796192126 863295145 778018127 302411723 406913423 725452252 263426783 629986843 51181825 481104340 767464126 176546601 490138634 532463637 369981029 484723118 800450947 728180137 109756974 594388515 223448427 360994718 697768924 327294281 902432612 260207491 608348944 441989793 495236916 511612399 255680981 734295285 549260102 207657210 142069525 211095245 629848871 141032642 722090785 200057083 533308425 154273256 198360109 124543248 134637891 485337104 408872657 192757732 183292622 30782053 607508617 584554002 157044682 344968210 190602294 738995833 622775543 403645130 694512284 425031356 486057789 58667329 519650018 377556931 483561508 647177648 653356820 800324152 413280860 67692629 223284388 914544395 239941687 635241457 443186917 659497455 62023210 614155848 156181391 182469082 361657680 288966820 131041598 849173897 31713766 326775891 721131507 227937785 685026256 688126756 723670417 540585711 665062675 876375534 105043553 521905522 413450329 272412426 758666639 487302731 228474736 660782804 660366250 431856268 42473419 186765869 63196968 999690246 275481343 594515708 87375071 995474897 639297352 182188712 181379213 2475720 182702593 51783840 80654162 194504714 686061103 858329299 455852593 586910075 523995895 997515320 608333971 853325376 84000292 411345736 782224067 318461255 880932002 860524159 797444722 545333693 396736773 196034782 425975605 621766549 360252419 592972908 755739906 299924488 482982134 359465648 129004727 454609936 58217051 278326073 466649747 822498027 340832853 174176790 989393083 279071390 366456618 526472798 290801590 964826224 406093765 630054570 235515122 11581290 868451891 52859286 320727357 684873950 56630310 793066564 145491788 33567453 642307445 787257048 195116599 73739455 336227994 257027837 306910203 875137951 807813938 476966494 254978039 651420893 357035137 494284590 744086895 364813466 295879147 458187937 164462092 871555647 508009852 746042736 476922458 729448182 570755169 554334297 1955913 580965935 84215661 18372765 477578669 41999901 883620757 747285121 678474942 734514743 939491444 748415949 443801753 722178487 414032072 124214352 434933693 747735582 636366579 402199130 202098830 272500142 672943483 837876032 235268565 951039982 5777290 745439707 386424126 581749802 521067374 227760905 789538776 622595057 921573658 986102315 590659225 147435925 764434596 400703910 255330008 325771950 333421765 16356706 332019921 651668632 235595100 522909518 366381605 561571568 848202731 843625433 344248407 327904794 369903128 996064379 283527503 276921278 348223534 670692394 430156763 37484359 417379737 277128677 103034409 849384547 321955182 352697133 874748495 126131590 780108000 955017863 30342340 772502630 779534796 293858299 852185827 860615808 78171438 363791768 310327663 663816594 25862570 827538414 896500490 891165727 756171780 463054482 421650108 714966510 174693288 837869213 845214835 9262219 828198691 878330157 712782205 775918021 841359527 474011107 678596879 383956014 517286027 826980196 881222338 953829791 658911177 50635225 190385936 631926193 273284735 907130734 86019035 587761732 950754414 774468310 447182055 738381820 348540798 9026501 440402011 772311231 158147640 189531509 253478212 773688888 607846986 544425762 420350482 728556119 149005575 730247822 262853914 549354447 685428709 74821246 641814290 597306519 467298045 248823098 442208663 277248106 439043470 370451217 920583082 414943047 323513978 96488659 457251375 909625841 7380167 202662997 325984365 442803311 497562655 261372145 177530001 240673933 364485456 570474499 343094826 578761818 965126861 236862829 291952302 696916136 774425900 697922067 514489332 871603088 618291110 749942880 575632056 991830763 164049051 757956288 577064219 413703897 717615627 230952484 503157024 815154750 695928861 97540225 937402160 221052736 83109276 96401744 609294999 495380939 433716340 289725968 48973317 166395405 181029434 809144000 997885965 775531258 114746018 309783141 139637673 261223625 290199558 551033738 810002100 632561524 163127782 349174971 173317742 83922748 1175906 816440073 977076732 513070372 812063170 780207753 821525222 433155953 832783599 300459221 434960280 386604592 301415927 982743433 462671841 287336880 81310092 460105927 392189814 406830340 391332998 906509236 737195120 378845314 407591005 420307192 103464906 797882950 275788207 3840834 516142052 695540400 600595136 994348994 969419011 95433953 901510645 25834669 122159054 320654659 155566680 436372413 244354002 113022462 493872152 639177390 593366528 166488963 654327557 623886274 329682730 627890437 557024536 49878590 660628617 624901883 673163497 24207083 772685370 415416736 922945591 439925398 89497532 558346099 851564644 731572368 739484787 792082871 441241334 577548078 854879273 1864948 981037080 90012746 206601608 202942836 259433238 176918976 531846305 571041735 914455781 217348594 534552935 515830592 822791832 531273797 194674741 121046133 470343660 52963234 824511044 472686530 39101885 108869366 557963830 270675399 153635471 282376114 502452878 125042662 41693958 711082059 660334133 374460614 370767470 754355387 177484535 34279123 153133876 783263998 513912836 628150971 52267882 290732438 700252271 74235890 606421831 125103624 508846514 73259823 209707941 417560413 176169513 428772589 454642305 833973410 256021394 474576875 900616063 633706856 936192915 608303532 805038692 79949892 264973364 937603320 118289818 290536272 537438817 555481689 485135023 708937897 441160297 242826911 267777238 733417711 214589058 868297053 175956324 977348552 329529666 160570729 336134740 360228956 792000039 890807648 658690244 894118362 216053265 218989087 205493622 104761842 576880067 757627211 858521936 449418074 753488997 30163402 255938012 356657738 887342084 235159624 574231497 170574591 425237009 721567668 529250664 63773755 235521502 216745920 625487663 912765891 399071013 14766948 950611002 846345952 573419648 130185563 585444037 188825823 428049393 249727652 195708083 521430417 580992348 349512962 915811850 376872395 745121032 287086461 443311477 354226151 51318307 751380191 925425344 698524738 848851771 214348856 657114976 80696764 316215493 226516315 832259817 345586235 817643417 612126558 122895765 685469992 830404980 838891294 597571268 926975984 362026868 153010105 702809462 224423044 62179488 591291666 346938067 41308121 151478878 632354896 936903844 901259369 179577595 549300831 625645015 379490993 309556775 783586413 297903358 463932849 39140214 683687022 828353744 705716591 183266016 473227673 952011943 442380660 776456001 621608681 167104257 914497869 883058906 455916958 358280704 300952331 146721230 124907449 924644330 17086916 696635046 190609027 315710377 474100240 758752462 388257030 374588235 449595532 470139669 131436690 962972803 649786458 598949425 854933818 866861350 124378527 542298425 786824277 410098608 568657412 411649577 275707645 49247677 586256182 383211617 643387027 92781712 261743463 581262630 562775353 953074063 475834826 775868960 225881686 737405124 116745498 835860954 29555478 455312734 47115796 93403718 8028392 852088366 420899320 89776438 188059134 598638635 700024076 990121700 407192528 747578094 768973593 645195371 24535961 158206262 21987820 262406731 435535064 491675494 86820822 393269993 220696529 575437826 368758317 716057356 816997898 693455414 285742025 924088930 314750670 356520015 535572871 313169401 424143277 247979071 928689354 752477894 111937786 384626205 554256373 541798433 488994380 146594979 976906994 709678151 962212605 810901422 823307694 49814231 533780654 175274178 989884058 342997846 248788417 746930564 122960684 727808939 887306718 185464893 699602012 335826083 942309999 147186270 5801767 116777582 270062371 264606966 46908176 903696672 533963886 226455870 983266458 366990129 580140040 991503118 881521103 524354046 456244586 917348197 370385596 929904197 922266708 943750884 406855154 589970093 530093386 527336019 59979527 17617980 229275154 840645404 675724051 804025055 906247735 53657035 574938932 348237285 877440905 950655636 199147786 772421252 393850011 709375949 632751931 791665747 105402180 92657263 143916016 617368014 477841183 640462489 782417750 903622358 845690890 882000397 946148895 984659758 5553835 564931761 521750526 74749183 629736166 207158032 538110510 864945492 548175464 115069655 792976364 889736351 97927968 119758680 17909496 473350451 466585536 661991434 673305 902414279 226069568 6608134 97653654 451392505 969266780 575893900 710898621 279177929 570497553 95104636 182287711 429458714 958585380 997722846 158983762 82258484 169867931 695741019 149220846 429805125 80289089 334432193 661844881 205015771 156108838 977645442 486659867 114319211 816200733 300765749 905633650 533090254 791485245 599163156 531142400 639305919 299797345 205737597 784585776 509632094 215978664 543214194 886076404 655738031 14339573 242858264 631999042 614562332 708673904 364063035 413205138 2717679 967650563 79748809 916325986 125877977 26991837 442269011 783906738 819371374 592699891 983151759 25786249 354506918 885038202 286634712 407644270 135151198 152211566 279943596 742928111 357086165 816458255 291633197 368368669 569754671 784634463 438978465 204613646 824287478 790085029 814049266 703203418 456314004 381265900 455638063 389935775 855334617 200078724 516654857 680439550 85963643 452686720 592833879 736609435 200350865 580769335 908931218 333110304 254882072 23936452 105222490 400169018 660361071 268997766 295992815 134482971 834779610 472214944 489041592 669148663 793039618 501241210 80788672 768619399 670289522 120593470 907541044 209358473 374794524 491017820 353844454 658790717 109030867 85431046 12954829 315064041 928185295 748179125 984981123 565129815 797412652 269306786 165069765 704346706 30374250 108144718 697525239 704311852 561679854 64947706 638238366 976468027 479638144 792671536 360535011 583029336 103055308 466143288 30518551 359781470 946148833 855382435 419129641 799488177 436169908 332501701 646037810 402566836 919208606 20335154 315844842 777239378 900557530 709783624 658449711 912011638 722373128 754630565 602211973 440581778 747328685 646620589 471629201 334828828 790980529 457699077 428677533 856453389 643293407 412015643 642270488 46260320 405367144 141578139 740890643 941186969 438435424 485143291 42981572 788538427 453877056 263042288 595977223 506557265 676700771 801855991 761587672 851196902 420183945 710728909 822274522 759445901 907948118 64467703 467958227 380146905 233803476 129034043 518104109 317430758 152988141 144586277 871837303 172575439 867665394 373432452 77968354 761854005 180656919 208976874 720962501 354238399 238776820 682149167 411341850 483926164 588761605 861294830 131389950 777067490 639633963 282283526 785483829 153676123 874244906 741031450 166615459 511068595 927688745 61121042 927585236 16802083 449142580 657996952 588457845 862884329 492925885 624225436 619112664 184158918 571041047 690127313 895477364 260353406 759652090 328869677 614452067 441904988 450739714 822495597 520061923 628865451 22900784 411315598 360116694 772651070 789629287 126554453 860649793 33010153 49841648 517215688 394555600 193693957 135751927 614286259 19334225 215963632 475288331 267647013 886132533 121021323 296878754 305626864 750487314 721507258 955007634 16676140 328510499 718171623 399640730 951744436 600608710 366420864 826287575 576414631 865187581 742021749 519386447 205330152 500396270 387788219 563673706 347761823 209079651 424420299 216124787 589484983 714197323 551476003 92993051 948231005 179047223 106059972 984691703 895184775 351836126 948589746 323877629 722066795 12419737 115348088 304580619 656268803 446773223 121655713 489957728 345441424 136145387 652702272 949887777 748643604 200594665 38843241 814830549 941176534 755958220 288128437 554574058 51857634 972658339 379345346 268324654 342412935 533463328 720071857 35904342 631042007 277751576 613236390 298435706 940144170 129284357 793345356 634157207 378879131 446521479 705307214 939815692 841752713 503472862 215285727 737031453 636114968 163598706 485736755 78399092 67687598 574467148 232164612 54571930 644149110 443898010 161530382 187807874 507397088 90410799 65713042 310647551 299397663 830243584 800701399 288499017 31155625 757054376 874891428 392224381 195517883 998001125 848541640 893906714 466229203 184983064 709251987 856119172 478035508 607104201 898709338 969928324 820461669 99915041 56344566 239438790 142244274 239468911 984926277 437022809 178809258 944647076 918592424 290030387 724934303 568583126 318569092 677211563 197638697 62095040 32364737 142538237 600828323 249182785 973899854 897950154 18824877 848328153 583156635 749818005 737259944 997388591 28623901 173124678 709219901 922833037 438162637 316019115 556039126 676702562 559359657 610256626 894505508 89364671 62753586 979595825 609040279 53395419 224498413 376536031 368175593 544066703 698319842 271130968 650449044 172251611 28352032 22222684 765270359 658620511 307878967 93170320 316278453 111719139 40974780 896061947 521532021 376889551 368241609 805078411 829284387 692504243 341225850 601087118 25877390 998147777 461350513 450912825 597609288 395201870 25861458 198976549 505657129 204870485 12678216 226090188 946033869 643405043 542297982 352346128 799362577 31354860 616453543 606805429 809270169 102267429 72117879 503360482 680654157 877914152 44937000 995462564 985645784 122467747 124431094 791424876 232779304 215966697 692164515 805903244 14708721 700533359 162298868 870718653 582034474 444333904 377929265 543711387 423833230 408171466 909725865 120336935 403129115 674004159 289534508 631536197 124439191 437394229 651708047 562950716 462661382 165011670 594210092 743819833 471821877 733224561 430377311 587356107 124551219 716963447 829337866 742534760 530857938 63676287 609398546 489830375 910683946 77907138 826930655 935521541 838651415 385378975 85967840 731101664 470876342 45480728 467529733 486316158 995771372 945982036 295080515 2796871 519091679 511550235 679809044 234271623 70395514 187009373 968743156 67958254 645037038 498458795 801450213 854785295 595704108 297209020 611916524 194726884 990997611 567986154 131892625 591323208 32402344 57602482 712090467 58292604 353847073 956034360 197450098 699048099 154634713 829516224 559924691 32018245 929272344 575791926 998970912 322879952 642472936 763978919 277246965 266845714 568801177 448838342 90370420 968758720 782713405 35833448 348326850 446402291 500591661 961774856 32979336 848621222 228540802 525354308 980469106 366249273 898304156 62864734 824877747 3296497 633047199 900462524 709461888 54478965 452097521 71654248 356007824 17413971 585280702 247830672 492458147 750189177 730378612 883700999 783821560 946105532 985625415 670881474 632410069 57251668 386043566 356704349 767902722 480603742 545877476 322659732 626004558 124992345 706278760 159989194 670976521 874607529 434214525 194826885 498252680 978267416 324057515 459053551 113707173 652492368 359671612 646615383 64875325 793707362 680778688 57019310 558655920 551327298 858660489 378831371 683244387 73781576 194369584 629806119 474367809 513805744 957372686 575801570 27918902 62326299 48011716 223119548 674238387 687508748 640865716 225595996 460573229 374545260 456789381 39794957 922242462 727581959 487948194 818652476 804235779 980268301 597667004 272159484 359505884 975293073 62682180 695456898 588179118 144701197 597928178 636783784 435243396 957787869 768687425 39435118 972282218 724536255 838278640 889943157 121720817 506126169 306330242 734496130 912243119 463439795 563212223 918782209 749963963 133973433 356753969 884199551 110100277 177429946 850871976 609062191 640874940 427158508 390855351 660948071 546156022 248751845 757529908 401159712 555435276 206709283 193137851 4667257 21662251 578198662 503642156 310067507 928042244 286373073 197110057 541393462 87752268 780868140 741042329 568718860 652979773 636941477 913904424 695599457 771903251 629459882 12601796 109690505 696594320 788043408 589680161 503133178 345745785 453281552 546348342 95819981 673334295 710260676 4090302 410486593 988709047 55371438 453195449 435775288 879113514 202274738 540238824 925770425 977282630 934852375 489855572 62184556 880374371 207274507 507429575 79624737 684030942 915293980 613364305 639890761 166136217 637117119 504232133 841345403 844690809 596885452 372803385 308982513 621598951 403856896 150585994 647288584 435965776 340855417 626746325 595696324 151873701 987356222 419053311 586086217 329155036 778812597 173479215 150955619 14072173 359716907 276893518 566440703 861892053 810978896 632158350 410478000 980231190 496716984 404777696 37019947 172556341 622851931 645212540 261963467 313545147 569983253 654995293 682481422 279614517 297148455 369600962 556872725 234434484 421254324 871872175 945937960 202427726 836763461 226580330 877401648 729380763 243758406 422084350 403259964 526391096 401273734 926681275 563711484 301347656 112730811 656558772 161339209 414243310 871319548 609737279 696712347 19949268 94544197 342234233 229774737 232934823 842260470 726450880 37559661 838693016 536425300 892764983 123965333 117579996 55997703 893330245 590541332 48446253 616312731 904364054 127537174 425510472 853220607 549676312 874868335 698886509 834395400 701732992 155416597 198604002 418748399 103976387 476530338 599155824 821740751 979046429 634045139 731242980 979221544 626187021 954297611 167276943 803764319 229238487 554560977 311130823 938821691 619000065 850900045 457522276 998784362 806355670 650532559 977529668 187589882 548535270 13006664 295755975 644900832 598997124 633135568 336765779 739472244 255713351 313318174 159845073 950505459 717909129 366337299 826086190 993408764 840149227 55836463 410066651 345338388 538773967 233160474 645582158 469082914 672020700 756595997 138111 369842931 497585534 961555110 913800812 197055927 660966244 377219272 73727381 551733122 405048576 432704184 750903168 385326284 956605450 425534033 20274230 715092210 654799358 988563601 327708612 427827378 292582553 818888218 440787644 369783987 461898848 31441330 177699505 523809787 421986585 404993731 358216382 705441911 163495503 375444956 206834688 808195958 316172754 994645806 643083287 431384110 485518901 182385423 691952041 931622454 810709327 968967802 526813407 651350026 534928570 753059214 776686055 705566091 128846935 797627915 165295984 289523836 507857608 512965592 930143537 441507078 206974965 666513279 426102882 219351093 31956360 171426479 292466752 49373816 389267313 344057018 399736462 430238245 860284002 298268436 499056655 482933234 653359187 948996058 138829069 797338493 55324415 992410184 435142613 864337862 365142630 624000322 986468153 342058928 377461577 878983628 965332236 391000195 199977905 446832530 786686633 851341933 417786729 811970913 793973101 846905084 482354815 989644716 835104569 499252133 234493383 855510280 97188081 903490113 788634456 793567920 135134463 114482571 279497997 614454529 153831376 979484067 902492933 773311487 217876566 721361037 620069923 982640591 364674180 756848819 982760590 52137275 825656277 637881183 917634098 861553713 802982342 959802178 329751870 410631236 581143640 874675440 354424484 994666282 515850895 347068257 449492125 743309116 525029109 302223474 595350306 887112697 498031127 33195362 876364404 178570883 144639239 984031574 60993428 605898784 578703320 642871253 171552971 835162810 1524774 371766604 425873956 208529760 19682187 394493835 449352685 159603907 567467051 148438085 553131322 538634681 32988457 373793172 340745826 665248190 320582959 426156148 695673216 632396142 274470635 267606852 924946675 955412748 55649676 246971464 721810398 638550271 352085321 546500137 86424233 719843919 610691546 925506163 494296958 711517996 732738813 584829461 661440205 215781736 25708786 951953893 511226312 939213560 607211264 814775578 197107943 863530102 176809454 106594256 410413670 192613282 753628810 184180103 300157634 334000093 250199590 727332772 480360256 314469036 182825238 718588911 781014630 853381691 948394291 382777620 226884736 829835735 410239067 231927074 685825052 375052403 995836654 443485711 542825614 173949732 847858259 682822705 727815277 947369381 423209329 255780550 262046228 648478932 284643638 81805421 109697058 806061875 935528724 520466347 159497210 396648808 852271487 417157992 47547460 796143293 486849136 816174959 601839466 289465248 44486117 824334065 61065244 652946980 900868190 471923458 991454669 592660607 167320930 43098395 169533235 331733386 55263224 503560599 692839627 825103172 493511470 285761078 823054162 468368719 227422358 649973916 117174861 873228658 49129668 547105491 47039618 252675605 862358481 763343301 968344701 864737480 117743067 282942915 636163852 998263996 289405315 532960513 475323331 64061256 514883181 284191767 754638713 871199333 195622851 282900097 75483849 316055859 88409267 25972000 719656594 629543538 409005804 915564728 196000888 106379530 840720677 44114544 768680801 421892227 283028375 745909333 70615032 563436941 482736253 915318230 774211885 743358586 998778523 507743305 738485938 956966335 709533620 47523173 521433984 954472055 874989331 710813126 950900816 179325152 307672067 516844909 513876003 963123931 95260759 638483517 836978875 264994928 180390115 149487743 214714655 259275848 731009536 564240735 525074971 39090225 296766476 947020652 380680893 970965918 318191080 705526044 201627866 173325348 680274296 448704838 965311367 344336383 24493095 534680486 442911648 959875723 484374880 69623132 753468996 450010314 972681494 729019245 360181590 762519525 269693501 688613185 100558334 595362723 786305358 91761955 177033510 325335283 378555079 294558404 160405502 944908392 492019625 511323065 473069177 127918264 101431800 368191480 265057742 56154429 519907135 412699231 511110391 241889396 175241993 221929773 284295477 76273792 488335721 156547719 913686666 904773031 195966835 711562484 259335741 233138900 452086208 614902754 95495002 519076372 682581742 842414111 361452847 722178329 692545054 63687264 953778129 202000314 419958133 311396285 393792661 333385329 355402395 645067827 640916631 356774107 560422719 150227745 214593334 760541244 423827344 172808651 897967766 463346168 668425925 55979995 742405660 508222491 694074263 757575131 958453494 393730002 385064130 495900603 628064913 483610096 948381576 757757265 294147873 117999978 955034157 9371860 974990364 561346523 52637308 969055073 256736447 994150401 900506688 305831799 843989128 255773246 531017676 587016058 950981562 927534872 97434740 912365619 858131420 354627513 621696274 36255054 922061370 58279023 638199938 998414298 332956258 720834349 687560230 537071309 488909481 588096009 949471330 319596414 318989988 301479356 68609313 1243177 405989807 595311141 488576590 561021039 57420137 713898182 249706076 193105363 857052214 528471877 868705983 457760317 317598140 875490285 816854129 313522811 412976486 175516202 512428654 593807547 820739812 107176721 565922872 57345299 288719529 673852373 336690259 491017210 713183852 907130451 295741642 911473356 408492968 354691463 421772712 99348041 635590683 60920341 763960704 55387926 757016650 835736257 8604134 436091962 334253564 723382519 230654452 329043875 816155323 755778372 898910406 713480863 160834134 999161306 114759678 778835555 720201570 855404816 979523136 925637768 429907892 966376416 283840439 981693320 65030376 552457320 666937487 88421189 562415838 867065450 4222329 291636611 627461687 376557515 614114346 900933737 743399132 236871447 591125979 253144325 646520440 915416572 748261323 430266309 731045625 407444426 549621176 388932862 837690131 795135994 408572522 992825704 15123645 377578660 431038505 462784671 940973489 911813895 628209985 94758308 20928496 201863173 243861637 682327387 830138428 637352612 761279433 156207371 782762653 40485006 490362471 651957985 583554269 989598353 782619067 213303404 524259084 124404000 211860391 614620962 612667388 896761553 900726544 905379034 601820101 63074525 655600735 284659793 760747075 241624484 57789440 980740005 386173843 473547558 436920550 344651996 136832154 223156618 401586437 634508894 106548094 415368091 772658135 821349751 231394858 967190854 493637848 908592343 122503374 248856605 129792010 561604881 845794397 890642391 997865586 410317087 589179150 734701773 231029401 828736220 941226204 82660991 868789003 590329737 565791750 105776653 248835803 446313545 203461519 373779135 700050974 767015588 146286015 866109054 786456683 517966600 44356768 243205720 715354978 73260355 159410306 448326912 673242402 875076362 476957303 66271051 104515792 389561462 450395863 776814772 433768727 784514 881648574 505991128 799852707 140445582 952241033 15788283 459570341 564989919 340651357 168424066 456148306 662360604 464152480 164796279 197615204 56939475 482029182 277853193 752347031 860598770 903796837 750112264 839323437 829064014 841973897 522833773 392520299 784823071 357616993 612287696 68279834 700903810 50794792 184357360 773641990 972070390 239724637 251336751 928946818 481963487 841101379 787548947 797736163 261850375 679653218 698192583 640874496 228828696 958897668 359531159 946571193 555905827 831196857 233199480 869324909 523350044 176684755 462568061 808139138 823481691 283222251 390598499 463939552 745120284 252799834 555440390 832319094 16938752 450841793 718626794 980197044 765755530 122566785 360758963 151250192 37033891 607809348 457564845 843153281 446146583 970822514 129199173 926644743 114723094 354173885 908201357 357631777 81893299 794712982 469944508 751662165 689175912 216203701 488512172 941369516 940360337 939391637 563006811 994083634 922561260 892712181 239859818 755778938 157196831 448104024 115074465 305909273 886104114 260269446 854669673 840852263 726580241 778312969 332823376 929427137 789675531 832538033 990789257 243417993 253786198 131781904 251241065 915183908 877843848 393608191 538321131 248020155 191056159 190392087 920207661 985573243 234488315 609643833 411329009 364704533 442004191 424889863 152915997 419174974 616334067 989520488 392514875 832281904 204390469 808390920 6481402 193017384 683770947 19235541 310693035 36168166 194080834 97318787 18278852 170705456 896932859 660634633 793848417 509880399 124270600 751457570 126111422 57729935 2196075 579110349 804683454 808709572 521301768 995333582 879388775 755244480 999878183 693969963 646151268 230160350 792441075 83568047 772665474 535645818 666182141 25376618 244977203 856192118 388332985 975054638 127961358 960186295 768170751 532751380 207508812 137998246 26977676 503592181 13425741 152367024 40297087 983930610 451109137 220578758 624354012 443871213 321381568 226217694 801841164 27546893 777665827 349235056 160015451 847880510 540893992 896908281 632085369 550991791 428033377 804751740 422884090 673705554 861012613 741948412 665017046 190917215 298261998 274608898 225040873 336082129 895191578 873803805 998718580 128341735 407469355 434476894 338416794 25326757 698569063 200499160 380824804 355005776 253638584 683839014 303848638 476727798 900418092 76945125 997832951 680734692 264246902 210670901 145626693 97271086 81098347 630506300 451585471 498509610 522134663 18723491 15355745 532543221 183301222 486107415 911348875 356465644 550516043 443926217 951631490 414910516 948606108 13220079 196971246 835885364 768694883 815164481 681712219 981784086 822958543 848028028 394958008 668421705 37510577 250240482 640256474 502394881 15070464 89117624 360765434 126706870 389951829 78352583 276530739 497124769 204073839 763604188 503943429 331132994 867644849 683195465 813994709 522474717 232739999 305828961 262147690 205968631 952418149 938597375 417682802 396292574 637815376 233965568 585956603 33727263 84622162 308307396 213193722 432371470 149815938 344554929 920615367 766348609 834846362 306125232 219654303 531040533 177130871 118282670 138660897 923729960 355660445 164083741 383778770 187771101 710782897 645586544 708860825 709992155 170272509 307585954 541168195 495997326 669214703 496047792 134191616 591982757 614968729 898284826 71361764 443902098 809418547 923887974 885274983 472969997 102806677 375613341 198426854 543709585 286155966 755816396 422074399 178472926 373290064 642830469 538793401 843457141 912044048 320410971 819831994 658935071 528495467 998702954 257565967 187450215 769720556 867706316 228677639 84454171 152665287 833715236 345259736 392421071 716370258 294313752 664814873 359523929 770992006 438074063 982078790 459892054 197996930 792422775 203934528 350492068 63606024 762924481 984050890 686696422 230397951 528725347 642100749 437156356 65503983 706833813 391259669 785738664 30503304 965587349 458538833 379591361 587941659 547801891 456710679 38615556 263221535 730170117 796375325 230357350 618698158 703257988 338318849 215253155 207853573 386785006 511780291 367537083 401027847 20437522 501269318 442199919 429896635 898917575 646317522 664681416 62298570 30264421 452307349 511865489 502152194 889088073 763436061 268111832 613255893 775072342 871067871 933343345 704397530 318529391 469532084 629771891 200343371 20836350 841959767 968566712 868339846 445339248 487943656 75662433 855372429 121966519 362562923 536838993 124774789 403802567 565905482 351069869 817778746 580418585 248762831 110633058 650646682 821842986 868755627 612416671 269099574 6477309 265511794 364309078 232916164 674962581 496372509 295512000 21058207 181304956 284022662 962599126 310640965 345637440 625153007 147149784 312326616 216314608 950227836 885281226 735797662 940953251 442317748 449691890 75751554 7242481 968427268 63599964 19423120 305104248 840146748 184469846 401818492 155103832 91730447 870699508 46562076 719555767 957984663 132010381 380537833 752595775 838594768 500091452 667480195 661216411 163311129 926671968 543452458 486529533 159001014 503288604 558694469 62155675 347594832 73354456 123834079 923935021 916812659 550753214 13452069 520159857 132745742 253899325 593257193 296584616 113611511 560142218 580373026 348372502 719278949 665382426 962597226 821791365 712674164 61953066 524437119 659902403 574876836 303064119 816629442 456012575 172501594 252683142 396919227 667331824 550745182 964224669 610945427 446951694 887835484 29228488 832171416 947678551 348177251 185136021 193451196 220332075 519187049 783628120 412526615 58220785 95059140 930193320 744413537 155323536 588412850 551097568 843977081 223612406 531995602 860999071 325389536 736325269 200240041 716473672 490885182 141047521 229758495 653103747 216561884 986054867 758062335 355269562 669654313 717911657 12024698 151157149 875470134 664366116 400467108 787220382 225960249 119178120 529650166 139585654 531854350 250718111 442286539 121694366 540286385 485857655 586813411 767821527 284740037 608683679 257072098 67338403 158257168 895185838 798273490 909768393 932501244 974730940 736280221 432857557 530937880 130839015 30726292 591426197 769032342 172059600 333308395 586428061 566021066 398809627 238868282 352394436 688231857 53589491 553171453 622455717 284303719 598789251 63292181 170482719 755500976 355674494 692606278 383562198 499015024 674780055 628135351 117377967 152787507 593963274 322618485 359771224 387002022 207947282 709785839 884966077 128939803 781333360 192885371 623940244 915677706 989947627 139427024 538277075 338512522 42524106 610456202 226437172 158389468 993774940 73161130 956732344 75765473 998517616 125538835 836587297 202677406 837352157 259459086 802649974 175087295 124216316 619877575 411853699 642791186 19837224 571026125 836918870 529563912 346581317 64677526 633455555 493840439 74692663 399910137 75503329 924227290 11465062 407569330 889387659 980495439 632938048 546931169 47499233 734057880 758943415 806129803 372714180 731214299 28140991 29796120 986166365 396015842 68729810 620756947 134845846 341013916 764671852 199349357 109372319 498016410 638549902 707733627 432096363 909963411 217442879 261104627 729606960 38286048 490233094 281209779 3650795 730144256 617422194 380007418 82768090 876109334 350238610 816885485 345981696 646296422 68957309 893714195 565818532 622160091 798963916 934387162 177403602 564774532 811360539 266085904 86352600 993058323 280298635 317422186 944525514 352848221 363575107 622237696 391916032 913610460 986684650 892859087 362096531 536961584 121368367 25018422 199340771 303658137 910947394 55714169 728931347 638564735 203764568 845868610 788236939 224714475 375394602 905120027 282896246 313266699 640314486 831009268 298625602 649912754 802777725 888660643 390362914 110566101 82766212 385854303 68748687 38296335 631403859 178999621 37080771 501657886 450915257 671067348 176486460 265648483 529126149 265158256 285713983 674391654 972470926 672798434 262840915 657486672 256223533 257101270 123930050 877291632 24323518 394304603 20835867 352564663 885412771 267607911 639420851 197946683 877704512 3383889 383722015 889505720 11301504 898530645 320276155 529679626 693753167 81320468 99223846 907766452 66971677 410552337 283916740 283966556 886157409 904173877 106668603 404550732 628273940 29291595 527355382 820392947 993412402 695127429 540539557 899183202 576488509 460666613 226782907 578520272 741960377 650692885 328332783 273243927 547959473 470901056 984583611 341717044 912804401 658666550 152651744 967235274 285554633 500766364 940929760 674918304 896829713 229842297 904199811 864016414 672496415 479742651 609782867 790666452 415238930 963023280 219635743 909171700 864852107 180594061 709545596 415079891 709437999 134896107 703395135 214019948 602096166 435540804 264633348 138030300 50074271 452630394 616349866 908689383 718268490 495427153 636835797 929403506 322424540 101881328 692786027 686165767 232008591 510517605 518097176 185220436 820751263 295876894 38784714 654283436 48533710 691212144 692441397 57527428 286603744 837319443 854558287 548920567 866973984 924230051 675492309 508922179 301706970 128628769 693973445 638551626 11583455 495056753 606036194 816736530 349700100 731035354 406966580 736169285 189686434 136913545 323345541 48463794 303654168 301815309 579005156 684880074 807512388 453553372 892625702 368750884 756678670 861938893 769068896 541885433 851297758 439598749 26303854 268389288 195680545 211992682 711624048 180246579 672853191 654319163 939526215 128170433 212033224 733957749 738256412 678369050 890944666 402281575 587407578 580797998 851647933 782668480 116244143 530886286 348165679 89568787 457254543 411478001 377770744 43733338 886603953 214446257 889670304 504352368 339030288 229914699 2126772 901454998 107731435 139686883 335753541 506838767 966490693 171965118 456088424 349299459 700585574 458133189 780144055 213012800 71876696 531323656 731275214 254749044 557785194 274708537 624272335 764051796 872503217 865150765 322191071 655425785 600073346 403205983 525455782 228269918 727412474 70864237 96336595 537343715 21907830 305171353 869333910 73379277 946549019 294062665 493529124 275364547 104122447 901202055 619401783 861987667 879601470 62370945 543774603 983632491 901694550 605015562 397108834 638245600 565567179 946875159 493140481 507720682 897127700 711257668 989159217 293067174 911672172 197151053 673704127 336122771 859701330 252070293 602785788 996248853 897567497 648540834 719449917 725911542 126738456 470928030 785729628 860549344 203349964 302493400 98939701 34000356 398287537 955490881 557374506 561797366 700088861 739423728 639995040 854609006 606663845 410782622 617441152 799298952 911577254 238236715 593593783 288232677 456321725 98491927 569174198 623378184 436141135 737870346 298183922 683899610 571810818 262624076 343113829 414638631 252217922 850640973 3048715 558717471 549801405 744507679 298879846 416405462 481684967 316155383 65919739 534275779 603153783 434252207 837966035 501000517 765114088 886807623 827936763 817316121 101167353 830063456 745269252 196952549 615950126 543725759 201900931 845204401 515002444 690894544 845234834 52797289 160580321 783521057 586063181 926115676 996476345 212888802 856562262 67476928 48889450 49436012 370746194 30173483 45618634 22728887 765892458 873129243 303512179 983091682 250871243 43822192 96553286 929955246 900275238 627459565 594397669 566180099 246192945 288454842 687706935 477958507 888408867 513874661 539698151 825021330 569391676 632144348 351422182 88710092 789247291 688192756 264061413 985336463 270671846 409465830 165866972 886393076 515321222 535732044 774400390 146045754 872205672 23622441 202847714 324341571 217107805 718472542 469460148 806278934 379337786 539872310 378125569 516949851 58025561 827272923 377013143 919404514 955430935 37170654 396729731 999931932 608591444 375527859 884232344 227368352 736140022 26756402 206476271 961917096 990717798 371095064 580680289 236105361 132640529 606687620 366525199 11805791 114009576 434229370 546803675 153541942 677214432 831535715 829775340 995807970 717710963 497127307 21033518 885224528 57193246 99767202 18372559 969877523 406518753 749701692 306824900 671539424 849196738 981670737 355761730 309657106 101956938 693614013 204674885 796846119 460818694 260500417 735655692 479737664 680820231 900244864 892211098 649328549 112541026 916442499 192273975 344043583 450183601 717231414 322256366 513065757 99792785 628131688 187185165 999189487 88273954 675639503 234918567 858900622 74544522 406494338 119923989 1188210 907951986 22268541 962065009 613249594 834894727 848898080 518118937 917647912 133322234 540728496 297706034 315149986 835100673 392163797 390784547 37561267 70588500 236149275 457766165 460199559 289855920 512811889 874182778 576371186 796776280 197173164 954157187 131210986 679720335 515195653 8239784 164733193 535225887 834401943 735624740 292563724 354648277 131898082 576483959 93338966 261561346 563690059 545037794 629042798 10888444 561094553 711924206 770483580 424079003 925853818 996841958 812615888 851173820 719309308 71322456 530609756 938689985 102734100 427661975 309640757 606628112 760902938 680151356 698853653 161253264 92936267 949697185 943691996 651803951 911810630 236515429 268239626 185184862 199279760 66293995 910676807 522946707 333499152 591249370 334401500 918289094 306682515 830997150 220420151 865422836 445488969 450400486 655909227 384607135 114738502 421689636 738350765 832970829 258841346 539459856 842423256 969182725 936887258 942685221 667056618 882754261 59734156 542784035 636396933 217852750 434672063 261612427 351511919 129580294 953081465 71128614 535901458 694829333 557673639 763243903 39255293 976698520 257900952 106034532 895032161 620760370 592085634 482434665 823996564 316085638 99578108 28145252 34162066 795541438 707516802 532968178 663635063 739358215 672211957 330507761 391060230 809976595 211735576 280916996 735543589 679811221 880448532 787678994 740178271 903830472 745048309 550218439 185794400 507621353 746621226 819558674 512897149 28152504 112420105 55662245 820491817 607166715 817148744 470337913 156897409 95501564 888626053 586324807 811301569 726087430 361062592 417897487 153128909 631276523 352330204 291921557 530330793 923286913 888075809 38155487 599036161 154456352 287801277 695415481 24865698 653770278 185230398 19532337 671003903 879388275 155048217 743414811 532431277 318757613 216921639 19337869 677002471 209139197 788032547 635189604 92931850 676406289 331089709 877449406 57318426 516532760 476072778 350737790 265459772 839326729 348698337 273468876 109121082 73870684 756535615 40577938 73695746 814921615 769563924 652758272 971113255 613904034 513875188 993997576 804267871 673584027 474329048 408195554 659079939 3113732 177758106 948025738 867233170 348986216 295111036 192139325 147469358 68168153 730701986 149853440 855274525 247379053 545409171 360507417 730405193 863191228 178766268 209737108 800162497 654802532 124935149 899532223 318614326 778447237 709455065 493365166 789569407 238393670 76323483 471602616 759557397 117344846 190639148 287780343 217902231 339975499 751119342 438730444 205403720 777969007 494710820 249984858 282851980 181256941 675627383 619400198 643870318 806748545 262883187 336169725 31452189 661907173 103187719 773794478 22113131 48009053 108466953 746034252 475459661 731605036 36713136 126049869 968110941 379508253 175647768 910461165 734555739 214033915 62117569 967624876 447226536 833637656 32396304 676805836 635296713 263373770 590843853 951158740 145377770 483364841 683872932 789974032 822221400 103808851 920523428 254470158 946629126 206086761 484001731 549935906 31709193 767691407 271784535 842010083 929366556 573863599 149172638 825541804 535288605 210507191 939375159 15818780 857763726 656603926 382386343 333288342 339993109 571003715 969914326 159363522 623447548 624806966 105705359 1430282 429087665 329160173 195294979 499656222 782508871 210805481 145582407 938572912 624118516 799509678 895472081 433682617 45568401 994949190 455407871 57873266 614325533 461827263 875976336 863096668 270702906 967393704 481500712 907348985 804897711 158754200 179928529 912999440 767233764 606969512 399271541 737841197 352635497 45592308 203944549 38832926 780138351 400238877 509994965 615201911 589764941 202840777 475982685 16556815 252647420 266117922 82953849 333217665 318946460 957615443 465270282 929479852 319192045 244493583 938798804 162179123 67869399 555431178 443478014 839452414 20646626 468615037 218553749 296287671 847614654 593095334 800685832 716184398 407214781 277739334 450960813 990506870 295574868 694173985 419837243 662476581 877630366 548556673 694601294 200960792 276528601 168010164 981149927 460484173 980272614 864147337 555330281 995140742 408341965 676995031 594971293 725072589 344111159 53362935 977823023 47704043 159878386 96275269 137734958 838508271 324199281 488568738 64899856 256423853 952325962 504119285 768721836 761243964 480985782 849721765 19247294 854325879 377940756 569084961 673907558 125631101 724929382 313961304 211774633 243603250 892100306 312881729 163548655 759420348 674714402 232399701 834861955 221693702 841649476 842288400 578967318 867870784 201875916 399133299 920567869 853461853 804338029 621347717 264461038 656101779 762853764 622841805 452032007 238023135 462957709 366211290 826856391 573544318 819389611 308599996 483707987 937884277 596988452 54021768 803684915 566504459 117611491 146502871 261109458 362619721 307526645 324025415 617206017 165476225 690779148 929009145 599761268 400809668 847959039 625847313 649325379 456072810 420454984 444748346 516163691 512625038 814642308 17970207 147702347 225393040 423339511 27492339 279464487 712084113 607534086 649000170 337434025 97708538 485119674 139809214 586198363 244581621 1513796 52212011 286816045 588805874 650324595 235618418 957498613 392346660 496711487 346828762 377291498 875412482 715051330 200175402 402184233 509016518 944794938 440376881 704042289 14995697 956613513 210945343 60400742 627379141 16485557 177334697 861444753 613321162 905102312 539939912 672654174 924972105 66618224 839333370 430186972 579275476 912141120 950295072 302368001 846845372 208781166 427240223 964057636 901342873 108815539 905433311 375567233 481712327 932567278 951401807 590121145 711326691 533048225 558137567 698409295 448176209 699784306 185983748 693689132 846328761 853594028 433606839 364916507 497660294 672167100 405639414 401394510 991964006 223891124 958477122 585912279 809937357 453156043 445965344 802857776 328881265 346411226 797192088 211429556 207468751 545549280 113950649 18098467 304906917 491977856 667464467 296661794 454861942 931250046 937052475 294583736 832696329 423028294 236123466 610254547 260140266 429108581 574197343 147676097 566223080 703459597 591470616 319641527 933519509 172308886 232559901 379797070 567773130 222910967 175737238 6169600 525593120 88483409 41630127 423490735 781046135 756772965 709917211 391797791 995342451 633895960 414139534 130252407 141437690 6555638 636336194 251576517 666165431 275630509 772342899 427711863 325758362 177776781 455462627 352846562 517946454 597086735 239227991 224346046 353289954 184514635 729974551 447372711 734535417 608704640 411052914 797178270 843377306 826109328 264874040 784324743 467117704 415223425 345872190 882589609 403903690 304442621 252613598 364365617 173828908 264869330 704582004 203130543 55264189 485757812 223763938 325319062 171270992 570194550 15845900 340696512 526936059 632175125 584655965 405797353 48732058 215791277 371713857 131003951 443965005 318401089 948289961 841729177 729622261 261741303 701265290 612628364 138924987 219004314 610916446 73590359 46948490 368569367 760651169 196946857 258807184 553790464 485403989 220994069 391663041 816339212 447258239 356819605 573402452 841384853 875162535 305315588 774658116 46264600 765277532 854334115 868084432 217366712 832397486 352977557 305951739 541121980 44374962 546362466 328176652 281612813 802293250 485713016 640325903 685401273 733608250 999756965 817836371 742976627 658496892 758911646 176942059 520010256 187631597 222169212 356084525 656284939 61077814 409387834 906870069 927915010 764588035 435425592 656319587 256174902 110047623 717148347 879556569 875083535 758791159 496930410 969567230 341534358 450406154 751746515 674461949 225039354 841928320 58710500 344569159 99351308 3642520 482567026 546124813 306681794 392169111 330513845 563038662 924958391 264749384 936706250 955751087 225503657 381898615 666737200 566712646 314259962 759669877 172734283 903021263 557636400 211878039 271117285 949076943 819093878 798673847 878139560 565117587 285805081 363241393 593292709 423910826 441420811 65468647 871855312 949506663 729596002 353040574 133287041 708847456 827775706 420056095 367251444 477276402 324600399 224485879 866775498 76252602 90409797 494036407 556627078 182742813 822967904 715931604 346723089 84046273 913650412 948663880 799490359 375329298 184517462 855879439 389364264 942739646 864678832 192500907 481242360 805272377 325392945 836094625 952388894 574551098 472975283 441644538 77074169 510275132 427577396 671760835 141305414 716938750 104578901 624673165 343006379 982128387 762626270 985881069 88651312 783512595 346661176 711014141 905895873 818370488 573265393 358447834 499810221 526758594 925548092 35057188 531683882 69864644 128007534 959922817 963818958 955215508 94847874 137474841 521722391 73056975 31421846 321740059 869619173 378705490 26301036 41369143 866616827 299256002 679883498 816023331 556438401 563322630 425939098 785079319 164486277 19353543 674839595 746052432 988871797 384399863 254969326 667102608 504938150 28891975 492596825 88480412 670321361 464740015 774959240 614278589 758937488 184583402 24722103 357682752 519530214 715394807 871434441 626739190 358644404 947477657 150637252 813109685 585662277 990892248 611860307 334467028 247252931 575430782 319600707 69070003 673465535 908482715 697153798 555967793 374240429 446887682 644700979 481460532 323702885 482876618 959402755 944845349 176826788 90227917 176024534 723695473 895914377 766749228 866282156 750352649 283585304 728526025 978252461 772087779 59764154 899326411 843450274 810845814 112356283 145058846 940170873 475209026 870527691 261302000 549258180 339528518 294131838 85845045 279999546 809988232 949755084 90198820 275538229 973001873 688453777 104584377 379056435 108417262 954197518 344802353 493087830 78298544 719797606 629722000 820296932 44312045 501557538 739231774 343206343 260740157 86764718 993580261 998785293 708567357 634877145 940134709 438308457 384352271 906448985 602185505 732026800 487926488 94159429 170889216 534625118 995961665 958947993 596486892 937112847 614155511 118805685 521191750 139022854 292372524 462274014 414678320 551942057 670151699 235977148 420428817 863349762 823626087 188746459 523741973 402593344 170892005 996459306 932681131 287614772 884958669 434193022 421132293 333312981 988119141 422280976 571879323 922475452 729591414 764901371 936372136 733851560 970148301 577514431 887907244 633707004 554966715 218186433 1882600 638401340 960209046 150912968 340177381 82089108 23663158 443717250 370541293 955110993 405573752 657982461 37312144 308174437 659693759 989025582 374862625 487583463 707279214 376201581 836241975 747789969 795828335 816550647 521969453 511654720 18818479 769224043 900885921 786110072 107133343 673507406 335305208 303398878 942476725 524321671 790722521 852884924 628147433 452878819 426162862 81552256 314675256 332196754 408993830 19313725 101753637 188795048 310533814 755514664 638070323 893511581 531656211 903677468 587911532 222614990 970922425 107813911 166763741 628600825 258871143 47714747 555111703 480065733 448433057 96540110 990870448 526244664 584986157 311771066 873853376 189040959 205691030 226054669 217797221 103893033 449887404 761354490 24766783 395123500 713372418 52575447 804347636 609088479 463774063 473779357 777381293 681873598 435421070 872978027 416643479 969298346 368130878 90088451 377394532 846712422 593693474 751749964 190426823 325823771 871165729 291425486 156161788 174776533 117306087 835826745 498753853 423393795 88926307 310090462 727409486 747023611 880534087 754364980 987466226 779983987 70962827 225421397 659284851 138416649 840012523 62219390 404203550 137157821 527271780 756988306 606257348 490225010 381803195 774225560 266828603 296845680 923231990 964199225 394600667 113437413 305845728 739678787 799119106 872592223 383474057 70385704 985718672 332208211 294414532 289456511 816846700 241943450 896487848 161511298 610354941 543575535 547552784 563511951 488908977 215066482 449816091 967645352 790079353 197853736 357408940 714964978 351123787 11165816 504792043 254680890 852134303 518045103 731081666 176472171 55385587 19244157 378291808 760559897 697097799 146279286 59844282 815087865 391729570 538262931 148060933 791025766 727676555 850442926 536146237 958566110 11508112 320319497 14849442 813474691 779426755 237999304 862163766 276858267 864061751 129703538 934972480 963587345 806215559 486024564 929321675 488199409 353241680 587047326 798193448 399891439 707823539 829871267 363877992 449647841 775781076 262273182 30824162 172932929 877419101 180730504 733978803 987084716 914966779 909513411 445809721 82039397 725524960 87565202 985169047 699176402 231991616 689327006 352247349 11003134 647979220 13545587 896753981 534397974 608004698 555192576 405950495 558836460 6316050 745950747 433014797 573565303 919840067 581199099 261709184 116770385 319327412 470094780 637955249 512081720 591348019 501036510 289824801 347735437 155283986 476871878 902393618 783828184 329500580 149616700 915001355 493993794 572876229 105894124 267139927 729905689 865114704 899683045 265299847 442048079 510862758 718466077 657350124 406470908 150498605 888674026 11937566 925575128 159494095 919417994 783212407 713271746 602781303 439735708 846279577 861519163 599488152 508379813 316127972 704977643 811473061 814430349 11130880 180510747 489453722 200886559 728740698 478856506 290598002 865842060 724047262 717985881 289114798 834261737 272410690 583471534 393841364 647667372 282181116 991463957 44759534 835066163 620572486 763446666 619339527 595306045 652622561 716020144 653645746 745905518 224050766 965391949 926011523 444500176 803282519 786656716 596397459 695331661 638301572 397443001 990699264 416171318 316717735 536545097 849267050 466151103 224490321 977571279 913804408 693804672 834518106 394845512 425958225 846073845 193038941 407829712 79137060 90806271 851174457 891036971 851437984 528276834 980250001 835776317 139956604 368967493 547526989 656485010 20445424 362419637 641948695 994058711 923398202 407342625 788329183 94443870 339972635 341178335 631945560 625140127 265048151 713418918 411825272 708489649 172484665 247858450 986136316 268044245 345858828 226106660 860829153 553330156 479422115 253481151 592465644 471409148 923188178 310987820 465197348 823244463 792951538 658531991 184619346 385591763 937693793 437577359 896120456 32172763 347104512 67147402 140430999 793594204 392560819 796648799 516978327 132447121 889766629 635495626 870753635 982782680 229659393 447144939 309696026 716153395 141337338 812556743 999131296 845895368 508825540 726449094 580701210 909718113 83759064 95441459 196348790 163461613 743866804 645205183 508640225 270248445 503116377 376853247 694225230 772184392 448964043 195394281 700027638 773574439 949921685 937403227 643453906 312324121 339624258 839726740 495299363 946099265 147679461 189177529 256656619 928672739 372017042 499415634 27525233 588989419 462187490 377796810 536310465 689303141 210073715 233962738 533117226 335366918 353713254 999286142 996020158 774870434 798600160 895996806 137947605 554157235 68046473 773231367 938572426 778140633 444381712 657083744 422661948 405582420 124308644 707650005 425985551 83057548 501128060 719531536 123156073 610423178 935973713 825030811 454044533 381612924 36135647 63063399 268846243 866425909 648144232 623958599 518987302 490369194 645311792 233476982 747968373 12698742 668510722 647833613 359079882 897576023 629631913 259890830 99698342 190290094 938619000 257696604 570352715 699005443 395668931 88522560 817915456 164915583 842863716 58109414 527916497 821020017 514424631 731685469 674714765 322123722 854553501 726920603 486592710 440283296 477339645 607932663 710972948 472246447 376893502 3645613 143421394 64192467 563242575 953854558 610562464 783237007 771551392 793118093 656017375 101257609 142550694 122727971 686415416 390849547 618687322 547081963 687660566 231864452 165994939 89207831 382432551 190508037 430691143 230462393 984698335 384544197 343782534 489260107 240153588 360318878 214826880 425200424 42082531 387446925 214092865 294606608 785842282 959555893 414045532 485780648 731395340 641875037 514935397 673194231 870811792 985491309 758858870 458117611 667457666 888460533 944673451 180499154 859504305 561894695 135294118 423758561 614777263 379435608 425137419 473708465 114953044 793322883 37705221 817149372 243244348 281083078 291013056 154869477 800451908 242058722 759662316 559915757 441828369 653573823 986733377 44741119 116561289 388864998 507505141 955796261 412318039 680141061 302838343 635030224 257653099 938895215 507286008 762657108 958221944 352361625 709280717 688122217 324078709 566249118 354727439 902238379 964926237 210304188 736570122 94739995 899291247 931669461 496038289 875754653 578111278 317201135 422894456 60800888 192017761 507234740 923520025 124572889 472413396 558190835 691983056 852903504 604412822 909370653 448024447 920484688 958692985 190615241 717776651 152007091 404511638 11587376 206178780 149550645 805769414 324466865 672476257 738885364 310574633 741348174 326641546 248321527 358052515 925100846 224066380 876972963 798547034 75342105 739017505 277093703 954204986 521500415 58142341 918509970 32997233 240882289 535694714 217553175 430729203 921144102 671758085 16966352 155316983 419556728 489054638 653928600 937658487 113256677 746643972 166408624 675016884 92871310 373284119 982247227 233817265 948040635 715893500 91052225 354999475 206044244 405804365 934406320 224806087 52955498 11337638 976084694 878376252 518381484 221592617 477919977 68182308 703802866 442405883 478031103 385212120 941322678 233863621 912967190 95260273 344893334 883662388 528785037 720546896 859828692 387333753 210144425 13200790 235312854 368990409 71203089 397724332 657035174 524185822 520240467 767593917 129191538 211930228 585061469 742338871 909667085 385258445 431781124 712086606 991537005 517378606 797963392 153046905 340345899 654866015 486783726 14791923 403238150 808708911 83889101 356743483 179910496 761742830 441597058 2609044 89193151 368728818 72013012 345460358 634781005 934627346 907051888 246929499 769068633 585255726 4631142 284058019 353226964 986014373 714443178 714932145 808058325 236602333 894999444 838958875 624732950 907738558 139887456 647730749 395324276 916136247 469255599