1773 3282 883545336 493526835 215176308 50843997 166359949 989740235 328965980 19490202 97393527 821810361 48052782 849754036 632591558 161122390 132894549 532761925 157344334 267695784 720822944 209904990 687524039 986837855 957926778 457134435 621236401 81268192 123127643 14117872 41536101 672970285 945810131 261195357 751990356 229983606 929438867 224242776 199858270 494273007 38774252 140982926 515924375 458305092 225993885 336012626 129274396 272887769 32687363 690457960 523419995 630923261 630653873 47259407 543216505 610650229 715723801 865160411 78272503 607394393 41278108 529304914 968625101 676836189 272347581 627174899 628986530 564361040 223181612 22949711 97363731 599198516 194018214 775026551 102653275 926497788 454431840 804109277 319891286 769603918 707885417 549897985 969907725 921292146 100182484 333837133 429192763 857313461 181152778 944045183 634305465 354857023 18426292 198923843 125239611 111752442 422402293 287854952 742926767 132253693 165888697 782901687 480265771 345450135 22753141 953572902 89067505 446023710 715002049 518255634 941178981 876381067 70312370 148202382 790043383 184114395 425975307 934235638 419965635 244153866 173098349 487682135 448812776 804090299 207324204 922475520 409444025 692359824 568582549 866457855 542950554 41680960 902970852 89952387 420193523 461851905 298541589 122976572 69715655 530377430 235609153 311960927 76461709 258034226 901544108 881075710 396041891 1393431 418071380 31463420 179718602 369724225 739352637 393898987 208078613 509708680 804806349 432929707 545092175 348306659 11935913 731040052 79508023 800617768 313433120 441614752 687367816 134160457 345085800 827502367 768997805 40670541 92544269 739277965 602245508 4125829 516895224 926333335 322161780 651628628 831907301 868971382 371896546 431131514 540083817 232608393 26539649 332244555 85885342 182867442 510813107 275704208 239904300 814142527 813535606 302652192 827064623 370404605 288249196 281959921 164773488 56660321 152072679 846889491 877695203 217929102 179038443 385780204 878077033 187916410 145643030 93459065 327516089 215891136 708986551 37353432 175409316 169126843 179508840 248349736 619682602 666149480 308228188 4474235 781468749 436730231 988184686 173553463 585175664 70638984 979472052 212529339 110802080 475243772 814729417 291610941 351534432 155646440 667328164 920475776 602346813 641103113 98618323 609791286 15046104 642216018 689112409 602042499 283329081 698570460 467123008 170938729 50984103 691341542 475358454 721797228 291466175 706444271 157434203 519194700 772474080 107179672 123037419 858602048 600309098 540999391 640139736 176059474 118254359 747088473 330269251 758734788 465616624 674248809 672066511 715224141 694423702 547262302 437026690 872519166 385684551 71854198 867364261 581523279 897682606 616069301 818227183 196346481 399265172 119745483 832008511 652302118 88565004 250308219 787255305 21433940 771864698 454663457 176742205 381666509 12121012 229885824 546961252 666392462 80389475 898648588 473692650 224361440 319543656 736612587 573419425 111371788 420257337 800504112 482524016 158844885 158552829 818717771 460053840 616114084 69566407 896085751 664175143 885362196 553252757 576669673 331992389 982277413 245765899 286097969 83618469 646266765 276719767 350713131 175218901 48287867 18079563 991221239 54745796 119751939 278247231 970887701 682977224 815893776 210493751 410755122 80016400 672689226 57339572 675476122 779698405 968991918 453809659 196556031 478694224 80220543 268403220 100206947 198149857 480620565 545750563 714439245 431338298 302950461 863931270 93562975 132405089 411273381 167927262 496705865 311187749 82148100 647807454 806083694 883999737 388508954 688381572 71771660 20355964 481766122 766103045 55062377 735047021 766605875 828096972 524724356 231984414 71132246 572493325 817760570 821736076 460896242 755812583 506594912 289095872 112634271 473997409 14243184 540204997 677340589 878483554 503014702 913479453 115237959 17783086 968050572 231220092 476066082 106832209 697464801 266720988 922444083 483050886 711830892 300708204 539435131 674064157 47330274 723228027 346323195 858617651 203075222 163175575 381458113 465004105 396615516 887360776 748388053 411536278 297895700 697534134 564897685 348317210 661162273 201015087 743333423 503936314 590325788 152947159 375959546 249403635 572566257 440322582 929433355 285606680 87727483 114877306 785791556 862127989 631177546 41920910 806011649 554582692 232964165 295766045 842998597 320174051 67998141 668394348 685601264 449742074 736012544 507522388 252180767 588364421 971498441 579357427 358944460 191743488 441411440 76206220 244977404 382586814 122124491 225453205 989648703 793315095 791906368 893996572 365471386 169502703 440708121 802032960 60700616 63775063 19516163 828421304 326338037 765595283 968703063 776077633 6416849 455657244 911434044 90897265 246475726 763220995 638098168 287863772 8347269 716381949 854436384 145323025 129874778 957214665 993902487 604602310 438251594 474623626 296489884 403229436 631740583 619892319 749698167 306014352 820204224 127173664 179209856 145248774 904795038 795002534 307479363 813614803 404435052 287186254 707652341 718708449 965569169 873974715 153155231 767093730 207741696 87507973 207164858 26587930 954546149 695390475 948287739 956661999 601991758 9838381 485006207 730609270 842977597 963171897 220718168 960487646 778153479 238783026 170193576 886887880 292493990 528815523 484348326 978172626 526238688 399233762 134488928 354915498 172158294 319191943 398779996 817671896 125301892 919712979 270957118 281417799 741565086 491556649 181870426 534227131 73749766 570535092 921794272 987664324 29211797 396584474 642037446 408988946 281493386 88703830 640765025 593451462 351292076 115180485 655968124 869553115 263629199 214888456 650321521 606429730 646016905 469407228 339067777 588338258 500235234 131017012 775575493 961329877 988868314 22586799 696440209 419201359 726108780 94448079 58359286 619341411 334162013 136205501 802698610 995716333 798950616 804452827 226598426 919532972 169196180 998360849 676519075 351330721 837876290 329457202 53149886 120073611 977099220 581304883 348585606 801229873 616126127 429913464 408968425 924450774 758492226 465154822 347182774 681347839 505140464 50755776 250520958 539747314 422655313 14074847 691670287 588107303 185964091 300992688 333907474 80288931 254796569 843992225 346183478 995911105 550852654 5197260 285646414 432075345 285495656 156887432 511803025 686695675 263974390 890369808 682176440 184425060 157867427 967575202 839664066 541820226 25251517 579320911 638720436 189986664 586560699 464584664 400047667 10352128 217267691 998286546 820896133 218348279 165171654 430514056 418216407 466126265 204656304 967422819 930575853 264061735 618324864 553589127 917799492 521011434 53397326 279999884 991090991 426773761 122066264 328180901 675244440 646664826 10684830 143735280 822403518 773155588 392626116 299440366 119343019 635991913 916888565 752111789 870043776 420234409 262547433 261541715 688672244 908897704 810936920 756576919 769701430 898036525 525122896 656808404 456865693 599515634 368168254 795210516 64387106 634949798 482444944 6751544 965849939 585714215 197898394 508162258 344600458 240171160 482800 115109285 5288459 547949403 333458984 111864567 826559637 203265999 706814693 34061779 927246463 926152056 28836724 35508467 111431866 578792973 726631044 741971833 278147381 549574405 707705493 377055914 605599365 957443817 94903132 849324337 37545105 404189025 8448376 201526267 377754242 614142848 926170896 246032107 883890033 602482960 433114518 433159599 645947489 969420018 517846107 811180696 624634424 950144029 108081991 528678841 106716003 537388207 375487675 563061642 943161482 385215589 280704489 995046057 847637775 47419396 416692637 492735032 653186884 726409360 288796011 50101609 262044618 683703331 856001601 553459813 718133208 612076206 57250630 458028103 860488788 639225698 451441657 274610254 615675553 269998937 104410763 56889170 247493246 276327358 326129092 749974761 14036370 60823522 473033988 394601089 425455587 615005463 818486357 909389251 125628688 610848153 674074714 708828311 135883654 55402486 592775332 767185360 270750002 174647459 433354196 760142001 154972671 471700753 492754373 185262023 815079807 437695772 957899634 451658225 422107638 12000291 74560154 421153886 17962888 135698076 26031389 180626338 539218710 245856875 134934933 522382399 731540525 318560994 703575269 332078827 50602579 544182617 822535847 963915277 550994682 475870020 658938642 408227342 353052516 909948147 124275376 100551687 808452072 859044579 345725942 576734280 778213657 776953261 957418257 481290318 256330911 694070124 667620208 888135991 340245781 803912615 28069361 681046307 315548273 533243368 834545250 569090543 968447219 491696167 668648725 386319760 766284270 497088315 818060848 402737932 989145889 665258884 392331015 425757779 236984388 834907421 943633195 893064856 896875042 996741706 886203897 984808638 857835358 914990640 847342779 40336079 699819065 679484593 987777061 53185654 900893922 810687417 977913916 700528479 252182982 255421865 128200836 311534320 193210235 687291328 793796838 524596104 830714626 707985832 232911298 855762182 712530566 371672808 425812700 825277011 510834455 224743875 175710741 254301021 827060565 373074444 446945233 955729475 954536208 697275312 630736199 101511670 649231846 93290672 713361554 183063488 964967336 84214159 932358771 617058011 22071893 727021591 855609661 264207649 233925061 656432365 689723275 562544254 240084890 786865480 650705855 293636156 385801451 182032791 321868047 266968607 600504527 450844160 631971662 20962382 189806907 534430222 486119176 12029289 482896347 807722172 945850735 112160313 956025366 57079536 528680847 922631347 454724659 36817704 487251367 49676077 146409235 998114385 879131216 754499785 179472954 654024987 27329280 365305031 514676982 325124826 292382075 305036710 69800819 572595749 250590336 961176189 342773409 848535038 276979314 779106609 710084430 76809922 487114744 221098420 276653583 440403804 722920222 552521501 855659456 60397761 633400403 822334526 332855426 662687278 774311879 875441902 651996564 285502405 244109017 951385838 597595402 24612795 526263 99656888 637957458 855012013 482788715 906752564 893778018 706630386 884446761 224376049 529744193 721488764 798440110 204097834 663698669 15668529 907016228 815406478 402642589 879427968 117454059 725867766 223212575 566118723 837249814 786426524 730550949 229001593 797651212 168762157 444388569 715033918 474164439 952213322 372983789 630688719 52586034 894961775 409550351 635194804 209537508 170848739 19687639 176662611 617414089 148429037 252446481 81094373 8031972 885172499 793578747 327263082 455474623 100753325 137063196 342183597 571309616 33970726 854922752 809345772 539485363 203073363 299132496 445012437 750242777 826396709 506548463 105771239 254817204 965236771 110233217 8355413 347692645 270987517 502880444 697342513 52963289 870856603 578642751 630926918 105427251 681160100 839404814 802811058 433236599 256853580 107528542 288033132 79084613 25643923 92918622 847870002 130980597 500170189 851873241 478585790 320054889 258050926 540061195 703788805 80291304 643046652 315261328 984850832 250440292 255671885 920613122 420348023 384982333 470789909 523525414 522019802 532965143 541178414 654187699 177746031 459785765 707738328 894494468 662963496 850941877 333214148 140145615 707327490 882332078 620696952 891842390 314937897 952144420 433730189 17477372 627667653 116162721 181073308 385943418 558836099 582483197 797166240 95859955 968280909 498912331 105221699 730978001 987164732 853007903 687928361 215588340 377169050 980921662 373161412 844714153 894405364 901408460 846678512 56688197 79981018 957226814 752058875 955849342 125835082 329675286 183219085 121367364 48936744 82236530 128720165 70828693 859450735 733788107 194275741 56666836 221302519 607347655 241818999 351386709 711097108 870528147 308339902 430568045 990177447 285711975 450940043 36308640 843228862 594007499 723341790 115741342 451169931 438899073 905561039 765955012 695548636 348339952 969990560 250498971 568761570 47510515 46657134 77897670 819569776 392182250 603545438 477012806 802951533 112655884 669608631 581769608 952199443 24279219 682398920 914810024 520183706 170094897 293610584 240025713 398993720 161194569 525028461 805959598 43030153 95318199 107798612 428794995 598906295 459864270 894236884 553306085 266830035 465523082 169583627 330002956 518132586 820629275 555904231 573574425 85698340 657151093 190111470 862997340 434471068 555669350 497560629 37448106 675268803 88145790 263350713 66744098 9705540 316318628 291787989 588709954 466291725 562647927 165475666 520217952 611471112 355381702 336370092 29092737 569060508 329388317 304964072 275537098 270573724 272318142 70479959 638849079 952625969 680627071 826188736 66713431 452538485 789589381 646092196 358855170 95935973 376630910 248827844 589600078 533808732 415200579 408756035 652823651 239825482 655481823 552752893 615947394 279284455 337580628 577794335 549145051 295303679 375776587 582904176 623717784 404298951 829651054 246285116 926050602 449490769 501433244 185996250 697597543 965369718 41648844 733609265 190656803 24817599 108393977 592816316 470942929 818727355 525087489 244008053 133229516 420877651 637600919 820515990 938512295 986941831 714976302 57363052 835195148 785322137 980387940 669364851 720968722 960776383 751980049 142377391 101165809 308878280 562473448 383477288 129814015 908937924 458693719 525088846 479966271 211557638 764320065 401999706 542741762 60542042 606544791 562819540 481937645 106409296 85081400 132005716 552978950 550423540 355216669 463724054 621103790 51228164 756101916 320391186 864943741 973512965 928784047 558480657 359149014 437662806 212306108 781691678 922426384 891617110 792977222 540532380 649997775 447068016 968449845 702488169 447453219 603155983 279243688 311934748 498896617 116655313 865857746 614016485 157367746 517464657 110751353 756057307 849700863 48496291 401235421 198914474 879090156 228571263 122651420 215754906 941307525 388293664 597443655 945833410 952320464 782067654 370439005 116070964 224603467 2273397 288002746 139688567 243169176 458261894 256033345 174632171 14668372 490660580 820305372 950277907 270975424 119582388 848693975 510161375 585917 823794083 827090990 347143910 382218366 326732919 66540195 67116245 699166205 458589165 211337708 866023403 826169940 577003335 559937019 125130052 1862022 253120506 360636515 644546002 348409578 875962592 336454509 833463342 162067393 631238655 689846064 774547341 54474965 304265737 614400479 477436110 893499130 943879828 637713759 857979524 438155526 156981605 938347004 652644845 578948821 171831898 938563045 797018022 165998104 871560714 913824997 861939547 948422651 47172329 806106093 276839111 741300146 439978072 348141316 251271188 336096552 265352936 259659697 837941615 549454939 822158864 194976093 281337032 849976014 659848883 573483234 313873692 507712606 20316507 884923573 353825296 337659512 442836339 67771515 392159015 775595604 151473346 794740086 141955010 239316713 970889802 206168689 871041742 859165632 197256314 245469679 542045122 968620356 54262315 748250797 72284249 195467144 998084703 363281283 274668495 542799588 11175206 582785074 739553989 769837094 861369732 750373191 79053046 58611370 385250378 74496735 292264574 537978744 366388126 856593584 80051642 995165217 954073051 894976827 808197877 887582299 240482073 949239553 592506925 278997901 785785589 530588205 152956190 815987669 976907023 968117191 144333948 314177114 212712903 937979392 267437531 282759863 130404235 137623654 587686895 236029513 24529681 308587438 631531137 622800757 794323100 644138687 672805184 445583742 418005141 344454512 412679844 76561250 755587067 194142833 611445660 864015285 64090371 906487856 693751843 529465009 703439167 962101261 358886058 70786323 914242551 148212781 637034913 313561890 604783656 588831466 725197779 492199639 253947963 594286517 288782109 57657268 176715403 918955656 351670912 865928552 343082904 39969022 394726930 900912604 361281196 122475630 272045094 365178265 673744868 652506121 163073788 97659196 603912188 16773102 450034154 501763180 882971331 156652766 910899830 672083782 113449036 884801425 497403636 177790671 639203368 27522441 987494654 838770334 96027102 906734143 456447391 557318526 565448944 988710511 850689840 243308317 750893839 7807222 977483962 252199854 920446654 252024635 566259878 364152387 151782344 481627221 212912769 766488293 653377345 973253273 744703342 243975983 609739894 907635836 635034521 493549140 256152694 544590225 277626457 768163219 326877204 917992975 644525366 392687414 560136461 884312104 466182171 158978412 175972029 118399352 253453569 122179441 408278804 160129121 663294329 292350449 575712999 536443448 160530878 54963823 278901666 116667345 676377444 856775974 403574379 766131815 927199105 396409356 297745318 519515404 863705749 369798810 858817380 676277403 843604652 265453275 18064500 476433798 187729982 667630139 893049401 276906655 108454882 662398218 135443407 814128222 245670172 288047435 994285539 846816991 849353454 518146523 138123062 518860959 850006764 836579430 81870403 797633125 464498108 587416727 732327588 913001033 788491920 127908099 491576150 577756689 700457667 89413164 825646536 829265840 623967605 942834156 341815191 137909002 575863729 310048625 637855805 398505036 290230326 959340314 150655198 599390516 133994422 262404532 52630718 162779808 357597424 796098151 793678200 695621757 688748688 378692529 370738288 927741453 581374705 710486918 128129465 814492098 242065682 910975343 553093592 621907628 853147105 944409260 370292386 397061618 510046653 986762585 703339180 929984419 138926620 243414562 782023544 708728319 297994535 298848300 898623521 149016369 472108248 266594274 119876923 767050921 239969608 119846243 56808836 63797170 858754455 526629290 746803912 27452494 278777918 790687718 39037308 449958707 338182009 60904806 116808045 265900417 831600760 307907488 302685667 667030633 570692305 492364461 100726529 670802587 586254566 631184727 285706002 856898547 316026032 541135595 276209764 283472281 97283094 141912768 817409663 968065382 495220822 551193709 912759235 629486177 602353439 553006958 120475811 209853207 66245207 133529085 805002850 243308537 1180607 147243444 47108277 980565592 539224139 203933923 333163787 320413611 559673172 681481975 467063164 535437779 546636919 690327021 80877193 435599395 181394150 635004426 7346322 970563144 654389148 237473996 612294903 854582420 15957753 139270758 899357702 889638472 8416572 123662531 390823403 400749744 941657150 263152253 886836419 241053723 302452927 147963170 717300017 53595964 526272064 513446085 731105509 438349157 829284650 198345876 506851149 578464705 888801082 280158160 921105182 423057151 145827079 800065325 702752340 722152612 495364068 768369131 323684339 739850939 967674524 798948329 382887581 208262006 744030042 129915059 640058899 80395839 313175293 785045780 898576540 519033931 478511447 324636644 334510887 479523522 147353888 452869134 485794827 653818887 559137228 515545538 500952004 673003543 812311400 770260092 244783552 81367065 610015879 861754281 209409795 717806227 469365994 243949010 882513910 510426798 362851231 194877355 921205464 336287576 806875808 606172647 331593088 958458714 307615309 247387274 993310929 681989815 142539795 279746885 421642199 944429871 10225442 672245344 584785073 861141375 424020828 99823804 20907509 294312195 285484367 766259433 886486579 280685512 702417387 781439739 127203933 87212139 381769397 641491660 236261998 89830017 743635559 372420178 658460140 578601589 188344482 339209202 580951062 96016038 49727493 914676998 851186844 194260006 705769681 51979564 554251828 892762083 506855824 969700828 952487442 856329558 832343501 556994173 658202077 287703363 772028413 947925847 280023389 828450212 965239184 671829027 544662667 584420352 630973509 446934238 288881579 629825047 798310480 820931516 791334783 150645806 597775545 539551086 557908540 382930295 98330465 773503121 337730773 941177852 565225954 706733477 792733798 187011533 475856635 772577334 197216751 135147938 135041333 859960984 563689615 633637458 659253180 768373122 579476514 215280651 310081409 57024557 789076852 494965020 181477600 226081444 492267146 389565599 649638789 31504595 217324092 191364973 229077575 734912906 954595942 767660036 57454606 339870882 53938862 126406365 154030109 921806417 595418006 898971632 584293927 798026466 919381994 380727024 552688445 692380460 948946794 933780325 758924989 55651495 555917448 51759706 537605596 463387619 767716325 385806052 188651429 401586430 164746598 416600711 39189152 527708575 471434891 630967878 100094538 260271250 688700693 104212860 182130130 526865390 830504122 425088470 602498344 11640539 167532566 175916357 411508941 322744883 179101157 832594292 833005660 835377206 224025776 602753636 841622206 852607592 910241234 664797472 877540542 501241975 809491744 114524157 562102033 874694274 71843484 170090885 825988860 318454426 827609472 878009119 366410950 537078528 41783756 78193995 447747114 825326135 370430198 305890174 634969908 993569065 314699490 636612373 577771153 399871681 9478038 439305910 735275243 89581609 931123226 282344019 576421452 896529637 292058066 212997132 417643108 981844480 940117697 316477710 59210047 900064896 254939406 411033883 868645452 961301110 704510200 683667275 884695356 655478795 537976368 526852219 518385636 615817144 269237520 883637634 303785712 925990292 187958606 974420144 317594053 386803512 859372477 205662521 767967176 623670789 561181055 146262419 451939132 277846332 723647004 545347633 801916085 932091018 412050205 893404208 154583878 804461910 125509794 74623793 231116062 671192790 648032317 12434250 890215389 176591319 434591710 238948441 766630305 62685769 569166688 598865831 620570849 329905275 311067363 743385878 970655376 671228416 470881080 718351526 438192885 548654543 436848884 263583781 236411562 30276732 849780506 256697577 718395167 38150388 37100148 456200716 335427567 989315522 275762212 987324695 553866095 520811330 955657357 419173262 932724670 253359688 279023986 127385205 867493885 962670174 72364110 490009450 248861297 386683955 518916429 605123639 596893628 609605912 543585971 536504355 713856505 433173942 944452204 224370940 125957394 304638306 31830062 187527305 51310468 446995553 416067653 133963258 534256708 217847610 863062391 274016359 490805145 665552182 693886974 55682757 849949167 794019122 593450835 351205524 816137958 708550783 581114252 927419043 382236629 349263924 895690654 860766720 82653486 798079665 170210847 305734404 806374461 8279623 119879167 768830366 432266664 777438753 133037612 543440190 35624951 394802152 223922656 893486494 125682284 499253780 370840423 507610118 262314556 454971420 234837574 813081591 98737450 513851709 502045560 46900447 595360975 853417166 507899775 398526824 864586464 735862118 185820645 340028540 605191156 85596226 967295387 641125062 916567987 648203609 944835084 283559864 953852033 967636495 461512110 982153229 581587590 438948520 818931123 792428671 602367849 17968653 925366173 150233580 998460650 224123025 842163484 772717826 384910438 354470868 269049609 467486907 179850985 55871380 630468863 860190460 279986239 881833952 21628449 817217103 752867670 707143815 941320902 260944681 232632402 958116770 664303816 982772213 513361407 168500282 211101952 559730537 650422344 322323066 745035472 66126844 499387830 926471687 291089472 444334675 607817995 655824472 227250510 972850907 603971126 704978497 724106192 154425588 982693952 539319755 792889931 892861452 413016409 252943433 403008359 774837589 113892860 330287880 154590401 924187692 887429087 814321723 644179922 318746831 549337858 726369230 884722141 409108719 939993157 464527548 573007270 499080410 963487029 467533868 323752623 450907613 577278380 674332963 546640445 545915633 300892063 191947914 968518516 144398189 632455873 176740258 864224763 115777 879516902 507181922 909850940 862507011 207842035 631963001 78085063 680733731 790624085 852157796 224939988 729683153 469967218 767061775 902405062 834053323 184998793 671838260 111783738 677952884 765096998 445554443 315770241 440531742 452424690 262271369 807902386 329065326 788631213 512121441 493093605 400971144 132815860 589176844 873460659 752198316 154503439 313746801 890823706 862940186 192079625 333770288 750146374 555940855 971595768 231035418 336177945 848887385 134688896 837245108 863583871 608038240 253132888 862410314 285473653 498714815 880759402 49014836 970859611 534373325 401874653 712444287 610638975 388068939 267094843 37323583 95029 302041074 255163820 489597474 365559801 458967825 716721688 591996695 789630374 422926949 434757388 230146528 39518334 661405648 101759863 787447927 256662538 731212414 264387092 523683752 364704052 176863910 750603575 923750621 54722065 558937995 283995794 661027663 341040724 512070082 920220000 156569275 779287301 813582470 684324668 956577805 711881924 612205560 100934021 346870548 914538902 368122261 81765336 138392215 669710975 919756298 828797784 890809020 280815187 418943726 346637352 257939551 156399875 959977653 977961468 670789409 355332302 208526182 576782571 346014740 242156801 298884993 458997893 656175139 218289756 179121619 55255714 575943611 345316669 798218243 840037271 645122894 306910692 150529355 432027156 98100201 539823798 11171631 76145112 98079127 196570622 601048816 399462610 134272360 519133068 663485010 257995708 990507650 35655659 618771350 489225593 896354985 816307642 724971006 741724654 738727662 607720479 661714386 800837341 918279008 552547098 388591961 145738700 653155822 735390904 50604219 458030989 580782215 891780944 433766783 969652805 587672934 433303987 4407739 227917376 105527350 271766209 902445315 530840572 945117359 655407927 208489211 789635615 21344472 247402625 38202101 263889233 843641813 562567801 976460971 738013575 445340774 687778594 597298736 412656025 959462699 986934394 586583392 548367809 165595285 789669399 810178748 926776268 412874734 625309372 152388570 393451829 802044356 885606166 536642364 344006026 324447577 404633665 848314275 427037266 140255166 311620490 302391596 464831164 286577199 648849103 231579020 788969290 970228010 113608323 540728811 468553534 137691542 764799527 352551509 315358184 644521592 973774509 28204314 551885438 256178268 373147675 635500939 560885981 444284552 424093508 293650504 242984726 377667336 678256932 988436604 943749875 452304604 307549124 378101138 749469652 804673066 525032321 211484173 683359707 777806717 526212227 356021074 841031215 702252079 391937745 575986253 492485079 862839032 363337949 439865235 945040080 301965842 183127067 793849726 74997804 936453910 167585175 651188983 431862240 676417352 363083423 249839304 572364145 876976783 632905790 12856814 486561885 30836780 66619726 930961039 2755259 361179304 744355546 180638377 74854547 450993058 879278489 336223718 499731231 541983208 507261985 639887519 715037910 692903790 915772226 775973804 263733881 795983030 442828676 234113408 869142015 885411046 353757476 879824081 979384526 778765488 319992961 628860634 879613892 7182635 470427983 660758626 527222462 855643971 615809639 194378734 950010408 255597257 786470399 95060339 261790398 401023757 767080342 194210149 321621849 496205654 301377100 716300385 477310664 914090864 109393588 127978055 139847384 305274855 101494779 854737737 203418879 832221833 734429114 249600829 47136404 908330265 485644292 711832462 710908091 531155427 266325339 826937543 81660922 1713343 420785799 507040840 78462083 50104269 276081533 121406727 214310207 899470912 75853968 562745199 190021441 542232323 66744263 317235219 411748306 942718085 980948377 388822540 686802710 361681181 987515414 201888715 14482806 698606114 760291152 792215563 227264475 524861531 680425288 191930114 570619493 557381353 886533776 170591446 393655869 635936804 598888671 329226338 371019861 955094893 805396269 583043935 230766132 498804690 250673513 389038713 637313047 556576365 15480409 323470198 553563715 309119475 895605745 140181019 382927454 695139259 335692636 724440762 293441198 726241098 841385408 559716237 107518816 342197576 589949705 29783190 575865229 11506695 881439111 358885208 633833276 978421086 535880035 431652403 568006397 162250302 405989166 485694376 930727648 540345646 789978889 873909032 243940843 640099194 156226331 479423910 876396329 236172515 534173801 376645871 1954991 163260700 895622913 273699748 455449077 926238364 295019657 325259217 838036892 977900659 819937888 130257853 798464814 450623474 462649737 527515377 829154318 521064287 483404953 39870650 967351962 168711170 561307479 323018023 957076007 221883316 350318455 596156361 576090319 709536288 611457613 977168880 446474616 995124710 495935095 473828528 229159552 727714734 436759647 464473789 719710478 600766721 740328534 280543115 475811249 32059521 201409929 281552846 589366352 567628440 857598059 629472590 787978498 652828010 873495209 967489250 29591195 526617674 925006543 7005098 506644402 340525450 923680687 964352595 139769201 44799792 634458191 345465735 549562379 730488723 382574953 275461322 84963514 75143191 913606228 346895340 263025828 620299719 806688911 435874835 277775828 620566247 674325636 817352686 251226923 336582527 985248405 618460052 672141653 159814509 64858030 269507072 107121923 353760710 245348512 820239384 300885900 465876175 137311965 65488141 31963787 248671050 26319428 174198633 804098354 314159548 927809633 204169679 883803704 246601456 348123474 192499300 580106506 270584009 67564990 380914637 370398661 669966963 710209970 933469635 104976974 145525250 814111738 740137137 474847836 745994455 457921928 157323077 208650221 299139542 535757216 444929997 83355051 315350296 402284041 85507623 499196228 457786000 550145114 174768166 398142333 3472863 983905576 580558691 821358615 630952514 352305725 753054948 934707255 997969273 220502617 558561811 327077584 810166092 491367151 253550303 72271403 74034572 275474127 555440339 380441138 203252033 815220145 495838375 103276272 858546778 849057584 889959049 626569946 876880162 975310901 858091862 710238938 108899953 589064953 840719488 944755671 494631551 891754316 715576558 85077170 107798701 885450161 955295328 79046133 206350522 215615830 22739593 128754844 610739705 190403823 273737386 46220535 799036242 353499081 189894562 426897459 139474133 913526670 120432592 802595049 817780257 846852732 984373017 793681280 76741686 108212548 51360305 400916587 515886976 16289079 501729790 578067583 162663813 203254550 625988974 821566155 463549741 352886133 733847495 139812045 934617168 172161204 337597203 31049208 502523292 546010072 861822713 243102339 578383562 830102840 596793298 537685562 535109249 360356694 776344116 830039669 841592030 574636732 20891609 679939554 692598854 749400471 481906495 960830127 60226744 67397338 250778986 454584416 198878482 904926193 682689459 862948498 646624082 369417416 531489560 390161579 953415997 655058395 184412043 863435588 262791677 680156221 431838082 401238742 573853567 548341530 459359108 538436317 874657603 72477516 28103284 121290281 672400560 747220067 533567403 580138979 364843188 642267315 30586493 447320558 917277176 160794281 941819267 25906876 369962162 378649992 354326733 151629529 769812617 356456034 607880753 432045224 786045817 889000046 383551125 819763996 475519843 372480238 207000271 307676169 356919305 373009233 128501287 664865692 527632825 95561016 103967932 460663008 166596006 836467299 349617638 274042655 150746037 381126891 725064348 64903809 652281519 618533154 825402381 793915699 347016672 760181593 234439938 838927897 659359259 152110098 947770015 249142582 298151150 269614927 510027564 28027033 810900297 539580131 54439976 50021023 69324446 637400805 6099481 698550978 508181698 323749921 468270114 295769863 464330206 499637719 442969897 618941402 177907288 594885734 143242250 137097914 600819262 638724086 549029934 830433985 306836749 242136491 581830957 147012972 204992484 412557148 5996145 242405368 679139002 887582650 191169027 561597663 700189080 218771681 688714317 965435524 8578532 277267813 763437748 948986938 351141874 471175832 775862433 61163432 551529043 240762713 498206829 430086882 920333837 595938689 607375727 838894093 853368890 681910271 652886469 243039031 367254357 679633452 909461218 618456202 688939227 857981303 212135125 154961116 749065152 975460371 77027947 936048270 869395403 162984429 604940862 610802991 365696905 94221293 964176988 288282452 642432971 423296062 734129521 615127991 198575891 393541764 451910548 524838324 117740042 716324589 768430426 253659035 620650866 485937419 600060815 835510649 868906753 475392229 392937810 839808028 937595082 850387252 735459584 111992628 673804269 661447187 253136760 301151319 941870757 140634401 144241450 271515194 862996337 469130833 259784882 514778941 29245782 61808709 278385936 29656393 736611387 780696210 757431111 422002876 488514516 881817986 752995297 755864459 339184628 955966728 812785433 676531723 323594436 980637048 323991005 362655325 595150827 944794653 746903812 756382906 571906531 638526485 517287884 399027742 848407235 752252851 841545890 538019179 623186403 289231490 526954708 497473363 451896429 860125484 266098868 182858483 293047341 543209966 612170304 576833667 932147618 849849746 503852464 500853734 404511586 698551205 580408874 601556451 890389360 374469435 193114663 10982059 224679570 983212159 319089120 212611313 812647623 457056905 619082135 21007269 815896315 422612730 691284045 716984828 90807728 460191810 68678209 189258695 566921878 754922487 466449154 342682389 868789718 709776498 793826742 743898820 705330873 202158209 125885463 929364276 190400883 973287287 571801139 880034556 582685327 73171504 822623185 852019275 940125927 621304784 10292693 806619167 962792990 306678743 629696957 761367184 480862121 77273263 853029014 536715094 430561045 185374203 217271620 624963944 517120378 152476000 692863170 818347543 736288309 395223113 99551650 367113582 351531677 548495635 951061009 115348745 984723384 863204357 956209711 956405233 779588754 222182378 90446329 326288383 861962204 923421379 712250249 346905301 884318295 138992236 331206368 389437188 411577284 791710614 907962911 115385310 921060543 210456529 484301516 442586333 278652528 710547886 778636319 794422821 21737951 577811629 721106230 112126807 208416566 58305549 305105338 15186834 764360188 414006475 581755175 498094948 756564733 671925060 112366733 373719948 579071805 998374310 364710906 664457570 257260218 753445448 855464037 460117675 402116790 322773605 242642724 563132541 573996116 522341362 583230175 410469727 65587990 55094121 924952187 749754840 781731449 249502979 956528510 493213327 195820127 552711840 517812533 698754889 957097831 666589606 796203722 208799011 682974737 253557842 226599648 193542241 500418315 224100451 712166509 967074371 538651964 343489740 392334600 866516630 974017116 512596796 584910409 973048755 679031476 204901806 22124941 431257117 237388953 97342094 204195482 469216057 370666999 540905161 631322265 126458039 560929272 653472821 866151284 47426251 375179958 897879056 273243866 789652292 520689347 499039968 694669471 737243427 508007903 945190140 275762897 264471809 907400546 940127155 918067586 334270423 630718775 640025081 867171275 423167958 341648837 710196595 915861380 15034765 243980023 447060613 965970009 332448610 988511671 491965805 74878288 495969454 845424501 798023312 65247132 721535217 521559897 561333101 847378264 665908170 896769117 544461901 781968593 572888031 442073856 52040207 791802990 2148253 904648271 928198638 989574378 806515037 500934989 106393704 149377693 70327395 582349572 734240481 72737599 191151645 13558528 824209373 957427423 865514088 222963414 799728239 996258079 19156928 482806538 299421793 798027165 124538696 244261933 917038903 272112152 218422602 564113366 572702850 45290555 467928239 198753883 148937979 843345053 376641631 797953689 695009454 22399546 650795527 98210505 871574870 289486648 981409451 842567318 136299521 844966249 635968912 91084373 934647292 307291162 863297066 363974943 587880255 314709673 308052665 163840208 86576770 407696805 203483655 254190438 409778635 6313429 369845669 822306115 684558062 846435094 668243543 256500215 929775538 259446715 898770368 426298008 710542206 169915133 374613045 824837604 49492433 29549260 798010519 24017514 58170372 933683159 172160660 309417310 739620363 356906047 708691688 773680339 708033465 849983966 688518216 604052849 882205458 537218085 861902135 490255954 825126557 597487510 595828990 342637327 332092584 367897403 911477813 316732581 239514817 712212940 603650635 669365648 31001418 146685715 222240701 972201787 111982144 380490675 637814654 908264637 324874382 479242654 297353164 115420289 807499206 739568892 260736151 340186312 864866896 818947444 378841326 375659811 22226247 629114020 481286806 283708072 904590954 274266988 190995045 65249841 522603081 435870314 376919143 221322882 88667591 916457479 478676489 565114043 376417696 558633603 700986114 905790699 25288170 517322594 706167843 74567891 878293925 977832219 365494039 404943231 15766318 491517333 864417459 964631754 506125760 453251475 315543078 380314848 342444500 840198240 577019681 679303629 898977630 278086129 521107567 354861758 800573124 96741495 586895242 672276430 709519095 31031745 940964365 661217017 780832689 973247914 965931451 936092685 438058826 491065441 582762914 254528592 722522290 498062667 80090571 881853339 809129131 287641113 677906373 126080891 812161250 567542141 242565927 948043198 509572033 539767302 63875296 626907979 792404096 315565371 748698928 896872549 315680007 969631120 196553039 486251842 326150097 10647864 359198804 710321153 950209494 944593980 7637516 329498310 326816020 202864272 434743979 799901659 276542668 634787259 268867600 158959021 704000312 964460993 198629278 427959558 507262161 933873940 699238488 809888568 976451077 479387621 286113263 371812302 546920278 618609727 277293219 40732013 566081768 282955033 526292251 985720644 717881054 959399081 369215269 273285140 952489716 487780557 887642871 520259435 601506415 913739581 372036205 356644960 205620444 924708986 14602088 237626716 668881615 374218992 269684458 590567483 313442703 235752381 341172685 49095249 381227398 508483300 816642189 887545484 977220923 217315012 390481324 8484602 950288991 482024057 306647536 382651531 914487055 817655466 28083419 697333631 956422404 876780007 827062801 454028945 389894738 439884508 737184285 530806293 587748182 170255476 34533321 84429813 344566979 60047593 957083768 685365336 957194116 137175889 431340455 183527645 832408146 609304966 571124743 396271197 396428453 627751704 176319641 311893722 164612011 445938868 617166940 160799507 897102501 243563000 600607321 163080755 552374373 758244612 558620792 98821295 507725241 254630031 441519245 757968567 629736520 579148881 942345490 102779000 664300172 373106004 355224784 269613378 484842429 243749343 25583998 415646442 883781217 369002422 525643650 991602893 766943458 328371089 945064259 610323108 250187064 99038053 863312940 753194470 425589220 101138614 606131633 181565415 323687088 484296030 304017303 252992105 185257498 342655065 74264216 348309337 23919528 39136135 619094790 726709898 601386745 375069313 910001426 101853213 775137603 196462304 552003518 989678752 859153817 852724035 520521497 916962840 557836169 920063267 366412395 450075385 6190040 478676700 329178280 413224726 285909149 896077435 860458043 905064479 519850361 592120779 365676552 329725930 467551253 712605243 490794673 70500224 646564987 510162214 778756115 550845950 657922523 117443882 28161897 235409320 374298505 731179738 394104112 367035181 212978936 350475751 673675735 728039693 620255614 840290312 2363740 13011283 439812239 565196805 213440036 682556000 295335243 564793054 953641501 483092460 692447906 641492544 483477009 565592689 347986172 356847455 983219506 866382928 522785824 433613146 82155967 682875502 249449758 648001647 26208189 901489988 865015950 729956955 391381812 554197240 305154117 832037547 448562551 174925708 548204512 272275463 575426600 670900870 429434334 190863720 804548908 52769647 919516167 725800870 91086710 678676519 636384157 159440101 668672182 967039973 189671310 631908632 32049001 738446640 923806272 229395696 564395799 18881612 39935050 130189628 102128047 236493037 722428602 204906322 131856191 419956479 413622996 147341100 324383204 318029198 162436818 413658142 282702531 669234183 849398407 712380644 126570234 294682360 390183007 131891313 874447963 243904380 242851909 611050024 544275610 233418585 526147769 426111917 749649774 44029857 507151701 596446319 191245275 856286370 634137987 538341600 579708140 308250556 948760909 724296578 313786256 897442675 278481106 965477302 710203793 71899535 571551937 302922907 66988918 10303414 288382572 421399629 477414140 977052388 238500432 579597041 123554375 866225304 608781095 342840943 915643765 989891860 474942427 946760201 698946526 31370665 489023753 264076081 740063433 887855901 978080174 461662998 513262006 437315722 438222916 31395498 206006992 40192058 325856469 243068480 212267847 737692133 226239156 512033048 583829050 760656962 166518101 573240797 145440527 596348809 306613510 557636351 105804503 678180273 708114903 699964598 268482165 181210183 208139733 341312326 401153407 425030716 75069150 75884178 753638034 2673435 964430734 377671627 250497659 126199349 920331151 308003563 415651124 739927058 905661041 14514791 805244395 217486802 518630974 612796887 918680033 865221579 331047219 704552343 925675366 248109965 923879403 979573890 412291474 816558080 197682455 551466104 475794826 803395196 50411433 99327189 553359661 17705821 280829529 241782605 60451558 339983082 163646926 717181915 521668003 599489113 550610559 538755786 105813925 357705117 210709935 346454612 474631310 538984991 338645090 441677984 407382668 506443176 52424204 159998219 446386385 332788947 890113726 426248898 276809036 788756024 768367604 740928021 39899683 800386731 296686677 932777064 621824874 708109317 641254019 254822262 15158451 245114698 418336428 876628459 454415206 69169925 851393345 579817794 787105291 877889112 649776298 8914392 261473260 523653448 648583665 79417044 570833674 159990945 193988771 857264626 235992741 908559159 402563177 190199756 435937772 398124456 431264152 930596858 434762446 899630101 825542855 941311137 7215092 819249569 119573449 873428161 405540544 932277376 735367726 721985815 336950641 254593544 708590803 41919574 353734329 158817743 277501010 245313352 371817140 188916158 229346718 102208688 308132023 14032182 715129277 249970345 950907355 843073701 854061716 568682922 906405357 788690336 396426915 210305602 536690309 271991045 777785771 482963974 612873378 350609417 881715245 596968574 977289681 558024646 466219408 680156461 982683323 161132817 836842910 846033691 763335522 195871003 456788437 585774162 108296136 725910855 767512131 310153216 413892659 11301806 687119000 358750896 409652935 96025673 153911780 156322941 797854269 899790729 37724756 285659945 108067409 704360783 887784545 376580353 742751129 783698124 944868653 627951111 61970950 79655677 753056471 853613889 780874339 905738433 535751578 478415568 393819982 83767608 160655058 148920952 558939183 181228962 664004589 360802450 463753992 796317314 638015355 39994347 636841435 538064445 221337110 549080973 872399607 345674112 458241725 726312651 836942769 365107230 891018049 903598443 87296054 905017221 318013310 522885272 545787109 643826887 674016151 96269335 510273910 71900818 91197064 729760516 937184435 117038621 202433694 123733759 568142670 696270917 930696833 677048397 187039060 890054983 335242644 359432394 414696429 736765689 479263431 243098165 507402549 856183059 35627744 867000761 202384409 941123758 98935850 90641282 80129056 807522196 340608384 396419451 810293219 577742876 320281682 303512681 474100087 700129646 429380188 310349834 925940682 834020121 994808861 8090216 958751056 383388939 957002249 485706226 897341585 479280563 545417912 275166759 125702866 827407386 483883398 440640126 308367773 974089686 505514075 636823880 484145001 760503851 454025780 700344876 713129269 417152691 217834561 518413979 532693616 630064237 152344672 630651133 896366922 523049661 86838133 98028809 801844134 546236788 402222645 565013830 361829862 298089524 889688543 54936983 309009253 916482315 459541676 143642985 433776576 944742473 981423838 571757980 297116401 509819619 821368888 986692688 779720549 369496370 793102802 492149118 34677509 901807486 601072895 487674623 332467278 336787049 547414142 473754681 173865702 475744034 81387068 405402219 625529242 738662925 340764568 169834377 486378665 47064481 277375703 541725815 33450143 343526228 762597989 366596150 779144194 700738714 950600278 702002311 612297117 989432313 21291081 910802142 498625575 834751555 985736807 327550492 941484956 405884373 748515342 22893056 187733891 888907938 813602144 197828696 266811330 621006086 351085325 758147779 505527416 310376000 425912338 553083534 316964702 309440759 907994105 725501786 719436106 457896280 696557193 206573621 853670121 40608708 169344219 440567419 841937492 391089802 451971609 863203404 828078670 778662923 37683058 499289899 615545400 999518227 410772467 520094036 35704272 499955632 111828231 610927986 450845823 718281413 878016771 325981749 399865122 278561276 200086345 208822219 639226122 684733962 977158375 154684421 827173403 259628872 889552204 376663700 589095964 445201139 102224534 551957034 698105398 585246601 187727840 512181417 419284556 15316227 835488581 976545258 253361244 398916702 500980322 397070061 284778765 285720189 152791568 443099846 6469620 8614899 588452022 879615125 21362321 489941269 931538651 22505540 596255017 804339593 151011438 36598421 971995811 514844224 652539464 470235199 590349158 969193552 853802641 132980101 738875326 536969432 312334751 394564575 424782288 536699550 181588417 368709886 428804547 941720433 359780013 431089760 725454157 210461403 204752236 25368451 336988167 869104906 242783475 666445621 134400006 176552708 19437294 26338427 628374325 934148643 397865473 945063341 105578766 896764372 714900519 875784689 830090200 850574501 644874063 213725809 165395347 111548159 25672496 431797943 723046737 198789761 832446575 324426284 768646699 347064015 511886721 462367522 972966157 824059297 652463679 585248977 38280787 863490977 830854 826468492 807050180 389413979 596386699 970453306 172111114 305511898 28435601 542182720 273707406 691858791 450119461 982884069 492525838 609881077 441143104 215656004 603836464 212370121 229064807 582248057 860983691 279234707 301462561 384570053 350800405 406366291 321888671 724399848 752215153 119291415 479276344 293811258 412304195 949866495 343282445 360455448 790164819 728814666 108906586 86464439 272229193 949388590 761861023 674117062 32116158 457883795 17718722 754447999 310465750 675581923 74675133 234180280 406064544 3847511 22377124 491590482 629439650 716613751 884244472 554258862 734901356 334590345 49830139 101033022 101714962 455500099 672820749 688480427 561498138 5157536 119227354 626891298 322607620 955964574 687291418 774662777 300961645 858449376 395058575 168668360 552593320 480993442 983716889 633980280 706660096 4649814 986763647 21284889 505218685 167561523 136444014 586680383 788627366 525124771 896719817 838857664 440817865 228687709 820846441 134858539 966687329 498763488 89758890 111829347 961427820 85144629 530531290 872806239 571197669 116703882 293949465 199212673 26268695 387076081 576756086 648466222 168560859 823816008 775612515 776060066 442005881 805620878 250436905 36758831 868230094 936565722 575970580 879436891 312071345 244181845 601324377 22854999 42029935 279675854 9365132 913015104 983445866 987955027 737584614 610216327 401763766 965587920 188359516 555326715 551139324 744697518 184901589 874191312 35165949 271690987 581078553 688494333 750158674 300776224 756872456 778931060 529515842 812945310 750022495 113095644 943063221 745175708 436030360 482448970 175004309 613817301 519931163 929079778 745514964 906910247 135009420 115412805 287767182 749906425 40946493 704924161 655636499 848922768 75402921 139243890 463896401 588477336 782497670 600853743 182576908 435919185 619554345 580648396 829868961 116563795 221602064 456989034 471773369 286283494 331145246 129594036 555721351 153135450 38860185 139406681 230922980 45976461 969884422 186474198 764576706 374967503 760418202 671694947 54483593 161188930 277408885 947783025 301502048 976893560 185772606 947365436 192282782 246287701 926114976 197599983 411494570 897252325 809731741 124365413 142021741 863795527 179811391 133216065 850515107 789610770 251725535 655616542 933577535 408839895 119322342 510830000 449591135 501633747 331153059 585579919 394129777 789934204 457039206 538199357 402299667 350845780 310413117 890951349 191452715 803317924 975348282 129601869 451259126 758320486 359165934 979584005 323634217 24947514 924350201 588454830 806204205 298215728 235640939 601285538 294330799 514679941 353020511 443757905 557930455 955605462 171412680 731054075 173367965 210930351 832015426 813462181 744289244 98687242 808475168 583314455 526177161 150879967 281177312 20268395 500356341 638340331 246702255 84164724 475297532 446347233 36599590 724794405 407379510 192461798 962445770 440341276 754907803 161956451 948176693 239965504 797924381 936367873 435502902 676642419 682697664 900385991 241464728 503707790 215241533 163991452 830781956 853147377 663499405 118533723 106486158 349607796 46922144 174115972 90473095 476543103 51834570 952990357 925067834 98405367 617056813 593959536 47093070 30715696 649557787 981751891 225350169 718663797 325214333 245729079 233622699 865959519 205959257 996753683 983828700 201893130 350257831 49328546 562742939 459796212 388191944 399610290 174254184 369187702 900140781 588386265 382786424 905901711 546171134 570044900 951579489 811510138 926000869 423395275 756417755 249041290 832015970 305446545 270238883 302227132 659208912 569318704 273408361 947872530 800321740 436021594 34301230 793431704 616110147 212344156 243319085 918831112 13393665 894055881 530193768 740166768 935298360 376645486 70256390 189006670 753574174 119517608 656045497 467002086 402627154 144022946 794204237 32553033 314887705 979635433 148381311 810870036 326540121 946014849 538503106 379083442 784155390 687733040 246556749 255776397 745504610 567934586 705316645 969363714 924930371 249663641 576696089 172432279 875881640 756603556 680926777 619504514 588873987 595116702 711368409 600579334 524684322 349902511 149721447 885857055 826836970 948962789 900001842 100713814 954008184 954687273 910972141 265895947 860859504 410560821 89738224 720698383 942486434 742161167 474676850 79516406 298276320 373267473 465301839 359833223 397855244 491957353 480509575 432323711 329457202 982386678 925219058 459422958 227437937 229411533 282244833 156584849 789733658 327491756 686931524 616668557 576949276 664013169 680187486 289586394 3906230 75006504 867259134 228164980 893194892 326492945 791022740 619650499 53949365 864753376 919810696 249091278 334227958 250970520 805413861 463419640 449983411 629123674 977878383 53812622 444756914 431046 547809212 168104213 303949717 431457810 260652023 985076452 436008282 34888273 893210606 316309225 648950120 302417658 643010120 988194251 114093599 809252242 271401682 676830080 592958109 941842717 537861794 977755847 217883172 33013668 611183990 488990886 488840348 490697568 521730189 477396382 44147390 581947334 111503391 974552391 937619541 56119085 591112198 735957463 999176134 801516147 320073497 196113654 241051990 802943932 299510212 957397210 697896416 354178613 826605501 144799023 294074431 629001376 29244253 884246452 136412627 770765310 587107753 990405441 980973165 715419217 550062058 970401846 173041124 525334215 54757845 457457005 134906737 603455179 925279922 891294468 142856344 767401395 362986133 184243093 146150128 765018171 147110032 743657565 927358718 408167228 100019379 29984445 672835044 190454032 84537175 700642954 20874497 236567118 21675589 799308126 348892338 702436816 668361527 632753814 743133798 466015145 170665553 110783340 998145432 839635183 457520337 304170368 983463942 670230803 96762674 541992921 239777534 582183288 923901958 939510211 826268581 998716956 263799977 590545484 934901048 556291143 379991856 154424929 214084516 640507550 755498128 294664221 825085150 376362993 967888925 66188899 761515940 496725549 592721661 634936819 725495811 336125718 348221147 520141258 148449508 821349284 471106032 644030025 146906494 443812093 596254839 610623557 994229503 448018783 664191553 957565596 262968012 839514310 896049503 297363202 52574651 62224721 827530898 315932413 205350597 388254465 831116774 494099610 516740732 823235652 316605199 824788935 818416711 118577101 339420135 41900014 702310326 499785503 858592943 387296716 397547447 936595422 737312415 448823841 846620328 882889021 203686674 573065704 185892156 45824502 517663050 172732718 832783774 421386901 845077112 208552173 548794646 300453624 881425980 379141486 932668103 21390166 903886139 895237638 151660642 594149760 209288537 408890025 346901795 663296279 2031178 26343255 928031642 871535515 284816393 270859527 565462938 830926716 472734759 475688559 237360067 402690040 604511877 971001719 167470398 498475414 261804596 192480962 42923689 361191721 307597802 20488296 795994128 715754384 905408997 113017322 732112385 457981820 262615488 82125559 116160814 251276127 838885545 525058708 120866870 907693653 243059754 164788612 385458604 176848896 383444833 732628080 916157034 692666570 331497548 841005296 326324682 16906092 140362562 768812434 16506234 104031943 66782600 158671487 322287452 901802505 658730548 167431629 575348908 421715995 326006772 67132877 981156558 893615461 39447125 879478660 650530372 900644331 520395388 244037621 994142442 525905935 527472898 245080366 832340011 594307731 463579157 282643558 716505808 962811989 52117843 342186337 545472090 367845238 119576311 680402069 950813050 70395483 838187942 125908643 636840321 651588418 623472884 342625261 854434684 963719376 559985789 546338815 602271441 124378816 874575073 534903830 529879537 465555257 864818416 858737963 872595674 894102964 14797165 664763636 70977679 407364741 963486750 151995029 46905127 304590333 715105666 965078134 222182931 227164146 622581825 707847997 720035923 948655106 983037135 673377322 477712873 896008692 330458781 983766005 811313653 274134968 740615878 365038120 206197161 754666899 752546187 758180160 868230783 555961979 342820241 128049676 877281528 834453376 173820732 790591640 244481551 71921618 690659120 437661067 103561681 615375613 191168178 128974699 59476534 113329980 393778380 621086020 297135357 585759751 224424849 611171638 236302641 840094029 813052079 840481451 623694951 383782923 898971727 209589000 757774312 318289984 678458205 531330908 961859036 552646086 494932928 917942017 785146111 180249649 741085719 230223535 936632414 642127535 250151710 748237967 791102990 769119412 208221746 686440637 945359485 471904815 560203484 129855748 951131032 783065613 497027943 287397312 431488048 372399390 208803572 406055490 189067474 240732312 668869519 835239539 21966474 585035961 113460819 625867586 915844407 246113750 356668908 753283996 161073916 435023643 12041275 145395442 533858302 69385118 895612703 344132733 496076146 918041485 469966550 973477262 759580094 585263249 367575757 130435655 510421948 985356451 528645031 136450144 225501752 924429943 507218935 114182698 624661889 33018180 708065345 751290854 937070596 2645736 504109568 381472398 501483617 654328091 437510804 50325421 873444638 809920777 951709292 121832863 849118212 238088371 393716048 295976419 480374922 695395601 736546411 248577337 937265509 470816817 488312919 763262498 701458773 953969437 467437896 950012155 664209000 305590506 670956036 437473620 605107407 510405018 704620698 98951711 103656680 42337078 67980108 841693337 995965467 243451388 459515144 266098386 68161094 691202362 33695724 567430059 785368568 85027486 212275676 777793614 904263441 182517759 825311379 850786104 823006162 813635767 330900428 786694582 675340537 159691687 419097775 365571501 797994391 638820012 999599818 428207203 96917194 997142904 519006736 342970298 677591966 554184030 507812145 293178932 190191715 99993948 208032772 737164676 724279184 794007826 588084007 790923666 447159035 680206569 534400023 553653171 323695553 995298653 695592265 781355642 317452488 426856683 979486082 890330538 200734358 28749432 835513502 901298145 815562657 134048077 738080133 207213486 381591480 309464072 482714364 682359708 592809993 982404934 732997370 439483696 411633218 24858289 688219518 979432859 911424667 522116327 850010823 871640160 589667714 410973921 947330181 784881875 168784873 54144440 328472187 383132712 511306165 517688051 855919041 861628359 61724215 522112846 965696166 440617024 216081984 473314303 443222393 654102161 721667525 274968349 86017918 217665267 250933189 712869891 264098025 155737805 576414675 527342472 574105311 897626481 70407530 190443509 838831800 499668685 284140363 337198309 333339315 187169601 57047309 359618648 657523189 146588171 730420846 563147273 530045462 828817121 622508820 574398774 798957995 877150972 815562860 242101754 869647946 319785551 346484906 88534336 554402065 866121227 510661535 762011420 121483812 155665674 531507100 566307756 854618662 627180325 510690421 543172878 139736806 135980322 99376953 35589262 501572826 772539331 858948506 223911549 729864298 756318071 525863855 40201446 444094650 340823113 363710307 87986086 399191689 291736348 293223583 334872846 889568346 548613946 894148894 60376342 35433911 832732168 856270240 431145402 375564315 788489787 376562543 157114159 223235518 888538200 817143385 319552011 258332219 893000372 200365040 660742098 73778959 214193870 857788271 400689870 930156930 926971685 511531294 779567481 81993146 115425616 590196624 87641631 707058042 367272449 765174625 577229120 74718368 70113961 671350177 542874339 861475550 943049774 870186109 968352922 706695451 19687495 380511998 567441391 61056588 883440974 696748989 441213373 20967053 510671922 631746423 590935921 548177080 190347817 184633305 888904666 153570505 419025372 496463946 269518955 725863575 150753630 342541719 345232294 274415608 224328477 5567032 897024440 749904131 629380029 780657255 573578736 674559132 365150885 244698211 549833364 283703769 870759232 258025380 158014394 523967329 494154961 591142915 513451056 748143281 387920191 523326196 593834390 502148193 566697282 105164561 552005513 180324935 451026414 49387305 622598946 821048844 631510862 677338744 387212921 866562453 521820528 547388830 608665263 792616444 482410269 294526111 606975962 318585265 1944526 773457370 625503347 311580273 794419216 292457353 368622106 136604317 890658742 398955305 253952444 789966231 235375681 70519717 414487201 263369704 395582098 495588516 715675055 378020801 723631305 142947541 352066806 449435065 248578903 544996854 818756436 149861300 137837515 727028285 164366752 166190854 383476621 422161535 748285401 354926693 538706915 473601859 134290961 274485146 364649300 823403867 772606110 417337591 943417388 868818385 796257619 846586063 385987911 309914434 446735445 708929156 789401437 822195643 332590511 692339762 243210248 937554904 771014932 346070170 866589363 396208853 347469573 61866120 595848772 973382369 954771485 180796208 579745620 492415506 741514809 883707852 108973438 901135619 955595016 163151117 284852430 965120639 430025372 749222484 412346303 332787102 320417676 653709048 411366409 926654539 237200543 395372969 723357136 633266773 541767960 73048685 211725820 245397579 481070439 872975837 587413177 476745052 628200913 432745655 535753383 822865855 620803598 791529893 490827986 337802831 728269568 95750821 853263188 546749049 305831362 728643951 592041403 556214166 63439280 49498064 547803853 829942561 116497730 543505969 863048665 385436361 207270000 504019431 642129286 363734850 661507177 822753950 460807075 360193921 254982266 26555854 825569482 617264729 822441537 380991928 732975453 720310802 347059888 770818499 592416631 690881211 793903775 501459633 610321526 25231811 274524443 479383682 818417411 216759181 235470953 525707718 777561427 812230929 261735605 197938909 981524517 121167683 337368431 213754428 466832096 872097528 644905468 738618886 640783397 681552083 631758784 65265286 198850690 64239842 993174287 560787485 191421085 960866047 45894602 640346019 49199942 829963386 648816570 600718477 170738907 817816379 729025634 417812892 454478317 167428720 849034656 352727594 34888473 480854402 806309023 246078623 868504112 373990390 909424890 152033334 314150655 424584152 592294246 864471585 507379613 968349169 409157159 505661639 255198065 893600027 188849551 36524985 266274417 381251699 553987050 161312512 264305824 467139448 441091064 833581774 143859139 521373936 930907632 950575117 795595090 96564979 680696171 384339397 732993901 455891487 898744428 792864897 993067446 107304973 309409473 869355174 682831779 525191215 126188137 283275608 247114577 103791936 716779556 582429781 10724474 293800872 683427747 969943708 871826939 128446675 780919865 295173050 635161303 686266764 431151327 80317348 878107428 598459005 49941817 450616256 969055569 563411755 674126001 389602276 617697505 975310212 80121075 119052078 912419818 705757451 538164781 901634296 356584635 761061857 96571754 265337740 380646738 446737727 443017983 536846238 752365200 126681377 116383022 36937437 120509824 727683676 415280279 641270507 157625976 28488230 839337338 877634873 731170951 827088146 197174828 179774117 623380232 126516850 648028631 291467046 296275360 880943577 989033689 321383045 62172719 434789626 159122984 69170387 593514951 89904260 769557248 438235013 431175007 499055741 807881963 295319648 184821537 273028748 481181658 130153743 949886100 104775054 303395713 538564751 861173621 914742931 96127669 315764366 254846312 428748007 980118722 266864839 537418096 316646433 871562696 150252426 540070711 492148054 665790275 271068637 331788171 732704128 169920897 733423507 300589402 876449297 587187258 69660973 931902900 554962696 392878979 382343063 7806941 222449922 119959974 864885310 234279118 948966840 427368447 259794988 959578824 833266906 850064713 902092339 553489832 941830304 905655299 381719909 570059472 532656722 632581285 828827145 179483538 533012593 658501598 252782110 431802799 597748004 99198790 533622726 837988829 652149659 99776981 998861189 826525067 46363196 665322132 915782847 11663057 511032587 326680185 342006848 308840065 532776846 488503993 437541558 12975553 59077256 384278908 595281709 743596859 27897199 699547063 416629813 434009093 977801639 13477161 67780666 57111084 865038059 972403070 678353588 915868841 145015856 521609987 107272366 99978007 179259784 126370771 582284191 889025208 60794372 851878283 161888606 269700939 24952396 76038299 933587826 45404638 770641342 607813307 523805309 43105089 206470928 633834084 510149995 679606137 1840956 572041879 17080363 416757685 88274714 265116453 484096657 996519296 566477406 508072775 67515365 657609842 116162873 357843819 920629800 364448110 786718391 39526452 353545155 204533786 651019344 893167012 619080155 304390765 214228055 380999830 669879962 126356231 477387216 536488510 21706013 477302681 56599138 206971869 293392697 298782086 727509178 610769316 754591486 827323713 689417294 512991434 629055077 979105773 930480332 452890336 589891657 887225185 227970716 579245319 547977667 891700489 430570412 255908946 957937522 532946570 815665638 611458341 661682596 407134280 349540869 68716445 609788425 362743305 43260406 522664500 544763446 416205882 122087236 886872645 998123085 125346687 884918419 547710347 566551606 547575553 351478579 954182944 272053933 816768190 197166911 283578759 937967211 157769097 413479367 619024836 929397317 958000741 471200712 554262200 755247926 537968894 712118699 914353471 638294933 760463486 391580513 361028205 480140944 758310582 995061149 365465475 5320084 698150766 396015484 606979651 360114283 9710122 797372909 414138925 702510721 491817730 816122050 529127966 979680108 434292413 232470007 785823548 172952185 883875022 789395174 22159603 375024059 218071744 38516458 128871109 545677553 583101611 571408623 93219099 654602772 651845817 698377622 26900528 283489074 504772666 690686307 274997140 267743801 84799114 504062425 824076089 139306956 961735030 554079888 894693122 147079792 526294038 575345285 743746844 804748686 391750147 7944780 366195508 5613140 539507958 366656935 958741737 759752790 516615121 930095372 844278196 599422317 121267390 443182008 669380205 917637741