18607
549218330 859379495 322713486 629233917 370676373 19526954 497065962 965510605 264078579 588188024 737811693 789128190 580076281 235293476 504630982 104397021 387321092 263565612 613202431 564030824 385042060 420192594 715075421 694066272 530842319 36007208 950637100 704179947 673600857 828050735 460035340 83371945 121405542 760845599 265180710 904507011 129294785 447310357 482770416 240969926 977301619 280953982 807146219 377021389 484152908 42379076 896377786 673487024 865694691 314855672 893383442 486835848 500175840 528588480 867454140 7434234 910618035 998240065 534912493 441417186 384446808 527833923 719555108 905475742 472205781 197768132 397730234 423475721 20433352 177325405 344005412 647127087 848512149 616920540 482361407 901451126 119884235 293823178 848755535 816428568 152346051 459578501 14944423 886585032 161929507 161353709 686596128 36141011 137569687 545061578 686931765 241972382 535678797 590438622 738513802 439045327 720761859 554394159 332232892 672122019 722634635 369808417 372523001 690508199 534930107 145986236 929297124 357234694 896727655 19054467 427658257 317109525 393527993 635179935 945446985 31212311 282434113 230810849 560780523 522252597 480651587 623581945 124237865 978305732 186878269 30450273 187759873 990384697 817835965 160288953 921749594 227380930 104108967 3232661 721423000 26800872 947644364 548953370 874276340 118382581 669063654 400551087 418185125 501909826 535672840 550126054 314483331 32773318 505392377 105713364 925402234 46079115 642600115 175586430 35504654 219648750 594986468 681832173 531143688 509042738 736778373 189934376 150516736 404142504 216865647 318141782 289155199 910230222 567262842 167001713 758268232 320636371 36628147 52450493 116990850 869519234 231068166 46140475 740790144 982157715 692872025 974165182 214874889 304770537 308993266 300994652 135657715 556124469 163723971 947462857 285268095 57491386 28666524 9809710 693553294 498443563 477900092 783322635 375231681 792414659 359778870 874502702 879528591 822128073 439401568 356813603 143943919 968456743 22981242 470460283 233021046 524898110 374146837 269878340 835476842 859089120 20153955 804764636 445500296 276331850 127587354 3798199 376911554 681367736 455821844 570851962 413743252 874018921 939570731 283228336 395720990 212481001 674979221 402837920 480393586 524181167 366655102 869027931 33148993 484455777 516796399 826367826 565323976 203580773 906009741 730022807 914742266 614395547 893638591 600935008 876920977 586371504 3809689 481578774 86684222 773537741 448552090 274877775 15148081 54047095 366445055 533714735 839108127 787554251 895357335 643929791 126336827 708264949 202641510 72285902 582587822 688975501 25430633 711222025 151448881 905989970 107487039 635829286 78057108 329570882 424157942 918233685 189415927 550515032 19222973 809067232 517423904 688298434 711671635 394729638 781435403 636431274 602289763 338661920 391426573 836065174 895990917 719386691 543059277 377192741 927771773 488634848 984736427 809099090 236613704 222169252 464923017 475456469 499698841 836262683 106958850 915032401 455908801 608451909 290915762 791938454 503453859 966236379 868370945 943860267 768089955 431217660 291433185 348189801 517823057 843358916 980866258 437066562 405065067 910765986 676564793 17454043 962839278 452193470 869769519 849285122 655236813 925330525 464468513 866048051 606890796 368385546 765531477 977303589 428886103 285565696 563067042 306781914 10618891 88823684 177516320 390016914 884783532 54936892 104387747 147557322 940462895 175795847 461534762 682960359 799507771 529870849 272897617 388533133 428071476 85771232 890186251 407115636 266223769 323689682 637677144 619103935 573096879 413197453 971774804 451646108 836879169 976699562 594243421 795229857 385369285 945538717 82619555 847455996 604678905 706155972 994975735 231352364 122441839 632191794 682297802 646590014 623563543 185129148 386610314 54891529 710738662 788565038 178871462 922130941 584063749 808101410 637285428 558280177 450700610 568316490 553921937 295996027 838227860 395286871 712139803 759261341 234402101 386728262 717819562 356201548 943446143 144263912 665674953 400197896 149425959 260770933 318448362 811300887 139458476 585978326 796469226 199894595 568462267 932157314 81551187 374380661 153824065 242081226 377152636 556735909 517834554 272248541 682325880 539245072 728775999 143431648 382036626 445898201 220185809 83755974 478248556 125664556 749110567 412826218 3220363 596142150 643303784 971274442 979007762 314784040 694298992 955429869 548690286 278273616 658840897 890012171 200998992 150017644 231440942 512230826 895733290 432497129 365587435 576731956 120061044 166160353 759140455 982934573 686535934 428600583 368140611 940859558 220695954 704845027 570877676 966706143 907038696 303513526 851481858 490463510 686193709 941344679 981654945 783792402 582884282 116186745 867265702 432943124 300730098 971381673 245218175 34299051 401514941 829063790 997217473 230900613 198329990 846764441 864944855 320684399 248613665 830309263 568365515 355870401 143746951 219264506 643510986 28517412 29254684 978758090 819656525 999195231 747854712 331345873 469691293 124935298 938877996 199141770 900951075 639591383 214933971 322573896 314642968 68988823 91118757 637788619 711427616 445068888 17763436 245438537 982277180 283583811 702253492 595560050 570028720 434663801 896162417 925713787 896105982 931970999 454736676 877219456 234300322 286421222 442407256 748826497 426286971 986710766 381983442 474537189 30007540 698270960 810581473 820535140 468203176 176189236 802011607 384138236 703905110 477976444 304657279 795855156 367365371 739778667 784861108 139270068 916175637 786154675 644125104 240688766 433381121 122536047 436357312 614351423 563642562 528442455 156047008 337439815 456667334 100028340 643163725 92720585 86386256 186823337 794567998 688635794 941427001 336187467 147655467 355517161 797860265 889241267 467778268 98488973 833890607 165713793 551545934 236912542 365659306 786161618 677950393 397162313 862891004 114644196 640856491 21687492 985291996 185966619 46139621 985639779 367246387 476939197 414730078 119277536 75547641 227775356 208547262 266054916 663770251 104903351 211403234 405498399 220751950 617424768 279073809 461456670 762486177 290077574 106587453 452719237 319368578 22344752 843829728 34234198 984161708 799741141 323798623 312866420 809459509 685413785 13963046 821989727 730653575 3069263 424712216 881169013 88431313 418672671 114598878 962961115 197732986 233992776 23232031 957291916 36057324 268569734 450007784 775084765 635164086 897785627 551482576 944824297 889683616 441300760 331290645 986929871 807434247 250926685 576145901 364861811 892817642 660723996 448164023 302676021 95925531 742153108 874481091 550350954 850454320 932377297 545250927 351968555 198426772 169627802 457505779 203783346 880159806 1528282 92684911 890367917 232510630 324942189 34542012 129203236 784000098 744810652 935337061 265757438 414716171 615501336 640206798 433619729 911961728 353556070 786527617 991700201 466841662 506191063 878777191 821145665 774969985 688618984 920900275 382160046 621470928 594766736 521596559 193780059 135950465 149086058 418618854 318028882 831982325 45725188 713013261 656609494 295925549 361994990 656558466 684179312 807336928 148839154 594909407 48716110 263085558 424323188 820147013 319015043 501869497 559802136 957831222 599242386 271776484 959809315 424829685 585594544 907561516 308628626 467991295 327407172 801949435 426150741 990725522 867198467 874829901 427758682 969929078 740025033 464730154 879732910 362652771 526909982 647314542 375749888 343370913 241706715 203728666 524783762 964125010 815212484 793533397 534193156 670793096 817935453 693787794 495589867 261659393 806262554 269622577 72137341 264896000 93879209 467725313 896846013 245663251 179910932 171955288 597751894 898447310 698181849 209324870 343124047 142610586 542889265 811150855 295048017 518905790 882958158 919955056 407064045 626465217 934161124 579197703 892471236 499804042 117885047 606884271 443352102 49408198 499442323 956872052 967651983 72137502 864864468 508995023 44945406 184735626 258107997 976286069 555148412 23261345 309098400 96368410 516658539 35811057 441316344 696554364 892291960 398256623 730579472 335127313 450299392 378405736 192885846 601087077 119515438 792459392 99048978 166054136 269465323 208854861 214340806 962512897 437520410 318136337 280181123 889663219 546568717 238085598 312613235 891797563 503592868 655923071 883818041 141413804 858435147 485618840 875335126 828308821 245655 696342755 618983020 872125941 83426322 400450253 262147221 595011432 76706387 154257840 869167371 490385505 352731805 548468749 976410909 192722787 140757339 275321372 655403182 234061150 293865617 949489687 782452839 608881664 539775361 969381334 732253621 391309076 543540818 34607265 164870796 75829065 805186207 761829458 443204745 635551173 707714617 363123167 242048420 877104789 188497812 333100641 110221011 628379709 798669177 872683850 550380609 257667382 659537286 525222467 797023620 965818359 662629829 698469729 64671506 322539388 803838911 914378134 869587429 833415073 253043700 930526951 807502543 172403364 855317856 592373586 396871851 215754716 205240610 384349486 424846770 129666650 826958024 102240237 728325683 443020150 594424126 837894790 126066619 136318272 359667145 627549450 101288193 320885402 832544281 779458150 825548195 100278703 971560244 704126285 441361702 806208894 55536355 649438945 396076792 274975617 136021621 399335149 163245798 742223796 474937510 649763361 420936120 218735217 613397481 614513684 273982115 602063052 886424047 224456904 586573775 905497878 771320803 860445903 994307716 144540809 140421824 750177579 119575327 484866710 641345156 755583714 979121344 350183530 557582862 404094413 522891042 807779898 445095159 305691533 715970583 666438697 928549000 18211135 128310801 904950796 571131015 690147042 754553525 449902504 931032349 434523784 868244678 451571786 84775146 363063732 393210486 694664377 892248353 221233295 952562419 291168263 502468782 827960901 835489014 825449960 476875091 392678821 312337297 176348805 987860437 213609408 210696414 53167732 208417886 290062467 814589647 932952310 930542527 672258221 389056117 472860743 388718375 580925518 162165458 646526089 891937132 526992071 137734814 207818199 883366751 132577216 46282819 156152145 114830600 158082352 808911963 553562666 948774417 669596416 99230055 403528816 607653308 298491980 364142132 694289807 330854399 223359135 924310692 883027618 528960497 419061127 742141738 417082653 509029811 227021674 565432046 705820399 443050182 854543729 719070111 817435978 57389337 996820784 27742249 607909519 203727725 212615869 485365325 880604564 207376656 62855904 497400278 198487957 701567231 257497205 814640382 951946534 185938467 413350979 581197548 810941510 47563905 802754111 768560394 790975994 523120838 839062459 278751972 885629089 899517739 277737131 335381951 856581562 555404744 58494087 527017775 153133643 149580722 820662977 228996898 907762895 76999497 696459489 258412602 602859464 601567618 35317692 858020615 322996766 374664181 30600630 196787112 346640056 20680797 333459258 918632648 241776787 583352113 952649650 888396169 374689901 394029002 859837608 973572270 511125498 186538709 987497247 968486684 844996270 108306218 769015411 521839669 348262058 928338542 745245728 160786160 983906457 213182089 233044846 46190127 426087380 906489089 478288700 858719448 70051933 289312553 732093463 232525166 704075357 588189352 636631850 79544225 443244483 229903336 396586014 384499552 479278099 133285276 597390587 535029933 581948462 669848392 951239795 302956384 865028189 91423395 587753750 349754456 330517646 601355564 300396494 307610004 294728831 421821706 473197174 957862282 295063013 413118906 629202536 371392680 719247565 875334285 313371149 720642259 370155237 959036772 327439790 454638493 20136491 209295677 888687402 333350180 812951293 741772459 58621234 540713563 810892672 738845456 866317822 514952908 994754982 628664378 848778463 411563485 735835691 428185269 921683244 414450388 108955128 64026665 584168220 298159235 428155440 953127902 147178109 797041140 567004015 109458355 216636107 667031064 659704454 645865253 825934385 917820669 50746565 748641903 313780099 61234437 581721575 96157194 995643173 377927990 975359780 515592189 644370863 926627098 626792402 546295251 230720034 80352600 485336990 359304270 972479324 94992103 677255366 910442839 158354492 599011345 278694992 715301219 583071225 452751001 251653795 272496379 671229436 703202872 555193346 631071561 858891895 432735892 72587722 510802327 112627536 915048887 72432294 942175142 34370364 992409743 526757204 77320107 789281037 408540609 404539540 57095921 117938782 109522133 587046854 339232731 273995348 904493829 24184000 866876105 416886438 240672864 932701559 403509207 933203752 37540635 752313134 209420364 362756950 934299171 90592344 385215553 405474967 467973001 624102132 713430214 714345386 240117738 734471642 633342820 947410551 554927461 754091766 974952043 681789159 837781742 259412784 60559907 457323364 35454255 743622949 165202756 306949194 434689140 398380614 699409004 629107698 408533458 989365048 796264699 403910209 121785308 162540198 308816123 123351109 510433847 345552448 440947292 540640681 777386051 58799052 914010607 561688075 201614550 617690944 469414660 46300248 55650330 987124584 984349467 511773910 386393621 116901296 786328824 58152846 324366968 31613645 331887394 786037159 349782929 775865229 633182151 62043050 345093619 12991418 291714591 828514086 390779142 451955107 587230269 338298626 478759864 714791126 723486600 229931110 951516693 60511613 829660762 195774229 288234418 36724055 446103307 6882114 667352181 321531911 150591081 247650736 235205966 623865370 176080606 852792745 397410542 718407173 285767527 594580272 638550973 493703710 609995314 564844919 255085589 977321447 117933923 322017288 103842799 49129596 218872866 830475022 822079217 685573594 913717962 87365985 831414102 57479022 244370128 616372293 521744143 959601427 101251640 899150876 860371858 865533630 966175789 243964225 929670558 805942305 538752549 556545476 468764553 776950673 560639678 412156399 296715116 117710922 73413436 439593979 180126534 55586920 245309060 96630952 322433178 840518318 643908804 304942832 765517045 351523688 389414730 11700786 351460157 565358059 517932951 926654221 502793593 88420301 375261826 901804043 446358995 758470757 49973246 17697118 668382315 702668321 379669224 260043664 590040683 453674826 955550559 347893927 197565078 119606271 458424761 696335159 886439971 143273996 276034325 188773521 734635361 944533282 113928860 380597561 423020393 808117844 152130735 253787477 935081221 515410999 184677046 134834992 341238731 300984985 733042272 313208468 878817025 966574454 444093818 879665223 991775170 967056206 268535737 525246792 594399694 249912265 657248502 31407107 674884746 729927453 666742504 955109051 509596397 357154746 978223979 938710668 459645082 472114610 748766065 805553962 51982041 809165485 446320636 993398881 397219843 433131696 87233948 638184053 240033110 685803968 644980429 851687102 960017466 329205772 200376864 313591084 608157920 951879739 393574740 454846848 202975425 329464642 606923502 144829863 278486472 200042279 997046203 470879899 534997916 638157038 856758828 677486123 655705044 810097736 741505699 777755011 929199111 625232692 254584711 308998233 315806606 358843206 367732690 736853805 203466847 258062377 602054508 623246262 34843712 724959648 531580713 447651257 547397629 100770789 327059147 647060498 68854764 652485501 143189414 784879149 268442765 950295279 266525832 876829839 247761947 999958378 102267811 296179166 392394962 480359585 830522037 362239300 963163016 403128196 904540370 803887059 972688384 152290378 571517939 594158864 710409249 972997525 417863581 58591620 966235826 298990735 185298668 735171243 897587127 780180069 374523359 962438000 551808262 58978931 427409412 240005233 690825359 347117000 200371524 213571995 294579943 52308355 104938580 441345513 953366413 567068609 834160859 853893213 996686508 309276709 102367170 406855607 220394112 769937578 777705445 918850578 210270225 804044371 516572540 295600396 376892782 785473532 428929209 339768893 285886478 486991468 614962201 597213997 110319276 315672325 780034080 459382184 415498247 506537383 768157892 550561567 610471431 158717564 127545968 266977437 928122326 910875004 589759291 303600772 550536414 94344872 231440053 810016397 476745926 15212684 489451052 376177885 666601350 835627090 371805064 172739966 419553242 606953772 935575078 897677234 62421779 983025046 654219279 244910571 772422794 586731945 488573902 801972153 985475951 653301323 504083349 793853111 636648699 234309888 12992964 171403875 399703258 996362723 278780203 591578462 323272864 202025044 81529723 628121351 955018770 259416137 828399320 195098192 732662024 457816675 65372004 573329163 323064471 767156466 331648608 22717921 454621818 786512633 982130082 656502113 660837526 746898843 504490501 429117832 224135406 870555981 58407821 122028179 466005807 682314298 246779674 783426528 129681578 189027122 377113715 662720983 635424505 916877959 100044536 225637482 934933518 738522543 133029078 395925750 435521910 170525292 655261034 185069859 708577325 376548861 489157567 923514250 358300156 492003293 667204381 796251777 881155143 552300087 285085871 37661474 970695024 423166197 797176733 605355707 513258474 910406563 157268616 783198100 823735666 388086159 648620584 855049899 318042352 214841784 827452236 178440875 707738001 401730409 799438699 831279764 997633772 935011158 859272592 653921047 183177237 982106637 775991790 474022609 403792202 123367655 220717439 777528800 605736074 644094429 504238479 328830303 165823374 929097139 134460281 189735461 328391983 950131711 640142997 41639180 814441777 778130314 447497785 379631701 252474482 515250082 636201915 192008092 896927318 353102018 890354054 329845288 391649163 174317170 425184083 75915684 368413475 45088656 258099777 898646818 100555357 234050093 175114192 543595780 764687785 815326329 693716149 341954764 463656667 451600109 918570930 616249877 413671694 631788922 683974070 215263940 415855157 921952890 301708920 27654352 797238565 640227789 304284362 753796973 936418902 648722458 160481235 705328286 918450295 742009712 19373095 946831694 380893403 258413565 710766062 549395977 921295333 172702655 899306501 459227324 405076622 414869678 582815898 132479434 534934100 432065980 140020563 653833768 596992196 31828144 34254898 596838032 416343993 716945419 884945753 592173484 824206843 594433851 934541455 190913854 130910531 515651487 604473195 497811259 751084806 789980902 417379077 833131316 543734172 5598166 31768999 903793935 275298416 485082826 745220422 693690632 294419044 222077008 285312582 708282389 416260068 80754515 256717577 262316507 997132143 636984039 715335940 522187206 742018357 490667748 774394181 793684763 595794726 563025268 850723689 612197194 935378151 172352200 767412649 274750894 525933543 460993291 167030139 785737617 385216067 143020123 387843304 556800805 82801473 307355351 404732137 139238082 306890524 128619381 833490241 969491808 720396232 54269578 1821981 286631396 533645054 661755058 586569959 216891718 692039258 931346589 31564887 857200421 56486895 429832319 857095845 858499954 336038770 561958369 131095241 559699224 133906663 681959166 62058975 944413808 740615738 813232627 476745918 448828601 514057219 471853998 108443400 268600481 515999354 157877435 172670974 737195241 564657036 191422178 944154743 313034303 467035923 31018102 943715733 987022111 456210298 603683829 322688780 216869328 307462087 723546509 249594282 113100466 637884214 311910357 448424420 391063945 72163177 279039332 86690904 223051499 778800969 309769821 465649107 39599281 706261296 365348399 547604429 521245867 968580056 837365645 33223889 736937550 555853556 325400009 4365943 338546899 250114621 193355051 745600187 65530162 965200206 832705138 308612846 588002821 855579558 606732408 77367468 730757197 475097701 752862621 762551721 629562610 137308280 125010874 67038236 171757122 972652723 441163039 535248238 652301295 976619602 474316503 959129489 975051478 433992771 673463235 507247853 431890911 591681538 559855260 506301030 366344487 271214328 695644942 43317545 938366088 995070701 136348427 900166192 776190183 926503031 912620521 497459298 958244041 919067413 174057170 751688289 46150834 314492792 440224301 221439120 33308265 226831975 152619332 950767929 202769756 210918276 657911977 617860804 899253143 548785125 867870528 500376885 700941856 464531353 17454717 791899228 378584476 90529463 618023066 440139991 172541619 666138805 108008782 781631996 189944416 121854968 452667009 505970305 315652729 951292253 513603076 570367245 922990785 37232791 392316170 713080463 334718544 800104944 499142345 268016888 992837866 65030666 745844104 975964901 915868224 132723344 246113244 3186333 301915224 113123849 758547196 913656228 893060634 851599002 179536436 769239822 714123878 51760589 453770797 772681034 911834694 409323073 719791477 129325133 758759672 838956887 256727841 194269907 446302087 978217962 136941739 703857422 453916752 653907865 480555065 525849144 2005564 524055033 715644297 16269097 46721188 129902114 779128574 578509132 538894171 461626517 343044758 973174668 423630382 946248723 475189519 764855463 724237426 141445041 719450370 159226111 147932392 995275116 167535595 472754057 447577112 467885991 5307088 731154116 788490426 802645452 105074410 915350585 116867738 267692657 231845322 766188642 825621370 316564312 454719866 321358855 704840222 330880153 17295256 133859338 380633388 16248535 706740232 432624636 259821166 998588427 763303078 36888175 962850976 53336754 910531448 593543963 154094317 863149139 540516494 633527428 587006875 964559862 516471528 803159501 862805225 355658827 206168173 849771731 462274523 645265351 545669435 314017033 49149930 663764245 613796231 278997996 400366904 730237400 406503424 985846415 273334252 792617581 639743127 172583839 97654334 291691005 144507987 491516776 221555140 274124664 512019447 398055224 19270709 379665240 544972809 523333053 902601462 812890331 209162212 565893291 853490448 725111456 92160818 850631322 264522979 420523996 174451307 308984421 228230516 754859631 434347011 982810265 538362944 882489171 416374943 663426921 62239718 417980146 513382427 5515359 505200320 100906833 877876732 117009892 223827277 609569976 211649007 203585927 717726746 200565479 840502013 389750368 810687924 474892431 634702895 111181432 862984688 714762191 549384464 133863205 251927243 986156007 59884195 869169417 925035798 825340738 544546917 377224317 259396403 744880582 92137085 323095862 436186550 497825781 318859197 855964970 407462128 127373755 882102084 637748057 558145390 478323521 488770959 518202378 912158103 83342476 144517197 37014779 421386081 622623174 579475277 181311020 45050177 716283113 452553049 54463232 614780884 599371673 104351182 300172723 520769657 722074801 905581688 155390086 111270520 208483363 148233333 9963834 807407234 938387900 500961035 695885471 440819400 781395796 606151593 160674028 416725701 78313160 920901686 213477064 410191368 691283957 518237634 979420815 192788103 412901011 399986562 585599848 435599295 16712803 333079624 465134232 566112477 551240855 653289793 853997535 239463872 77780003 630194642 485616888 509578282 121900671 382605908 63114795 754828675 789997530 719803649 229551267 473201867 41055744 855906559 399392312 205702838 554416086 117035896 785224340 150172114 225668148 145302016 177494231 388674875 889325451 987893965 480925636 408134958 889960648 599114196 786889733 675307164 307448525 265836549 753151294 463130467 425526706 929533095 299470450 199719178 541415002 817404695 626316826 451240944 977888520 725635089 641968494 105610837 960879925 773377840 902996397 717876456 47509489 423140491 376218796 41718367 85744889 624054546 415608203 218061825 605030973 220980324 847767910 207180407 498110461 129319392 284372752 71209592 504112478 874149211 984496272 740807390 10582992 916608459 519331706 31421484 892682701 804498325 94577092 281829539 669987902 735852494 907794539 437336776 351319347 566772820 585409609 295734771 72550899 596641403 674422268 110725482 540501433 85621158 876330019 725748420 688233167 17039778 510763329 70891950 21542463 366918455 887986271 630660738 275226458 276177927 626373720 253324652 517051937 260887850 751400217 163264805 137791115 959113470 245012305 564449 475335985 785718446 441444685 732842613 342907736 116377136 245794413 765569295 346694050 208621648 483205395 421299838 947246393 258924724 743120699 881085978 321248828 727607315 580768665 976931047 15069861 886610419 898518392 555462435 904652899 543647028 752817140 638679393 860613644 296439316 187580355 640826148 672242 833898339 699491983 321216869 660909401 278254787 34269856 793633571 616756538 180510369 874780038 465642549 12396046 219979956 197088412 856147994 311578808 496925487 138346020 412359092 599441590 124406886 257354091 145425856 346563912 185235244 249214164 448157313 909596048 529765755 485247455 847063259 703283020 122986165 596801766 69170549 936498790 720190641 98711834 997350156 359693574 321415262 582070409 29075890 931577048 288172429 533902217 409160637 659848960 579201347 726518042 756559138 638355032 395997639 480155882 216352257 961316659 991691457 574439832 551733492 612440856 68377881 686213581 637094873 371296008 65206099 647961825 705717483 929084297 109957044 995350291 683172269 224598036 444768111 844956238 68164897 216084322 543347739 677747687 874976750 322981476 54347386 545707230 766262782 511885099 499670991 128986958 766161430 586735359 891966649 233726248 424813631 666156157 667839706 149303467 457119333 741052891 195017389 615378412 100434635 994151389 240116992 31394192 38038767 607260956 263059471 229241895 892051384 904099673 469100971 163443544 719621264 830351665 531582062 575821435 832148903 787587733 620531470 896522087 689187175 639941609 606865987 186614619 420289349 641820284 197104379 291885578 561138630 137479063 23354469 489556918 696816581 781367414 821859914 995805038 812755729 610626597 340731061 26193870 828684941 712826179 902077372 898205612 409829169 374923229 786801233 986470075 620758045 696769237 584282964 582752199 279930397 975502298 472349218 529259012 142407770 85823470 114032631 236748142 476253005 409756036 934225399 144306314 985652309 656525801 35656530 196101776 808833114 617512075 118249829 225473124 729878793 172351629 528989647 292751415 368613387 949633381 858926095 498231697 778701358 886263417 926873421 722382729 944825778 891119064 186577034 902115947 410139234 875842308 199561305 755614561 288362413 558578930 259229829 654526242 878901861 684407672 795828053 718438430 664985834 632505970 771204306 104154493 621096050 906510721 513549775 388989220 796996418 249403029 341934095 12502140 612696617 130688100 307060489 67841747 958321329 93545014 936878711 267213074 509988822 969030368 775715318 738544888 713975548 451331056 450090253 416670830 508895708 686962529 918510140 343989094 464128276 351438725 23066870 462741479 899349170 404743573 679150190 31860510 133891573 903060043 810866759 73983187 460034287 622060750 719130374 653618697 910825070 645813842 107959659 146094921 839374791 425099940 460247237 341827247 464687829 253809034 180917506 234896112 173097353 987979326 685765059 578725875 724818043 67054482 350983367 439552272 201891568 807178832 828098644 683486592 408377442 119031886 578462909 603228306 516425645 118359976 692093995 280623183 917783976 730253571 655666528 992695254 643910323 206552255 744649375 576887994 585350355 816522764 210721088 167983983 129717948 224207095 549683774 20700171 547379122 142681646 611646087 163909110 278253400 870583464 12377370 871116576 968134874 201092887 802621998 777702873 222406285 414454379 797437283 29179317 75777791 293526787 802806610 195698632 343604616 573801234 845839095 296540628 453341836 53541121 811263666 474340461 667805370 268989082 751644406 486332456 979956880 344635139 632256270 780726525 711708804 92168000 570544872 609998711 627732693 586739998 813057053 127966489 514081425 297532555 228079879 399462232 496257031 876288593 795748175 664704178 559854086 307852253 990299362 352659505 978364618 798099040 833680938 17832459 740082886 943289170 448182934 585847924 429589994 693346848 17362050 150393185 915453500 724616044 62249958 183453305 377824325 341170846 425200395 68044065 552824301 926814742 60098268 784998840 782082208 217538572 790797296 489369420 369940535 682142927 196911873 53533099 135390363 738511449 246680111 82509655 494387483 945236290 616844150 708840815 456822462 334342646 181735541 94207215 913926715 638866114 166645788 845677052 978681122 730879295 298581773 904146624 644777305 801786388 287309335 725676365 777313827 977388380 113213857 52587310 149523921 263243471 765435905 275175723 867882483 238317545 259425065 98808507 285202870 855229367 938842814 935285057 446184456 653858405 327714539 113380209 985483162 793432866 784432863 941103594 162512996 59619319 144991149 973512975 29587440 773396641 84183142 925728251 173317696 353416843 875849831 56911487 154871681 281074230 779072261 387089094 478808083 268182703 321274326 198236223 12551563 876551963 828384529 203686650 972785457 372033368 648011723 279911424 123671122 132696703 314462867 610052213 643799726 464893459 649016113 82215901 169895032 984543518 874051624 280100570 846150511 305631915 683296995 814265402 323212960 428521031 353583092 303352094 479832582 692152479 428972201 872698604 755375400 896220830 797968608 968912835 633643306 925677804 116708546 659759469 157540121 68411621 166861180 202298600 598560362 737336412 36619753 256066467 482150868 666357791 672003602 177730611 970134901 738275145 265880426 207035147 905762228 613470029 525861058 64744652 337291893 664398096 106611751 105257191 381390491 215372225 574766058 801137811 763142344 903110555 127229098 506617147 545545900 910024505 412722831 429709784 313835398 296145431 921138342 891673349 585102845 59060476 730086118 387868731 136128663 886339998 569350465 368937036 865832324 80466165 605778223 688094651 195716597 10046326 263719512 730323916 822022439 85356860 245465994 165363611 421990149 165354597 147050621 137207549 29742833 226794082 178041425 967088463 273188719 685237061 636136796 99287310 760053170 934625212 264755976 878529293 859274709 356847153 365742606 441843562 729162993 282917766 881756579 296174949 805284443 135964419 886721306 962139324 391026491 376350192 911599825 531104107 624516910 153097362 708894947 748724095 461764218 433409083 609944071 943346045 257407451 271459181 214969234 136755149 947033692 962652437 348252833 924691176 468806412 936806032 798603817 745801151 285786076 228597265 742964964 753454548 450327606 494950088 910026209 307238033 275104074 276263533 711755550 809526779 694189399 55967196 829705187 274632215 106765395 171639796 44858732 590645607 282456994 530707220 512165411 421074519 509532718 392394787 824644343 828233807 881732117 486338587 574392551 18500090 936093108 40729517 894764517 311674778 598765097 840858536 297135161 348074155 242606104 374075237 777534084 709934182 45317663 235497911 458578064 364665954 813873922 593248972 985488125 145159612 59262720 912448819 606389562 339509861 705640618 998158707 406339908 719154055 569487523 971261175 665192491 645007382 725709789 117345233 226284676 702764087 403492625 296014951 603336641 363971971 986868495 699671096 193808475 248208752 157181842 523960129 792975470 903343584 383135342 790071513 406190237 263726749 853158049 537631543 82810254 778981787 322494281 441017316 375634144 354324598 167276238 55419425 971575631 236405148 443331546 787185685 407603546 234419325 225052482 51600629 560123663 714776128 658531440 7912048 716190775 485664388 980865329 860774175 198850313 390654327 418852997 696355902 29363878 56250608 434098963 537863426 732175651 704270783 536529697 411640261 658838274 908163514 737616847 370255324 979406103 197264451 626772569 948407946 3155650 841495689 469264622 472914181 638532113 812993903 835267595 415005974 822601304 442461447 526261102 333890454 252047765 870130098 147634291 715695881 856446599 85552885 847285 185933745 846395911 606220921 228964478 87253186 910035943 150857653 501725506 291709026 952389125 74069232 670713372 626524383 430133659 681614719 447515962 796888228 352785842 50146251 257399243 632588447 737708477 817996426 282201543 424947168 653072560 694048810 634505869 667156229 861817135 473731555 515334488 488701391 545607143 404283318 212056464 651860192 348816886 611177389 451883308 541775221 906304817 933945931 381335140 771724033 238050840 156510104 951221461 539200480 933874216 596951450 580424326 227133187 977293727 482353276 352520010 337780514 145878019 801473052 814609767 555851129 610779383 907493998 264652230 475097943 748184389 244562416 946213888 178139794 242653452 430814797 770912643 53446879 543352155 526133288 486919388 722895953 269432119 798095929 678837468 9903787 504446570 618545189 73457641 619751318 504571282 83248291 317302235 143677448 629655103 766365209 695940966 41284195 151096514 299427957 171199926 105084448 406076092 792253782 298500019 794089384 191098150 352914126 455969781 606335226 582130379 847765863 19367063 272757783 727693433 592989663 377589754 463610474 708049186 239799229 628384982 341505254 244282728 95536197 849967907 133766084 666548100 527904997 361979539 358746830 599589687 569535919 914254378 911668814 427542055 120162871 686827908 746037452 922933762 251069885 763734986 748254872 555825666 874775937 587734674 567065515 830020760 953361547 570429009 692780509 942392166 353529013 346904930 827824750 91311989 450350018 594620208 504506038 21013376 133688309 275301832 895766968 656683550 89495803 390931426 455704680 78022249 437199723 713932135 716429364 606239337 688043673 697865279 761847911 102823682 764345828 10776512 789742509 901571941 25992751 975814084 43769668 638103163 103036162 371293089 8930387 15307508 449951861 906755799 888886229 5263994 352640307 544784139 247288850 290757479 322654817 737687029 10076714 873879808 676729879 73847269 704017337 801892497 320547346 749656403 672894453 98012697 940798208 231959265 314413654 780132245 860198785 585567190 656828200 66545197 556678805 995176989 120114288 64278099 936384567 624936073 703701831 98786135 765124735 668410399 141282312 475001061 977736324 824778172 871272111 461190604 993554921 89175243 74540481 935006573 357791970 637185964 947402241 184476483 488627280 908521241 228107535 651964908 372529264 93381896 768193888 340718704 986059532 6523473 640331482 956488821 705112756 441281440 538380177 125047595 375013210 905214749 891603353 939165066 368488830 618504848 653610179 84428085 784668678 88618236 412489891 538537905 541400260 58592457 479721438 793202590 432540168 903291566 807985125 602845992 488279219 921771831 478719151 967214762 227712181 495700355 215745457 556020501 551020660 533459136 309587775 992592508 290512475 246410066 772973385 943897617 334645491 976734931 55110421 167101448 300870965 885293209 710404500 623888941 238357683 1299848 825602286 369830933 935297414 72032766 695093029 611754438 455867206 424864526 719155479 808585683 238993963 745733460 259423891 873520876 408526826 475171568 852511999 204968603 395999409 81307229 884108787 215207609 940746924 125588311 614869525 763399929 966796988 698331632 476865971 334434780 356601266 513265612 87213800 476136163 401186355 180385570 302090498 983910988 286801664 467262757 782360505 600359993 215188218 717397607 292575332 115098418 441845061 312530979 685983616 413796726 583492249 130284540 652635886 442378710 863497561 699921971 688698492 361502704 53199179 610925009 613620063 720411785 958849473 548848978 604972608 311191744 550600486 902648722 227290661 86714463 508081342 280332631 654785251 991825080 88667768 174537416 142000139 799791412 689834409 574672833 699071683 550610967 320738981 383364236 455621235 496492938 725235221 849080583 610176386 479065023 189835693 88647162 976459227 427018885 727840482 998703586 838019765 450735605 558862865 552376058 337593005 56845852 520074065 834891154 462529142 12223886 371411460 809977140 152024181 22040690 104520998 848216268 954616713 832684433 173352311 312838590 162305237 451641138 4141544 105643266 18192264 978830665 159476471 308763544 597724661 358221715 389402763 111245599 392170399 175150132 801189445 690540826 851419128 295724878 598718249 428962438 752803483 768875262 464954895 399841136 455323182 253475060 896554956 973332178 844776793 957505875 293894028 203169652 260709690 987062272 548395991 628429751 689157977 256477603 619827140 481454756 876148456 9528181 187095503 166290857 142584146 818040032 694734748 433015290 857425712 339418201 804243289 53814059 918089287 636172603 194716904 582121610 558602153 55881988 380663528 302009920 463319780 220633405 193829870 405840687 882624099 40159944 658906676 91688412 144932252 975462313 784370379 668269846 804873176 556390327 931358499 433826529 319860349 629340692 622027408 756936034 867353064 412295030 256161865 55698038 998044968 914066182 70091209 96222172 352265478 655448519 316155555 419246552 426492713 25834401 397682482 829283272 172352467 796592540 610799462 557911586 201476457 216323440 943532129 130750216 291253758 748041684 52875222 222968488 902304215 118456367 969576969 825535216 101245621 886885307 32562480 80843154 2936606 296426586 392893591 408413994 879857224 232222700 392862185 889330813 485455024 734223316 146725436 72178505 152417578 537450818 292451382 797372707 810030557 30040329 68379963 768473082 134525006 494765318 802954428 766620494 568857832 958114625 136713991 781800210 702565837 950791504 184784514 220191960 208672342 703206062 791386229 873755231 366967658 466880633 905757429 943027140 535805819 375755287 565419180 131959397 860006070 630909329 353734476 5350977 78055445 746148060 893795087 481436149 4376386 669238564 811162490 227223486 551734540 219463049 500335928 776664044 293933686 106672874 498058305 806454537 910460891 527163726 839829178 780463529 503330223 889243418 832480041 239911862 963972330 117298732 365821744 507344608 329125876 573774646 647758765 406472980 821726885 198970321 773668037 652356631 934268617 120781622 431152706 323557720 866805293 920604037 542002568 959872754 455004861 650918543 278583630 362454415 986633396 278879336 988368807 621633549 652740598 97017512 286496843 969974711 213632739 18994991 451040953 127095343 887361242 308833907 220151672 242354954 474938230 834748009 897709056 989306176 802351794 195500277 106514741 255384270 783421610 805130419 707108783 581913035 125025656 411598773 480071222 758100862 935212488 736458303 74708842 798905792 374832993 687249199 615723964 259305289 910546534 930549131 453430525 585511821 454818510 363527519 826538372 522718429 841384901 309654419 315265567 490035074 225248040 28440848 211248500 443822533 108543824 848735250 317212383 579946580 855876008 669073200 895187313 731146469 448454743 264884023 71728145 432052214 432429345 198962232 356324303 738941990 163596334 481831191 376097789 293011618 643323761 725357734 812836162 329609637 108885016 697822401 944591885 88952954 565949538 29246675 716550737 969969241 647421181 120629689 108876960 693773901 858706638 118093437 168823678 314405773 798522629 742557425 707069812 760271667 659401669 346779426 861647344 551953524 35573108 344273186 487427791 30595338 822835730 631528486 835571200 957909911 182408000 847759430 678998881 95575157 601051434 132277968 880102042 576120452 189532132 599533427 683006789 145727152 669429927 940675655 368992728 644582395 398285146 171960493 926736364 65935797 732427956 674191277 550302474 219601973 852088396 787480248 632123042 480000110 987204712 192125155 411031846 580909645 930290229 84328495 853576460 81532949 911105274 552596580 844154993 83661314 585741156 129564626 3890451 263042155 306722877 383065578 904715340 857987437 590206515 678353605 757593798 65735049 902360690 743762394 741777952 805161716 500460628 380850974 231104728 587720706 907037924 698979110 789655429 35411043 213161902 811482268 903364350 131788120 152212263 500886001 126900168 531608623 617969553 958814467 883526275 755005294 20541459 31980958 116775275 345056702 671561092 342936864 719045514 747889978 857741529 215355609 153269740 267654806 163526558 518310004 245801512 352590999 887188710 485985257 766315052 623402918 142170746 275759655 86269131 42885100 215787539 742105623 548038657 518987487 700279941 421907403 38898721 529488957 630983056 241122875 641517741 61914823 74246940 932104489 19537033 561009518 62435259 19872586 156215529 22566247 363829527 54725800 81914403 112220094 41559994 753059276 51108550 336875960 34676418 223122806 913761668 420275826 561253201 144084916 442304796 624259768 92381849 91345531 73496775 607556593 591747978 438624747 842012189 935833643 816242071 22865604 740958637 251390368 747635672 503849010 94698266 225728731 349483216 770636508 779834745 927652415 84408078 2412337 158265182 336298722 277369678 27743938 468323866 479284016 336699805 864171687 220028885 404601289 443563694 221003658 227204189 885549182 755772063 456530117 690031046 753177769 546190422 694576254 739289657 571459108 843643804 32659212 822377851 549782432 154114449 441517549 155996366 391049480 661147182 221797709 509958271 193534280 385495945 501752717 731974397 747324577 990761095 535684362 315036615 567754481 214970311 114153634 778322470 378066561 978718027 913228042 214222876 395639344 143124759 605254203 260587076 8101202 515547275 873908361 503417284 622282657 545877585 217025902 26230329 42088062 758596280 527173369 335308194 897208453 541259961 701274746 948468154 819631632 891144092 729917288 725837829 922318811 621970439 886713008 597389021 743124617 448491536 539855249 419019557 131294920 5864048 432972011 395929962 591959510 328761732 400219998 630687071 98465887 407029174 126002853 661386482 440229235 862774020 937808104 999465358 362659713 544176130 320160070 484235094 668789997 92593735 598043361 687954703 281813413 198643822 225705674 848323684 821843743 689571044 956589755 521777891 748489772 160943488 16202664 990979354 557618785 547069665 177844494 612520655 428030416 813537730 212547082 65217123 457271172 881693480 195046962 749509676 527372797 251512145 672570628 277406178 118077128 178332344 191074785 752358194 27537546 706714503 281863201 342942262 642164623 47489462 295276513 121030298 205493327 149171411 91506621 33010467 978517302 131477488 344063961 433788888 57445173 475203853 196823638 114252907 484212042 514707855 404882143 931834915 505910449 459387943 747390172 246338882 124082721 350297493 989973840 945759737 202669155 650908841 260474709 646448138 936184682 883848032 197969181 589925892 995159257 247095010 740302158 340572750 561901174 685502836 544699955 27527242 811755134 660566216 163773270 114886400 822225399 903301104 400040364 825834420 558725655 326851754 980673048 124353310 992409257 962024443 505349401 530414974 773429502 857392360 30403973 711316763 97651827 8094418 913400228 778739751 713550613 920450950 611617795 740463649 608324019 217059754 442954721 434765115 119154661 891203999 695385615 868233064 612778574 335769957 524885328 631916323 359104950 333772918 406314576 518470345 800873120 475853095 741629228 334522278 706931124 958702818 523286760 878414517 928865560 647859850 514550047 259183234 749992121 694612472 826715210 267308769 403796195 243318758 841976412 407340418 61205100 906909048 190590893 158194655 980655002 484230919 987086470 114291621 637891368 599809088 568409642 634958163 229071658 907047180 382906718 335144639 721710697 524838843 511998555 170596100 485490289 249334069 860219120 191965077 997966100 858015518 278654378 458690670 787060170 720720842 50279013 833894212 712503412 571853420 734811885 764726291 751217223 191523476 359217211 656382364 381718908 423414385 976835458 965515835 876858861 337152315 556706501 230878854 407978769 905552522 536211598 751175492 699590050 49853867 846219139 789973677 730245713 751487132 692041242 355968957 507103926 521790245 614068960 804517319 373990227 699635931 861638224 247818416 707178672 600984030 256505001 783170577 667998028 887921392 897498244 618314064 379510459 874841908 128013192 298000227 320898574 200136227 70354580 19208993 626577674 806936389 799589570 843709646 477540617 572112794 659929899 160995580 992438210 441823292 783791063 157880238 962156163 585093771 124246144 286965814 866120821 958112748 273813133 427730773 742098398 568325765 438454477 84938954 568762785 138067662 116761360 382440133 863112903 636905997 292601066 274303243 193112582 24448298 965255449 173100016 533201775 82039122 51981427 206330812 967079642 428050127 870169118 696409850 63042606 531260208 943007647 691558647 553378794 41640333 444127558 59851903 110685176 800038625 568356103 306694411 450167877 205106217 543270100 648757652 227818701 691195657 674382469 218292698 384210831 880333778 869467917 338625801 930530915 244857201 273301292 413753877 58732546 113355541 134464546 908287651 378472415 307824493 622818676 652851718 608939496 923408318 47786539 135215894 651445193 573480045 153671114 636462355 143632219 702502597 444420709 702618768 717209878 588033037 634883757 615426143 735541109 984542174 478885329 707603280 432271466 890519796 740757297 190234653 179402579 683294547 34552667 128342629 455193262 389031928 330024758 768761670 66664880 480546800 580305095 53173773 660395731 285316520 769449407 66087774 790723582 285479344 831513436 628684125 268538027 25956920 284667036 83904589 817570043 385569352 815426029 39536975 37801606 725575358 34055355 658377017 443499514 459734728 848353993 146631264 114006640 845094894 920506207 914875831 243640588 639547111 186625668 319844670 841954598 611363242 309849473 522874705 274437843 362616296 669533768 53640005 252814199 917691843 782638064 245622690 826165132 680899456 92250446 661089913 490466454 825835443 595495987 289259273 827227547 126152842 193443520 678078641 970377179 274817993 113901016 663561628 117226683 98669523 446885616 733536733 18539570 472549722 263094715 62368980 513325224 82998858 806863912 939616744 878631241 743603861 227846441 749029575 310091520 60472576 315571887 569906810 950858014 573849563 407458637 448417929 520816422 395155096 356153641 593455193 330197319 172033195 399588079 829717773 257263081 875313463 248294383 357482098 950140381 161314453 329775118 234403144 936819878 122758913 677737963 182182550 266394864 166249844 310080883 547005835 702856134 125840319 560967391 273715968 748789604 591388198 117235096 780930032 99544160 298335540 357365487 350835017 354534516 908631598 461823844 231660598 924588803 47295594 355418534 288545991 115246592 888418463 271386773 713348667 465670004 781019413 71088963 296353932 176945215 438227578 251568276 322381703 970528708 846947570 88774154 632906 239567861 155753287 392031248 620356313 920479295 942956880 620221227 651382873 674351681 58437613 486546715 911129036 835481800 996746524 50600018 256174479 265949099 111217988 26258665 96300054 348952664 250504016 291140996 520808848 280423750 629902568 751332135 203690501 100372656 427585626 42442460 306724974 392447985 934536825 167403926 919242277 989392432 134809595 349048324 506058656 409363447 644062059 172560855 213690460 61675949 274960395 364968142 900523548 397241298 724978290 308760477 970860919 32334320 242984053 424864852 950816505 201695889 887599235 178463435 165059536 406499007 333172188 515425257 712347065 594008937 731422973 189601955 975277490 952938241 253939481 285567778 826739382 777093833 16220251 111515162 617524631 485982522 100607672 872961078 34518499 345289411 905618986 802112989 486158160 451407366 711321494 391049965 865450441 383350982 197056030 626581992 103145286 171619624 998246941 713517421 192496813 465393926 504088270 744862049 226440317 736536444 361273892 768020660 979934937 866198109 568176174 823823048 42503706 268808224 584235637 540850402 890330210 882146187 464030312 459522094 440550161 57523478 134150729 81118883 589390998 463670280 280498038 771484212 765216099 165516955 759046214 677020249 111073283 597760045 85426745 125061087 825969636 931909785 835394369 291539383 119772504 292255239 367399946 403439955 479489042 33182740 435507165 930505215 988423770 191598153 5553033 621012417 342993267 721768100 277768009 918344660 973526682 169637407 848361657 39864810 35721379 156782331 20580885 728502789 242031904 858835882 511307883 567297065 899513311 430630655 687946624 679324612 247115508 910844746 460610757 298516186 142376939 347007441 204746191 988758263 166426110 182612453 359520032 490728169 789497895 219634337 169792506 413681830 213639357 275838995 137839705 271565070 190559982 771253880 712890231 683053898 121268392 724361994 518672989 120084954 887794797 688473561 659913993 21898494 864504821 654091620 547987179 653203364 172887549 154639325 169143963 479327549 862802249 645818415 379402923 459224513 912056920 197896630 826197408 258078101 230740626 923363206 73668691 334757579 383098472 535672855 905370280 575333448 353451290 603988674 539415381 276822773 469764535 613143779 684791620 233200360 589197659 659345734 334019160 24627387 573964553 645422370 650165693 394911223 356032717 720959710 592325812 968286947 12583772 509778236 790849592 497881280 459839088 439165272 600337264 810281442 154126690 931098917 95840843 813292918 709598018 206462662 630672419 83732667 874476822 127042022 865467844 938865816 638824483 724632896 656071756 296353765 973123343 817776952 867748636 76886591 870316940 801278544 254784462 539614572 997211637 299289167 860833110 631954180 146807499 618535141 17401600 621166566 751426980 549662658 634817262 381717214 258128806 80094162 439023425 440139447 234134929 397501900 47906705 40316869 499701074 853854405 403334828 301083055 988028844 453196955 120822015 416696995 430389800 608962259 555489790 106448510 180929899 188252912 428652726 700880869 637144441 257273804 478972488 99718654 234388830 918946981 769397661 264793285 214612228 392772917 811005726 366134218 206253531 510719023 547226048 918526480 124786569 679939758 904211584 10927789 694779580 131656987 914816966 782537704 548986772 300544 179012655 161247611 394561806 748597307 873460786 15621779 978328145 456856831 697637938 140681849 215976887 389082257 480266112 603719124 855545369 605265934 578872069 267503148 749740544 437012270 101248925 377458619 113246682 286916546 116886444 951691135 86067662 405208246 640393262 725820495 937864159 357088486 471765319 60825441 432081737 685494105 152299123 507763433 44065850 789502097 417561153 674570625 894782939 540676170 104038975 150324176 357562949 20879939 7900691 586800567 606335552 218628827 407479289 936936980 164759492 897714733 206738253 158580657 473371053 566886496 287889396 675202141 519354572 834354828 924840043 641801639 247493115 342491166 901495424 872406398 210755549 447527079 551352542 267874665 174458755 352600404 22997248 373919797 157848294 667471511 924550893 688280319 105550563 327185391 97709293 423058639 504609423 955765900 695512876 308595241 609782443 715188994 311510676 446519836 176721992 741202101 606603948 317648553 911955113 159738120 618305742 850926668 330562668 846960022 888622721 383218109 854290641 178981979 400324506 922812218 48688319 189681597 785860452 525093756 412950218 338125715 235159824 991785391 67093997 783263313 882025727 161191482 615843701 24598795 326241490 141376873 605573500 690690066 718291148 646500834 151745301 299767204 980940190 826024616 252270651 353245837 481892069 701695725 256509627 702752432 399257239 963114071 420305252 387401328 698992158 134430156 92251585 664459175 301459034 223683819 677756983 683788634 341304336 871872816 607339239 307577370 169967498 870017107 50112101 859730476 173568377 670226363 373573484 611703947 110847583 267095744 362920676 4270947 944547370 637125769 342315361 650617094 197404303 382633989 581929542 958255383 749536702 404260980 681741790 1246116 246880348 725215108 998287578 626147326 578466915 464341464 423922510 75016348 863013093 434871239 173320902 465316744 353333199 727604264 154206685 861761986 641365497 753268348 137406249 389115448 840081552 703417268 268970546 306393287 873088673 508714199 523939032 47058998 766410723 608599923 72548365 704574446 283148195 788527802 29737711 793850247 851834056 932491097 99623429 7829529 214833875 441371334 173463210 618712477 309884662 257185865 736962489 64533085 986915645 213019122 958511292 400326759 199241993 611226235 568545500 675033107 354286901 453066984 690411314 745747450 98802479 630455271 283480440 98719364 465955797 991076423 429776236 310195080 740051786 223277871 616306977 163326883 588107824 934730654 971519044 446832666 738426057 474470765 527699686 894185538 572534588 596338064 677158574 835183306 54359404 253779632 952472197 228289245 563451660 111818386 249027109 642677175 464318809 630371286 791294710 536159233 318218726 92172523 449632570 152414199 751213412 828030538 892851638 996047791 821071043 634293924 455620256 702260942 67457014 551477746 177586472 142272007 176352866 665174268 338740825 459063781 938745661 45125752 968103476 599453085 207926469 419444185 100409945 929546635 685920607 109589961 760637230 142668423 556176721 926534297 445216588 190528024 577063926 333100047 479989648 38819722 197530647 478656042 27065531 638681356 377744708 59875331 22971804 482715076 725127433 591083529 639037464 1960840 49189767 153291100 908387095 464575557 621335265 923442209 184948141 419855471 831442097 98892390 530114504 185772644 996958608 584518768 128657336 200288364 911690401 32543183 941569311 32046786 376110446 304959565 194867262 361985140 703399650 821695322 354073663 390904610 644566870 114084067 185533203 676236397 964894152 698265003 156107592 896408572 122404608 388719606 276961663 761878263 841277631 754779517 150217711 237917656 894875412 308097634 834467444 834619680 101220152 323607686 601350942 716947262 806714218 90019203 455801388 219770169 14721337 280736732 53260726 659876301 256445272 277426082 842224609 247680637 854704668 173003844 34260705 330693840 156424986 586024583 812335539 694733926 861764273 730569568 448783006 781186533 557092846 506610597 237741210 969148238 980560946 490956118 975198575 460083480 62876513 157508474 921380760 831707713 409382914 621473948 158124940 556663884 615905387 809374015 561037067 76697154 424511600 791825107 117421723 541984322 975422010 648955353 789719727 763120886 4086542 589816578 711119995 697579922 182676081 431710300 755056277 669486850 393242663 763944970 338919299 696828500 370433083 915959712 853953407 709441245 675729017 889469585 347234576 614609656 359836957 590588439 548962933 737083300 188640693 982421494 669317535 83993160 479728187 235018760 675102446 237638627 96653864 969678945 300081190 267348426 517734785 475417110 931386802 986929126 549585121 509771039 647251779 940433022 714308674 710007669 916835310 902942096 42033293 61732774 841551567 726007238 66623987 609723775 244370132 946610457 810440694 499657997 154514003 25933999 851285373 981332760 823637335 773830744 554667565 810358386 245802851 946647421 655758142 619066637 400004607 360136082 446456308 625482713 910852426 108154001 627635472 950931931 309094846 256604105 305217870 238448308 324467281 43285242 420546138 193795435 161074151 566918697 838962230 666525248 768514354 481258922 855198639 410676110 838499086 216022924 825820832 638973241 944337271 721180774 677057501 442826485 323160328 130495783 146267184 10046505 23115756 176576913 530023313 595717287 277271041 420934467 450826952 546721746 126965583 640188306 393755216 743744880 558405284 95146761 662111608 954668894 178660245 602226805 426797800 853700660 951317721 384626165 329981990 108055057 836332759 518679289 241124716 802033936 986858800 533738349 811529945 313947501 400711104 265471858 905202398 761624202 725311428 510790902 45284833 201325879 456571703 907042345 108415874 12984911 905376550 205905660 174478151 792929649 220536655 118004251 336441402 376739937 359358544 61678469 455473549 121411757 727875837 592177840 170311712 907953825 609417876 637805252 573758257 976573828 288955335 926089899 853960449 495580379 492168984 453234834 694905991 898062487 389831076 650091266 769655206 580817956 143950221 852987873 672051473 435575267 95257406 771121516 157629902 552714750 773105061 976147013 446386386 901390156 287631939 363167433 17629015 410521356 799811268 387597950 925983806 864336527 733509743 3602699 546323517 988616060 561246579 905120252 395633019 182065752 717553298 54345469 945781135 543093898 981923716 478214504 840038007 775086042 402016672 599828758 311133975 881797865 53630069 596974423 400505613 38964643 164402272 494909125 929682654 510315958 715345904 839547973 197197257 641555565 803247093 875225322 323313271 63877709 946535447 544855985 257012969 49056151 355579044 142921095 188484597 136804808 258444122 195504510 704637750 858405307 15578860 173201035 935406195 749419761 653793237 668428462 391901775 426709905 383956176 339140208 665949422 707260057 591531725 581652828 85600080 72129747 937109655 247720497 721904362 658694904 523891116 491391546 548077690 177885114 577734651 865375344 189526195 996364110 733668068 349762373 549013136 44299755 734424422 208117607 454723778 492164018 337594397 934595229 643560609 195359433 200213375 172886222 209344397 929155429 4584006 751666165 12600925 535521231 516180216 566387025 198311607 909960466 665899230 460877289 113510402 201899425 652291110 227576081 609191740 947855014 792006532 499507147 560379964 683905420 270238713 295192342 901570695 10879544 802323549 526908877 842448815 223991996 440103409 854011477 592514923 80064888 601223490 511809508 54949980 467863118 532178882 182976552 844253449 261152674 802517987 607235395 798472415 153245528 719408119 948446741 19343525 64730560 592011687 434322316 548544803 93091932 235495405 220819496 947982398 271681564 72031266 528695598 843251953 347279136 573686064 583913315 415781469 599570297 450467199 390402314 867230267 929631698 984020818 414462822 775961432 84692391 924005597 791718125 210832121 268292406 370497150 895399546 693681530 80663261 452538397 893818043 23763125 665082134 78969252 894701641 610300849 291932808 954775132 838695500 692469479 923614459 288122612 666851535 914145892 646218417 856067503 40059227 300914467 533943208 385310372 388839921 186856444 990189958 331304721 775618056 655497817 690682076 104684177 91565298 801359044 819212294 575173429 228572278 59071679 239511097 494267164 130144410 677546688 542839247 236618580 210255885 814498768 185142544 753994016 632024388 498753782 67609456 397581332 644010740 98118121 527696902 95002725 690331019 913948988 322687046 769001106 108965846 594076686 367792682 212298225 976931395 462501986 705959274 638685758 227817504 389618045 566333198 530149569 788330028 907037500 617227228 292461436 979174908 935955508 282903380 738471427 199897748 465156821 431671475 922433415 881147513 135654866 681221609 836545085 36864784 444007767 710954277 936452566 140519780 44078254 131574351 814212289 951676130 146059435 672590828 187863345 991375456 104318094 347082233 550574020 663988360 818004518 890626144 89301950 386291730 842261235 351087758 310756935 66819189 592507099 933871116 464370887 474652123 402781444 997702471 884434090 6157120 152703297 184194279 259295795 380490072 11431030 645220524 760970445 734944204 432597392 196637675 603613582 313770974 452820741 732948556 40872889 496407246 321838020 165755562 87726327 814229461 355693847 472603781 583074695 95626176 430916727 145807766 492614763 936081877 941185723 264593550 82230353 122424648 451087202 735331074 705705396 154070234 995092889 569253745 260812766 911320420 510196534 455951037 483379538 604679294 303703435 167292565 995165337 213945892 758755564 981679817 827453108 518105850 274382754 645839147 443251938 121000330 856384790 140638433 15363858 539586481 89988773 428002164 163090805 885032035 864048418 179736859 117026319 765902956 807095685 740815487 108346901 43123000 882471386 758128193 565296003 983509514 408445096 226355005 778852152 915186873 319512191 804794635 466549205 92542595 134001616 134032694 835975170 14474357 943492723 811769062 973170821 162147257 871617854 579217179 768582397 714188945 363175431 454877017 712781967 4280638 193150726 228220566 45339746 769694882 834768943 118208914 485580859 653858077 22261948 389835193 801521254 817392600 859159291 324244733 607217948 788535660 823072446 978212133 655378495 126811633 560532713 805611538 141379844 908044471 679921346 905372751 826881073 601090743 995432539 266957386 122863760 720108680 943128560 306019963 293955903 395723706 235965337 212569407 758210292 90911662 150236983 569556653 668701123 695616257 301772316 644954239 462268890 481455335 92861539 430139627 94277956 515034112 188700218 213237502 124973920 616577578 103369756 173292811 602080258 444352257 838350639 887520750 145802760 49612099 862875999 353544281 875084433 73493514 224288317 230830548 794663839 192941104 519647248 3915214 805323936 598029134 143976499 463756987 899658210 818286455 139524837 478633107 93321800 823003856 60129182 220233856 763504318 821890803 587806799 683997723 673201110 915772234 709075886 1411108 174330688 733159282 168636053 581813273 473508848 212180033 64206049 250899415 875354132 568399729 457559310 67159817 489092556 672980580 526218744 122992624 473248395 679433580 826808292 369414945 983337247 266269276 477283884 235364138 530121432 318261380 836032442 908365101 946070480 547296267 887931424 215636417 327940166 119229331 768716258 352174380 533520869 809318538 631682673 55543970 869170813 719580499 594288769 61606300 444623533 21260509 188572185 628386962 599808483 240708578 105138570 46489070 749552848 829026661 84068525 886565561 443831767 857507733 101339271 551488592 716211118 502604953 486514372 307411454 308630421 275121549 276843151 413666630 15712738 794814330 121255677 853512944 646518805 938603340 242406384 741975105 581636476 760502399 967964288 654230451 888541869 850595117 684465259 749612037 120568576 623060424 851944844 855083232 602246705 525586167 130640178 666455480 277246483 121023568 155707715 679401410 195191638 734819611 616591245 401094186 664175453 706636506 493153377 908611205 75181025 345151522 189858348 157451600 356849842 977659679 790343134 916144773 376279626 164232489 928105427 435033519 693635771 158491706 115275491 538249039 153877566 990804253 121552469 33358064 24679463 718643004 880458960 619322022 659474296 367239277 696211634 358407146 268697236 225290042 284094464 293280373 293918501 310527779 805946688 428110456 754752962 359753617 80032346 519928808 48577604 718502490 994843576 91455971 336034335 265833751 550739757 204695795 251791205 413837174 397050138 575378465 134689715 905460699 427566814 318410316 694166776 834078360 175641109 986931041 804620723 493267979 165888366 607844167 158099896 22890608 400717820 120991843 962110181 99985472 527136289 484014364 65339857 927189422 802090058 785284533 667985507 358347040 507518896 879135377 976756853 592498682 296474059 793300303 361691404 849218034 460112118 328451297 79458737 984506920 242573987 736202691 308241777 670009960 718494654 156847356 692030441 30375387 4555874 37353387 206758511 436238485 64709554 453631113 836474130 749214414 602351610 405115283 676661934 149453278 751411259 935872541 477237540 100148799 728713011 840487931 8684252 121782815 422479121 686912786 495463689 352897724 327831959 287456929 31709658 864750480 177919285 452275440 231932693 350173134 92164822 848621030 84853124 920945337 385721487 952322672 735202274 10630727 795657436 195720584 142252026 717041251 975568459 609692808 647354900 641394510 10614988 939203235 650865167 543398339 353950091 113108320 911794747 990302560 891981305 36894256 492557457 847042533 406550055 46325324 889805930 297446423 237844227 208516692 745694121 49410974 134232343 482628484 946285402 755235904 222458177 656802845 795442015 275623230 147359601 887521486 264023424 244197636 807035537 901616930 409115593 73352392 417535187 653946939 305341683 240838705 90508379 756450569 836294650 501264026 736229815 644370427 330969091 533419308 504337235 324371559 533449211 855897428 86660536 553750881 223739691 107785499 809006530 634423456 804743894 721603210 323995418 49796678 270417692 668021817 60657253 897536404 14276680 475726246 422904407 306411367 765680072 597571459 393420892 472592589 712981278 969288304 928506738 102670592 572892940 341362952 810547730 784478181 622586885 148535067 32239278 738276023 603648442 286040758 862928414 873767824 859927195 922496207 82698247 814125125 420669749 523401310 725866819 747971594 480724262 891593074 450457159 329400136 452045311 160972072 532897803 981194327 459387669 845437163 227209126 70880119 7090029 584130876 994802098 523756051 419107575 973956048 322402267 619541784 684660686 630190744 578091518 959445951 616514214 939670125 278023399 291038079 809247991 220010586 484381068 821610162 700018164 959929866 43155938 563837571 629710582 986260975 80163502 577303067 906894403 361608807 338870459 224428060 719923869 692428502 874261011 958879427 650317497 801059671 693080529 865263218 495481431 726359417 216286772 433796934 384485307 323623251 762443801 981954876 361509553 649154149 445358572 961780331 340737733 170967226 660476309 717212710 193995755 199023470 75885760 145194872 432752860 393143916 258325784 648158837 128714527 759323967 604005782 903086796 204008290 838184285 425902534 507639644 191916490 124233557 990050686 629342655 101278320 497418995 710414451 640011164 248402518 789775139 195692817 235497396 64673748 739421584 668853383 605486900 99364791 145583873 270596010 344533145 185406837 263696202 328886076 982410131 530936594 213263959 127450051 421509763 447953740 662170965 554346419 591540939 315918503 696236540 9480673 927638164 470956826 19791808 432671382 177843774 918939687 878561587 873897826 830215637 128298314 330504197 737863627 821376533 959377753 732647588 162082732 950436852 112931403 749129399 920063293 235716417 670821575 982221802 384895160 703424476 77569301 365647074 329323564 108327561 980186824 889432986 622909879 325943301 462035180 102698399 355146295 243896343 641536448 100167605 41715931 577889687 638195443 933413354 358934505 140163677 868922266 295920025 693442192 725651996 237583467 245065276 781263054 893119605 195771741 262963981 512390086 517042691 336959944 269343361 238516827 521668851 788043835 105715929 609278708 287013764 274641860 456024084 514500048 582221883 304777593 626584180 49456130 387947302 261351462 507633984 205056711 96862441 941767527 313597504 21587726 667869262 678241868 341476126 733150713 299651747 872865465 79269744 972285645 818073396 447083599 422657972 568207511 848824154 284371778 722605518 917485506 689194895 459699991 721905663 461124341 840008187 634386362 906975201 11468139 903154576 838838287 211174892 24447798 665010331 737058692 230883175 850269903 182392095 455201427 48611575 235786152 766648791 846492081 968588891 907931924 883546770 265350347 536351758 746267150 807262767 868254512 813275131 250055133 307495547 654747508 716197554 527462864 354784027 773875199 864237534 937858905 951681651 624772176 685985379 932507813 203059317 140963892 832396212 917300361 516679343 375309431 141060398 739659849 447648107 945202730 779553589 741569207 385799939 657906123 592273565 279850907 437580576 376531269 52543968 970958641 192638556 879405639 372147608 285349746 606438745 588410381 368494293 543751234 103122250 693403573 477274592 59439576 674937448 123028573 239951017 934386312 649228955 190752383 467748481 139594785 142035480 331299723 98841205 292137203 616591940 679061269 170758410 287624015 295154794 614377838 775530141 981538362 437526649 650771712 906672078 25986179 276449293 784091672 261302756 687368070 841665518 883013171 307121968 546720029 865121949 357012345 76425506 462567902 492905553 435047567 951422575 442679736 711558514 804943129 842051462 240938246 337709188 730861857 256878754 61161053 547507175 676479877 138437604 705894953 148781724 919547115 64169878 792025493 8364964 717366210 331195259 874706705 519237361 509715546 420791139 434878515 373797054 253982693 836530971 331505429 554060937 344237921 778559643 657941345 489763726 527249830 361434900 767775904 864693170 938512357 402253832 330373506 495474083 12884132 397064664 868715409 723216835 118507091 219603306 869779777 434916501 679506410 439891526 714922401 978369696 865614658 760689311 805919580 370121252 957491819 356095955 622955971 558935260 877312502 149644719 116430017 579816152 128468552 633611549 441886374 898412591 950112670 464991209 22908660 466861730 505629500 770895496 312366762 734632072 888849549 775265878 585374544 25178918 471119773 385875387 163478324 417499320 350778646 674059415 631684765 358771153 340241011 334979548 47261784 566052011 873470273 122239995 666697717 420165206 955878354 525961671 645815664 618998212 307480341 300292200 465407872 116718532 523597205 638503054 490365596 291045981 307517429 525218175 758647782 301571277 524149834 384070483 451506114 623573585 686439478 428631291 915606790 552861571 979212698 812641683 668981194 377757463 48854339 390126428 808360966 962690716 739730449 220833101 944151783 562739224 598348923 217589212 664688639 785168267 606187903 559277687 515728372 589836316 385177105 500297110 529463598 757455506 780253846 73961890 626719284 579332218 455741248 907017997 533663525 156680516 662712599 28968455 466809996 85175789 326802601 34532545 394458697 325065186 419742633 316343787 543324542 777948874 570614149 549635931 108551921 278699986 222876389 421519497 345228442 269203897 61452682 997905050 362191686 227358985 867006256 668478342 318886175 915729709 718627341 460826379 286188258 278652972 449205679 503257533 875536752 859769592 946797050 435672678 447621052 14779879 430167136 993482525 21159575 845906022 282954830 430574310 244570973 526792745 614876238 284872697 353870684 168361808 547654278 489275743 28477297 71179276 229462610 967901873 824820672 328964351 490570435 796125139 916242886 433260090 201565156 485093478 415662071 853416681 843764313 115848826 270455743 742360231 96427470 263884515 294764120 970410328 416224365 935773414 75017600 923668743 741476868 452720886 273886675 433781605 21037966 566126427 537716512 778972185 863134018 119752414 891318871 787645758 407739054 442439021 365143264 997754452 415814012 382364187 941245776 603846905 155373637 600919414 686932455 276147726 396334088 707364606 83318462 637284513 825805122 651321936 81756452 826692942 265113834 438990899 536683937 88445809 154188335 886502937 759542504 136572965 769711419 610110078 711932734 332893252 797204660 930665151 737525605 292270844 624590439 379726933 519566977 259880600 506033317 645731577 723255228 531150114 466181280 606069967 985463108 884248491 405947064 316911083 28511334 302220886 519439065 272851556 761929051 887783569 461199949 648903702 694649383 807223675 965394366 669201738 25911484 464723049 424432890 26622690 949668033 480724320 204776268 242738777 71270965 369606134 945120290 709315879 122264298 538025097 765679098 801218507 404072833 663538421 216731511 756534172 139379920 106030728 284723850 514714276 139832843 594593572 700659580 247328687 200423863 694592625 62107755 792588632 90191159 425134177 335426211 929867472 45076720 366116700 724393131 375041480 831848919 206012758 991313188 127321888 266116173 669927046 483441476 132975384 21254041 306975097 978641354 311655571 329054395 43605574 861030655 601680546 240468276 863161640 841268129 928225223 113445628 287383313 968579143 124696193 684136847 64040908 842234806 709579806 447328618 396759714 219421343 706591316 709447537 635202285 968097807 668807843 66449446 517820061 540526305 314914329 154050915 121902293 469490978 674163549 311494075 431658511 156209510 419841174 405520617 100143569 298884017 132522072 165207891 591615632 313922543 844062845 209661990 395759073 690683755 878486782 782971747 667105271 250338663 941351841 542941761 725805788 939428006 160750436 774021284 609578351 102360593 303846722 75057703 697449229 110989125 637705519 702647606 786919457 678026247 318210928 48961151 430047336 358079465 22805788 131331062 52345309 928174279 451398122 475028561 689238226 993561211 925285559 761181586 183556946 20760084 435241327 395854651 873793408 966928469 96894929 141186647 289216153 163365920 712589121 165048927 608540360 495406693 675265729 433359811 269318812 457703944 594102114 616032454 500681136 19503727 658014105 944101013 272689462 870456528 100015088 360030995 470838959 237953626 986513438 447942284 369231907 616012566 281443543 952695740 838697604 645275919 750719864 632479625 274682941 630468277 694415277 842452416 864249598 814390632 623486644 567821105 626266239 388997682 109944466 778434118 453262744 582556626 858119210 972246041 708414795 151898642 155001254 173073903 806545728 85739814 246489793 632705218 596286876 46556394 128712178 274521797 859767427 245822248 747232746 489628037 251591376 51882452 72823 49336089 673503503 460545691 497350720 943271956 292272331 288630794 833156883 957489590 160943842 86305362 985482729 283813099 734546034 13638952 343150259 216019690 880202282 726649781 38209371 688078487 938958700 231884740 530621747 469550294 647588894 620223330 864090870 821965633 156305090 591245083 6507191 975199126 128493913 581220704 9483873 617174097 899970519 30767544 746262303 554932086 989431577 733502917 898847591 717530786 623341755 69475691 492450592 413151043 271028058 323192908 522532892 797231714 63892775 320646362 403889433 401144612 209105655 203298366 271952683 654865864 48981663 927732378 832379509 113528561 497536795 31046431 681130125 442228717 940064300 421331694 805773999 34309532 559739195 731389215 630271687 601121344 655208929 531111175 416058143 275297470 620822982 954523921 234262712 799314490 24020617 454217927 324050855 810323606 601093309 804739672 340241448 396125802 602697229 190261957 925525307 439643344 94191768 608226956 115839518 741448569 297856929 763192532 44849191 464303603 782102653 969623241 424173440 710012504 372723390 548208935 169416481 896056886 183746087 122745556 810982906 507091276 99722421 78723621 182155 404776710 352582723 977761299 53351479 20379756 4797847 489294143 610966099 406540461 879621398 760200811 612865775 543821309 361159799 709860479 299963842 173677719 108545204 732002107 895972920 901057520 936062481 566283530 129122503 477249357 229454754 960750586 663620772 680376108 751522122 397084450 823366673 27231356 145726988 431317926 639860777 4957419 138580520 255922518 45449376 702214294 268969175 379042466 555787313 212311174 150081218 795337191 623181254 188385425 411106950 610182713 963909825 614061229 653578106 411500825 932920170 491667580 2200340 964019383 965697520 270398235 632042669 2529172 295325519 812935865 938236669 682229509 522694713 252777623 80997992 171149549 212388651 316949882 155016734 295458655 411675238 308767521 474637274 998169426 331664144 721039328 905483399 332243945 6965709 165227455 429342540 950570152 993958365 903994952 984863803 349130123 125845955 668731153 334521378 553269286 269270193 922163428 443708572 953905626 585340856 974757771 951368777 964147865 434917452 362843450 750222355 273026659 597004600 967179888 771681499 795469441 26466085 444414652 335153604 341133046 611355164 641628971 385837692 430551235 230016497 650728132 623325667 345401211 952259858 189029926 363291159 607369243 727597182 1538555 193945452 8383685 485046371 498908971 215831426 935562838 719033576 317656300 644596124 524210080 201984219 744801013 509879595 715447070 565944572 216083667 223805774 369307374 91159148 591380136 376845518 228134980 175782360 672537713 678936261 997253819 821926947 753542064 82443732 526235231 107785972 29668441 169349561 600466435 999366124 289703725 628680444 141474860 931497996 573196333 91331789 373541061 263743733 220925658 826610688 810213487 482888678 482367045 309238879 103085843 164557403 678781949 188848918 21364922 127260276 114472865 85424014 606568120 918325770 133915778 287174785 420582295 67477274 112868861 606173651 362846389 507040893 549331193 890217417 155274542 805958826 627788786 325703315 916436972 266348901 519163814 897016849 313721121 215429965 881450521 377286339 957849502 645911114 712228205 598382701 771889087 891988115 302547725 966936181 874860628 598552076 325692348 128859059 267978724 454059430 118412722 244241779 767343338 434281583 11291825 841435841 361561551 520036501 600668309 279301721 739458858 52694420 273853603 336387553 339576374 93404722 344981997 26033965 681460479 696713955 849728910 613920787 224492006 873317289 587261277 718808684 752835057 50307880 880975752 716778685 547624806 887805662 804182120 205584337 357598928 213197273 638045786 317114636 534557524 561167345 716034118 275021406 608401692 517123259 827034025 938192202 459399850 106175581 36348873 362525219 718117051 414127904 658370816 613037081 84712879 543923954 781713582 956771046 883387072 809049131 389078593 579699329 659608205 934442753 931703312 17961240 134925125 634356071 662460239 186455992 37029574 190300459 468092165 713346627 479412427 358926100 977916024 692952005 623961656 147720332 371380807 736767529 439535440 411710666 615523517 138434482 732600444 625553149 955823757 846263926 85839074 85632215 891470135 664787735 415907626 857137524 723578714 563687682 380398229 103986882 676712001 214078878 467698458 603550959 37805718 162079259 37921362 908768280 377454926 676798932 112081759 343113272 642449487 763505558 267479978 72624889 598141897 533203476 810580245 145324581 952187363 739950208 362165876 940661090 889084964 15745049 174924200 328067001 22076579 171845068 800536450 923975572 622676908 280989303 745760669 725742486 614561191 887409010 357454171 61385112 203372912 137818952 410202106 530714438 115827162 456143904 804627554 673080288 714320788 512980597 409610237 748584932 643400977 128162726 830219682 345103230 194840706 20220209 733659930 320751427 299754082 864011768 583718610 848051168 85323647 991759244 458332653 374189323 407940277 323921266 699396269 950780133 227694487 568016449 632000805 790546627 159699362 365946027 712378395 124643467 538963118 893041789 861331330 561703386 459613320 383793366 462416197 187528697 411053649 13029616 493211768 157658269 418636923 119561513 34402845 129472938 111383488 920375502 212622477 5681506 498269500 396563260 97231977 375329622 172293939 706265303 599068470 716796193 306188670 687676862 850605757 839994375 423118835 727016003 989793786 707114576 694253846 265352599 999421313 921513698 696099753 378589510 156185071 655308739 734818660 249703190 765099107 645525454 331325101 989225295 42023449 267224071 820798615 164809218 774795159 129274939 379470644 860351921 314928652 281218197 868719544 146306406 601560254 838860238 890962905 602674287 399550334 463502642 877057569 408189904 276575588 2734287 742354716 267288716 555189922 300191207 678247756 754015039 633249134 583072824 140565083 244238362 805016285 24261826 742065333 442234496 366751776 417644500 710038424 229716516 584633348 968860542 722676368 591059798 997196000 1050536 488776036 486140151 788177433 607973828 132251175 900311583 823053578 602498206 832543066 565989037 946959297 242329858 266497815 203511711 953447697 561708343 200972316 364015163 67839719 908996768 662930263 80796897 727660852 688870500 58484783 595209601 526673489 998073373 94910620 29186664 911493608 718667297 901828770 959722479 575819699 597032735 395975287 925287341 6363873 507809953 947385556 513479400 406929638 644599342 992859535 642249725 667450499 545205619 604285523 267376430 288586971 968894400 894470949 32416681 641454422 13540588 965493388 798118705 926297929 171186743 285012248 560936386 509159541 423162694 334073336 688834737 860297186 487283666 554912442 92615106 984182858 951781700 713829999 677017749 349516933 880111128 467850792 652530453 539402424 155562059 867082384 289056219 991693280 717624981 420970491 715546933 811715714 738366214 170249711 57939235 686665559 464358545 903944009 916296566 276926546 206019918 231709444 785772227 894225835 756212204 263775046 738662465 5738269 822093789 590958486 466132700 536254481 868229998 345987480 669051727 881551789 938669547 445565820 881537139 226301024 705310520 733570201 425149633 336273515 712736487 472980367 215936136 40955194 373199406 755938299 645983428 259832503 219333519 617104132 966570737 799610651 739981534 685616083 591177558 570552614 689960918 637336638 167806499 300130667 414359950 121227563 162307137 58590059 185810287 847724725 302100219 119212214 479482934 117703074 692491029 205731093 971878812 140943692 577861855 714409027 89490959 590442924 914409691 513545456 767386041 516817929 623353218 522845378 488164987 557386265 522524301 476207298 803261301 539100995 443184648 926668605 720063531 102256761 431553728 877948512 167740170 695072626 353978100 802978644 336636050 554261549 248479256 664083858 405089049 842968421 319677722 85422901 374587481 332367370 77274704 359252901 547950193 631394885 969539401 521097752 130350881 704414204 225949642 305719423 805768536 727992216 639594907 687279227 905960905 786532905 501024897 923702213 220664780 709695267 239148352 920172299 822308010 33198485 358634677 566611979 729793556 177580542 534513863 560674074 67076734 792528394 537601768 443466784 117676193 498243519 647751864 84148429 713882566 389788571 124356201 615894010 616945260 241477304 99431291 967564398 895636649 785248830 955234100 776408217 787694181 281081465 81606785 597639792 621987351 605587140 917224149 65766905 627636878 635087734 883536512 774174755 561846364 655257511 243190751 737745799 896561333 31878453 164714445 767363125 983530185 835175662 848754329 847070192 767211833 507591010 39110152 507505809 384241471 300307984 833526600 492576112 673610511 899003754 866992076 920566148 460994942 47677723 174451560 8995732 835217934 483663023 113877817 572112315 822856869 552835367 244864096 101302341 231429600 250333933 825740839 340503308 940531906 838588889 727251231 399733405 253891887 553861297 299215954 257520487 70964030 701628955 787566070 43026989 774247687 251504931 981580486 618323545 696469436 819401101 699803909 727893368 732868579 667400336 878226915 842293813 419046610 646288042 653997041 696402720 925270666 624788204 367355337 788836059 220574102 768794361 876054985 983015132 759818983 814621200 219916659 907105514 488139275 70100902 586768507 544852049 701878206 67564364 794614635 872383973 365734333 302174808 550535142 813355016 506841855 685547745 172163356 119144679 798971396 274392888 822131653 277376733 921725213 893829595 456914977 554907109 214388120 809417545 409204847 605820412 323731325 279098931 609505193 83464473 216654251 188268307 729014522 789377091 38376137 626167142 703988920 778790143 362065227 170607393 711089176 843827653 773373784 114725539 603642199 549702808 418664223 607604066 307458054 680252 337508738 233352033 357561549 875611622 956206669 336352190 875253466 519238771 859354686 783995456 182388441 742334366 570187913 311779867 984669745 355005905 373387974 147940369 31501200 107163544 838779943 380718044 866533539 134060172 350963285 584005802 660038473 660750534 202344581 336626628 638939471 691979445 797765620 340253605 11158030 64873114 79560298 228595631 719469466 840303856 245371169 164302242 548681097 35977173 638050011 698684586 340570720 125618685 613900288 415230424 715157092 353963246 224609071 223303968 544332860 88153725 620705772 845492369 448011344 343953741 579989930 801610239 856049400 644352437 430857578 618892803 727388197 72962955 230002692 518585380 350075778 776021516 359979531 192705229 781568060 144124466 886479293 676560040 717265906 532814156 873992035 95803944 148590459 287030238 830829181 502344861 647334357 344828383 756816022 940185306 620998213 994736312 137303091 443340729 834641410 123116445 862628510 40256827 227765131 630601470 98632603 958082850 45102384 825407369 33869574 774500840 64481784 229139730 635744891 73552884 645911774 643549273 770498556 788750180 783861720 988298723 263368205 794355345 331660357 551048975 989863006 452982702 967961592 346385993 456298822 563565827 97774951 601708275 760024766 943430163 744403769 990039107 543837222 45995366 312857135 649200853 921005692 75454705 497648691 225711028 169026263 654407591 150129326 77185507 778390444 587847129 517721398 17426884 171379444 823459457 967666318 827163335 254335157 818322586 376883790 751643460 611619913 672404008 495367765 241552696 339240353 966838144 801481581 677260542 104839656 652146296 325031474 898341490 808800891 645250453 324815240 791881883 261421082 802645522 9985086 665493173 67879133 297967134 542719592 334538594 220168597 970619892 192596377 95152516 358341916 524948481 433473761 889973228 320312408 998089387 231856762 974248501 223336393 715670090 845594560 442345457 356625750 67529360 540840177 898089833 685797344 907446070 388879981 954072576 119250677 808892976 699423055 198279944 833386138 172506936 371125040 200897218 340286439 963161728 379343001 751692321 64812771 14130011 196303542 157071811 409063218 968041054 223354924 361200076 253519536 232742390 456874421 667851881 78326983 464167898 154622545 205948762 544379178 403245458 502996921 303491694 156481166 817969621 649168837 787313243 873152134 734785331 863558551 144574361 745316362 631901730 906940390 490207089 644972304 860680637 714297980 855148379 323279796 368679504 613278352 336220862 57149756 307183607 432341257 845680809 368667435 560277497 204550541 410083380 37251217 523903839 311685590 156456266 660415894 66407579 63273165 1671244 547772137 967347871 851590011 555393737 829277473 676720175 177465526 264773619 368190175 132605465 703102634 341838007 502403924 567779416 700760658 533524777 97544 260277927 844148552 351638322 51687565 913097308 469626405 779759728 401888545 484703316 908167175 79156131 997859579 568979384 190045125 753396686 697077311 222067958 89118063 600383475 244424355 994045339 218109064 449894202 201175455 503789766 917171548 16423861 516859473 424646637 767047388 622540075 472171223 575133457 900238432 978622296 702579085 272552436 519491302 895427265 592450555 841173348 301800361 742726484 358541195 376644315 19930422 299483235 678794734 281156826 575399559 645375997 745125595 870514371 388698323 912183457 940371024 542121396 440084815 337013756 599809758 905682789 472521749 20009064 703872957 100970722 312631844 385719487 573197855 427813664 836321520 931470613 323358339 527814932 742834689 188697943 462729823 935697523 451409667 945531906 939936916 706998920 667844042 761645260 398770281 900185532 683892055 165981928 315852181 833322075 80145197 365802628 451374106 396882077 7566360 318840343 601318961 516753839 508367238 289335738 608262051 982568366 261906094 792094183 835383204 429928975 923011326 881999892 568475247 483347718 616526519 331390422 399422820 810225816 123518413 81971679 656172336 134044646 557129070 315099090 811714543 566791741 916751311 455741314 818010418 766632166 975218383 798318044 522810849 802819233 428262084 997012751 251777483 763444586 630653856 360900775 929097129 520123805 469212192 887688345 378211058 3607611 660384724 90947643 838058658 832334032 253458554 488794607 532973325 222259425 644560052 595240400 701581401 980002368 620951356 456037115 97426340 177931107 362999076 414081191 17449255 211196626 333970690 29919452 989179366 319532639 336009511 135948352 744899671 572800663 26142387 208456530 956891887 293914989 870374710 365174616 784637156 343752587 252548601 290363826 736483816 611986060 495054277 726139843 85848488 137837380 91163674 575950017 7374333 896665819 652753976 208288371 618102307 732655218 147355183 601923704 671709124 347232109 15146394 858208203 508191548 296563268 427225854 59307783 758970380 912000328 631492052 818815438 851267995 450363069 400610032 974484601 111918058 780225234 17281437 819073371 362594853 612170530 165139497 861823296 722936273 800232607 260267679 616235850 852446011 273715305 824809625 535271160 223488258 726557835 963335576 203110495 149889583 103875170 284954995 757420833 75205230 221006325 152004158 255904095 647636559 6027977 398526812 488399151 212538122 334127298 597123145 526263138 848660487 734825831 114708542 591833779 587174164 88360597 911541330 68000215 910796989 345019758 552987723 580638313 72833018 601539699 812852255 957196139 800077579 395674230 715381912 617836620 25643943 161664632 284334937 21541100 891326379 679742172 355712298 692545068 34452825 898760889 999006538 923869526 503060215 434824515 463658773 506935755 340323669 281644412 494153308 162118265 700166507 579529428 467156615 319879060 406954275 633443387 840898439 57128020 519668984 81292780 735867074 815091768 695558928 189540237 477624452 84252358 587813878 552343249 487828025 682585031 90045388 736595370 781682608 317024833 949227128 720856566 594669165 772098406 761988449 179603641 405848637 167506846 984930999 741146623 793840766 850178217 809990906 292891238 314693410 76161446 43199671 732773874 394456817 703374251 927602782 489919049 292464819 580174770 545299904 350801349 694169537 879230023 500383336 877906031 367988359 877079483 756014057 311266592 227956665 370325870 310169194 823919847 572349836 79094092 769698709 864763370 844264258 41385814 280217497 537277968 127726598 475793543 895676794 467374720 702914806 995510058 244163971 524049433 956747718 372413510 29023764 622036198 551675487 625004145 969057529 164338719 274495183 481195068 256923788 369189271 452504181 465316427 876638691 714919444 967860026 72700375 676105693 244698875 121856504 979991252 450501710 45566157 784827049 765835193 842699036 26384056 132293390 186819179 343075950 650937398 507588004 153564784 631099929 827856125 976079731 330589158 795081395 559425802 164321769 823428918 881416696 45446990 364434509 529114710 962091470 65242435 360453844 113092134 858537832 902152242 76246308 402339100 934837316 967847593 71357714 79483290 13142420 247461077 682173465 494275686 748773660 253417485 550419083 527681816 764329441 305638981 395291776 465903253 773614882 965035039 441871581 133170043 146395644 516030439 443305109 259929211 504379793 717214909 306843693 294545928 15546411 276077812 387058899 923105363 266934217 236878423 323616809 961825164 938453894 518797408 877626942 814093192 450018224 654928781 766323021 945943368 711731511 920049310 396505567 55896237 623970304 456059472 336305238 81859468 150625521 634828505 618504083 308080457 467652098 907044326 850045864 471840114 326020345 131350357 531124355 7031274 413236183 676434655 301610966 295217420 969758741 192391471 497851710 605097303 254485786 771460209 928395894 280603385 83081699 449677283 179620645 849418620 705027009 162892067 103127564 369242287 697452309 368183794 344521839 702386499 759174988 143419388 123257420 455524039 231017669 790338840 776678265 986045626 822040909 829768857 116810730 630361329 621722234 531598334 861095683 901165842 564743626 777655505 342546733 564593095 930974365 476412773 269360247 246196724 522279212 831357712 164011189 365629275 883677484 493255296 165112623 13292377 716885925 284910086 223905312 254788109 23290734 254429345 630922557 919501996 319284124 395946342 730383547 746234418 217104790 15114486 696206783 336023429 780856530 995274930 241059665 426726697 833224614 156727220 164591940 481731490 289279116 661829891 90482924 415905366 672958637 156173524 129473950 176526609 15858365 354200077 166579797 941202412 223854933 786494835 29016908 944786559 152806609 8337627 584015912 62994663 380743063 371903674 782999614 106412846 531311500 478568998 558399024 799939532 692953541 636640235 525894488 270316637 535795773 240330472 444080695 335683910 538962991 427783408 207859404 412456230 282085238 407410978 147413816 412671473 878280722 250239813 721054979 943935610 705223366 848106377 560633819 109599100 155712501 535767488 754452369 340721168 920638657 213819849 884056445 418581293 415701931 351352834 490597123 456126910 34873682 334655255 962052371 930301732 16813008 830136923 431131896 397451300 981138932 632515292 612188342 890100212 551378467 942696362 442119857 366138505 664934116 933583942 824368231 403025951 751665958 876588877 763417608 712096173 833582731 10161786 516726346 385671521 139597302 900212548 181971303 198301747 829039058 465250965 810599650 723468789 248952604 869471423 120271221 634405295 542360384 287197930 30641979 844098440 315718765 549984927 677592356 897132955 288877503 807427083 399047901 845047503 262473200 364228730 57289865 623900873 727246156 407139493 346660005 667019947 137890100 236550588 591434595 490241701 224626928 377995649 781226180 252163191 607063776 175605732 1257257 93691752 266698166 490030623 343111400 363213890 490471895 121463970 581825125 951021545 766229812 82234173 687097640 876800128 415794283 584697206 949623535 250440902 999071914 457957699 680129805 75467523 446746759 408493398 447780122 419856491 582341667 627375576 850680533 362291466 181804483 239894110 428572529 4831046 449461409 831979786 233459984 863384247 708411763 706308325 112661610 318269742 119388880 221607789 354962391 459197776 116985398 346932677 451730907 102837245 357605667 387342071 215797673 735179220 290957425 140839606 329533525 985406242 62996938 378030403 939118750 628240549 479789729 574808154 967541230 218848179 903047967 591242437 734386588 60267841 981257332 493635563 157349957 682799997 474868083 741467154 968901620 274449241 814962201 38850166 718170195 34051346 792270403 34703009 675016482 616765477 795436328 964588362 240720519 164918920 498960519 439985506 620242636 682349810 278290656 558653942 739626354 4896433 163894828 704567888 899929630 974158483 471575634 702873381 479363176 130542500 878508768 55237754 944516142 704548522 545197013 605832738 90147877 596016731 600221303 467195057 764217103 706657321 120709097 808279965 502495480 861513129 745524294 317542060 150732307 558545356 100709857 674673592 757179574 164091192 380098491 143398835 882715445 455652124 476694195 327801414 675362086 708853707 970403745 708642113 270363428 370513328 985283805 988790112 870712897 747679718 267013751 925001210 218278573 272324521 402374285 33329058 743989629 163329458 123965117 966881059 58397036 530690341 843087908 830343819 36155891 549977926 415895516 122451578 273800602 669345184 179229849 495457830 956177876 830976241 555528251 938719078 356790081 375193583 269975899 571409648 358421960 17637652 218670089 43224211 928023874 867900272 434464236 42059566 555696037 314205752 343031575 254053629 229383176 104206125 678089014 654657288 469268733 590004330 508218754 29482073 534235901 249596401 252327098 82704805 546788540 900261646 697401652 252504741 760386160 717500073 501896691 872881001 109258274 566075802 614346664 256051525 690632746 716369626 554213839 33519455 409483195 564336997 771175189 780900267 370548705 297375041 713135936 446568957 860803643 213842753 779992158 666458960 217960196 557955941 806894158 311754121 433446730 876709633 796227767 821129496 701292892 749479984 847562395 16474306 799498398 821728854 431898272 555311681 787051550 871043331 390145681 173385493 348796597 986488805 113204317 185245630 766790639 814655710 625280998 82023425 889989868 296722365 121309823 715870083 660575502 48311240 718468068 912166584 649216759 607773665 639128857 96828102 107105161 483710833 521560084 620703865 774181717 284238033 476443143 273229843 576269184 392489987 782348 657971990 600608834 929285017 686991407 491206648 150202377 63503043 497506671 750004575 575005178 606014827 595100535 11881943 855797949 729369539 742699628 992537677 534751764 378503198 934691313 729544296 422620285 664364747 184642645 273931330 181134032 707354598 797355624 502731993 953507387 258118419 414041006 87035963 368039587 513333085 267780931 982528907 99743431 564930344 625935340 271902993 126672565 129066294 641874307 314594185 417539572 350043052 438357684 740960638 793012045 706533634 981474575 70212084 340459957 779665956 392932443 109074676 461205396 947282184 286872192 529973192 367444075 463191192 156967843 105035375 29935117 127316117 352606590 92904255 548055244 871517721 523663003 789739930 139680321 634398397 562763536 446734473 79215169 378256066 402151871 146907684 93633168 675778724 343027237 574543394 414855458 382860288 781596733 362666810 631936097 303590582 61961940 162336594 457412532 801894678 312762682 721071393 138627124 261767733 178364754 148971751 335959117 216785006 407252202 558773326 611484874 224194816 168699899 478952998 118558836 508614703 744564575 205140054 383279461 957366956 944913042 486839924 281924713 352922599 425284384 519030257 267375694 439228494 989538086 382862752 444121064 885115192 741525392 764013335 358431502 691354989 306217457 984190042 507861573 531903228 411725777 998958709 886345562 633055921 479736031 722317574 68111873 664410138 82305023 759467014 685574232 599395663 191027219 345197362 583885791 956863423 243547383 434877981 352551357 951231947 967712478 34218633 477262137 8658183 264476163 346706902 698104321 361343394 110793930 888097331 393259873 474341652 413607898 867172227 304518291 925492583 726848575 93081637 617691927 930122470 525174047 427475444 74107549 166486469 322644735 249998665 443148037 310865709 99295690 783160114 558371029 786088861 150982826 497776392 901286405 732880732 200057443 952164035 423446874 262004176 430024066 255569262 52867404 933205818 186600146 330586082 87827561 937988878 22623914 803682447 309520223 777307305 290996113 476132205 406022545 487678396 871113995 172726763 945134118 877444553 173100357 111145317 24152286 497983330 730504288 877112556 67447881 832745651 437172154 549765765 712455682 565230113 435663441 887364898 411769374 686886818 530807952 575045297 527734819 647055925 460506431 696666574 609150101 683866267 231641111 885206731 530029680 810830495 749006507 177637081 11753792 31937362 49992665 394959923 718437791 670763187 600744027 243916987 69058683 35272499 320535378 215468656 509767263 759839336 384454223 916213319 165199358 548175309 866070148 231336154 925685178 268581322 473817097 26111809 198302496 945645362 678569561 140098702 678332313 864677210 850519257 87028883 504619875 784069714 48218118 929485842 971241304 369722174 104200999 666604647 554856397 685598752 586566809 816843727 151786480 909269414 390499519 273412382 271052288 645988885 406725588 207108149 335905918 65862737 662337399 975267406 940188646 132669790 289688822 74366432 979654143 489562854 856770825 260839764 280887704 330566596 690358688 828256438 914409889 986042997 493018222 616747054 590155725 538583952 116446637 570543307 414717090 870866789 982468944 189420393 397613141 927050141 652378668 28823810 660130740 485923293 583584928 50332829 210771200 52494617 178045052 712813128 435276925 355725485 467448753 423570193 302741623 199517564 212185573 431501369 581759518 526957169 739863207 88373453 193480188 122117942 305031384 843145742 635952997 520405953 66594431 248500949 816242723 468846413 749258953 160522356 42367974 21443197 118073561 475422995 917697761 306215976 517972697 346927278 101964205 801029147 242196573 791083695 999769777 714204289 863254734 346417526 211785456 393930051 386234643 307799673 490786281 334076790 685912674 80136010 412538114 788377810 226293149 966271024 267532666 953322848 237493504 766454547 633613888 376437901 712176760 342867448 925368809 605745798 42525857 362485805 107772343 306849588 601999577 646458460 191663236 921015497 160812919 814189376 981976020 498779696 827417795 105940462 756363622 857123089 647575700 579472185 972731600 567615087 930933539 970740217 129839306 857827841 724759164 892533854 91569855 863386441 772696291 222810137 369619188 25897137 954003878 855631513 652304974 679425387 589574886 768629812 461147256 347852375 211580470 443677226 442484755 800807898 611266702 658149564 366001275 610379721 940977964 867540936 196062946 651779333 206173984 572041838 193381796 721217127 741652894 880823323 279401420 289701470 686243628 676979278 24009471 544696590 236826760 664561452 864272934 170235078 620436234 658428137 197581329 739474878 155728699 908541819 699910474 268583310 525119293 236666094 410185032 554652961 922201391 965011743 686244059 297255535 216481466 928468688 269883344 932998462 261207279 97169775 413284392 546646094 267437861 165355744 147766521 867568008 99643923 736748076 60237138 68932984 293333849 906896820 893015091 421461883 401832382 736231124 525760070 407659304 646764972 521166238 236041464 220526797 61347254 291269771 48264208 69431253 952697492 107258518 114212680 145109282 696527816 17811936 138619967 349422966 520769486 753593238 103519546 444401568 95645395 887972637 915001142 726693661 303237516 946001444 633881649 170397652 193026798 221812159 271221025 622787381 949741227 442448101 68484580 59229333 71643471 951412550 319462879 958448901 622448205 265294728 443732344 727977345 640984358 872461581 338640017 585668641 59474882 912958009 413864262 746567550 764856930 355192367 695417151 531682660 805203973 136245071 350286434 507360560 406265257 501312066 891493019 209293725 28592814 221592173 385686900 111089573 990496874 889869358 233166447 351936670 977872946 389662494 147006834 64028937 446378323 96472146 807019185 456643841 782240728 848634500 427479154 683560076 618069680 410826724 714985630 284327185 746421662 285907975 204330538 319075845 861472288 968494586 123255693 799015067 545533931 28562468 329706905 531139638 39199889 330048091 446002496 546544299 632811088 129607556 903539118 259928707 689921049 252709658 490995667 670063530 341147727 838142146 696098174 133718939 667310263 868819083 353294980 555316164 659149054 386445916 15971677 630177584 935280890 718322007 676605455 108152105 149407402 398866549 9490300 400040593 894211012 193123718 94409908 217324088 766298357 425594683 574872057 583261709 314130934 614965151 433031525 772789470 776765574 515975282 503391421 467241119 470620012 782681828 163171615 902510949 560239389 619029196 823784466 834260081 545601547 541507263 715885510 64947557 382419033 458415207 495696976 344036407 832362325 665162147 191718354 211898506 616279056 536030749 891921714 568957528 640302095 143046162 272243571 188751841 553845593 145932434 160309575 981404057 47021368 250050007 261955587 716339161 989573887 734057221 990806172 279108013 714425259 622530317 930575796 816238138 918175161 803704533 621313108 890960848 155292294 810421017 960377533 180650427 808328065 457093386 582637093 146929657 283302407 191845892 593038634 422114258 281170941 362974527 367176512 694437376 837750118 53551404 410928293 229110766 488667979 776131566 23984487 278750731 946048507 451480109 111698942 38664818 37126625 117199817 318050683 457631586 792453380 727435261 548546133 163030403 444932244 403776688 702106593 167798267 270891696 170719555 848620832 824208423 777485905 654998802 175405413 55548015 927659430 59643179 183482442 620824541 752120384 85253927 120745048 967150547 553217982 816829520 833469724 778834278 564961591 11546175 714494243 214977306 782213452 188941156 344681800 708807115 792752728 897604173 447016706 321369029 28184963 568543890 797473710 575672255 582360353 638469728 719269963 407484274 523771 23919575 254182226 310312339 828160667 931773161 266086641 636873893 520141615 247424421 225603808 365851023 671206853 820037764 746206712 626948755 109965487 93821989 784619937 766348035 322816756 854722640 888048045 181153512 381558546 162353194 454344692 272713148 11550441 184929481 853201472 516161427 367654110 672460760 263463621 473557451 134206524 68936303 292344163 814933244 61544164 69253891 863034023 263967376 805652018 954498035 216206853 344152073 368699174 96091569 785355962 246055597 322841141 716211037 762276710 381804768 259612763 318158076 629774818 245241156 255068996 147079252 272056530 394935315 695596336 874533448 477112395 256252694 576938643 642325000 575515691 162083750 973407318 588388852 681265285 603730094 246053275 464934280 288114482 615487272 998813561 864768726 850758533 456070704 45124254 190381241 157132374 891005618 979133303 302330985 280868891 487802581 456841818 688920207 153764222 924482582 870718055 380950417 200967764 563778291 367109654 686039503 933996507 120537473 937763762 901470079 835601880 6879201 784721791 376772297 332739651 212801643 719545249 716535603 150305921 750462952 767410555 145925096 239421037 42110418 649101260 594864905 982052769 933766208 660208320 833199494 363560639 982469258 594625366 446350631 900741124 336588563 14014459 769881026 521197891 743267915 197024537 829451567 776283158 467814337 709809613 423705160 798196691 547494468 404881858 291144357 20424667 667099138 203155700 219574910 434340267 869653068 362660786 580757706 962351959 453912259 532629379 871686430 95663162 45132797 220788049 945714860 351085352 218083915 349653938 330744304 518202431 577526301 388881690 687959384 30571641 420476528 449251498 225626918 750698233 911940571 197565551 884185298 634102368 182904007 955697488 375588432 82362240 8051612 169528451 926602196 773230237 280940340 291124631 305259808 841709727 360267489 172934506 525884256 588354832 130007414 774301165 298625222 199776412 146831927 810694001 465906037 631992194 769250733 815620745 675093139 141105267 769384515 526699369 447950043 500959210 266203592 51758009 33765700 618205446 566272926 29210880 710014026 941739582 870498954 403113025 560843768 723658618 377106174 648895652 39185003 614747128 700171815 199474293 536036376 872789729 121418355 34218040 464486994 405698902 510780106 115904253 286596334 535584686 167923752 57911343 459001695 574483489 980913060 525678208 518958130 69731842 502074597 241611477 68947704 704481522 633165739 281474286 956628975 197066227 727547376 335976543 724420167 382033515 767148330 551479682 574992663 514962780 558059914 289518627 842018562 244418441 557076923 669699741 116371211 908938074 614838447 740453530 778597191 559916847 102484913 654790345 612567274 43107088 229059385 111105191 539741641 880635214 565870476 805880631 137016986 852732423 860049774 715768326 893280361 767177094 802354497 107116187 188420052 316762113 74598579 71809961 62231114 974563119 191036337 146196291 160965822 602059761 254324696 991395020 481629479 681832595 307167876 629715212 415442726 749106377 140941125 629677758 945194320 749287271 732678345 324730787 203451737 183383868 702018978 306062172 421739968 821653529 426204263 715061522 238946497 774051727 238897836 262173531 507812827 227427270 340698236 726851489 153021149 85820733 461236147 645446236 424951045 933684395 952351440 63676291 130511314 274635249 779043088 925728956 560797325 119310869 205667139 700596060 532845042 84188582 634615614 627862091 546986686 428058405 581630961 474570290 624557583 533653524 289700693 145624994 831423025 221806552 67585484 26023716 646384692 769126999 782998092 621787619 966134047 492308001 757732731 217194999 918560569 385116353 67606850 707577483 767728892 718434157 951196884 884926147 832628830 495468623 342528422 883570631 294741540 787037989 91987561 957632724 359951726 919920999 297076029 241344560 54547509 42427620 484711856 352734038 634627764 671412821 150711169 22765981 803960106 117541694 210607848 836345607 814175751 11814446 175183929 702903040 926114401 446602487 864058851 217016688 894132706 621107957 521607118 137098565 863862576 222139064 22958443 645082750 774824017 519378071 441817822 234299157 521593805 849505733 651793609 976640528 643457701 567192861 111256250 852300380 821578086 631314783 436281232 681485459 339245678 65175271 885386100 959125475 434336328 471274871 707387170 772322782 725850076 782601650 456850688 413117866 865785029 675320337 867996547 680796437 364494342 969551272 995540784 956592122 323119147 357804849 474786200 308381107 744123495 605206892 5113856 758924081 253961227 70057020 698928962 57158233 638428927 924120807 300638172 965100650 219072575 302074075 354596692 177259324 811159931 950133651 20084153 378855322 449726425 619320426 195226794 139327416 922797259 545152862 372279818 22453208 193042306 43866413 879117299 550229098 922593919 661864126 918501525 535658772 819420251 818217104 23425060 265142609 906576224 595335540 285090160 65772110 124819978 885038465 277101500 235356322 660373597 836805788 787362942 299822290 30581283 3713875 347591935 656720928 904282996 348611457 651983357 930350813 575153861 496793910 413936205 663660446 428281064 506646735 668010909 996976930 270198954 602296468 66800706 177871742 995276152 615002870 925905816 701353534 19008346 402525911 376902286 59836934 427934666 14081342 449264604 93515040 148190920 780100052 752136419 476718525 394906250 768934537 348874821 86276025 424434790 104830049 819200985 759063752 822673414 63433071 179988292 404745566 198489719 468152665 711243950 352842211 179823284 407229127 299303929 825220773 252602437 205147300 496877555 995809964 54789917 590707222 173954575 608459990 116562009 206841420 381018359 888727711 810825507 245705527 361012122 489351269 534999970 28130742 348342497 585105939 175212666 452701402 770953935 522072804 274375208 735009033 903987091 376147584 962845884 796229860 425027986 438895606 146389789 697491525 636601309 19799578 957767044 655579523 523965420 52414337 618066657 516816218 978747127 420166275 53107610 943306966 440216010 87919742 635854094 641976283 229272659 979205303 986707868 18693678 648381623 179168190 825607258 336238523 214087299 152912391 186592659 12278903 788522708 79589559 238559187 711034038 850055391 206958581 899836193 285628791 342486148 113853694 366778740 644502505 935124153 494591184 529794737 285151764 566187598 995389683 37771243 106782425 22558359 935372504 983986318 655807970 858886148 81715984 482481398 876233171 968696970 963030152 932015627 448203315 424732482 964961873 25661293 641243984 812240821 339572015 464612536 517536319 402813791 769827939 208028867 102249364 503245691 168110661 460393371 334751968 496240646 879537790 804647413 121657305 140402791 334188325 783873660 793983989 503701410 260169485 503099300 554837424 321368077 371259250 710734840 638343342 34717705 73370040 836210066 963307323 673795121 861813140 706005481 577395444 382769177 605586970 935387477 826954144 181197746 25048267 697463982 138486725 304686254 878207903 999757705 816713036 628113146 386460074 179456879 44384969 391594541 652615817 260537644 651386328 410740258 534348576 716757866 353765584 653300886 893011728 188325753 222776144 646513092 655357479 183284569 400227275 72737152 895840022 191269606 176922584 58664084 200360088 616498612 72786199 86389518 679093972 964801448 156184721 100989157 628869804 144667732 753300694 113448360 301932310 981499864 322253645 99922334 191581465 865351498 238575196 109087593 160775345 189764120 973128905 530297205 152485887 587570610 209348840 941951063 458299789 881899404 949798340 397482983 679052191 40669131 992616239 614820318 339713149 315270243 935238047 969008868 789678646 736507391 127376217 256038791 174441575 893357451 624418207 826708538 667853269 186705904 915643148 363782533 400438588 353134205 975740238 514997575 654340443 834787268 782307062 68867298 479710942 779198638 9990305 951928975 813346720 237424349 904178960 433377390 647334399 965191343 386395250 940192375 791467217 295296337 792089035 655398846 597309240 965382218 301326734 141020508 560773135 478041430 738652024 525414992 843231707 108612202 558294220 995623027 757783662 647227956 935149625 956725885 706479906 877019666 77664632 664557399 537492536 105668478 5397406 98463276 668122413 343821280 466061103 27102353 387977137 355645281 390634402 823281611 789940246 616816036 460676129 535054544 339229943 272161499 939231029 848226133 226951160 208125553 520016788 605899410 606269761 151014228 297442607 101284015 854153644 686577744 42320338 641291855 58433305 387692974 582916443 85632539 6408587 286834812 499233403 681890734 199839596 504133787 996477183 455754810 715785168 605264875 945242532 244477347 385999961 610625595 882749874 515629635 304666580 39363823 761289497 313758800 815193288 898165393 389615276 79409080 64003935 848968976 396036898 503796815 126679536 975561322 308390969 169684064 759935159 333512266 843900205 985520608 739809159 499575703 870563801 726416365 296498974 681492603 783617497 432770696 228591843 764112333 948771874 756015101 655126818 813177989 36193958 375952605 898287392 790135719 325672037 460172740 326613775 279275602 110714454 385654534 389743563 134088809 530094855 423630923 402841731 611448717 706999005 254071768 473118200 302548122 340171598 394792561 65439783 230731053 147332819 904306929 27916810 173926011 887999408 509415171 583912091 167553253 305210443 681878918 786777398 955541380 95943278 287100496 167491785 251052274 356500339 175788735 436867258 905060648 331640914 974081608 912388685 47380326 314806368 493480587 814516828 994272158 688996783 245644333 947190720 472949795 727577332 229860898 526291356 572034974 455515751 423901310 245543277 162632601 642919813 351497321 609081602 292138386 64203482 126063671 240890747 991934287 742648675 312343997 125940759 239808810 782913616 162021241 773498029 576110527 212384252 975630678 494117155 564526888 602550231 517975593 658448526 575283697 850284429 649201144 641941369 365728856 999838106 561924041 191153250 190496768 922746435 415280851 409030532 472028122 431825524 596158079 369070454 927985309 721189612 647863796 895159505 516064882 979471835 928850277 175330740 653633905 890230990 495612965 483422850 315262188 444872469 903985309 379038977 816847247 610119787 400864828 92204469 728662337 876262590 117664568 316664745 461846596 775054407 212323038 111989746 726256315 572128227 734857597 954066424 738284811 509887766 159217155 4143461 781660159 885885875 505718423 799351548 474634320 940796754 176164585 545467927 773427347 81974628 914295591 319223499 108829536 637912624 54609627 824246286 740076069 298825999 739113711 239224870 191869693 118199266 751329173 820888979 707221953 652573871 774558240 187429599 48711 388989842 580487283 788646179 612025457 337111465 193163963 818555856 860972006 597899709 106512219 504228979 428652368 246571573 895080206 895413462 796136193 437185827 782698032 781139759 21123592 703596227 741620688 535280906 337793788 271086956 758014325 104340314 806110913 710359009 443670700 534542566 899690829 816126510 882020357 661483461 789922274 934012377 911953761 898077512 207861273 212217440 81541457 314001710 360849628 526157531 815505040 640625962 968814100 353088940 319700945 30295097 288699757 913618432 849155096 999246511 95794495 519481675 595138358 585496544 440691004 682084100 687013879 197980212 634490647 570687929 33106134 302017058 744444219 962904671 655940939 343261463 581793294 34679740 334437506 442749187 50627004 552499451 211826637 822696688 857169875 251162615 147672 754370519 233210689 807786119 562205748 500782019 685964772 22651162 901800016 268170313 821425834 390376865 936114222 449463225 372070950 571993030 438328953 909010235 535374485 660078636 896702559 62549348 512472931 216619486 253803924 587398907 562684151 407100581 456876736 306687333 666785843 876368522 90013914 160794776 503898339 93002081 446414168 772673130 485500276 186123569 392082204 237388000 220148261 632948510 922377331 820611893 760029532 67612837 464707742 846932346 69505596 397544113 646918148 420124931 456275825 961258602 116220206 818492618 829555913 279279186 713499308 597830156 305052392 815871908 977506549 91173543 307736798 775120602 770980327 332159913 865212785 11540707 813065961 294914467 155854409 693312881 9117505 37195207 441593184 358622284 318923809 619756034 438094693 37532743 467892810 437194406 940728171 528985828 135247340 629536069 668397742 22967098 346300458 496645024 248380332 933938577 30094123 481907905 545241017 759895647 764661455 720389528 795183295 274733932 332297002 450544851 747345968 909528169 411528938 209384824 254778190 64678349 605009679 615087087 812737903 31385362 984895713 829889870 49620085 543771828 743610232 823349634 283397305 959217289 97585519 148428110 919997743 147426128 573627854 550549858 280986058 595757610 656584285 123994183 693824047 517174075 975577463 603235384 881041276 888543956 641451246 94157035 288005629 560383318 920765965 446552443 818784931 396653987 838426977 231490475 225583727 536511039 736174668 4143822 11659180 761661658 72559163 272420473 640387714 247187129 774825399 703772128 629752922 856895302 680627370 322387728 681913447 673479934 401066488 741558911 11992872 9038349 45030605 657130469 834003943 904476765 981576808 803502845 469958385 383243834 904206414 69323389 106321455 50241824 817712280 203164442 115473632 267607222 859705906 824996475 9382327 327261191 31699578 496776177 597007958 787229429 896479380 585324027 325670609 828578843 91149954 167131306 51965652 485318180 362882912 743047252 797269846 288391365 32904737 86389268 950055984 59925153 507387524 480118670 800225490 122975608 940542332 285789828 584972284 733206912 154204222 712662458 586316818 744316253 906215904 240664002 437533625 892451867 982034011 257723416 432050204 514353501 701647852 717543164 735000571 50583337 795266691 524870274 957790529 207744296 752082864 301816434 694782644 63038289 808882358 919137019 304483120 332534777 55870005 55133049 427217541 717578016 441691372 198497953 48074031 603397291 498983683 22328688 48127839 543739090 825098732 961884382 210225957 256940756 80096516 76091443 983521099 363669781 37478801 74596984 910920779 66166202 651371460 816849966 99494662 726125957 718242076 897138377 125323891 480923116 999962372 872861947 864350335 605523586 901640326 668633124 389527946 117058095 278760853 329882595 22134558 337641495 309608371 84690252 278178800 559354790 613280798 738752937 931002463 995029167 526725219 573478355 960161627 146081761 203305814 682649607 566417145 77634116 929140692 233068793 520218193 575306735 81149785 327735097 25969285 86656163 365789426 149669359 581186882 519146675 22097071 759619445 949162807 123701266 881347934 998591542 913867977 158595929 409930151 649039707 678649399 291600493 342729567 688687288 697533036 821246851 836681663 25751118 681681030 509320114 224358859 655466546 892057065 359069742 861704303 616693649 467573037 104209568 59817964 596624402 962486365 101942653 662334583 27887695 671620315 270067088 457501222 256281114 702644396 938932774 174725626 990295606 24069520 786694084 400236413 816991988 84212685 394747455 696272374 762498283 284994252 656860980 837315192 694616062 297967970 530591161 419361041 196673550 892044414 160300246 516009451 32305628 317899685 322947582 588203643 502825155 646330223 662017390 624779632 153687149 796303939 977633206 121434937 763563671 476497289 804736209 362580339 577481402 615876343 439318864 369879847 268988120 828266726 752008950 174930463 163185157 674522369 572935182 813263367 802331969 92680226 468720108 770019734 74632070 82334671 599707573 708636598 668418270 518229067 57186036 466840785 228859967 414460590 386035537 975301431 352104787 659692806 315979747 462112928 143836007 435482393 375778517 169823020 475224993 957795078 507175082 410445315 268993332 96279810 61844284 144189796 40335290 844300144 929461657 455429728 479041441 455629010 630911465 628940013 671883156 247976159 554991343 714696059 484446651 570164583 563549495 991460868 541318747 136426610 361842976 713390619 87425349 699215679 579482147 496170606 491408713 713340076 420720453 843641293 70266173 868733137 685149482 769561262 324282172 700027533 539207458 817016279 968819392 909577968 308542460 489146533 90616481 973984720 924178122 66638386 248858630 157153327 506222889 580600472 801821857 962365884 444874073 672672653 926912948 738482625 913179870 181739660 87027022 497234827 190728753 875772397 154509794 816199972 840413618 634049201 111112630 685742942 367503387 455438753 408936912 93572149 801962552 144796316 400883782 905740600 386428180 526470355 916614333 233331067 4545508 244745908 716225035 261592365 464945930 978174572 940268739 182503022 378417759 584188184 179013348 482104962 197209506 509242275 669242285 641261599 799915948 901411455 836082259 832999817 894304647 307286981 208449271 586884093 903241554 484166441 860112470 697422333 671644560 123311299 818469335 790116135 912136602 472322826 381835704 123101463 927896368 250235541 639087914 702605403 590535046 485296323 434191717 872726443 925973164 249687252 476744062 526430429 672035766 120419495 112623645 536449073 789020972 334895581 672097220 705722039 83745507 275464330 902048906 724585307 337468611 894027486 984758189 568645703 781024147 674174061 22481148 336072125 51710513 529672575 683250736 243683229 907576121 531900433 442346666 646476138 173821778 235239451 22541307 328025652 340159645 605065327 892566289 414138829 520484688 13858848 458683814 199136232 946635458 932130302 832259542 15074244 627540600 308742043 752377543 544749318 503347720 662408673 102084615 433428696 206586387 819624773 660331068 72971765 423842769 989592797 750859273 496935359 375966323 578726668 103977220 865415048 880955468 1583628 996541798 144108216 494564550 163151635 355915147 761212854 739316588 773157148 674571101 211878336 510366012 698722049 593283662 353017271 803845239 701916204 881531887 161529354 640007738 93863296 532729549 781985584 699003676 412006081 562312663 769339404 742973078 238758117 587241556 11935128 853431264 160289066 743809782 613194725 481145088 242457788 554605110 464210592 322845370 180979960 120929028 835111622 310031289 720835426 725132562 278317477 707684185 684386282 599174286 564983780 965060258 997165533 856629948 209606567 493658955 397790665 959738729 828341839 561681863 418137411 8588757 224298126 509617530 269681630 169707586 550553663 300233831 772002720 721737780 104230584 944822923 393744193 474245917 162088114 777470956 272972307 149616708 529137803 746227462 646793035 609109298 978146243 839257535 728363787 269494170 508771584 411536891 222385297 58945420 768616246 943855321 311775268 27152255 596174989 71196521 911625132 179564530 996687034 950281983 27163693 304832249 940887264 122189378 224258365 226864677 778854679 953157357 872151253 63543482 419259942 148918527 514461213 376277274 240001817 661415231 704833061 657207580 283661652 592684273 345028180 366803229 401741680 40538060 899763290 114624328 408821168 145754696 557028158 626961648 762454858 135803035 515917180 62089537 661065828 828363322 976545374 452703864 374262316 955332347 524865202 864633238 627229667 33935203 111335690 259322967 325989524 423012237 301271876 947486127 893763080 552667390 65450986 8999862 89056352 721536577 209955332 344784494 196213780 778572078 967807165 168591488 47323580 657888550 301017421 36861153 974183784 372884162 261925534 709211224 453137776 752111543 77217426 178149773 246540462 269514112 566360932 793006768 712815640 129891529 722985204 21639570 312434331 919564939 7310149 262779341 918942588 937837563 963220601 360557743 784813677 59769841 588972207 614306856 93848857 223286368 878245290 182159636 874039767 716432161 439686734 248729301 599550305 579436287 192086129 757272543 277280264 30998979 714204775 65973281 471742499 38549836 748244474 234460343 389391243 805539495 646424172 102148985 971905116 312811487 204318301 53537379 236753708 229279387 16991237 618631921 633476877 311929279 363682863 307974049 591378195 201622561 977970338 496021001 760108008 358502976 189334716 919906308 407854945 392149299 480855920 652659940 602336580 24971455 133698100 206735918 764481335 389656362 834179348 100735729 178296875 668525375 311545407 571375484 749257640 875139171 479309480 665980400 207734385 628306667 623869035 194111126 155320495 185113383 866681171 884608221 781605486 214067880 54589271 384173671 991653916 881259640 569707908 915174761 440576553 227268969 251723338 127401366 104753196 392222008 841782984 979336886 391285822 556549278 526213545 207840508 579351274 818467741 426342280 303557803 436942575 726247248 326841038 510469317 427396860 39331080 765836829 46611431 28395388 511910705 694747615 244919647 975538823 258516246 667897744 163518309 326794120 228469529 513760731 84153091 807342887 537524695 992159850 660575145 333462371 691269188 68869218 336961937 172161504 731945455 850733028 827964912 950284707 91764270 231699520 96391908 934945026 912284102 911727188 837309608 484544298 823745393 268361104 632042740 39875602 812884444 947027608 554273790 308066005 650819034 464391676 173036547 135158476 765998042 678602253 694414329 565685597 446000666 119100706 493896018 521283950 849096620 178192823 209024903 202647062 381911561 514198024 874602233 500212203 226691622 214074637 791571285 184676205 117311477 21692200 47536376 481145069 233479296 957376623 111922348 964941126 324758575 327931022 902471716 345295656 936263078 414674024 594290445 781359828 42481746 731761792 471781756 86545786 886281542 67045697 357649680 280956901 647825480 301658052 548964826 384076325 972262432 395477150 958042266 385763607 164879333 86319726 734287185 590820270 284000101 73129905 806192085 413214872 806355417 36751186 783454956 474817444 918395379 279098444 211920663 18720166 684945360 715448920 581189847 356442887 86059668 487896820 754752708 208783421 506945175 153356327 686371790 92536267 684332262 941925181 773281635 929444978 463378797 245158877 966647337 232947189 886184354 207116627 10557153 219844339 751667775 803973596 208556192 684771789 925657995 762280866 374706166 367495563 497513793 784705431 492381314 651263245 644781970 415727516 914320374 187675157 303836819 859284746 959136443 264721530 37112458 850749767 120884093 37962140 830200727 366847780 878702042 409424947 870794447 212374082 681597957 832118355 302462645 834733497 483614367 579956243 970690768 71066917 294836058 355071369 365272024 602190180 93214700 660252474 48659822 194957096 596858458 920701658 413938760 406023999 88332860 467809740 977888371 383012881 405963614 213726560 482202916 72754908 257981015 410723607 93091587 638238097 794531179 869778229 701683969 85888986 739709237 52335471 466022664 436392192 886489109 335750985 748680417 519851374 62971317 892557984 231631225 237830333 867315549 256889915 243392950 94707338 272892805 914037905 708440679 521651180 545142157 88942490 351920207 290899694 347904163 678516130 74745305 729571602 270124520 157602458 588183556 238402245 276108578 872993700 471557846 142738338 849927214 907014864 181577576 618844420 440975562 956620658 425175010 375671838 952737306 731829538 674727870 464729209 542684083 333981131 979238281 288491445 471876905 47011781 773332052 586694696 751314743 502070964 193801860 911461285 829471929 723634881 726787199 692234568 402225140 990932330 837452185 130344975 779889514 349956469 477185765 253836389 475381020 283869487 341837187 753780507 611209731 769593727 981063341 47278574 228938402 42826677 754470851 148551516 733307465 996245650 315316661 220312011 741205895 190443238 478043093 809949308 861141786 536071012 152048513 713338698 512500969 776217587 297260734 805593975 105215947 968542026 982118198 481902707 879178346 148310079 109458113 543697103 8415499 754930186 889070630 938740777 956445699 672345832 198748306 987846198 751757784 566862676 326087996 403519798 502538946 319445775 264745933 413344479 390668590 901010996 666708107 512011813 260594468 370958403 881312569 556557215 775536586 881969924 617077456 892077153 509832290 853994340 839509399 294656571 901929361 480209975 452264118 580912381 578856758 81993784 709718810 774686736 17615164 444204897 374283207 700593576 160772959 908598794 268810113 256728841 448973367 448296712 267062063 712869821 427252323 83397408 619319393 987283736 188763808 465497516 968195819 890714223 471591794 882271870 972533324 695702183 163174546 870118972 726704805 210491921 144292806 285001510 256136750 688210865 231431802 271341657 671533545 232555431 441875648 632712436 889790097 619992125 96319780 671782427 169369164 386733217 269950829 485067657 187983317 515957852 539351730 605932643 311842278 31729571 468566362 362098681 95349764 129760351 875641337 75337952 420544374 191828024 356739005 28748133 363781365 205740362 205768727 706851730 468635009 466448050 59816878 968471773 414765785 464367776 437920794 643632357 715961544 351547746 963402646 847502483 389109820 475117124 480000720 336229524 247189281 382210664 809405750 813657820 467758405 686174206 574437976 469139212 991978673 401437925 71198256 89632004 152810521 150181097 721753883 936197972 142443303 380842611 898171804 8342193 248354815 948534282 260787886 668625158 878626823 701542381 926634488 998015679 433449725 206436673 823645067 334901791 829115408 985900607 697077982 93460215 551759446 524794807 745000852 535402249 608544947 330426034 142877279 341739029 217476120 789639759 284944923 409059500 391367244 510931018 186476931 63765799 446097701 432297861 199463357 310560443 387718736 387421605 98424986 392025618 8455494 392196950 960752583 379120329 148404793 570299920 634187066 869553106 74858870 183387888 818459325 750232110 333611420 161338561 213557438 664125231 351872480 32464747 829981088 764432102 169338689 568119247 479824416 269731336 660250862 137421482 700346892 239595566 21931049 963391132 515882007 15288592 241957721 762561297 967318135 560777612 141943184 221943975 589201536 425262139 488123341 743055907 564606078 148266698 924876728 79312629 971143127 931448997 426477744 816806696 829459184 329888615 251650033 729358345 72548258 979991978 695107217 337278334 475202457 758365571 188900334 203576694 44569477 327718534 680389994 489334999 914456118 254290245 613574294 27564187 579436581 656208198 217656209 886305050 195759677 446681467 4104294 535483481 958270775 325986819 96522918 28816155 846323799 150048015 217825390 400804049 991203541 73223599 477627046 218868735 939386551 352590519 641270273 752860732 900286673 605850406 524753638 73607463 850423428 895671220 435290339 251421246 789958284 579613533 621471189 520009621 673437204 12288220 137670118 949018380 801057389 96561905 367289663 585827425 619135116 156120390 270645610 889377716 746938064 312946903 361080510 889947177 894565902 319013814 960188727 218057179 625226118 32987541 950055950 558688597 851719301 22567178 419882365 694750685 268304445 495536590 943637602 314021417 62239583 95677290 782086829 872244989 399972618 557858971 204399206 483315850 254822238 744282205 902002160 368381980 529136969 880098596 828268664 113144694 137066805 668501168 663198902 442478064 589584401 852772955 287046194 438170912 633738695 934621445 788404991 936505750 314044426 164749853 980352869 545638565 731490129 172302201 194651722 745158286 484715335 584737064 142570470 650700956 382820443 729171476 204919320 122545404 552420362 392506346 162136076 112610539 825981623 746855045 962636058 622573883 623080761 362763896 321463982 689689524 661366188 964181173 851464930 408431477 887874714 157113820 330892639 821513731 594635916 993382932 157652085 1071963 512856192 670395982 539608288 437887569 91947559 542754433 652842029 111017150 10551263 321409366 657236692 972953861 778640759 174995891 583178211 850599597 149590039 371322662 462199016 50364117 725747775 272994811 575856066 515018528 559634938 686461306 676843777 695992944 352125234 241570529 787753825 740913121 396273772 305386415 835520570 659266763 384507309 634347964 458716068 560728403 636253614 78741112 53379760 893596004 111117955 41548750 3658503 220639381 60701478 243999437 975460085 458624778 895057303 701245620 627134014 754293308 809988243 944060634 997960541 258025989 770777955 438685742 11318733 366208049 859965908 128935495 326527429 262431705 70043894 33239495 479668987 894480979 573174209 351539359 374780145 301694543 57592992 681960287 397408410 721486502 471510116 806523829 364270713 6868165 422308024 647706414 384848648 64578515 642798179 268149174 599043783 439303664 667324382 58844156 219352666 335744675 435003951 412370719 999446693 117747150 899086142 211562128 15667929 767390291 265778170 697480267 265452833 109165711 531059831 167405597 814693271 551383837 2780263 999426987 338869628 533095113 819441898 475270841 468677265 673258887 103900270 913941579 335392723 310197584 283274525 838937876 204198388 230041679 184207883 112452218 242961810 482246765 729809320 368912195 532053691 251432466 88391331 686532274 559237693 445183391 408342465 935979028 134409707 745423512 170660621 446848274 376153963 685623644 215409890 373609461 632085614 740491505 617824697 787483267 299299102 138972716 990549701 139538800 34076199 630735908 276327903 603038709 632440002 757522438 870556639 250758403 567193246 39340139 545299495 123065619 382379340 174657123 34386329 703528010 760750020 136995500 946825265 406960801 476834365 49121525 777559262 887604965 207168496 209478588 323322873 240284470 426703311 975430243 343715391 168179604 105395669 885902125 625212321 932508691 286344120 452690753 967572209 108772696 715529140 896977239 297606345 600660022 801769566 69948994 193128388 117650625 809032053 959787091 610404062 297988563 781027415 831924523 899856593 528291473 521219433 229595489 376811989 859112318 800432151 733302906 701035681 296661721 819743048 700680114 840971458 124221816 891386601 797928304 458892456 259001293 632695018 207069897 518607410 877055567 746557253 911334831 656725937 80557960 133254052 828209109 743435843 523409666 570797976 258262252 203308304 114491670 66150396 325837843 573695707 675303390 22262554 476918078 345746796 578378493 914148348 913284908 110021539 618095609 260015265 234029289 302441758 739829220 83640939 872406009 351839100 39445376 579738984 281360023 49930980 279402166 470675670 122767140 150240474 685864828 667255436 926934969 435496214 751560739 930843623 915426872 392581829 389634057 404615334 877423522 362489604 537604223 381997418 67098823 825639481 215444308 720966127 32705182 144692443 288391030 669856624 735845758 137729937 749508465 790850571 729077376 622056365 833032614 880638300 721711668 976817311 120029948 601936421 401401040 327220442 762063606 165169082 923477803 953135627 692884517 348731284 877154034 675695221 180961853 339899561 697986034 559025590 834345939 476368708 42125324 320186243 626938452 212231124 462524400 951370064 300953125 194925175 111734437 61902373 873785076 604809299 747000135 904373747 55097965 825077233 106873219 578566715 604356881 564483509 517967446 843854686 155274803 538824759 451618809 953313273 87076025 47329718 469238836 260398798 511331153 881693476 322673170 18223773 326851379 153915683 389284999 508453058 25046501 587626571 968233165 117609917 854606682 964161746 835688527 636322412 218307455 186913161 948729008 506010564 115306087 454708575 279829549 893537602 819163006 311787040 25653286 678282521 273017870 297676793 936149626 526820566 143262355 913273299 208209316 395683360 140500487 320764090 204445646 82072129 50668236 364907397 519309756 78307222 41930523 73711451 296879573 296731 944328012 881744049 843937947 310754413 187411879 554287187 472983751 802410852 245515193 834593948 402538585 817399039 211582488 982137569 592823852 702950227 264219735 163176695 137345163 634437363 586341570 404957206 374906980 144768691 137413450 298380235 868466612 87383658 930878964 478174811 684055989 190964442 665990431 189556039 877346295 550099921 755970741 737706947 38125375 813812680 146677694 235426431 641619134 150470949 364316405 943972298 652089775 910289272 749854369 999474233 938444465 780722641 825876699 693743540 158023123 42656767 456456641 19182327 536849271 353455656 89487533 724761680 88887769 22628024 235366402 65914457 595724915 296229953 30248923 837979302 305382416 802862515 887332503 401845809 553714838 635462818 226615836 183690109 960889204 404182382 963210637 935848654 449565130 201899949 374671616 268631794 926902052 646608884 299194695 477882760 673139381 636412739 264796649 504267811 890952919 736552761 90491947 998119322 418832925 905628626 990960619 797246020 269292436 873128655 902949816 288846773 788720327 633740140 283182384 658393921 248427564 27893495 917669454 12233083 58024690 398673963 429519058 214968722 478008790 431553386 277824550 881818227 562502190 948101786 866874140 300868830 494029035 72278554 908222920 135313489 703678544 628809821 740357500 113387567 207388673 473503152 998958855 207376448 20701202 591150492 410619337 781833703 684621438 736898580 530066488 564836376 122396225 888832279 966086853 195299284 611362908 94718910 300383988 224098552 946933976 208012364 100630566 597241745 283423921 177928583 666521483 251685052 929776134 596369280 935929192 28737125 408390052 490304491 301840368 815354904 144470632 682954594 611339408 171077865 63710860 666274367 508434340 180822637 997888192 492210276 886992711 283907079 218564967 11280248 53774166 144136610 760382571 459438729 530767131 327551673 49327247 715870890 920261960 936818299 632867731 377877029 535773668 614882592 371660144 515461490 540597551 777560397 482416952 815313709 48223296 552624182 115249544 233609209 291073976 25236584 20995461 174560977 889889428 771440704 633743512 794829086 303932307 770643532 990865047 510822595 850836892 793041893 827208278 265945614 606327421 906060604 348583089 123838294 531988062 77671240 450937169 220831425 925153454 464583513 676204524 277076522 742426410 742896786 459698030 678430731 449091534 747558346 816703328 451798522 914894853 41621482 237130661 827937789 399634107 443986578 369437653 290413345 393990647 705376109 932808663 880377867 290307637 92985573 6670144 497729794 981564336 65131427 187668862 548015141 87763246 375443173 15435448 205617768 160839253 115875730 991072508 79963630 435544210 337732866 629170598 252209552 905695088 464466222 328475443 302203640 849116398 453885033 157876723 582283125 817396996 356431110 382659312 510049198 609778492 956054242 949078526 225988601 593826167 35694107 917014687 691750309 803910173 185855239 293482529 905717273 133479984 764951092 248039174 455470080 532291630 766499800 747111560 977122747 628287953 401563394 881709065 473048993 289488510 981703327 360127455 231947163 723223002 10260903 255497672 343701321 15474903 143341520 652617283 326121438 457286260 576203971 682020533 691541387 451213354 797484568 542397403 976944362 103428900 636526625 387273886 201366153 796242124 671480782 847988105 490898476 650729009 813083189 572495103 55796284 85858500 294266227 475061286 855063660 398995216 261915457 949716230 768418465 297977354 863217940 752044988 895103207 364278698 364233199 82899438 306859970 432846435 273666110 654259524 887191555 163270728 876918361 824601381 498491492 246998203 282432347 529973079 421163561 547167520 798764817 58942106 134710816 297418963 48625386 14231748 814584968 533473243 60219963 97404952 25911688 645015541 987472407 731455313 487189709 750469981 99735018 942238616 896428828 756095288 982786102 215985297 304859199 319909321 27274287 314138470 954340709 59347752 376739081 813229441 621336676 643064636 595910785 565925613 808327378 171500639 937945352 716100037 227887382 716847767 915871569 164689353 45092821 348966887 604575945 704678036 353510841 655048483 160007533 70208139 6355383 37883740 275581961 483737724 285858744 825934686 848211437 235862831 159380481 98907517 145017514 446011209 161203181 196311218 385917967 240023445 427772596 462444637 59627363 451632419 636733917 870991595 507360497 567368306 897825363 323812424 509704022 229600065 839279144 652427048 372638074 512618865 866612009 738729643 799990 11769400 176894549 176591005 241300170 108580498 136027616 106207314 430393954 659508887 235197683 825718431 782202351 106267532 342534487 283831574 187576924 421883389 601260734 209633004 245523840 2262619 346617702 984976945 120972227 114007837 156513505 289816075 248543724 548806887 16109187 625720887 686465911 383013338 979162128 620270331 104102855 58990294 569971815 793239679 927907974 782116752 298389057 453229731 981263820 750067277 888330628 293709650 227721814 152167441 565305451 587383152 454081647 34528326 225952450 718757881 276873571 362757430 218350665 993142779 550564803 65285578 368392111 377107628 563607605 108528723 52533934 942120700 236272822 997110499 12955723 923128949 350762180 880076504 379082760 173238660 695889732 659158064 394107737 10461857 957747349 598750392 768273794 556389931 646472935 392499132 98588353 602357846 160276994 492630822 193419354 297173638 915937601 556537917 114871534 526703240 428275998 313632498 924830864 923333958 503068262 365035190 812611164 231789825 528292578 258710031 246021093 651524637 273367749 473041164 840813207 690601636 601936051 201524742 120528511 523625985 124571962 755927676 82435725 502173875 92287315 67234925 650246973 979875093 278233730 70132638 603245673 855469813 87561253 732650507 261261762 785692356 738182830 778454549 950077411 226484026 325481182 871166091 389652503 907067748 926432163 111820707 747078327 705954669 92903613 691452616 312679903 52874677 761062929 347707728 265722151 412498677 412275393 635592977 751507543 964176497 294311744 88253474 999333115 337910400 150231812 990531969 382451717 862674152 931784571 856789227 953861432 929534407 187605402 435905438 217583379 749312018 746881531 38324346 329259598 792854515 111590797 696644382 790206986 365192202 884518354 254535091 893347965 280135748 490400282 996884651 984949735 378295349 78115787 236543310 974576954 76121927 290374450 987242382 779869475 371866743 975895617 825832677 844164029 154949633 847585506 157822702 216451124 689984089 358586378 814598128 922842657 70389327 346369711 313351432 818849787 44076028 510036967 761531627 833086629 672024493 281790703 115449217 914530509 527087458 761736765 157833046 901078076 549084149 676358996 378411143 909330045 412504309 939850324 658120338 383186750 850659759 20616332 425062464 715386853 223357120 577050482 515837572 816489882 754106594 10629423 508322748 651124141 553820119 346686528 890851526 204707368 920971293 539010320 969787509 400166514 366979727 632769521 666806084 677811679 16400958 306971058 694337160 707629794 573531996 391178577 469745591 679732666 462192630 787495615 293255760 540788606 653663422 295046211 248728339 366582346 721779212 563163690 766195656 995770200 150405134 93921062 509115555 222653930 849044337 83776210 586144534 217514075 194801590 179335901 561536955 321244206 836890964 829690317 661725043 458889661 351200733 993767546 648138716 694718865 574734428 691438120 399806198 405464691 428473707 385541077 825394281 288171053 87338248 65418118 425116558 537374977 428214926 368486151 654739690 527187276 995917067 239009547 134491597 874786857 96740297 551757890 547409760 160976737 104662781 967834922 102743551 49094315 526685031 749429310 263234045 765510543 659862288 931646346 817735852 199672788 675465189 89719673 20880322 5071034 680502004 29763167 878833161 695301978 938733151 140924534 607798554 848544868 824270708 706677032 755160841 995911065 41783333 789446528 251209027 171467521 836669101 653128296 587821293 149200706 339725145 763918174 992835281 402996384 311737526 370326190 46208983 312058049 49398269 781138897 759542247 329929732 889724749 188594742 23885428 940544799 423132561 600029230 909786227 786775910 198259556 431329237 244005448 342519001 785771665 929338553 586516966 30165686 195978076 675965918 686224306 576146116 425416547 69093565 419513857 774882277 384275339 629563440 347910522 501266265 467819485 420872806 443683816 774907291 23977813 173911558 485265659 224611976 122287911 361202135 405731969 219442182 559677853 425470111 165490705 36555256 40561767 370997829 544844491 86938284 788408364 672658526 572944306 608034860 205783092 871520336 673986445 145230743 6415197 244030895 255800968 206913484 136617754 123448421 157387573 338624349 68625830 110988257 400115399 523874591 944620569 677482886 202132128 940563406 895263248 518305370 118271016 496433825 912798920 248863692 783187573 331875103 791913972 915015227 40473073 10723717 582862886 508520382 447212023 649162882 906808126 292384586 790529941 517672643 221442306 369913392 920535154 866683870 957304443 170190511 135511807 638118347 256544215 8534543 143109093 201564328 167586174 780776474 340068072 622233856 848680908 151906313 12807599 722956110 856307625 154794562 298129475 569712153 275007839 707220800 590952987 667520102 123926128 186379234 993395287 415712744 861156465 35490356 592192133 160227375 384265472 167842799 505071173 156020738 569805650 436276902 749972774 81532342 84525537 964896429 714290711 329040783 993691559 421400468 74517753 918363382 8464739 843007460 821157750 845210656 118731119 437235964 703392914 600978959 92238661 976688368 691851584 848120208 859070512 42610231 666789411 210254445 148429918 722704332 460988805 748244663 647572349 904652762 512167068 636433312 519490575 257761552 323701158 79702234 570665073 217374073 875887920 438295920 302866088 835523510 62579307 462574299 913655645 943958137 676466871 835019435 651931591 380667389 234995786 675968630 649529457 779572932 537080645 55394819 256190187 261774703 297621434 535026181 190592991 824510484 868247385 912859088 625839465 533543363 777254058 185540634 705628042 674633120 139193568 793794868 86509018 73473498 458282605 376232297 984029117 350513284 839273018 682395045 74357947 189082685 481814823 299702045 696466242 547001326 601563133 286711418 498404191 913621286 98398345 820559926 414614356 834877518 132602966 399949844 122697812 940324383 544410721 251064652 129956300 834270151 351178593 304277567 898929494 125628934 372160181 590599158 715937506 379382000 636624124 771965516 430048565 870463858 894672623 121353073 746931311 994592140 422810178 774637819 71486573 289008011 613423833 515513006 994280196 134052596 657855667 993478911 211044959 46067673 900211178 243662142 468497456 613177954 612447664 776909061 63344485 137496930 341971122 127674868 160172008 899468911 136109380 724575263 79590010 426532208 683250378 694350043 460779048 698728028 689708691 298180966 581920025 958171111 72222343 125453547 944276992 287810906 30527796 532563930 604815492 752817962 927783903 399451834 440829336 91214997 95534871 903778852 645194152 452862601 978078086 652268283 273563179 154169331 621926956 557447168 466671263 385923996 271438886 963660660 423508123 126970786 919532112 805387802 139891074 780342006 685303991 429431988 567556501 755789781 763698910 910609198 970978758 649355123 163685726 588067669 21856104 63452845 342819569 814287867 621050557 547596532 797021833 61315846 537173540 940779991 834226351 327708566 735529254 457653122 773384009 265198787 261887170 962512904 359915747 675246005 501976136 648565446 134052973 23277914 362409355 682412653 948084686 713170003 127740492 32371929 948445213 476705522 964337553 912003369 561714997 396806929 432766761 855466074 799651313 113709063 675516267 263596873 375949520 479974941 176435830 914409162 766230127 526224351 48042860 621350115 795085744 806497620 5505378 562590172 476500889 18584139 430423908 351663154 242941651 202931865 529811358 288363587 394803411 443443116 711384574 63017199 489789128 479351244 390962002 840783034 74363262 560463072 618254874 240749825 288713818 155167011 761167561 113670356 536165098 863537282 72977798 820712392 698498547 880201486 430008066 911833044 188794532 642338444 548323033 384821174 712168926 341272248 720610759 114193691 558399165 13361688 730723311 82370424 789185222 440749832 694433995 923117759 992294864 715356523 786438744 648580888 610559358 299450041 632184550 505880090 96797484 594063614 825301561 801529887 952526317 253241590 807238306 451836664 445228341 119051572 956539120 385299673 213573219 237045283 377518067 569790188 90124078 384964340 410552067 810396158 400254173 460106552 64159564 716000950 978184908 153582592 79776272 534513705 592713560 524188274 944220985 523055437 671337988 184798544 122804032 51439791 413657093 305999124 843616604 408667468 634977939 648031087 679539937 477935860 491348225 218946530 369781626 273425182 859471230 301347556 879465009 311313358 422689644 72971866 377872721 243959576 913719123 681742501 821896749 818318769 261666999 508559385 10387152 481675003 534252867 489233814 883362621 25734008 165136407 309303794 943354738 936266614 166415612 23999704 638678998 577851607 941226088 307446386 292423752 225712227 729523135 915452050 824018029 593353367 130826100 41390019 692192594 253048673 223076081 790691742 120138918 824097039 534678573 970385823 606108594 265911750 441488329 13520527 333132842 399329459 981959469 693817343 339128339 314079678 751854288 364817419 527823308 638685775 644544945 521078240 747606783 408547366 459857224 727513897 139675659 230644747 354347054 538266586 472363448 465201973 509644547 987723745 127811992 7383727 452523245 822169601 515139682 403924798 398822844 522594432 703287461 942611756 620565433 113173816 132163713 665494594 918054473 858220800 918944710 123955905 968212572 833013830 653288576 757290036 711477870 761724547 847180780 967779457 37186358 892091666 156595572 784486538 167759446 864710452 325016421 815776827 175003248 136416850 442082871 322100882 584514814 492519710 645133226 513868012 249973688 150343824 384396955 389446423 996588422 60911933 81333253 766485243 38415309 868123137 774040739 145413759 822003677 735667392 197575280 621444845 18027670 776313093 503170923 237395691 258897295 738363855 140156654 74969802 995119613 195159825 799967302 673436778 958944529 355949209 469165089 726003492 719608204 999403437 675591470 107192200 944227392 921575733 933630000 967267563 489823653 70284876 674683503 776943789 124966713 94968887 579278050 893691903 659630374 920193966 191242153 268390342 258717292 78619724 832923411 763841066 487087644 83829064 876800454 996928588 27454337 780330833 216582165 353523104 231783836 818363448 422635934 817055661 765817417 414328423 283545189 781316600 228223866 281169351 74700291 390558286 758561350 138017681 121743980 549103112 905914338 19204478 675129258 459320992 855191016 107983390 609406475 484005952 145434409 938907393 885443038 677510432 734239990 319089664 119865799 745714729 992886861 250618539 443264979 438615785 497527018 190465615 272203963 440023299 214864350 279460559 399970883 723621746 485523589 446843932 697827974 401353473 723126367 798347186 414264150 312725129 37727974 96714904 850358022 892525852 553767191 618065080 607149055 313556160 748121976 952023631 30521740 245498587 911649136 804347942 541657269 877102322 356687976 581207092 129073788 850164146 712144793 270591890 736221673 692883055 835557287 180572397 43906525 742064058 986906008 559754690 119583858 698760689 422928205 980775318 269114662 172240123 437408091 395630364 192709335 553819684 903009186 833975947 994785788 916531446 767201031 275420208 992367133 504316110 914867752 874904010 162616190 391088582 29938836 85906747 80628886 706215934 899226534 685163799 460868409 550447915 848390416 89442983 304801108 916906745 772317823 727072539 896572127 246325640 756375487 129738661 294708204 431802106 622885905 255941463 420676347 242064301 638411774 844626533 81510900 851464212 523788233 631806420 737577410 395265599 334755498 311146349 900657487 261826964 288176598 902678024 926583989 580989736 70279269 374460805 693457141 542149722 576604284 478685520 74564175 253155854 562641414 661327664 716914050 294030042 31079447 904612222 875406761 899562873 427824190 868782903 521888442 387417569 780393234 763377072 594753625 237318869 770815797 959135245 983996981 712495627 325010373 933288040 717923470 361129764 633477751 523974677 133728630 987944721 893483775 870972259 261192068 123958226 555544604 524684444 268190960 291904368 613339476 194010023 18090121 707018992 935140168 270963294 144351099 911269048 144193510 725891099 766958050 715233012 844490085 221594926 184271562 838093136 974473767 701555569 497427475 800302074 754414717 414937374 772722546 14455337 413186561 592595848 734270802 419055297 43158984 764022945 284621942 110659531 883002929 230105933 539170109 900064214 506484347 917742447 983000713 48533419 834425607 189706795 464349880 366340196 128517345 965190994 57687733 420359460 190962043 488865476 791244057 881971519 902124717 95668127 304037773 326430382 348110419 931677205 66543107 158324373 408249196 99626589 981529118 522334170 223921978 584951121 257980059 127644599 978177673 292792672 683942019 335001449 711905515 188691761 705013045 260819196 451974118 686151094 628885706 880740332 160784853 390882887 114318930 562236319 987906665 369316150 571015056 17050280 815524968 40513639 990444571 299706271 84923338 525403799 690334719 17685784 842398975 60175689 58821048 198237112 390754671 190282747 742840668 505026314 118597267 240886533 272859953 220314258 629469576 883852143 996960951 313425285 47903152 534677771 755300533 749082946 135838923 382697730 805904804 850911291 265390157 381639350 715991434 585779858 198413828 820080137 567691477 771577037 220620962 922394044 45495529 272251928 487662560 390009794 433366959 204690358 953571718 835255301 965681305 591006708 951349373 183590988 997611215 215462374 175823562 916267884 390455610 80357919 445020889 651232457 376765773 759379869 482615489 463132911 931249907 947416849 94904802 553973786 500062461 210186625 829498442 539669924 595219501 200236293 397072908 405613919 252469714 895755556 506294592 231535996 898533287 268032873 289976039 108803014 486209789 846766273 43233799 846356635 468289904 227874945 834299147 795312500 623289233 971200244 733793639 385120685 595800335 655314672 536734144 805194233 441121651 999546667 318007017 287756248 478278401 210337077 484228270 280794695 376832324 331352915 34927860 947088502 4018645 805018369 209962301 184244193 142124948 508649923 413624003 821814825 882940430 120652650 713904225 546749125 292763130 437605667 182079483 311841960 346999103 781441544 925561218 789464205 306150248 978202452 494038760 290712938 489379034 321882855 266695563 120415376 104690711 935757018 960547158 692939861 574559445 454396225 460557836 135828847 260408383 634755478 274482632 788357907 863678576 222361099 197555405 817057379 10425424 553466066 158674396 125582418 179027390 790530640 136532609 776991650 294214624 411116917 827800783 605360944 360807204 772601102 204914772 934734867 61240001 806088535 545438927 89961237 871553723 991928969 300051109 785010355 586289511 348862178 266687289 48189431 59011102 290316114 829029127 19176029 875438925 504962642 104036465 104699340 655457954 967613802 700778528 59116668 834259591 863897369 437221472 930797229 497298481 947156344 93324141 875549179 473039621 776206636 685434035 197361713 94506805 50062135 729860578 542526616 208307406 368733439 482599432 656229381 313222383 993148041 239513369 645493157 735777751 703108326 920807053 910248641 252671170 839522570 674363744 289558292 742409755 228782018 255388716 76364750 684594235 679955295 315672566 185308112 303040095 364589972 86696894 4003921 863874923 318678104 801495799 838627775 942891137 754312445 932378313 668924752 142526466 820694830 964028382 607071408 669099452 966372467 798465962 324352418 425042837 446367272 630923288 107768069 41827348 103544071 73330518 521398302 823509815 299284651 18646307 88338040 943353374 73113429 650675345 774204508 565944492 417581376 696313395 177612044 249908933 719282573 538489055 509646279 383365339 420871207 919770281 546711345 277405000 225296810 701183705 835893520 527572436 377129551 401417777 464478457 492359357 792401845 139786283 533274595 719306564 886275307 205747463 574323287 53981624 940769387 335649121 334337090 113214994 578094521 548723822 90075917 87051833 562810474 133380641 102386848 30042941 922318436 783018928 738850971 36504202 897668791 415009767 713044538 408515233 191524355 753145589 150899362 685220848 653961951 611082935 827343048 873514318 883885247 1050500 934385309 726159943 929238288 918073299 196493884 175985257 754314325 364009775 133328764 206123044 5166011 232894152 937973547 536206736 454990357 825858578 450912685 538365074 648301958 350414641 511741220 47726947 136074577 324424816 395817112 445233935 713857283 697497419 376493432 670942485 689648017 303544933 774406190 406772439 394899016 541085734 606906124 577329982 314043844 407393165 582722032 286438673 512844949 774971211 605584228 398817860 378437295 727442627 343009313 324690806 928701203 175884631 957976492 797400802 911698539 59363127 69832898 447350198 82741583 199176038 924314225 79771800 390907492 509742994 430634328 362355130 477793769 14824107 240501173 9821803 248692670 296354208 44867932 507543251 552342512 388183836 928123999 24757158 209126127 686700701 365811803 333244406 891299301 582024153 119344074 754559314 687648340 691950250 165585426 498774781 563871912 474440904 458983519 628939929 279990717 721917415 778295053 239144868 613956154 22432897 910762711 38720641 39852864 254883378 929447491 866370079 796183327 730114004 430155082 708783998 171590712 199937387 889805072 26665295 324271450 613529310 14405252 834685069 930604941 65426265 882513247 172183617 622547251 946297125 987951257 547762253 893143083 894529782 758741398 449020368 676832354 649311825 131977597 313731136 293950859 56692989 395115535 439481807 465122903 349594229 465967461 465343974 815409779 254390057 872643193 885406066 739829910 26838186 613195143 558314259 847311729 374250558 43731820 135698277 722069968 747180381 975099049 508310118 5425794 744322079 961061856 503936898 884249914 470692312 238807327 213706731 808597203 225050695 808133457 684131734 238705576 296522659 274114097 549950519 275516274 603092572 873752404 963051002 702866731 2917186 886339526 104593659 895940485 648180822 239983452 312077295 460307892 834585933 370655379 482836228 871074757 71331614 591150854 465386563 909905795 324757673 863313693 37803107 775729357 78697746 245365088 729869386 34849192 600483179 740490297 855234851 57312982 909607384 282525549 309733662 927941756 711895910 590786487 988338201 665178311 527618141 454383238 851465572 750379434 854258030 102408004 706716165 828422699 117122956 343327845 162423543 915417628 93600341 356946809 564528520 331620106 596062586 78084720 115942819 519543240 817539406 798243733 839489379 513109920 761128391 284605937 975051527 725297310 131791362 666243728 707049580 551778076 89967428 581837167 302059386 851502077 857922261 856629992 541859768 886167506 231985927 291673101 586862606 453407613 904579613 565673047 727197370 703942406 851381606 990417808 444207824 827284999 626186302 576037181 361537324 516448750 418038820 645213770 755401449 129400131 900532204 789409936 874030905 56451964 41640245 563536982 935483182 604065915 539253558 707119137 858397976 896556756 801708043 521655020 14134082 473890676 668167331 716017901 754638957 68918983 125158833 527576950 744050367 799712294 740279271 335597095 105034791 186854141 956674431 933059638 732026068 754848372 832300536 594833539 66947095 409348626 704430911 896570011 421902304 514575678 448669812 998284451 263261584 242250038 483044401 589308668 849556075 162312677 249080948 422469263 439760007 457497214 417718673 787130304 519834639 500167521 137402209 639892755 150169308 520585513 664492502 234110676 782236327 218349172 430761298 204317145 911627172 414089749 748061028 358620375 847473761 274741814 40338355 759366521 337275917 256412096 816325942 593913020 21176007 772014371 75116963 343396593 54195551 484964684 566220321 650528666 995627007 506237085 243574303 743407304 619138048 14874162 185828250 678424538 7166172 970289944 665895790 435764372 868456096 91010483 477317709 417931026 700909966 871044918 919888980 830498430 775004818 945394942 855883727 884592586 272302073 545967460 661664795 591297631 24723313 360444428 788655316 135376519 687041652 478814167 823380425 251591479 992829711 125941126 730524823 596159640 981092575 278239127 742352037 99515790 523536274 468358676 28179024 346551468 616175190 703793332 720027357 28881699 26473354 398298856 890947497 853970623 303234467 510804985 442419680 749014579 791279603 869828905 809133831 97372722 706723618 838099461 313579746 515660430 274671568 419787005 863994826 887460977 892770016 921660019 941722564 29028168 965933434 818222942 327866503 200567292 557872379 735656176 205186955 738555021 410030381 451178599 686626662 394047474 707110911 501485038 642295152 302469091 62927259 400126842 615760646 558841188 272397007 738469830 188122933 928351208 691126917 670416923 755072710 946106529 417988657 613313795 513495153 1677246 332797566 219962849 26897683 879777097 427737515 997499682 882436144 733680727 447217976 386703513 833679315 183770219 87186404 635385780 820321664 583780015 759619602 300996981 875131102 677944137 606029326 41644131 29384761 115384191 36899785 540046856 357652475 501306932 634479499 516044861 72198886 238214923 364328194 337529532 706732477 388528058 461378805 398426189 529110465 923138662 83517285 468490216 356946610 814514565 730632333 187849353 662935597 715471219 354200426 69150258 427358310 971700363 374979229 855528010 974318245 807087389 136459290 182226660 930331187 57560865 305819476 472791662 890656163 624332006 286942657 593443024 981257222 645928553 815183399 510255503 151339544 28534545 978245389 56898136 550728766 383594286 313110017 293747493 442328085 84823774 949873930 410121416 104740483 106670508 373134462 237367147 825506597 520663292 32639507 166686839 332132358 738265626 52123960 284101825 529979301 177101253 606127535 29971868 835737131 311296897 972748827 254307044 447880150 230722803 776194076 969588974 538343827 234857345 617254395 41657576 742403788 74142084 663573862 949620725 496618409 569291660 273343780 329193314 890861729 567297971 561867450 590967570 491293763 531623215 251131405 979984881 782643803 318607131 281149898 400047002 311103284 260709042 523357027 788647000 221195898 442176847 636215002 661687560 574421230 143247287 204827539 444768241 264340461 120014182 71900460 749488632 436191830 983663265 372829988 511409476 740708020 254050125 225473003 421496998 999543095 913872149 964392447 218646596 835160914 355357905 304580486 18068415 566871174 222225740 242849465 190358901 735750378 359217798 808998586 393937946 501257960 156583861 384087629 507333394 2020187 823035775 72222593 251878807 218383459 732988662 984241446 151340307 485104743 204887190 44807373 817400113 487408832 959155569 843813402 22386599 427296322 244858458 478722724 206049345 365571980 943968210 253524878 993846160 371631074 7042146 450652763 992268139 817867780 53717260 311059467 365237530 777706546 283583556 176901812 337218382 835341724 514550510 43124254 564377888 327992162 396068183 780735305 750656092 881602128 133430717 733047786 136744272 324557281 165300211 235197172 433781871 521797354 140985408 201391036 646598911 833827339 651132819 549224270 637730916 769061001 636208020 985806157 340606189 815695984 832334373 648632595 887016533 140946822 58680711 712883744 496174738 466737664 233117674 417699669 72948900 54227675 595555556 607158423 768724890 675681181 576382106 674014837 732120925 565690804 496579669 153013906 550057634 962285210 571032298 431131167 424270754 408471860 448122283 199093904 775039674 627868570 290444360 913696163 477381432 68865420 658560467 193780138 558167137 707849490 759975720 795733030 537050917 621577514 424726724 285412932 746320739 920985407 121787198 641467457 465772624 182592045 59617632 492134321 695176038 720271807 459301532 327965134 631151714 95737744 502452452 930033543 880898562 424560900 781044316 738150219 655527069 997185005 692735163 398044261 592182948 499065950 294405787 19398551 422025504 793960097 709997892 962961485 177730568 896308420 859319148 238067876 690543503 208601231 839331002 285814042 654997056 44088142 664474816 906492435 239604653 675371746 698836599 311441733 504624749 239030293 554271040 327452106 175317645 1654248 530669337 560653757 435455127 266693841 238586882 550884365 515005448 758508467 37720264 463980791 213320317 676458537 208903307 932155424 702153958 474595451 719407648 337871784 171140842 177907609 960102497 594071802 528520822 919456432 687058797 775511370 132698243 597175592 319113340 869212606 189588563 164038699 544879173 662284471 917994041 486994104 910927672 273145347 920604168 123308980 920454296 22433185 666782222 714236757 780195939 307125647 79607295 786015756 929942294 152451829 171581264 932400688 696147857 119678549 929469635 232768634 536266595 657929963 360876489 878384093 275318188 354185302 679697100 484348641 988960518 646345007 885086263 835319622 945563425 761681128 65160048 691223968 595624239 522005344 6747168 468516815 297178552 724282523 282903985 838356331 243421817 16181069 629095574 254900592 779387361 186280019 119431050 991952839 801325121 405123392 407732062 409769059 784883039 983960524 344696856 815534283 601863635 506057082 828951212 446375043 467570217 728436257 576870735 543570654 218829280 102484733 852997896 175067782 349268099 910220077 144702930 527786694 889654029 563109386 440379864 982715117 411373803 123379913 284626679 897306333 528216153 824919286 143760119 792869068 24223499 602665307 774144813 196684415 879404633 8704499 838107154 191260831 90413804 715129922 285300829 304120031 847137950 152235057 764749821 177978819 884545177 754049113 474332667 917411917 865366789 96655725 671045725 853282713 263313438 380130715 949752788 186829760 663850796 231422686 959633680 38049170 705677473 468043661 356609757 585198624 492878736 138831228 176545335 876504058 497793888 121911763 645364276 432068689 546610247 151327281 332422234 619624595 858617165 292591809 249490253 123644211 193066839 822658720 45729129 946405106 325720510 982891978 602498494 722139614 121858962 136634446 29472074 547744463 358262416 892169035 878834150 191754078 779382420 448150343 59083466 122735497 492908393 103133493 52730999 371014615 29994274 188784074 449296580 572512671 790824054 186062217 303779313 728156668 593838656 390719587 990468558 574663532 270818776 403991409 795049717 162751082 20428131 751507990 783598039 61430788 115224501 242929336 367180187 87948724 805397131 174986835 271353275 99703641 93992674 701574333 54390855 67204613 70304635 86929379 178248397 595059113 690960762 969120509 829858614 273024698 906211102 197075428 679677266 613264091 926663865 721064092 668899990 133865662 882438801 377494573 791913358 982307313 999657629 924166120 656891967 229639305 844486897 954692940 831655782 138462746 950960159 431182575 830386513 888244791 968250814 230927966 684380729 124695592 366400514 232686942 14696061 359842573 738272260 560663899 988016126 414752438 585778860 532392775 427587395 567711792 988919419 446830779 483625645 415530513 226601099 13015017 699737089 166578364 771220939 216349444 606907058 81895970 153927786 146607671 376183222 747837254 254243667 437177626 268680773 369527451 510723174 335386472 237939721 594998706 46817097 732160390 438957259 914790367 448383627 766080327 854869418 491719259 160191099 101737283 910592159 108488763 930360295 358524596 414657433 882954755 136330744 578951377 729544915 901334842 768458765 813650884 55282194 826905116 512496783 933697273 766298706 406808986 566290583 768984577 283778138 933554214 51563216 834240630 747538346 441459512 314427468 286449209 485397062 75850562 693727359 91754403 396846448 750107540 88585459 271496431 578589414 318020507 333154446 495114495 370961949 420927609 301356554 978820641 731291685 627696559 758952721 414506832 40151278 32331328 521916266 795361322 410002753 915123399 158528913 366380601 350381104 569732855 729465283 756197473 64356313 992973706 565807691 65953013 889496431 511948569 725796210 410193357 651419252 873314717 29560187 396738191 262120526 426024342 308015504 75441393 780154910 367412425 844496484 739046827 316110238 643450248 873733236 911418845 102174587 1494971 259210684 488829994 794022567 726351144 718350532 611976672 515029151 551785334 675237255 476644447 529463870 549891733 921017886 707187454 424246592 679092942 119342846 670262529 795625250 190319495 283550320 298335458 127509088 896469676 589176022 776020769 675289479 388908406 254161771 912151816 553534564 760693707 156137483 651903284 777043454 225084126 775569521 481930045 745801739 695728752 654507342 673020144 984063156 312158399 92920975 661402830 316130098 584958059 126136171 905850014 938921220 31334874 301763664 425632677 598548565 409852439 132789157 486420118 431808339 747364335 155746082 259042629 325204147 358211377 982648487 252639927 724277249 194422036 330169064 886977223 410105852 837820613 378965061 411519086 937658077 979140345 10095021 193270680 239592730 222231788 23037367 248469651 516655308 76852800 785724444 244463685 927065024 561175667 116657088 233971738 87461275 434036125 596839359 749233965 556612496 496313298 977167874 424242546 337010089 708564675 495689562 323827371 33835860 959034535 77485440 691524746 69068442 504370230 642898994 166539108 137219763 298260650 881735786 735500615 303497100 637148078 587633512 816010501 698485049 591107006 912644464 851256801 656673497 714336950 974236373 168297885 934641686 232863990 156411185 98192299 496404514 820843614 70474355 359349988 617151212 509210988 192595914 885556016 578463539 162026715 955040596 77935314 574435849 211228384 333499224 191340522 347700677 127539714 218498162 842634990 655698920 100409222 398775885 665213235 117614743 314718740 457691160 21643324 22110925 884270740 984868428 89604793 450706722 965620985 62076965 594641656 54274663 940381838 696739597 506981000 387504104 873861575 787158261 835426897 988069723 836477191 54546311 851205047 996249104 715662282 424672257 158772767 985596456 705625000 44976236 411815333 348144859 313270194 814738140 799593734 622805897 188676701 288978020 955296894 598703485 356943221 270975732 342955011 155806690 571186171 446714635 153437916 70907390 904298675 980627734 877194035 650196982 370726237 123050800 390559677 262944145 624915339 769663773 50763381 841257887 931446364 557741339 626947643 159176282 259333920 213415135 459684125 203085032 553954349 944678760 133392044 184564174 95324795 623599257 678865573 788202200 937124150 990203783 749845846 377006073 261023301 591740788 825692584 91074568 224586784 583959815 283949553 470988505 745886091 214108892 155538660 825259658 749025435 403763804 689248970 607194407 173952844 952525061 765535543 730966886 386181652 270046691 610510221 742871524 892016714 258211838 683507196 634492078 630409937 906192108 746769774 693967245 163051972 986536010 11922771 751483913 575857092 187927322 11088818 806155649 81295578 35046096 476934731 70526916 523921557 316939806 382684648 540752527 395504853 559108659 788278401 984492472 927333560 278325918 895952323 506844410 489628391 77251155 551095238 546874862 4334328 953966010 409458929 297334370 533888599 360874398 704667675 548106482 662469790 788186287 555216752 795648548 68066994 1243743 453990993 709709240 30269689 689763927 263471109 657288909 831185854 47838632 697121428 443080041 322889400 311169769 112796138 176483408 132699834 794595723 606556623 855911189 516020375 556949387 214377715 289696859 363036212 535691211 682451172 826484141 986443624 111395323 267589140 308474457 205413173 677846862 851748901 725186092 162597447 446421599 933325407 722875165 428166703 998567567 12689449 692638137 243929367 760422864 909460911 265165042 702359250 825783359 875036828 30188424 345924497 43143499 112123259 738664704 394241415 558005660 50943214 832097780 719574652 227541111 925413099 640530859 467927502 627123742 653463381 591675316 93787868 90965369 200400254 376482931 379465461 773684210 908076616 507060930 561792409 837588122 104176059 966691017 989118476 979647463 765473069 835057687 992017291 258727645 525297875 813287133 363132600 631709922 402441205 683204009 788349191 559630001 955635659 246920278 644304887 507857601 153081034 871021591 483198996 152009047 938949664 612346961 365252192 379128015 944239355 731058575 726262820 911589029 963716174 168859577 831590204 257590901 437951095 500508850 230766558 210044759 148296499 859152079 472234941 737254390 861209729 453414357 651004371 416127319 896299836 970771787 681147295 505793377 978307555 242428166 801260872 335236811 169005925 212817083 993482870 389999533 793469512 783172238 373902509 119959968 282006184 271815515 821076496 944392747 873416166 102679064 154043946 498130170 977785080 54566024 968745466 273809092 621606298 51786487 904730254 341269691 819553891 214520567 235239972 505713955 676482430 635235030 245145434 181512510 759614988 283641459 706292901 273621448 669442403 410088664 368873965 189613658 905106486 261382152 26529973 667947824 546924221 674772333 556797021 315708789 795472913 568567444 527119059 173313190 938896736 29505648 335802398 933813301 704663032 93621956 32630166 82667488 953705632 961597960 398831948 788635181 243694158 83909768 313681562 925960003 762911894 975861681 2253913 669429507 883073673 546724024 93363034 379301211 987686403 480690985 288547170 758352806 777825102 121616403 553025991 352140468 820568703 191438368 822718780 977614081 690292655 196700210 41509016 718488019 975973221 807181039 12364301 446401015 797827543 881417456 650882864 972275294 891074645 402943887 665441958 158684316 800685098 753556898 162580156 684204249 423673738 408913656 607513202 969455771 759083313 852093883 154225711 492361156 14599376 385417373 640940088 50688159 896711709 12684566 331187480 807716795 766037979 528855137 95104820 443041402 742763500 621437239 579806 585610794 917442448 556688168 228987934 934570038 108720618 907953739 818747485 453752638 116511194 424260479 111633868 233955471 437505936 475227895 589402839 103088845 435853411 551211656 80726535 31140854 593088496 301412756 610862496 960745454 448162052 637478026 223065718 745291622 50414096 560121967 572763744 181599039 102632903 244110073 405278994 28042617 730112962 103453291 810322301 587328601 777517061 955707808 195109240 115511142 392207673 601134656 496358852 443035444 644659501 238080387 634515886 179781605 699947996 167072418 366162214 111220536 185255763 591616931 841159043 204709457 866290624 416278643 302769227 672944410 798593843 558103905 321148048 145398809 864393663 750072884 222154226 90963578 896787862 273132959 710150149 780217732 115184126 114297866 126978568 280998020 701188625 194545177 341789021 93442756 710779598 962089217 378205832 636541161 992191305 266821473 162273534 186023364 589942920 276154875 968101184 105946830 567316743 618578141 643670724 362998285 801949791 196471821 781606529 606214827 353315780 318712216 95248049 711728394 500118174 653897482 954059359 825858852 309122611 632722120 656024549 782744840 797995903 47411300 519601617 671665787 777538810 849303253 185105814 393641949 81444966 4193109 629315416 784284094 439814481 129489208 326070474 699419237 292022341 499456753 442062944 715528491 150698634 703110049 985782843 148946452 178996187 689013842 883346298 345732336 256488319 588478295 617891013 920124778 149053877 966521071 376567360 116668561 880723672 38036198 251677953 828642556 837641967 726898557 107797610 964632891 651801462 557048288 974168396 799751549 788019671 961264358 772092203 131620797 956341383 589173745 807164783 935496109 944736868 912947406 845204684 181090411 309547356 51033095 115786103 401640611 273761862 428330966 971788386 110817932 401759264 745615737 240201575 502939166 879284032 840938527 380973991 424175003 602305276 500778099 125237185 188712017 241263166 29964665 422363405 364165202 298945465 798342261 635879486 684671514 897769274 604787839 484457767 770792240 278316688 565224263 699107743 32171442 152955269 19581889 863428762 523244081 943629590 731766303 738974257 542571557 30425426 825932865 80733004 817917210 499180741 736556452 875961590 612113375 741864995 474440685 511925698 87388738 402257280 384202989 137885227 926217966 511196002 772470120 336484849 490805683 409056189 811661588 61009139 186525312 511315008 496450225 877702169 870570503 667938530 945680644 67089962 1959107 297449290 438256215 23184287 507277094 344766003 865577885 233423486 588369752 128276580 424922649 384825908 34883529 375516705 427107428 324161580 54885933 316391573 330187891 812575738 849111780 969814909 880413158 47101535 560089535 357278711 744108517 901260389 702416514 424547967 832624848 187028934 704920192 451934196 186228569 790642492 442886462 580427525 229083377 925998902 670380491 596137007 895255492 778338307 858949473 151883688 553006126 344116834 898155935 928752049 174142552 316714234 190230220 438620171 815441113 494814518 568837129 922927337 43408393 515578522 400567538 458827128 566999471 434563235 801559548 377399683 396448146 622304298 617699814 285009741 312948618 742520720 877099973 452404714 723295454 546281849 761174136 32346972 421580729 167991710 133965590 144308899 956464116 464109541 752854441 172484637 697372487 153312156 481216701 277488744 749255940 782989943 103514703 991905389 513421405 68428338 535569476 56138186 511387389 452963257 87982331 3391585 109344249 343370636 894380964 694117197 697496026 846166851 195335596 208151684 322036490 972677070 888681893 979969704 719431305 183089161 200207615 967829093 906464092 182968822 6348010 494380045 810691194 640716930 72385951 118544904 155300965 516913543 336732566 620939665 847406331 8325119 855536904 194483517 434543251 478614106 830890704 324403175 825429323 551344401 787315232 185991815 924134509 716265603 273931405 25672227 765671572 884769986 868398982 315103081 399071577 670791928 777981542 69650991 490531536 605414461 252591682 899735170 830166360 515935440 16793144 952830222 461944818 802770059 184543719 715899495 332323097 693024075 536991648 195515081 33061154 512245861 891167755 81214220 382942167 153205695 356390538 486966648 359228412 274965106 923624684 478425651 903368109 713891125 897804561 513632746 794854224 744434390 453539022 64310005 783616609 956839665 377700614 619662231 974432655 201059976 154002429 918127516 199804148 687326418 433853619 932055395 13490688 36483677 399641672 562955705 511272129 227029288 693958790 476227628 33810239 95021848 215096649 935698216 494907156 867711701 788864367 293736478 401750798 472028179 504057155 692392075 218440187 334656851 854151156 839726490 624160371 835150586 413433344 605471230 236004311 602402065 950412393 536034798 859184707 975929136 444753662 332096763 167824846 866641576 462975769 523598437 805722414 694239818 599011296 49513239 553673028 57496138 880327808 4647256 289082594 544235386 930557326 176376221 6951238 752527126 713610478 653478998 402274192 409179632 765090240 806968924 806163864 289803581 742207865 452597411 348350732 185111594 417221333 909555328 291933867 701334037 320906568 842034957 528974324 512158129 514782070 477217190 912875249 53958457 972826742 404420260 41733094 643028258 43792658 283868683 667579885 166082160 483537515 612384371 825641856 918680490 878377727 848441711 597599166 773929439 351846240 338156372 131108600 193380040 106201849 446695705 36584083 430979124 167755776 545661641 158952488 663756439 756855958 824561294 141668657 619044975 738490866 160032546 724065404 716399735 371737093 168121671 693751162 875646389 589787747 852082292 681031216 91822976 441129509 839268109 631650110 371915614 9537028 79275277 616242475 944081869 745263050 570458777 111790014 347877209 574590972 970152693 923982042 917548515 116426045 617339600 440609587 851411152 284395252 939998858 486000883 107860236 578702047 23213169 28495291 628024867 858927326 903501501 19241196 439746961 45573744 736372352 751296075 136856284 902448233 604090733 654713662 996182849 165467249 193418657 436416449 508043281 275112120 774055516 877776728 618411363 628037388 602826632 274685597 498703027 308410501 772316209 66905251 168417314 555326950 436506841 91831359 932106672 510073678 978368528 163179923 440738237 232047234 332962247 248722169 509505701 778679881 793851183 524536908 507282197 474285005 152597672 661037614 822365798 103379775 254876455 548374275 310420319 208082141 180875977 49064694 428445054 848580862 370063692 863903544 24446093 522536638 577147373 726930953 961625192 775743659 714901058 421312146 796203870 282687010 5672679 267497596 7819549 335080473 379378960 717328604 766134468 388751706 787675989 305214176 930204031 207452187 488679725 541392487 464007431 766761280 2187107 994543070 802893431 272257336 72684513 855145591 780431768 105968795 115673968 172023091 549198975 476878837 698048316 908500655 319132645 659720478 37524537 79825896 467077643 814288372 723682209 785736616 657937505 986776061 247152063 927091060 921135423 804170734 368276116 18276354 946536855 5312007 285627536 552347152 744476939 43036022 261051333 322239875 232920548 174546196 844886123 26667909 875266526 584254436 132528686 792246461 480696505 124737425 47266295 718869925 382175574 814871308 209691579 418327336 985893933 60601786 243052801 495149605 217797776 227452415 606807088 830681114 393485531 938544428 258027565 738460451 924034772 968151792 913858464 835490625 409218137 52839607 284081233 958372704 249497841 356900326 217403603 992441173 792243071 692461786 945533207 880484561 976327950 756618143 661347241 424632191 685004940 60037056 751565646 628915564 384888559 49282777 43787587 217134599 787032663 702280362 839698760 27489557 396487944 366354656 679419533 39935960 161260742 284063963 163251422 568467446 558358344 766536137 512627226 280586024 646341245 685132729 828834371 447868177 136946484 575068650 183922497 173108166 769400734 310281190 221124826 750604547 446665605 343522745 676995756 654801027 763872772 26160051 400228172 811084748 430141855 244231410 586261119 949853440 156074715 978975492 247843275 375428986 857336566 732267902 482366702 820811533 841112530 307463658 423478643 700292361 850674514 679941900 352907184 454482811 495281088 774307568 285801907 385797773 898027158 256866198 753179855 142220498 430099407 381247357 11071388 34142959 702746314 904244372 193689060 511247966 80325236 887450756 904502055 785371926 693478320 520933280 639247670 128506814 732938663 455830220 636285086 842819008 328736046 518825595 214508843 64866864 399409540 52657632 300270931 114856431 439760096 355687389 698130713 424580701 865359253 725231900 517455420 463465196 509456598 49506185 252969342 23908253 111934488 803829615 993121898 347099296 633787834 614872864 873000347 673339559 400997239 799707090 83582043 901574199 652633127 423405309 682070280 329849208 879688557 985721786 551105737 772104087 196592047 343112879 309929476 261351259 719012878 5850349 209710727 343254430 407580865 466919729 493366414 155914034 62715527 775716926 946951089 658308461 458493015 86816479 337856651 66899172 451916315 14958930 956678270 286333011 584576559 909098852 576282601 24190234 282974517 781470842 611142875 592291582 942069440 927307280 55192483 197068038 531965634 566570138 522811688 499190681 399148201 371600902 443938816 766934521 667359660 404069375 286369453 553854312 650642701 96416949 554401333 793957405 961772418 304191815 36858394 34888845 752259880 646870330 837108549 380013127 231183328 339048807 117999833 813794051 79076499 778780127 111794554 775425939 710957868 298725861 949799022 937378321 380341490 630301629 81439141 282611080 409432903 684406249 221135899 823073550 799918453 785305901 180021453 593428813 272808634 798071077 364737731 98418702 968124248 704306896 243494670 437204881 994830555 548697974 78304609 629783861 479081232 969753631 825870644 688664852 856340710 122424402 343465226 255088097 44527763 671589684 161747589 82745302 735453737 221494260 858634655 330458827 282342051 74953002 40903737 982283665 932028033 981687225 868483569 299342344 899300755 104623789 365715302 101467862 985881714 41915114 209161188 722210022 51520259 319271770 311084588 322542083 887389336 173243669 796248498 769603210 521909571 234045611 184222289 877012632 33642178 497721628 35471066 334791704 123568625 484593793 147489476 899375059 924270399 707277641 608123894 844456255 297325144 835627124 371826164 193570956 391195562 718788721 762358922 762808563 184689066 702941976