12
696749898 611322475 954355232 858085947 278040376 704285946 76638730 361208205 442518768 181777021 76404172 180276908 572679807 172980 231516847 800753982 76800155 834547326 440943230 168342289 775387082 511981548 184590830 290361135 882668527 674455415 666720988 671288117 223893874 702576413 253484584 920643772 313898881 60356175 631246079 444455623 617158487 560401175 805663829 59677248 742178196 734584367 92470522 167374362 587273714 176503735 968128344 664073869 11051055 261587933 832416159 638954503 773569482 17006982 929315638 508754368 691462398 596036619 32558845 767872638 151129391 138559795 541032769 465028273 198915970 172278841 909483896 816074457 732680016 567664084 728268071 327374571 154764811 673254959 494748934 742038525 849758695 315393637 406112387 860809750 576981571 91044905 352280612 203067412 108051888 281596243 711821780 652030652 730149228 596896991 419903283 881278620 735456786 960936052 198823252 934372756 985731260 108307141 602963572 570927635 528487592 183748002 898302207 683252403 857002962 393051134 277807287 559278016 708444771 683919674 272604125 137942701 774964580 624884737 341010113 735532834 906480980 52831887 387563479 489146567 502245244 659983128 370425180 237702024 473435539 569248432 24591139 459166792 530071940 480071078 30094421 911075898 663819080 780912994 446844660 373338401 26480487 724651947 932616417 734925258 261087980 57736901 872867960 36052553 682621638 66394432 624101753 441618977 119226319 11665225 930765545 473987930 524164719 153707084 711689954 997600259 722955517 588797459 309283410 105543816 68868530 191894197 16619707 585203977 972807191 315980733 958542378 999287678 40632673 743675155 586729296 301720653 801412056 312113615 190289573 336550054 378508047 814391326 778169031 350250733 678572918 708934569 824238663 55253996 862641654 388444976 52854248 438113530 977242435 362137659 396173712 46110959 554031856 265309785 483831302 379355407 581290518 294890039 378643078 621923191 38565187 965372374 776160210 692493610 130002348 966449783 29043657 508510396 633357469 659729054 858761129 164446746 221179983 682999785 219700742 83821630 71444754 125071357 374451526 901203555 487209016 770625238 799830880 893757238 35935016 283662175 273112638 469741900 578552215 504272083 91665084 469633768 322160816 720341660 14643737 452163165 539307803 896203767 960673561 25181631 555932815 819434683 189628377 777112798 354950827 261845485 713450794 278911947 386916842 940418686 32631861 874125858 563560283 832462742 620399456 452011665 116124910 893512094 921753565 547193491 250300536 865935015 869343626 572461353 586276668 883987363 24624511 125584464 632707490 985298072 3282461 41156664 657249114 192910838 818269462 864716307 454756324 384236615 143628247 841673166 177171660 28776474 568315384 740731943 861239216 41231199 192743601 829880493 934743293 114497159 229590343 37560189 832948540 98933962 610021542 271741567 835437692 634646053 249842398 468145175 472460484 253124859 509301839 982225964 446035698 180087660 846942264 753308388 416840641 843086877 447497913 594012301 871863351 15813290 334744237 585618927 57044489 380004204 415499413 844304149 347017729 645089756 881864338 179966262 596540085 344402239 451707829 431977770 979048292 701550227 752639311 304025135 954675087 114457509 138767458 253227144 294545169 985709722 6535525 711385810 681312958 306549804 157914470 405692668 174879461 492658707 991311595 84440316 872662911 259327367 928744465 72196999 756933490 663125162 252163261 353473568 7527394 556387456 637967704 839092052 110454043 390607008 995633553 65129123 505064517 134401004 170872633 652126052 972627092 29924524 216028221 506456409 336474328 373942691 912149078 511353789 866601398 755977032 595794106 591780668 867820766 377054930 663977667 624754249 892696459 768657294 830744183 752740219 325044743 468711880 444348631 435498786 711835254 439982177 353144275 69416130 426899548 376533274 721542182 399526633 406457798 937570403 905983043 595448493 311513087 670648480 106802275 30630844 279141871 555112747 474927878 146962630 784684044 138905538 624233245 677380496 760079198 307493787 282637074 85123934 776205667 726985705 373139087 340557280 19484242 578799728 409973410 446383790 955333003 131515585 845910423 214307160 69085981 604409825 809755653 233115434 127574664 769074295 116262644 259232902 176703401 591190522 258711898 961387445 582612426 882945144 491284300 342691617 42955290 773921375 280331918 819160958 500907073 505987371 12234597 520391315 84787092 422208008 966775105 40120088 553723593 665201888 106943615 475325941 122128072 916699268 560957741 102219103 685773556 677220386 361452005 862476958 268410901 620163903 676380762 851023328 355625406 167665056 46231304 398580697 941586431 179079588 70258014 295009863 685066959 82492611 667917545 769854052 504700619 487209009 662490506 58424206 4927256 769434121 386266513 127055329 538649749 947224254 229274432 76939664 476960999 590726437 939416622 745371901 63406699 468313744 448911588 419032106 635978800 347659258 817612803 430081590 526738847 887870817 577607819 211805799 970363428 245525357 834176217 475064041 732734367 349183083 386004613 737661623 118617197 624787492 717233318 509783312 424528105 946507750 586722977 901489105 389750546 378655958 499377365 453157246 846969702 948288953 872189352 335464861 148464570 542318514 765546451 675203417 430189324 195670630 887009217 253069111 441195987 573701793 728133152 26446713 922884876 966654131 616624703 894018440 591441616 333858014 403801745 15969715 132882124 990524722 769975186 375149036 221697040 269352544 828306282 68666735 70157856 553011993 404131597 218622426 95330500 22194407 893825844 378036190 217865037 633351420 631105302 511577391 59569572 211754813 538024104 982454449 30925304 7165166 876472882 622366920 341023181 132790986 490853001 326421671 975832075 113344546 701570707 197529108 382697090 382393349 118712209 305371312 935405342 522843806 523993739 883252209 397554580 270335942 113804758 615419617 756203728 597426426 126997001 815773300 809181240 517537472 798227742 840106544 524702638 527216983 314989823 718242185 512524336 658359191 44663849 488356404 771703737 746234557 538401878 6917187 128627899 657114087 312288499 916549607 32474253 836282238 652318175 430028833 959134546 618639300 45448443 715338267 216065719 24961811 383627927 877763325 395015649 34372028 570386228 772234653 561589012 885376052 490476832 74113341 396251602 387657047 414986111 167955332 133891597 953387989 174872519 115035862 463018435 487161019 884101836 495492688 175959616 388936370 925521521 135094156 7575663 823486331 702948789 76157749 700964508 86576709 953921074 95980150 120948738 376823662 720731169 535054116 114716073 63724360 461683823 510967675 451381408 729186300 678923007 437789371 535090648 706311893 405341600 998109083 45989271 141959795 493601765 221948887 530896165 271639645 209559409 390988195 95125969 765024565 319662310 796090477 704117640 126099743 744586993 677582744 502923405 317834522 65153219 617639478 381558882 526837042 128607146 832940290 108539701 660046520 270729655 643630349 366358406 676071255 641739426 412347677 818031050 987857557 486812930 201443574 259497195 696372340 444948135 207139531 313913264 764610445 3230001 18030897 890710189 600333361 695613642 393633587 918167883 760766861 11273059 152243124 140120263 992396578 985183415 248659964 652443091 108429429 892290314 871317863 784500684 386546099 136181899 455048093 226920015 622994830 509008033 486417210 171883529 953956169 693556741 485796793 718566607 549303109 503827690 461793155 2152829 51957691 855426743 772837078 665240919 719216168 925080202 805361182 564129105 910263610 906537512 69088556 18693032 651344185 940406419 655710082 37890277 76588312 963274541 117326658 699583142 472282568 603743869 871466671 278755096 149816969 209779823 997321703 551636444 713607513 311631218 553789273 618081571 19574320 179142710 283322483 738790488 104222906 941200031 155435952 867002882 847737536 224524508 738212281 351598081 164930921 246438722 242004724 94035599 209713257 359331383 793618741 534512191 963075252 517601771 813267287 965408587 727381594 663105349 517045025 293505466 974736567 923350664 911587037 994310887 102493368 47425879 585617734 59232640 988625910 741053687 926235522 688879806 965578195 664447796 40477880 130509109 910886519 134998970 77061074 973116142 494330353 870679815 507628326 309921964 240797945 173411972 275330545 820695905 836517321 644891936 114201365 811253882 568242593 878304768 658081128 523252327 778247014 243698856 582484967 619389283 984752543 508720483 160785448 802847097 25684638 53779694 785872573 789087523 188778665 862933647 762203658 683109018 586129822 122348343 993030983 826927767 295760315 120877887 500140032 132277630 765769823 466857763 796047878 186528775 197678890 306645365 709781103 975925904 550344221 292266063 595315181 387613123 653502912 756100629 42976580 679187551 809880324 828849153 320791433 998658989 691782793 82995085 534284366 130428974 57859794 527315342 957356742 206136476 648193229 310013133 190930472 266479411 776870896 986978350 453008187 974549786 146140074 162789283 950475684 696484296 307571712 398307224 936613785 961074625 6924212 979590365 492778535 669320902 808439511 813569968 520496250 352738664 749081419 54780610 483167638 806941214 434612318 293040739 13077683 82805541 603053872 56524521 201801318 232441127 43502864 654809505 206990907 42159304 817598788 9982950 738643600 125170494 260806540 527773745 938761485 267730752 507364103 431540013 937051655 168319974 97626340 310064264 373575004 846707760 364844874 856742642 506165333 799457193 2299741 371759382 734779100 457869979 428283903 936580418 690311107 324303133 443906283 897302014 366462437 114021430 759801330 105106031 91708290 20607863 485396142 30469768 140854981 992760245 314526147 77906629 13596578 412152488 240487260 387171582 258860241 605332134 96430584 765025574 257305686 98730325 136784949 844601152 409116670 417585218 633697930 99427770 741888351 77604206 849246150 108350781 191625636 609047473 65973178 283333927 482171702 551369320 166320061 623026684 396645925 480846209 553449679 262758869 892998697 793936939 649930452 4375297 251785433 598877402 769400871 509091119 550124093 758702186 206208631 959240763 28803763 839906561 58668527 770692114 917510767 760431043 879042895 961652769 221994876 797532440 97503055 704166578 201418119 263823117 327193255 598064044 744669326 880642935 860822914 637668016 527096233 363269725 642043313 778881666 962147127 263960543 140489145 364787579 875179095 346697776 324028335 903982858 186604330 235213228 674674965 956631463 995644272 406234219 918284225 70155507 56283018 15787274 774322085 257701138 132126757 101515334 855765182 876796083 834674635 569104455 366980458 214287227 784890546 9023764 993168894 599554032 125500673 133658032 964341611 679761 480355808 140886306 757178985 519476504 376099534 284370309 476107960 224260165 690604528 246908544 294415672 746887547 115212184 68737751 4588678 247338941 22769451 712870226 124135017 709960452 134491041 343631841 924247679 919381587 205171971 769932932 371451979 330672644 903590964 335793583 183868771 236463131 476679889 941047756 755939635 705295790 77934424 84563954 929555955 768538953 183988865 76487987 367942859 299201049 997742111 225047903 399056357 873027928 790434495 375707740 435504739 924925536 719339582 212268777 696823483 924511553 982201710 68275455 107700557 738309033 256585404 291569328 974772165 585781660 85133444 583228159 291077443 163067868 520308480 73149757 784123187 704297345 2154110 4582405 3498387 999896221 229630308 255071110 872924142 20064797 630778851 160945240 797506699 350118426 373214018 346846541 127146338 355415721 267638362 234846895 93724747 376740133 526416224 921013278 962521793 464066034 356757797 106115595 627133902 877066277 179265352 263773449 433879981 181419463 268355854 289894734 33832043 497986163 544965845 906756186 370567326 175744689 67701419 20590384 378379481 293431803 219953292 505525819 648847524 487591654 740372715 595088638 864331787 119305298 368618275 679369939 583371332 577892438 785485534 63021593 307475074 964750887 326795042 741355055 998686716 595150897 31249783 32518752 93137053 576215628 791791304 316220745 604476683 712009090 189327495 982856164 5440886 409280787 488381976 506804777 896872442 81271050 101893408 613720588 200576348 323028049 145606887 783947680 900920488 931092421 846969274 60911921 748359667 173764309 802266977 747046376 768915206 833516760 632081495 714568625 262248747 423872792 883305736 866725430 135881875 72633225 702097953 993839135 481914012 42996288 500643905 231302813 124267339 455053679 697539768 324843687 630598094 843146655 108791361 384034941 774239069 955760635 444946863 375115096 982041310 247213833 122161465 603472876 933246959 606759326 170557860 48012065 30632112 53863590 914737495 19030353 126496815 469351807 865385854 460927193 512348095 218546118 544746373 636615434 673599797 242286134 961459122 156714251 85432782 70250476 540749192 712188217 878527477 985696055 87303306 713085146 85426247 61981138 316558015 18673199 521256830 487115876 66685264 404405308 393495832 833939125 275952028 372509013 303290925 141337875 833436206 815639021 359883994 230698938 304770814 886000157 472985072 266229929 42714401 410934220 188996771 583463594 975638804 920040614 421676008 915458476 633125754 507102256 829955980 802200135 525775455 351212804 141832370 444977086 755618112 535328202 278916204 31570133 907837215 434723496 25424375 593789781 102878876 237824735 824488719 407649690 123824885 149990151 673879620 19055653 560924371 715392757 602519247 389079534 635433365 24195248 304538004 121075478 383813870 134493977 923275613 909589326 338223147 65107977 207082771 946357626 452952545 485998975 830444125 360789754 920722471 855868500 954579535 23601340 93693228 631584613 283767397 70034480 781574764 957647017 89090133 195015495 525556133 544125746 584095029 13505857 420837360 888633033 134581335 804651231 875643377 910373315 566756916 66382883 827997658 773839687 12740502 280950196 112355021 695700994 494256316 33077486 404085853 301352210 909195199 350295448 932936824 45478955 420329928 714511581 3125965 361936427 909527076 381198465 906062173 346138465 394704322 326899526 87287857 529285658 131550750 962931234 292175332 550824032 881830484 120172983 324663712 747087352 253639545 437018734 442788339 747895862 322612586 846874193 49248065 84324144 49686000 982184889 129803100 470015928 549212830 985445438 831952355 311256265 366643896 590530887 657394730 761348219 917430413 744682588 143150236 901497530 560130181 435325568 304837921 294477024 408014917 629501634 41564370 661654462 919036734 336869075 409550317 94165679 36259627 311314749 178489823 85945627 146015997 160809289 555961555 695228827 146254721 240430269 859001459 365414983 830961156 368912548 126763195 600907929 113595129 122429797 354921818 526241677 410271731 659759739 820718701 818286648 141777732 714799437 479941104 60814459 51668506 742007787 7496504 87928133 53322529 185986328 173873761 199338527 346795617 582351682 747083720 345566704 822781952 606085172 710981688 506259467 974997721 690261249 959683762 941109216 812691047 167121939 319867252 75479137 826881679 993102320 893765786 821175777 707901750 226223249 734506603 612086622 968231036 742003107 700014756 21553559 927989435 726404883 73408452 127301412 308756558 820492172 472868116 984054876 279093704 36366163 342830703 106607784 726627413 302514458 900233366 391834819 469636398 72616978 467313956 149034436 65719291 361079735 970210213 626137407 587302984 557233175 238224023 408050380 299236276 790755145 282120305 79742070 517160021 355528757 59559848 678432945 28537288 532427965 662487815 160147358 568794128 5318511 266755142 147937900 160349335 19504868 539772719 482502099 92121846 7086669 631536535 157841137 220682770 454263108 783978544 807985755 11496276 874718933 68552494 163248918 665474071 350672799 95507355 35150451 706201556 155067203 713583397 587255210 687495168 228587571 747402569 108805656 86422448 14157704 256743556 99288149 33662572 796516276 581790249 125784418 656119311 65843143 136141921 876802081 520106251 772636832 537304195 384118894 647355758 605856689 399884178 165346189 956529488 495391533 53013006 515247403 650458737 766596403 102502607 190470264 847700340 849905176 299275920 934122788 716579246 408535843 33410931 602758185 57568478 467717546 581058969 713687789 533560689 569717257 590489863 53666934 342354082 127794052 290302194 842226206 586167107 690186372 7572388 542696589 38094265 60585395 57943985 688553002 679698164 12962958 879023266 379914864 715384500 30815546 166554011 284480106 439351389 52481308 887238291 496919867 520198854 320813619 210607649 53759537 890530876 653613878 959942844 85401317 633924296 102761397 927627524 220091397 792947769 787716278 615304352 831042034 700818039 525764703 372111395 233032563 538727662 251134655 612947427 106628521 281950201 779501438 391108627 721301590 831982747 130863277 70737816 204697960 451676897 281345465 258457497 194724132 934959343 70916700 132641816 421399999 173678097 60269333 641491396 966625867 700501977 109312107 650184260 253836376 635076810 22295649 339385305 26320831 125946670 952332732 132949353 260413237 584350529 524057980 981714827 268849635 654921258 52452636 473547596 106598148 186314467 584521459 153838646 973790176 655438160 286480462 395190168 829116257 199266161 889197930 648258483 752284505 998510037 150959103 6120874 633586841 25771118 198022545 659907672 151717788 2871636 792857025 412131025 587222165 169431365 246362211 708588167 824352623 151331213 34652122 783467137 190162046 619173581 937305783 163952215 274611734 76302605 411658750 103727985 128085132 300856673 604502834 880369637 151883070 755461937 739006877 785469911 781233055 937029422 297893942 932950843 939901058 943267334 197598227 379639583 112698692 296476804 88227743 937051315 447808017 122879865 573034811 637970063 742053446 362856953 654438645 869181547 439159558 66097388 825425898 567244691 219470427 429928725 300130687 371353497 37907022 39137558 9339767 819140077 976166980 307233710 604607280 768584398 103017403 802205507 148223974 215716095 98682305 88968083 5283769 399006688 211847948 578318580 889493118 806417760 941175533 543931756 675599300 232851451 462545510 353541557 652612508 682015937 783470283 952743195 53369428 821377305 991880753 62709195 493033741 820564093 222459271 97641014 441664850 325476674 752362888 589888824 541192769 703561559 678856907 398992904 102568240 743221221 977311484 844577724 549638974 771003377 241025839 77754634 856371194 703571349 431296191 508983695 385587280 67282833 314243249 291473074 741176504 158640362 354182269 234210239 979204455 576641541 184367619 273385664 902118215 936730507 863274488 295827344 640292059 394647754 694820248 595376666 137868968 524648092 292470749 540024308 148167828 533496589 470295308 4539015 237067931 901591500 366039076 475171577 821390699 680282325 766644651 562567197 838922687 120826914 649293802 670643501 549984821 833661421 944029165 304619395 770391922 659820012 452963105 263200340 906984132 299713 711093372 897369466 524947805 3564115 289910134 525631999 537060704 760205442 382687380 626645001 514313301 748726456 101816572 335703994 281525140 868461223 750787557 972964194 841804503 400081352 496124054 244305683 86259132 292669579 401441445 856651054 952489591 854404550 972367761 711990083 854704263 683461126 609359542 232168427 539541607 899269676 757800426 76602304 511991478 140487799 555763672 26304772 741730621 657580244 214525132 23255755 378557826 965312689 848736315 72878689 217910400 344860362 169700738 304169533 637529941 571142183 13336946 442535892 425546727 985704707 7042334 132767349 521682193 616401876 364935777 61223793 368187912 122736196 990342471 880179390 115740362 546106136 759000528 857470983 56202739 973525661 733243104 287276931 938838343 581979412 360155620 9265103 779356141 529856359 313434636 269402441 100998535 326771582 711938333 379061628 312476283 718980667 511828978 834158476 187898903 876764755 747898635 408603181 852017317 738241099 141298930 967757679 136863594 900299458 825228656 45582699 873825112 410988119 332859631 665179815 992967532 693015251 674444918 624840032 75387969 987879554 894242473 28902871 167167495 458697166 260480865 479643778 30194192 772309843 166318613 218093095 501590957 914217249 626696276 206124634 504974707 767995206 173882306 494354668 520811024 851627328 539937367 247152495 262615441 872796998 912332310 108099332 418328609 439293587 732939364 493716578 279689500 479698196 375135815 446856996 938395362 635616681 779017140 968589555 260442883 945335754 39199009 762033841 712069362 665895286 968158475 69560428 286406851 994557147 563915096 807217875 846184469 103852457 54370364 961316276 829165821 819219040 69415601 247494423 111028987 654871331 593727368 243234853 134569520 968863183 690091849 925481249 604479857 321625349 894070797 864922741 119477462 933269806 479472941 831546824 451681451 300147775 753623618 590604669 147221281 170055074 250338903 993405750 126423897 157225633 807238385 955589718 976444674 729170352 55600501 939990027 236558042 649327869 183224873 223643929 618191045 725833089 149125171 75187262 47458431 895712334 792626369 166935893 681498499 124615669 850999083 133179944 424763444 604622694 576300979 571984725 774677768 826639882 417906835 901101665 983865516 77661579 709207743 812826549 806831932 764808244 752816569 43389967 414136106 788557808 267033896 884843517 514390890 268675433 960030779 414365687 164387760 605173507 581301580 845886260 729789176 284817022 831582570 7068979 889439717 260399908 579053705 516633844 87039783 849476906 270251869 70905292 927138485 979459612 736248207 733970410 596784215 341581135 629876744 10920314 130138937 896910640 748280197 497046193 18102433 560827336 911411881 182490193 166000836 345229820 880892819 895790013 630046843 564991748 902858992 372002919 825391656 334429056 888636763 912431440 36422321 11404991 835853098 963560807 843380969 424617665 550047576 440165177 766198800 179924313 303601857 896337737 929351320 51882048 245900290 947453753 465225750 157312164 129943939 631226586 502541984 863353125 379532958 132588820 428344866 134908310 357108105 106252882 321853732 98261228 18684315 358276054 109666219 707053779 321836854 953047189 131671437 871884430 245728725 750386604 904325110 401846949 499240700 833676423 306245363 745140990 633646535 771471113 902453154 616106840 255214058 257511498 479459958 634747017 242616684 760321191 622171693 599724790 866574073 944025425 697986018 737774754 302301472 660168603 297344892 476654692 465732151 281532696 201055482 711460877 31919293 105380585 113307819 531159993 791573374 272069548 128817343 425219902 43540654 31270490 41326735 298754712 141298354 373303060 786018095 236431405 133624244 408189781 836156195 852714683 204731566 386658572 590489430 507033038 46827168 887834322 983687731 365075686 21883377 37259572 76536556 53802670 142640157 42360741 437479030 934213531 166946655 566296373 211949792 210487309 450083229 105792893 361758387 591381584 331612319 147776476 827812989 317752929 408482623 516485543 170467605 613214189 755660481 613473401 120247221 655004015 353824083 956451318 20079694 375707460 993710890 949132623 429510131 988867413 844009730 866989161 775597303 10956378 285801893 987547095 73960053 735885122 945856354 435718441 179783065 277468667 583494917 7596047 595221596 991977540 376597956 618205568 457708089 132258430 231678962 430471676 639778812 585503045 239439353 659858506 961210506 85666602 461507489 243236996 74534008 305517212 962742523 850131311 168989957 248544409 690194765 242950010 984429531 488567478 678668451 16728956 766036145 114679727 24325003 213774101 106657261 253439326 831979669 416881716 238214122 916174997 847353392 877992934 354194402 86792738 390367800 167921267 172459340 851875289 411158263 99509714 9908860 226417145 949641025 178898817 474961554 492352149 421848828 311907444 980919627 100517272 328636400 599472132 67713366 205477770 665762599 26886993 311433462 350258627 443768709 549647584 266433617 291122094 280156878 620628019 230431198 523041044 788549286 402890538 227432692 52223908 502400252 237341552 278641053 304557636 268756736 606118973 649426151 690605564 918026418 482862137 643639202 99179177 82334262 711352568 157173313 600613227 738239561 468606775 950871854 34524629 18254353 69821831 325646723 150927597 690449850 556077921 673968641 331515496 811484825 901401333 236255770 166401436 991259251 514896824 470959072 260015980 121015790 120385216 803137910 891558574 455763720 299293472 843254118 390614348 10646033 427424 991227576 601401961 469034200 942099423 635926590 339804919 11921247 814089680 343248882 554887464 222683960 17217516 738919326 34168779 771135215 975175096 200570215 614910825 342588279 524045654 874926806 316120436 496947236 530581075 60195369 952710956 829874547 903449487 343325298 693036947 903876912 187069233 146955267 225427471 129168649 782881857 417748756 993606270 449487896 760997638 401010093 672171857 630731520 139929412 706340636 254383094 967620874 759427217 869293919 310209147 283472864 596737084 626329583 780420101 127318153 686524952 585647416 957192700 442490799 928972714 502746006 198884070 116041940 649701273 424311541 97726956 285099490 842060297 943849592 734587386 455574294 197376044 406759236 86305807 189821822 965616238 340688901 9959055 725043449 62499179 320168202 861032679 659236264 799014151 493969139 786554417 338055463 79616549 596263476 780546262 861105629 99009476 979430332 829663936 601227115 256258232 779907258 886326605 98318522 576273209 620913985 406409182 773649253 880189587 492714989 815987441 845805819 685920256 825946496 423365627 748419435 146114692 136914665 407655692 797645209 630883805 46726468 135700665 710500354 495506311 916246927 424122342 447032153 748193618 253786271 48259261 4451843 33693522 934585867 955286738 462483097 408016211 361695913 88648709 140722157 706927268 904636150 986527976 392847517 730582640 262409962 141266946 729213698 399324628 401439004 379375266 30208426 300681839 515075932 593225146 796188150 283839218 17347481 243220296 32032830 123650119 143995923 889001046 9860007 78581783 844287778 472343105 339114360 58500050 560991814 479836518 765427319 318144324 318880853 10791195 48726957 433807182 4574507 630457021 833131810 258529878 9832280 715856602 559211717 377424578 161598107 355399860 513780163 31461954 451136522 398329359 7628439 595132445 287330398 17488447 526230595 984134542 342347918 865344955 42634586 903339732 197697832 660578271 74000415 369095052 523885832 122727372 802902234 528460340 605700759 488550403 786990218 468049406 56923364 198718294 697990350 218521471 554118154 211770506 102499791 5254669 610099865 110128231 452903480 749946630 127616678 979134075 734081165 469964596 696995390 629232117 225820687 894693222 142326747 299821103 116304633 666212580 275064841 919206867 47189279 733281967 407757263 686695863 53847732 464680627 885414157 751838082 535718464 292048670 963608589 638218256 149819705 426224813 748346487 602723185 28687802 875963165 581857254 762768968 198444120 131369003 244517444 276781173 26062218 239360558 576602276 142366852 905573138 704183484 914090085 805278783 437465444 174363708 491974639 491313176 639044335 229905155 95667617 27279159 521953825 59276199 665497415 671773530 338017379 413843895 274496708 366705181 142323419 708870328 981990515 193283905 840239331 79024319 470065078 718817916 318384877 46667348 713701134 76474374 603367198 627791212 881753157 40832635 802154920 226244155 384662177 293715615 456149310 480329794 320994774 978103135 392122360 986492189 649876658 582656105 252852443 776889732 949361286 247692228 485760054 783868161 440976133 178515744 862892480 911041211 897333660 181277350 810224925 611034787 257751724 413592116 91342359 139504874 306941117 746013645 218265395 544119660 39729253 674414705 24449448 213240393 652517833 269088174 52248941 154910850 851744279 157617750 931800582 653621924 405309978 270076995 290006444 846286111 448592740 152898917 757327316 198442759 186692633 420068600 809477547 444444357 833660717 753336272 436465597 993118200 499349910 654730992 537237854 391595530 181662056 414203668 457352289 834179889 535808208 509601231 841607105 240068846 667218981 625924047 893690770 72528953 896001042 36213574 771331430 197110141 189112491 381175105 395552901 375805125 801243706 57546807 672765848 487420782 810883079 109231439 480538975 162749348 616478797 870293195 406861244 798140854 137013222 864213534 484837102 672821430 226331124 178960567 912890276 893550105 804884614 659097406 818595424 553402015 695310980 442443214 750512157 884423471 823618319 998581424 112744955 624862018 56128224 785510804 112282793 719527669 747258609 445338135 734793383 216253765 168147689 141654621 866910985 305160912 5868148 204264447 977982342 84715638 383225014 890872612 978265743 188109621 402486377 649377527 741511636 97797350 91820734 344540152 834737187 767955419 195637935 947482143 245333797 104282525 585509306 210132956 823810194 185284274 655471091 411119937 254054405 823618781 552774558 120965384 128779686 411159072 325229831 959278394 495874710 708454845 702667365 326656812 749080832 105153735 828550705 343108827 55467451 772887805 687648980 890204639 540843218 883286915 690203141 786177015 987569441 128228806 996309971 663895994 313513080 504297422 75015924 567567485 180432562 480306848 541049235 161728614 743982286 866279066 121007001 92373355 427250270 676190733 419030168 28847461 781344468 100097232 371956289 836811920 872985038 59605262 579532918 266344615 795408543 269736052 52521623 635494343 397964858 901347960 151906697 563994304 258161741 79438987 131561782 291110669 412262202 525127384 452839283 156244481 243922809 426362651 248617837 671173080 102553377 520164371 700020541 736414211 620261603 71976823 425742490 493246634 984098458 5275401 759591249 632023361 127527819 664629238 120034063 378009043 418493558 124457126 942003347 529171665 203896114 926081496 820282335 616158316 451208873 125637977 624919163 695131682 552000628 873537000 218821121 507070371 246217730 771358029 96000942 866479334 695851218 374259798 212242327 532466036 232051566 971833577 17005756 359579385 488979174 137039819 737588429 759989098 261496946 532108135 289160757 317909426 458189624 109443085 934067742 761914863 87597428 411503264 309562905 639598057 137556624 528384026 999184794 383774354 152258414 95185729 250253681 848109633 321961894 462496009 380575662 554013460 286845945 397581418 913592845 628341485 387137603 503697633 388330577 648634549 35805762 530007700 966543975 346511752 491967151 753128076 108426609 579564579 17147700 270505880 71678995 154704324 798889906 70863783 538478678 951148321 18565878 788732360 651774313 340527772 103744728 32349968 894541232 243107039 282447752 660650437 871448524 669585355 16864429 112295460 170736264 905186564 642303160 989796605 104214676 134270304 595441041 65157651 713834884 612588741 335663531 785513879 767293065 134553430 708894028 305771736 938218117 727459907 947020462 442508789 920504045 50765183 327375123 667561637 146388588 609822875 180728433 17837106 131924590 197592862 130132566 155177220 102779420 772435727 144973818 59510462 759222397 740414859 124668113 325573640 205519959 460331644 111087513 972813024 447401440 672497907 131101120 238135917 252474173 78121575 680644706 172978212 981403132 8019823 840539849 127791713 470359064 21268275 145628819 602283654 71377503 128277752 757460874 26673289 753229845 754951059 86183751 512452235 347882277 210851864 838025876 553402237 671183508 801629755 526215254 118584942 326644021 657316374 209237225 579118195 587954316 889881931 752096407 569357441 897901754 445152615 549665520 220777178 318937256 547810706 823060832 242831125 676088458 433038066 269504415 281834662 40505484 208204532 794286897 388387761 419056397 484829132 941789998 942756271 138975246 320521612 913857579 465619268 977837986 123094797 44737456 418308661 12976722 649350229 987666102 763394842 947019210 389847982 984172020 118472825 937658688 659749212 361303950 466263505 945303644 630808365 748098167 985809128 839012898 394901423 374196882 110585654 879730556 168503240 53341918 871222168 489024852 819715864 189357795 319379197 942810661 86611617 737687859 808303749 735961846 577870320 424214951 535497415 967718302 260903330 653970240 905376983 773168908 15274184 224156847 718472545 498598915 972255014 556798032 190128172 367156431 930994915 300713826 99403346 99498148 206572111 970625514 441039366 26287968 12499669 760418563 821614995 99111286 498106415 482435104 835073133 75976729 759166421 223086907 896211397 20069744 877057148 654104740 645755019 892331332 878261587 216743923 243446606 850516595 773541956 433574779 70189385 557053230 734288605 22109097 509067744 793377082 992734611 950107110 672181416 5234273 710525666 346312771 104345560 61148441 828747875 791935059 989641543 440430655 15021959 885852933 313016765 744595473 392474032 958771784 489443164 270735613 175515701 732889771 973768574 949057657 166464543 43957952 358627246 753269514 66067049 867694990 546646590 911318026 817802093 71344365 769068666 380844118 417657136 725930592 294508925 98921370 370382010 284150461 539352025 237920335 22519754 852368791 982515809 414993786 811140568 324475332 538245765 839172635 57365096 512014332 640746651 76346005 408488650 999373897 829615520 327072065 867068880 228778469 90906451 537387332 300122834 712491483 770747817 717779971 290938434 65256735 816701341 661320444 201923563 356053360 751757145 224443317 60938510 586789313 491953469 872079078 911264646 30199228 563768073 968629742 394729926 204514717 44975741 803218577 56404974 727107627 982807008 923473854 955886096 73713452 313377546 256008923 638721301 84125356 973788894 929659735 1898457 643006595 443496538 203822020 999059955 195253677 280781703 59998458 782042990 772735173 784593902 545823995 802934401 200878334 366970097 50180686 405393052 264462204 853399263 461798026 991569831 688722631 237788239 947455920 614952449 403682151 55981202 253673744 340323873 882286463 35849838 342222331 525293051 479346377 398560717 376869365 674600054 679342421 289384189 309159403 452077587 926494457 854983399 107528347 127372785 74469855 157709033 385282203 338932059 863624663 847080229 330501883 552347287 937384834 130474162 19816095 341066979 38971730 273489839 681390852 921258193 309339678 876129549 299067603 788686055 274690260 675936968 315802468 954032681 817837523 477478237 258626627 744331974 184977995 218671340 724221125 259447850 376380373 109503321 598379909 92521395 809099916 928881792 644868682 746484743 911872320 664684778 940068088 950844051 790690983 473975300 872102237 100030654 350104842 23686200 741233075 477311468 699623168 909551909 283860508 369977051 387030140 542487135 114309018 572008135 761158475 691046509 831455986 990055215 800549830 282352254 82576603 462166105 63750406 579961652 61167207 975622726 97162789 1235289 926466770 887853772 475210589 651085367 840400793 677831797 674771567 434150227 155143259 226911094 343702130 439003767 596888145 583248636 834007269 563713529 7773130 447682103 107276397 839229116 437737311 907826227 121581364 372830281 222508691 37848136 952791933 283675899 13470855 49954715 284911188 792453992 937808487 612638143 296055718 630725639 290469933 970827285 64875860 298129558 50254738 261094356 737133326 499659250 844342992 423656954 63372772 852116122 871339057 23165536 543861598 161592728 930991763 517959328 534423009 6016814 555807464 487214935 289692713 569278319 389686016 574603901 214248670 180010862 39758403 510304388 810736502 330228336 333648032 875612362 628357895 383902771 136706711 218007580 883562021 833566069 641664534 799451159 685682184 365519950 822616695 82060141 527112678 606124818 600019469 61535680 612141632 155826926 401266981 901834345 577621612 790952997 328954605 791870282 970963860 368713008 302174664 781700355 551457710 635822696 509829076 32331964 872241833 499052153 250339544 608320213 185134581 744520444 260287732 870816765 110040388 82904420 952876907 637153066 541545604 405412735 551205113 6203595 561239662 952472094 760554306 138861267 743425085 89508904 783247915 566905304 310738278 85422572 201122018 862195989 573761635 710951094 894527953 298519827 62519606 997383864 906840041 247654187 741904301 167127766 970987318 704461055 102548552 776380584 194130481 496610523 181793313 745335594 502814118 595549341 697807681 115884784 586926974 293749125 57910054 370174882 860654429 368648333 308113821 61776440 83360681 734391822 625243900 830405000 32911642 540279872 827788857 939751683 787934059 422209518 959395815 611437737 126670566 61944361 387818314 173317413 411071250 422127993 918653007 913885368 17677327 468977048 29770145 604604301 762726173 87680200 827295550 475896962 308844899 135409364 390189768 244721946 722317552 867950035 75126939 755229194 408229900 755432163 547497237 48680319 30158040 359409411 660118056 9344972 273870138 900452736 182662386 684941388 322580723 101315386 451343116 192774416 570292434 333629627 797378718 185534967 273826193 477190627 513948295 582671092 465116357 904138063 827393038 187433902 624604457 755036344 795179462 32834351 510468500 195193058 934031043 540626540 554602470 446665458 549971512 828472608 347118187 732633898 513413990 522215276 686465651 964757106 714989693 109274444 150903092 364884770 294809411 424729286 842075397 808757706 7400371 307191747 565412129 687309776 347142015 42532945 294862479 142321470 75367296 805330979 337514529 861914705 198473878 892116999 308580156 600961756 573105966 508214710 186112014 86519949 30429979 872577665 903793421 745419672 981852109 54696507 110304435 129177880 331942159 804896198 937935586 191858896 112087938 355864074 879168672 311746319 398397020 26547510 454067790 326280682 831878489 644098685 40711747 882868733 388732043 349291903 483830483 961838009 857506613 669942497 900874325 740452959 395036521 657184105 338388990 376888623 564396978 301209792 506066503 896339137 106105983 296518449 88198027 70710288 504898889 819883065 382456607 903295909 846430576 689040763 82092951 530825424 333139441 122804698 413694151 721871484 324612967 750041000 536225853 34635940 272499856 437100171 775088899 667536377 94284269 113477882 44424993 511197614 414687674 403007863 407536744 373310024 552042678 348251137 444020312 56941560 168134196 678993285 812753836 14564765 368034042 894846787 397906555 553689849 870167851 811600706 128077693 194780811 414158065 664303546 229416751 686657921 101403710 4505643 354194291 48204345 970499899 251135651 411918325 237703932 506659880 819455070 611013956 58702551 20222566 55034261 115644111 188356762 586543913 780914313 55437893 954577955 528277459 453344449 360784163 398445303 117461514 488861856 445742481 531619580 153165395 675159232 70793860 107085471 532181242 424988152 7806183 355197500 528640169 419724508 592901432 35300042 91695937 203915382 94002593 111918504 111466009 62163070 152791632 698009922 695593750 208229526 505104236 223871202 514090341 865888400 474832872 631551855 207266615 920575353 15687794 360432011 448250944 86481655 320033848 980432186 363986173 327840031 188146045 892626342 600080906 781047478 927926384 691776843 984962860 874445343 656211713 948945235 789124779 809003346 499471517 337234888 17232865 4575746 561106091 383839572 722980512 35938956 15391420 930247128 809030675 883595588 143195498 257281612 970077243 463229346 90230158 186579775 643585744 278376203 79206110 243666643 59423674 859648860 787959852 896902900 586610562 444171559 698364495 228251700 105691264 197836005 565486589 122924129 54928117 126592673 359280067 630424996 15047995 227187853 413188483 676595036 110783434 556383981 933876648 933377043 872129693 876623172 119956811 515715430 7515735 51679287 611898439 66939409 911328147 399858285 816358676 497938702 696546210 367239530 726190403 802237474 565075535 144193351 777677969 472520018 123302390 136958029 102945007 138350385 364145882 516133490 667461787 327445683 925033837 453854794 260822719 797163524 330477960 233295897 165395313 337993695 284975184 777293753 257449470 196303325 29668397 926324512 546758393 726214607 293564035 125465155 380968440 711155936 
269658506 158646402 183675948 392960896 148120797 139137321 383827647 512266679 655270812 51289427 839712362 432821008 505144222 953051448 82500891 688138548 186347338 247896205 26132236 471322522 877706324 136098072 520142213 907374721 62422578 66900600 486105687 208502979 192365755 867074127 919658916 462024262 878236895 955851230 854985158 26357685 94988544 91329165 391140730 602775722 142618592 83369452 35596724 500279180 36420893 118097615 188417721 75284597 218510186 67066323 546607119 96216503 55680762 66749326 856107590 118103340 986166299 194729636 179122685 31048413 61803756 951297967 493072675 792557017 907149190 200574193 818914702 854654101 291903358 62571792 457429816 287038316 145941244 345542906 787317497 182362137 463640522 975735218 257646734 682150708 895317908 656770219 630883578 950998670 576035911 486991161 921618376 562202203 681720798 100741054 593250617 596040920 904555388 938839658 241114297 664220937 139413844 60028992 518875031 283833568 122600784 828821214 570871885 121058394 174364113 210705741 303420531 490521001 38957318 413583631 25188069 934275226 70353844 656071647 885273889 646389755 143062801 659408624 61108318 677299965 612666045 506875301 125857245 517221426 445714952 366971542 33958722 437645163 279516900 552833754 573995097 254634051 234171327 144866975 375692445 408535440 208089082 531629343 899056442 247046401 945212974 924244511 181321620 15566811 432832517 919111876 514472933 428411684 578520493 428097617 105711643 43702897 934972918 84085254 560924323 233204229 303573162 594883046 670849392 583090062 233159 97360849 690240479 234404486 94744190 65932918 495456292 302833273 450078627 247029093 549879674 395291594 23789963 731201294 263374772 456622480 502829529 630364071 885034165 81350016 58461681 843262174 125052913 993434599 927347428 538493603 79155187 83436949 985893015 750004580 666527011 986126174 847365429 209283850 73047019 942109619 127733134 568503311 97459251 577811761 815532405 647338925 973103355 839322368 231056579 88994486 148461208 733886108 719358557 33495366 667752490 630336604 876757540 645321770 476287562 656621327 36331732 555442750 740058276 22224740 157963689 259101646 860867280 5329111 468385496 933914299 799955096 596118630 354933969 897414348 26446750 22982733 397269632 999550106 714821468 628326211 941060958 863282676 362212313 512935875 896778042 29964796 143272472 626051941 527802932 619560035 135189627 564134664 27519144 727764269 586359404 185482833 986865915 299743043 43328310 307767771 86173701 843283406 756402767 441107671 593214113 782849518 316606770 990483746 634915983 31428231 471326316 575976934 894710907 833538629 88912802 644005308 716019792 84701641 122573608 96339083 556778042 110279601 660473748 584297186 838043870 99349511 769780019 677426145 399092555 813108329 985193916 485266256 508908094 594113042 926373927 102122201 376962553 95497057 945122313 11878529 126925288 268964988 440371830 874152562 102503611 381800998 370674229 671039769 319019005 493247838 767378852 875797047 603527439 280368959 460094226 294087669 379718471 82390604 971513814 778811026 895498933 809224089 264077275 404407021 403337124 42967562 359045588 632816044 138464619 156684260 497210939 117906273 425649248 937582769 992058835 380669225 171900127 362733058 904225360 490919132 708497262 524120572 219232539 164541060 804489531 679326765 458628729 184207995 761717370 430142536 963019021 509732662 91882984 79612656 914139683 495220109 122580218 125701630 128036146 113561203 134902256 477763451 231467476 560551505 267862580 76042671 793737096 439762707 438775729 697962450 783198205 147272984 74599381 2430737 164330410 879088912 534273869 622959140 63296901 148507598 53101669 878832288 658240260 144984654 810961310 424896303 492721129 786057894 550597933 473273641 899619097 685500190 951037092 983602940 98568054 71416031 59645604 892305150 511178738 350937699 442783959 146893303 350727049 517383340 149324040 515057459 248988612 683597909 138016592 164801879 832105507 43634628 43634160 342862127 41135648 707111837 767758430 386373143 493169724 170872722 859646784 245305181 856372912 663200235 81424480 807457332 734616267 141070084 552278842 98311364 492007783 995062801 245204667 842734832 364962501 247045074 210308650 613951113 930642983 348325243 778752992 615264850 244476237 674903518 958126977 285611885 234531714 578401766 671985028 727701439 749274488 384148171 825522986 458163760 899864772 906947466 265621085 486997398 48017543 817899927 585308763 392541692 665479088 683029796 87792883 882957955 930074870 298101533 349425427 713234213 498943142 128178412 181015422 743419379 655598296 139142392 29031257 890130011 570060524 553532651 470347809 319335005 790197188 148387154 777498765 690061954 55334613 895636217 29575711 955868529 566052503 614884474 200926580 84047950 150430630 288719463 967005905 80505493 439337362 316431325 793739706 938280505 297126103 974755128 681699877 805240766 966413886 563247501 547887136 388990769 969296518 18234938 708325775 759493700 19138458 338340899 302072013 74473071 86493475 331647724 30341593 652545979 799048565 83784539 736593929 949479195 372504002 703599828 29984681 811841364 872547519 676240754 602638228 22189982 503512241 136854465 827430748 322442487 700101966 375317877 711433256 521914843 246069181 272275390 133924902 265207639 463132656 435996915 192197076 549626131 620161006 75055035 202172103 419209564 158839574 938766033 221205118 531343576 494882220 103706165 195701299 219946098 779946919 798339528 242136080 135975520 935193993 69566821 310934373 487812318 297401064 22367622 9727154 543470245 147159379 143652057 661194250 610292035 432165338 853391326 12434525 52326337 928446361 214606629 324052267 87285928 5889021 545257385 471145870 353287607 648963551 666847170 573233705 281426829 317703057 815369786 269918715 105413409 884936607 580853088 445742093 34854031 455737077 307985613 578324276 602896456 304154036 92034886 65704850 736319375 945426212 78139375 641162078 873872567 145262370 817730712 813674861 151151391 215504456 284820725 504438998 864468007 804184261 77672697 998411203 121887311 745558849 268329911 79817086 483011815 849183000 525559179 517865846 157436436 833544792 96190116 760332892 137698822 40741368 678554108 726534563 986167580 756693483 220213000 712556506 901955854 37943705 526231361 905623611 105964528 663568452 262578969 970432535 467752706 192768032 821360097 442156383 938326881 89690002 374489835 421338689 791389368 900049014 939204536 948825804 586110165 887911018 561675055 576325353 928652386 92745522 155376275 767336325 849439005 228105642 479892825 603911218 118565713 858640552 362051189 224530241 522208997 624630158 47479136 842478069 817398190 868839233 137150811 755725064 811045601 511640646 29580112 454951328 264206019 821301014 256293491 850316184 561728391 817968546 279157897 342897136 910714068 287050538 110233455 612669433 515156180 442642646 69097010 633721894 301283191 431148199 858252135 676008554 55778350 905731271 518486616 725692906 774570498 655637427 333934329 438132458 19794432 363514442 893083787 284000451 37331815 149377271 134316628 599060207 819862184 265990891 941957343 583092611 553041430 52190791 48278403 68197603 347349803 117375414 554435863 648632994 401039979 412687992 177157907 309334696 170935622 695644523 35027595 945506120 203798309 368961925 236154938 223592741 584992733 129238718 507593192 622324548 131132355 494426187 221384748 950994539 612933444 15858451 534087144 18491233 68049242 582365547 86688837 267915412 552257327 493641066 916548406 953297307 906329058 93706307 262631996 77264674 641867196 150175957 875287160 698181872 519137882 111442091 921774613 104130608 93197175 281884165 578971523 224329531 628826718 800356271 27840429 241760155 816214722 561927573 260251389 736780331 996809487 199456592 4695736 549066807 693097658 773760508 354880473 451943076 719983181 617512469 381724116 214366737 767688427 109527635 912548609 139342668 73486093 686839581 95989643 19199634 821240112 674961166 243529165 450066823 327833796 271369595 544343345 996564885 685813534 804594734 585861575 682623014 856567692 443073677 84206181 402181709 69350544 439086654 854124785 789333726 909115490 88365260 856216829 529320276 50409262 621281797 668662944 123895355 160637737 617168953 143094989 981877850 144646478 239140521 284461032 472480275 510510116 828804377 321561519 48840009 485915470 907423094 731463024 342483155 350496764 668185571 744664865 419847308 107272218 451306009 61697393 868904074 392187636 917914222 398224343 442596898 391712378 919403654 566492253 552350116 536572600 562103608 534227959 681219079 801244129 818688991 6215713 164270604 500009728 327777232 213110614 985925198 87716685 944573638 180924713 438213449 465275568 925589578 710577123 425064152 229411946 772274517 293968220 621599582 542705098 544708929 64196473 934417477 464112576 483205092 339283952 853201543 45308694 873511911 386936981 699069189 544717261 393152694 863339794 44726982 573446292 76450401 883168547 661162977 873540405 64093253 99376419 338815966 842199197 662469908 763880118 71611136 287260784 910364704 545727085 829965883 455073627 462439924 616899719 771702569 798161383 956183671 624904105 695986443 682211941 11841079 395055625 79445561 257510139 110911778 976688917 830956431 187362179 859857457 344635767 60902577 776467076 296528552 252234909 618666266 958998461 868631394 542793768 246259238 778996091 941037219 928741487 86586077 255993503 398157565 858288647 54154879 206857595 335709111 750141322 889069536 200066557 997713313 821031464 310093062 108625085 797720374 141049487 148503630 510094190 338201620 61922574 139077625 634730173 314157483 757743891 593728627 35305236 153054018 692504231 814301328 94091231 621245712 753403771 202601100 19403270 464208777 256755979 78777232 799917889 859413667 967846768 852500812 857126973 641394591 162593867 818268424 291631324 156159720 966772055 801725514 494361341 28694622 940803139 129091507 195368471 551063389 575336500 230673708 556633774 120357090 44975029 503241371 741602802 650895166 705842471 613522439 115103937 962598450 692299671 767538192 674528476 512662798 620038997 384171808 6573749 635149230 202440226 298205073 791308951 21728640 99930581 138186651 50423262 893250086 119794524 245791733 296829835 547647390 476465441 853463609 668004480 373956836 209221339 262123642 24851996 915063810 875646081 992472306 730178619 420462111 760010491 404707088 785641275 232565847 788878896 792215024 867715077 843835488 90420091 511540387 865564128 42867038 502243404 915987390 788633490 622037928 14295483 85463318 22201677 343277290 791443293 690206158 717234127 664625 952329800 594602489 768244801 680492240 439591154 498423413 100954344 52118004 755646867 739111985 284683851 397042123 531327003 4915287 240877604 474263460 368972041 106441726 517130498 871215445 874945482 158280347 345769733 741757331 96260032 367971410 85034615 887703325 58177561 654785108 740884317 10507354 101903956 361645477 543515960 541495110 860068891 496986670 593613114 468232117 236098649 878296965 865274240 619942018 735728618 106151838 94205471 104700652 65109930 463852335 975916098 792571778 622132682 174202190 386845469 718392714 542173600 471880084 458612399 600351162 126665185 52013075 463374882 81085507 413658552 6890836 622580617 126243802 356393872 216193724 594475920 592492521 947007055 459750153 64950898 682735666 418418357 159156369 639952685 336044653 623008704 468385142 981132798 97657746 642587332 367978260 816050460 184760925 692374710 274662852 637628453 671556261 326675927 101003329 752641768 740334480 960410538 375222378 866578282 169320769 443932468 313570561 761813291 390939516 773320715 826764189 926191548 44255431 838436925 566144226 232816451 313961988 34529361 213949242 411619734 529633059 434443868 227670188 714393985 126818571 354849406 204538797 798374832 681525334 158058492 403532959 274376173 118469023 778755337 993470821 140306159 75204164 307041376 902119450 466143680 932878457 581399998 244851587 977133888 272353282 810995814 62466698 586315271 698041541 276415940 997935005 80190960 710859808 78121552 794584945 690194745 432970959 999123742 341085936 114496286 9698594 744618895 241388825 128167617 375890591 87376005 120990142 451094755 394417381 23109585 917238435 179812197 457025950 14606382 9462445 729379232 825602196 71929143 168210862 376160096 348345084 166145861 456351056 911721258 244267413 103452360 601915997 677238372 955092469 943001933 644251024 964791063 540137188 738156215 945475046 916027779 825532221 66465182 367122528 72465961 942091140 136877322 252278159 251633449 151483704 261740604 981012682 829602266 333669747 1739903 58278722 682014831 167885764 514629778 446252449 264669544 470598505 48168439 941907916 425690967 843686738 438675300 242998389 236340285 29347874 188473428 152368058 854880095 107454976 372006952 927346057 49546110 508884274 179624209 301179559 512884345 441364813 134708600 342486604 775034560 136448504 400765326 309565751 156850634 767911471 755818200 421520178 238509969 656503005 215944454 516717302 352706102 654619754 759715691 589046388 683967628 948189119 593930812 391364083 55644089 965937764 318710133 957706572 327338397 350850708 111402490 840222742 792215521 246111091 35225706 419766440 235075961 435991032 581848557 391926595 56418862 190183116 813446774 294928831 846686121 29391221 811646133 51908583 536527341 423878183 493471337 73011328 224583662 87402142 464375411 132744117 53339899 783085544 90450682 233194662 133936245 201853172 73417398 778668132 300480629 108643104 50950932 535556590 397150502 632799489 927483186 453569365 822982606 740929953 748498196 522185086 622837540 412660689 426610035 159364874 836538872 920081372 232376202 61122527 7483507 696751614 46383010 913339779 332353517 136833692 146534435 318806129 191203231 72468199 949990627 491683860 33627669 941552 27240444 430778171 486257408 954723630 884347536 161756373 548169942 485362092 536457825 23523841 898022781 963067861 182888715 587078012 883149226 267781283 500716906 743149100 964532897 547099916 509005238 149402774 536449975 508056039 320725269 727653206 433040604 270715889 219337059 466668273 124173808 99093869 897446445 462947582 53817492 781793974 624703955 454503800 119672425 13678139 478027641 17695199 976746000 513432722 457289578 712411586 781214006 810522850 308077045 598263262 210139125 817082283 747666036 746589100 177654682 68391298 474242299 610695286 191623554 546095725 77363553 168313728 645189594 827326364 631261310 551523453 461636697 108481624 6027246 581309123 122159763 336571254 451520688 98905757 850003976 908810266 811317343 483734341 571849475 119394381 81997597 781988601 788993030 682179999 528577694 819164078 603087664 855336360 282375724 794711218 401432078 212255643 963024946 46621665 39582000 446802615 450661484 501218697 555284239 309205097 82527813 677444002 645776351 386564868 776349759 348296686 147891493 440183461 832031028 719740969 412094208 766544991 501729563 53603598 448724983 882823623 872767676 51812640 738159976 7659759 699040224 992108420 219915402 514581529 891246452 259497402 961384144 341907929 613232466 369184742 651113026 548276645 46628738 149405736 934841513 675494863 350218789 82733000 115678318 34766176 802473969 380288892 801311167 156719891 286408856 102552509 39543507 11692892 6881516 630219850 19352651 705921740 474844629 239268054 73019629 366091074 498765456 886920139 560515370 111997915 256104875 64144755 512790927 155249979 213550492 447632433 830744842 563769281 382881799 798939526 598535457 37872127 31744778 252362983 194592018 318153634 354915492 86651892 329846526 361797008 569388108 349199178 67718742 44232730 588467232 993254744 262840171 87232681 880174876 823355541 51746963 988796117 887500296 417054256 144046089 101050781 864686689 974790932 517336428 100084848 626246817 968388251 137956975 657991595 220751227 332548994 976145230 575666720 271717252 305991749 937463728 841105360 655190927 857698836 885338090 96174518 703469939 694620 35923566 436161175 824050161 87670529 424957285 711550451 357241151 421519741 665117598 74444199 248827032 34970386 174529047 875073849 3358630 312486023 533065438 76626224 645035017 361727027 504809310 916752269 667718776 294789397 610373988 175426063 5004593 348228437 271600581 708474532 348923058 307524147 144635700 172973212 247711042 422109352 737040029 604952193 843629093 254673987 679396393 92456118 289644373 853925440 967529967 145519369 18927822 353111764 74661959 663962839 714838791 579471269 433231467 235073927 874260667 43605448 263016356 879265260 244350252 534616937 587739785 593273310 694657451 584891852 766246522 942368493 7001197 355802911 399837046 850630290 610476898 931749805 795602774 900121271 638191604 615649100 898157006 657119427 968760865 972818966 173598625 536116015 552290228 606830093 623706308 279067254 502951907 886722664 158332507 747302159 273855961 598588659 193091828 968513412 183480504 959338351 763398264 42998067 167657621 15751669 893628357 778134519 947501474 541747490 530772149 585693072 157396583 428929148 95328858 978673814 254264473 268927483 367306189 806554702 875757576 991012497 85621949 231225843 877735155 96470823 831044368 4107475 695059482 24136190 972620887 731056352 835990907 736019144 774054419 3648521 751770814 520199135 781783040 551788647 61946618 165071548 137481712 71859567 594000696 85326936 50533375 848265170 354254420 417839564 507336231 82528355 261368420 445474546 313754198 139103568 394461735 144798560 143211043 89521210 21451116 968348296 673093928 857442023 556883800 447148340 713606910 161170973 967347475 347906309 712959620 881810459 512977857 702957699 953670027 106978546 788284635 4203395 807760082 142539048 274559325 167612672 225067404 535927745 465603585 391337968 527547680 860065320 388652894 523275089 802102897 410104010 344139745 475196818 120062392 901023545 774861525 833669302 62194511 594725359 34091970 775154131 476535812 547069827 330628189 282722198 506564740 118912818 139441959 166841181 113968232 414001284 334453854 339035636 802445395 800057439 730373605 182509434 512639118 119026492 705784524 314742008 381646869 49924262 642455193 354225627 803464173 417316711 40411289 865658684 12042063 74503259 493329174 341094241 621573087 823957364 623816439 128137820 795386548 763258398 294979001 909354780 29776041 481949221 100906776 832221437 134523019 831280381 14730864 647162138 802823239 573031754 961904146 36986467 475472382 456875698 391212095 131452914 874192409 431623384 997111598 738750839 506126643 342957132 932361446 127699723 19430855 408694245 108353909 814817403 24469002 255849277 576688542 54245044 737798498 677595318 738982847 872321518 361392058 606230077 519483649 16731657 31778191 333904154 53718124 507250573 790779853 297446585 638703488 517488621 729069969 488331445 108755819 87712972 683804943 41117259 67929061 703235798 302327870 28799337 370569560 326796872 284648614 947258103 381041916 22447105 477369780 120024756 894768623 838761839 578771200 266768631 855493496 610549391 453189152 909211620 117799957 96485364 59174565 609019811 613973985 788244534 949867623 575246171 728473872 633672559 468879796 796402934 189424717 771207666 825202271 412510643 98004531 109850878 212285105 331562814 984814356 689654886 304103936 732099339 528416718 882875136 998867970 236426573 493424520 304573481 145638186 463740844 401058845 57329117 925277021 15032824 845573652 875144637 442795361 426563883 361333556 911675157 75483176 403274639 682882816 900685447 815785282 633403713 863052691 28070381 964966527 700383407 717725267 269070457 432482739 98658344 4461952 283867068 335084917 497886473 588440550 333239469 814143683 989499395 390568587 739420697 857048585 88658598 467081694 152360305 515222481 680931616 64035455 590705658 84206248 599434637 343907464 899991530 232838344 59476515 780578277 50321230 759859922 350819903 319391687 44859020 449478247 323853640 181242454 637079530 674256479 769683004 970319000 488400155 611698759 213403946 80337211 321263703 154578910 399935271 473624009 669801391 80866880 390175830 113023408 17589494 989610468 309447239 917581025 74965171 368923754 550675661 125286401 981300042 901495565 444678089 26159055 203490171 621048095 59917875 840569702 295304567 829600880 663405061 636221088 293815998 876809007 716558299 467596067 31387910 116493564 941220076 553705667 49876810 183912266 519245442 67466305 173522727 828692681 837563696 248487898 50132794 388239350 373774299 31432829 142251274 670968754 910108257 345741446 292016842 970026132 186311141 439837775 652143371 849716202 76058856 945959369 579041568 645133522 266071796 462945844 614143452 59808231 869167877 664020262 243720497 388413312 584002933 417243224 69622352 421566622 518247488 119755146 662322339 892021788 151187975 804573613 415506901 61296225 150315052 707523744 883838724 189142559 147361512 535982088 38858754 75936735 334457817 470416688 721070257 600529613 785878898 187730068 660337844 655046769 851750330 904058342 895976447 288269623 173817925 965598800 709836245 692065414 85353939 224674943 436603561 89058281 29248550 852110462 2870872 32079968 412150565 886709596 221222528 412028444 275208044 112597648 340481545 609665861 583014337 61551795 62711833 221409594 101798229 575566043 876456363 953548559 332140744 624949170 94334541 505958670 590547963 804170787 50540443 528418268 28845723 339660370 617476549 910610646 44287191 620347422 942690615 456437757 507057011 163913136 720982567 782265055 276510784 61464105 244447275 712041487 975532273 159675474 933451082 77330495 735241518 662423804 883395420 67382255 287372967 977729962 425857291 730437296 634417108 476397734 258855558 515779197 816058104 876332107 426389837 860345296 349195888 221596811 169299412 856252900 385509947 890281979 491034314 514537097 804262450 587997956 226578578 779794716 747673430 12546019 709641577 482914941 674969823 593036990 402813563 962342791 423283311 828670854 545296446 57700412 157584948 804152004 573479610 973643052 533000471 852385813 686504707 882196359 73982617 708320485 590965618 312008930 451118823 934516299 826546027 255381266 522514248 53124598 887692348 122704037 65670617 597333918 605618979 593156807 42887268 8432535 408015957 466170579 689619755 953312403 376387358 847204703 609980767 949866968 673364115 142981231 654769140 212385181 877693956 728751757 920705667 321175934 40760680 371824483 108208592 719823073 479722116 630722840 625464038 367414457 753426877 543651021 817264742 211562215 136807821 860152010 72511116 544823778 178838948 762130872 350652541 555226306 461851934 960633308 357609633 135216042 956130905 12378766 347601224 686341220 593646889 120823250 7517147 486923935 492647733 115725739 59263368 972369849 598964945 684727406 192300666 204908182 228378420 9565401 268986763 217702608 722233777 341497880 762526386 753589091 956145118 113178920 161331757 417997045 926328594 518941390 405729454 882459492 383836523 753330678 421317072 829999778 874153928 281350585 169440073 219318020 249592691 228703441 44204229 848557636 913430847 89021261 905982184 141809260 98586662 174968941 212028234 673336805 368983187 974554621 279442255 325128298 940249907 440774012 595641709 719094861 959715403 1371156 454070712 196068285 607218200 875387784 26068056 333888487 156738363 48024495 553206508 406331054 276727936 449927103 107405049 190158776 538948364 13387227 184484403 490051392 40872534 396512637 15904556 409855721 223583617 295346811 587500385 16349884 736120824 183142087 735444745 548352586 37029610 42031816 744420871 644247810 917419601 623005293 978136298 74157957 671029789 383859165 333005377 947757725 833786268 292926792 990432868 372734625 158830385 27433630 862786017 199702919 423946267 878690573 462075006 500046251 26553743 49575384 516396135 762674567 85233838 104357239 311027146 122263448 146389055 907964383 766511258 63808649 383486036 744647549 990482979 54515818 128506707 176004715 854789909 814809341 468931508 697739136 40060325 627761893 725172766 902846342 679981179 1635393 634053274 142056178 501681644 660607018 44147929 18077772 275797944 129381767 974951384 586825091 251645215 121340432 347305833 18156466 37665448 730791869 615320382 880664793 637824053 596343455 909185875 345130322 411152790 230633742 42869451 451213115 858395635 768042218 206575817 390893173 769677611 693145457 532949352 123875614 206268834 577097281 141953386 482066779 706479048 969421136 68891863 958124263 943277934 268714062 828797095 833459748 999505932 444117470 566640901 637329978 40460919 475826769 982460300 304130075 706460511 877846118 607859556 417372505 498404695 814435373 808265679 120598665 360097190 193731390 244474279 566366024 623345037 238944031 48432796 182340444 208365160 969841032 140464700 4159453 238555088 821778161 837619202 90577379 118411991 404260096 727907357 11389276 732603231 562884017 315519351 291580101 293246494 923378907 708952606 791651189 590330640 369734644 912249854 950427830 415982400 156724126 369310213 39327430 395668157 417743010 221667874 456549683 240100401 214648940 460709136 478655489 36427095 298328331 569232868 7355452 555104793 149656585 18744728 287708017 565056968 334264079 579288118 858303462 110159345 140757084 649954644 553006351 363008094 414720857 355950540 778990495 571444983 725260754 818317925 819629506 143003757 892502166 276179182 235620524 107151099 736888318 714276014 996094567 887733016 136025241 3450012 442837802 138198192 22194740 583062186 703255160 208975185 14866663 561558615 171650897 155623747 64029618 724657248 518631842 478750475 80607782 150138696 902711824 805868536 968456621 722341323 801388659 713475146 851036871 37009176 673142612 440441549 603801556 521753538 328174558 592343164 377719917 623528726 730541356 252431023 206590905 433796510 461406209 221457569 847871491 633057106 229597682 911901110 210230713 748229524 243167944 290838495 898368220 145879762 949223397 719341201 720737451 603128415 285332706 424290682 492653958 958475318 864732231 96455507 480228850 45423148 541315037 857948767 668951874 271856387 110379783 875542780 558169263 424302358 949516715 406040747 909875830 179114390 170458216 120106537 779860281 266142527 263461398 530744860 264538655 212684789 102602420 985276106 815813204 387935127 262083147 160983521 346410438 126815371 109955395 679155654 172238519 651270432 389620780 841190394 923126819 352516930 569249533 333812441 776819288 371282607 739853189 539211478 550396997 762827771 659318015 182773637 28970291 922779413 713518498 293508946 987980568 816120918 131301412 656310132 204056038 393384559 817293653 402982843 372716297 927249048 82138490 544954816 578519474 471759271 238661569 354162652 824276201 660427468 687975094 453611848 31710068 280344642 992823326 434623432 43172406 504657700 617397069 924659071 279953473 330915560 70684376 120450400 147036472 201985788 776760532 203608876 447886714 594054179 606591719 820603011 373819586 541246576 218074186 952339060 13005840 456735756 159018072 689798407 117163217 699509532 995926621 1389652 979854174 841266307 436013084 875542946 198440366 53410146 652718376 478393839 236842073 723402753 598844240 236394911 925388541 228121131 292520153 225791614 822175310 899111873 46394618 48511256 292874808 264468805 850309 158397014 573720927 12384747 848195421 543400510 711894279 696638401 544790162 544264812 537904701 833319612 272324118 736345068 739246125 925042494 67255266 976088198 500961606 518615872 64999468 278866507 746737004 357519621 504658121 421428673 109147853 551052740 469939929 402022661 668037911 323306605 560419675 241758831 335691352 261131455 785159341 900101998 957769857 182465863 296883169 348190917 15785468 569207287 937052351 607547959 346766141 4307611 436152516 847727747 375439849 501151984 126594247 122176846 711187972 483768735 543605520 820335825 34821468 13545442 74874846 555375745 189368413 487810887 797134576 525059766 748942343 434810276 277678123 559228559 469792505 574561292 759935842 338094340 143768573 696988187 945642299 343051080 553812164 381794809 43295186 929252013 735463159 22405800 903945226 446651124 506174535 300067105 119503309 393512369 166128913 46894521 948888114 355497327 534705408 598539049 880557093 136164110 885865691 10751575 695392669 355658190 585312867 307844871 693752530 581597806 4833051 491911188 924648886 411161581 873705997 820460439 192929953 461685516 842866239 96875172 908336640 201557133 249458643 880356315 447585868 415587557 927250836 248990341 771084884 461956238 847529390 504158336 598120348 585911440 514909911 146029377 941569630 100222771 453874248 487838519 681820578 311223665 979749708 458985823 574901612 705972064 131962621 767831565 20173939 974828860 717223104 928510580 28902352 966681747 661383254 476488220 234785663 588634084 725478561 5870540 903106688 425524310 510028876 353743395 11435744 24938780 499772772 805521740 977677925 806163386 145876619 512014862 117387044 978142693 971000685 544805022 536631116 102963300 165152947 556805056 930308526 882376051 337831995 811727245 701574157 999215249 140731824 936359821 440365692 866210386 794746727 343472373 144251055 157291963 697215769 8203165 34747109 49504900 666241272 12425027 855668287 812117891 524439889 825571697 642776943 347956934 222893079 179408052 303436600 388046026 736213108 86261485 122938436 74045096 897988730 824512593 925776712 38720548 613388773 366142397 757447300 260651860 562131137 754214721 417943823 111863265 762417887 452690932 161368165 281175518 465115960 869552818 93293402 842072215 547640875 588586711 42545508 770533954 767994763 345982108 158579973 356724231 284759960 281518409 283285693 35265049 958547368 61578764 73985597 424452501 427721162 683949263 685104361 989852299 290680344 103048177 101715557 53098224 555739109 115600088 186790108 873371435 985152907 132599876 715443644 385310141 721186587 757989152 155844088 341697709 956487627 166940427 698421940 241247580 448458836 834224000 276512629 259522563 895802764 203014593 683975064 176040285 739480222 369079418 18408943 30160559 324643961 120124500 935775156 880383071 88240955 122565257 606270865 925910228 255165133 174230868 311220362 976351720 932220021 319580816 170565789 741224007 486521243 868987729 982471587 934980079 555728088 111500575 47019001 451530846 167031534 730994066 627571131 906511757 100073477 645980075 936672316 277233805 618620941 724963832 10133235 559378262 847529089 616404100 485288483 955210589 790634969 649025211 784078668 575371349 968606027 954644457 316595349 455127263 676148546 151583295 242623701 231876627 115600236 289642703 535923839 282631771 20636762 16011330 189143521 973226612 661991405 978332203 102976776 133128705 703296028 113110011 692506968 403341477 729514112 30311810 211068425 520149074 679337022 995147093 95520416 500459408 949791544 264632131 955586672 478456449 268731792 50726732 710333076 384332028 192885801 98773275 666963799 66038929 114784605 856107320 39265535 776776010 686955883 142242311 762421081 242768270 107868689 307444408 646109747 837382801 337756219 857178172 210048234 869609607 704841625 158085016 370069008 507149528 422717147 178172039 985605977 691448939 81415138 548455412 75780960 274300939 647228687 595261126 340339869 762013292 303884805 232121770 391305661 990840688 226880447 153726736 233608952 334749136 461171144 732235065 172131930 651443729 441929597 382180164 521053329 146771215 540265180 743638704 653920743 815498693 921810743 492043079 359463991 3225874 40498484 287761318 130043180 687727172 883022444 470383049 302256823 186907242 702504819 693562485 30264290 929385266 847289221 263873242 264134396 160976724 996108307 288782692 812420454 290554263 670962857 185990142 437325478 63744396 929628846 943762587 879243090 703955949 435805659 91223440 559698189 328820510 378984758 689741369 16547675 262007195 12640777 171320864 301430804 715145596 864883349 331695094 644530856 564688929 595568336 761181618 725665654 444193002 49964303 390602467 734747266 573443526 429108975 24589103 637187923 211254181 968351691 368947372 915210130 256673709 460170812 327424678 585494219 839155571 869682414 454558260 953679132 882323191 625879125 255109929 597468781 343278833 586805023 94515996 907967763 34889718 855697614 486149776 331599087 758178283 876752243 66346346 331621803 158377577 943451822 821326092 369631758 764319872 42789823 137358247 20993575 502960635 464782926 459004160 194632565 186981699 766078787 828057 69304883 244474271 255937986 519290030 587753104 695259376 613806026 495720860 730149094 322019999 981870636 61748174 80198276 711139238 980610893 264336445 869516816 776579075 85662530 91664933 540898940 128452353 229023181 414408881 483929354 693806107 725929408 531078286 880787806 492008188 531906343 802609055 736482459 787844329 321899079 176751922 335620064 788221471 672472783 65769152 110241464 506859778 980033699 42956106 70515376 813160952 159808917 792548558 442256386 97987813 884213491 983155326 78956532 113236665 250080567 415402252 659559138 976009975 946480538 392863303 320534522 478386874 195472352 909533347 118747563 369887797 86285262 454367627 158109261 611274411 372653145 120867091 118134183 205203204 16339563 41165925 870880522 28664846 833714483 313136901 126652659 570444333 148808586 58125557 683680999 251405519 473527810 195756496 79931853 420008341 588619800 400466375 750911582 784092152 162516081 869659145 6496308 248801344 176543131 164605569 860075755 401712643 137989027 830726304 606915847 154328590 724408595 330312728 182993437 410639437 643449629 162162462 981083771 644774581 220288020 517281129 896180101 693815830 713037625 976111954 113824164 301657418 229094689 717252112 938265936 391610770 439427616 944762244 640412114 615970748 109367807 353004229 17683384 99873200 36246892 477115597 254201790 760655488 807428325 289711593 23811284 303394313 451874056 4895048 948168894 672162076 522176177 696865354 365977899 87730162 672977302 332318429 389387580 902071991 49570535 180169876 146199120 341514517 124932113 786611235 957485265 86816286 992131830 827685015 186689486 28378715 157316971 293407643 641550569 817261662 583119236 665361854 120655968 34993285 522773268 921341229 707155361 44949439 470722942 925649626 132679601 143700237 110484415 374583547 898288594 12571316 554753423 44487708 354085833 532201903 683615309 164087458 619018189 528263498 991772473 658224042 409158579 1605804 951631685 50709142 818867466 534750914 568587362 792039801 422260566 91360623 565897389 129415920 988826435 36620324 907581913 974022402 32836928 18066321 201122309 783641888 30637637 608392098 680645962 384723470 140593994 216777630 548810928 612128550 745041128 393099761 270352585 6716067 247221931 74500629 57425209 66089390 609251543 478528937 710645557 31512102 422405926 129059305 13444389 263748721 18195996 773542668 90287482 903549297 791608989 143926157 539707544 674762992 752318256 72869866 59486455 892912250 289647496 460813750 357557159 887204991 706429877 627909744 893921058 953651808 702410373 803862633 872257564 164178276 134907929 435419481 48206744 557313855 564478786 914167506 673578942 435191148 687710167 763866425 338740438 331835515 907792582 878447983 6598500 512627197 951317849 918601329 258055807 93481704 231931438 615612966 980686695 938361315 96039070 727124112 744529482 798449443 530986738 616787039 815144085 665894667 52206513 863350830 75724882 469201666 630034695 749303824 904392814 170261222 365686608 95649612 502096737 125995550 826613961 361211604 638622747 630448169 132329292 896678554 723929873 216777096 364807880 557132928 7654770 460846950 136773399 752184252 111812752 667760138 221487650 926956838 186171164 126210530 642824027 114412412 595412196 272858715 863716237 352321369 443119937 81919204 300487347 797733041 60431120 127101301 11461004 699053868 757549470 143790296 448248781 333995703 360567392 813056661 743644997 368222162 126419970 880418396 120406407 238232723 400694893 194410423 165189554 586866058 320620953 808013581 701278470 916033149 933388662 417511066 120870878 229024959 351946637 421358225 26757993 412377757 400975893 38218997 111431618 11041722 34525659 412196766 345037425 395093051 77769786 88682415 615831579 204189757 821617178 588754352 442422480 222312064 783164775 460128400 661694488 103785722 120658340 215489318 872335237 54046995 633000384 993206115 283071954 984947021 267080700 162346313 249841138 668056593 200565310 213789122 679098315 235090969 625985888 876652107 482700386 556272041 817850888 98531958 760461798 639468059 687286310 55400637 714296490 322967445 515529037 375990971 426753167 636187377 591480289 151604763 542750738 76997033 144810872 825822693 914460420 264407938 988169006 164301551 784980897 41250676 378090674 316595571 128858011 856592928 193247671 611558398 412864962 11098553 710090356 25843119 503082978 249893026 81243756 69895827 572860471 449289159 445886799 852130004 937992902 889883454 3734760 480743634 966880487 1061998 159082686 733857267 117986302 999768058 898158818 902967199 41018727 128765851 219562764 22393105 985358780 265326801 633951503 250740101 128941720 196558218 129099587 632024699 446451244 62859709 701920526 871828081 512148869 323684 723958078 302658130 890207139 580209205 783401764 709603985 581271203 795000816 295977611 699257506 794768868 46652789 454741064 688303961 175418640 674303828 710697066 13293779 939630630 197164928 116550247 68572343 393723147 245649834 553113408 840174391 308509543 107550294 564518832 820658412 107873978 140993269 123316536 850597483 721202474 759234666 412717828 154990037 406751842 708695439 854247543 54037069 755348228 161504966 742341030 783283235 835808795 305554456 796577014 627955784 502719384 913127261 549044493 896442531 11293454 954674268 589133282 319802998 62224555 6168473 140461403 22614899 147161742 116294305 725728749 868364217 728045338 990962943 23354247 134797173 552174741 730118156 41350608 160039329 891623122 783691638 943322564 579948276 941762460 592415937 60420419 296998204 358059558 609464913 45957094 369353012 416655540 635090376 689156010 331396461 641258849 682133780 206527726 788420592 650944451 932256475 509301168 231506148 775735777 532655415 218819687 327910512 115289930 260170295 487949841 6913045 43861927 283788764 586861322 838140753 876204701 647281741 135138950 234264252 109263013 181096045 603617265 525918553 668702787 145289634 857315014 162477996 827423414 63842734 950898588 478367859 848615575 312716115 709874007 476867712 845371530 928693695 804778224 960661460 41380349 145244424 820090871 85242276 429033188 259468552 775899396 157754248 906750294 911038346 392018501 868529673 944650757 848152132 246964586 613353538 993441766 104279593 775831534 820865174 20638693 579246481 151749392 721770635 891962596 714139765 51154706 589850485 495349819 855932930 403028304 536730169 853693720 75635534 474488811 135243267 335104087 250388200 292997515 94370740 13942906 685016016 962900413 958593663 385684507 209864992 424463560 379126267 166660952 52811453 52507800 39816011 484574300 56773558 614103012 229053255 770913323 665257718 818903740 266263136 373707007 74448403 802993305 227400720 150083938 129998475 362643987 485188025 380386676 655641503 579558765 246845948 193173878 394975537 57955970 578858386 604840530 482419531 810501019 624017848 387747350 863008819 663833859 872321651 919782377 130453231 101374899 543212059 795710949 772795006 809475195 169417950 847243409 464984859 249335036 849843713 594983335 611979024 187548097 827886377 120136886 767106862 74732318 165827130 14598759 132688288 744685516 619439289 467624185 407702894 95973496 855371536 123228072 759807355 727693180 43010442 890260586 681584445 438738868 538487895 454379444 100730422 707905845 154139213 565715282 957240881 3982919 13214976 421736264 44047383 841101353 394389516 811154245 768350037 560216647 825753004 901038325 157418522 297708652 221178870 565121417 393682148 76550399 688349489 6005863 656759945 583876298 748782815 338344383 22615159 287270703 645240194 123345581 847692914 799379407 541577229 657450155 655878692 554792205 79186412 699926075 248409917 326092295 363596680 16759947 886308942 41866043 770314639 43727457 192091062 991493509 608848874 585773210 920560274 149714723 444295439 577320212 733591021 193078248 768180961 756206180 332865317 413421148 732068127 180558225 65316914 273645350 
838008380 573711973 680953921 769711158 126154407 929363839 95803446 489751087 798640152 834628754 384133497 421471150 878356212 576224559 265481018 339721445 14514128 38557651 489436168 458809568 615877863 75543548 651887816 236575184 831749728 984753133 649996332 416334215 17827717 567829613 689979565 708352463 141541579 223449845 330579981 267695986 5330043 278899793 609963440 803970196 113528541 994096937 77957705 844401119 570321489 195955090 36638923 584835617 234512741 526075092 43645178 850390605 601618640 548049360 86965782 285884728 385318853 589478480 702218943 255662936 9824452 244714867 964015400 151366031 468164712 294595374 271578384 473494756 573495167 881541824 129981311 539540074 875638754 60455382 383941186 298476602 256410472 420580110 735828585 490923214 799171568 631990130 193830178 253306567 32555849 133312326 539191295 417874702 722790806 93926597 673537639 732615259 191157830 490069398 736497656 659322543 784664772 8076033 985333665 210676298 889617857 115314969 750216373 617772970 28286717 986673925 768765938 284697190 259770394 504594517 775620404 58941955 136584640 969450582 312248523 21656855 102762901 703956184 439531558 678070073 797882782 965585563 263201691 989040612 455654954 999699348 500879514 92836085 7775374 338729538 156028749 749909598 306560873 906245122 220198927 334847591 745435407 988964866 619544781 5205794 346075742 395165178 64147750 335176748 217132119 228912639 356833603 319895020 932868823 648881527 997965093 583267964 614467083 113683144 424824936 922638403 113382485 778220816 15474481 973674232 116950348 24019597 576100189 423511221 930264719 796299117 758358812 528216485 637780342 230419952 533422280 836372450 625585130 450086396 24065557 842717249 531515401 380899160 15128628 316900583 29780681 865610088 900168548 496764130 979293232 177509843 271918893 92675710 955730659 139909740 918866308 925197373 163929337 494966491 201224954 94194050 143781967 959583766 474926901 634078675 42520078 8349174 470451118 668105208 310951936 494516675 363338817 842467337 727932201 230983811 11884280 610229248 96593892 912052828 106993372 75887117 942079037 231428631 21079193 750326055 371338371 792461868 675523422 535267709 139944718 876748376 481978125 283726685 688848501 956905026 917805360 731368579 817770567 240772837 251990147 128722496 587805878 467845330 823706200 315738072 698829141 835590480 925967321 795423034 600159667 885477059 723826517 394755063 116905683 597422077 145081111 340760420 242400304 673120899 876028129 382345022 402385634 358006247 666071707 91234129 167427633 436393426 675119074 985198200 529682629 779625587 966437062 117488500 247470910 642659621 285742938 946300052 330766460 64226618 594239445 930926127 949703677 170582321 178197549 919125726 620520764 323278661 112402506 862921068 996399560 988430635 245266083 251301554 198953242 763854156 195052049 366380875 52763941 870171123 351579068 582446570 502313070 170532489 699935070 749783980 813192111 985678009 548600391 143958564 49904620 995356202 927401058 852124664 18454883 105598600 623766749 638975647 281393627 736169255 501896709 130309547 577116250 599679158 381611101 776069492 363533308 576663150 142450360 416297249 299350632 346545794 998743820 801663702 517078283 551195249 403964042 330270387 389389617 952564433 326745318 291810604 800436995 254146369 996451634 818891878 212261335 472734742 457867518 493654963 61420357 812280593 623964510 638536607 411959745 5575604 414606092 628009419 582238754 409572818 44306661 881589386 756118612 895566847 535769448 273196888 299278456 939733490 455983642 541184439 744814282 782728960 832995043 545251270 36875322 681963036 216659507 101653023 154697772 674527026 595307986 216118129 339323978 219272489 854654736 751283723 77364459 121777187 231809501 659603213 531350005 128632529 393708959 139984976 24199369 929478407 413181864 175994191 721728256 869165506 717178631 466542531 504410825 402690033 864310168 393802513 84653063 80969668 495455537 91867201 608013060 90763516 160501696 947337039 162552372 15156425 551137121 239916831 989449985 782946623 899520045 373316349 911579152 145745363 513301325 788294887 927740136 926483189 964289079 649468385 648165055 533984069 968527282 5092239 789190468 832837443 398894753 726359897 766323478 894350290 818227098 374336531 985113806 978728794 174189929 182537 846401585 725327051 240099369 688367929 508273667 139619407 61684271 272369178 137881136 574985596 60664058 65621265 353985145 877469503 567606016 854666566 263969931 388649657 859758805 53160393 74003460 258653551 779520290 840326938 5520200 450263748 67179828 990634007 281508901 241369758 990816544 980426853 966696809 83432272 668794775 327486835 75568045 582995413 599856013 213449181 10497368 660520071 131586812 364482513 390505934 551709194 71665438 654475865 940358852 931424244 707636258 14362305 42594154 339672908 854689243 48114355 642453022 921869071 38748355 923961923 15755188 882081265 756905135 982451997 965513538 278216270 309938825 41081576 861211683 909794838 107047124 871709051 422831269 91150302 88707924 813337203 642859497 160373362 320329427 583218342 91797599 27965679 450097013 134391754 220154953 157302615 182506109 862607975 79171679 73770830 639086257 94926868 808368461 248507752 929895231 626398358 526724022 92350416 519996301 387935698 2145247 627043425 112161108 277492882 718193727 200869032 943346451 213569583 361242395 263675872 796787925 453039994 144157917 99401297 439948114 216829236 256703912 622454223 79437204 188391958 548741419 571039827 135835192 357109874 819547579 65730416 983508232 198787960 158080832 356020892 586723658 12742446 983064317 698884767 142751694 553774404 899753799 86098139 767343987 113512553 202290377 416648272 566552548 346448294 516049569 6500655 563277530 772753482 481471245 495231100 961145440 30212657 918787293 96980625 239838897 590851232 15227407 75863489 789639192 25824606 431884381 228879210 38567052 267465058 927763977 181318746 673755828 680034135 119933251 293616174 793546689 322223628 710264446 212615596 668671922 78830375 71632617 84465811 704100223 405620228 432213277 517762022 288349252 351000564 467259013 528188149 941851796 482486420 456568004 584007347 508311026 888452386 812886557 399394444 8433803 593166893 580713191 682189631 125717388 700646442 975805805 919264077 22870064 538586611 984396039 544058352 469933352 56028649 481040530 174033568 314165244 913253807 691795590 602514496 116770730 11570962 130702638 58622519 494057382 439787009 495146233 854884775 180755754 308032783 254279212 189189557 901199677 687508769 723895554 26917058 240671571 552217718 798697501 116058001 90804322 635609899 660116353 413254040 544154914 141156876 587287608 858320158 906927050 131599557 460834647 23697773 143170519 444053652 934836666 489744268 883840661 429982892 344629036 64596408 590532041 451424614 106302331 344248077 138933377 830197885 223681501 379604948 234931962 22378995 495662949 178252651 510505260 8295661 591506691 54660168 1968904 31310659 912980326 908895954 162910216 226331333 785110093 158597102 522901351 719946752 648341370 259258371 2446003 992970406 176371145 592978045 296911379 282673476 937226122 435844756 965387727 13423983 667966070 200319682 35802978 16145378 378572333 398824605 24441040 970079025 453484773 26409944 1389677 218981458 787822264 16816259 297829157 425448716 175413361 820730508 145395462 823754731 79988872 357831 669241496 256360017 445852242 966152876 391549859 235594724 254513991 356937579 249018707 922480062 409773628 137338051 938625440 788345961 536162656 815582846 610941345 989647429 694509156 464847388 61145247 334847779 334180014 358974404 760296496 509593375 32221272 758208324 185864466 112210144 758566155 707622328 221086528 56934757 526291563 612636387 292529481 780805555 969573967 541548188 555801976 231863954 678886239 346943775 20209908 215048889 15042981 483667620 57212677 709552137 801031374 118357924 44399910 135211381 329848695 804696406 497321123 362069967 415421089 683185589 326796477 26503603 243324276 547883005 83438360 769615840 160519386 375967841 402937754 982609719 917516029 958739730 214473666 596402262 158199864 87199940 663967517 173242845 423383926 721180194 882794983 224415294 692054485 779711259 212143041 874419546 436924024 709464164 89005872 852345113 245166112 415802349 878848716 488490389 963685355 962287077 258106222 124204734 338254911 661043976 959330819 108287300 472300065 26320844 704689562 483016295 113520784 221173438 656259141 536904711 942353632 391570483 613836371 486924476 23798101 825979412 213860381 460722125 535443570 302866253 313067231 780609682 718668603 44432306 121616430 682353951 6719376 379722652 659075051 197490654 893282994 470922229 305777954 218099418 497243073 10467509 701115714 610763857 84157313 209891214 184927 26510938 601461697 614021298 365951781 625259798 292517070 579812162 85981916 827960640 882678416 251565513 461086681 453863378 295997819 582703112 136217322 155233562 814942130 647808739 352724216 708225118 118730961 658502170 926324536 468490400 521486045 479956609 79254250 605643358 689847823 931955551 484670662 143825879 398493208 850622443 769085677 691010278 282950965 707583959 371487277 18145740 811665838 832573959 472009118 107663651 267793430 460742806 115413579 82735553 961067911 468137795 643477037 932315238 126639958 422317933 400805631 648126003 902274542 332576247 106285720 444638725 117048157 590956382 588464604 515541366 294095185 210066641 206551637 577046150 917650600 578038915 447708256 581832798 263129233 919717374 542012815 383439029 232976539 657426394 318690948 46560809 125564182 962167986 978876047 104720506 237002278 232198037 752846509 991793186 564774284 859132229 436431904 681822442 302604970 24896502 49880167 596700155 87479509 256431804 26262664 5130102 686987085 473970920 439479266 950116318 246204653 981492081 186071706 479181192 638918468 504762655 525742001 616999016 319447000 357134407 721719522 556449278 589332444 327082390 400758823 6623088 38730978 837190728 688445530 341335949 714603596 738325697 938036104 802083105 847273867 964298769 659729573 534260946 438269682 99208833 336893623 684474336 933217280 522965330 16171887 424652108 27727978 394430255 41651117 199691344 751564662 763370640 756140622 340897100 90453023 9415804 347520188 129184002 846606532 888482084 323036317 413726487 479324140 261072414 68325951 326598000 77887542 580571891 713375312 516157225 532297090 50268929 53147920 465514363 425750625 69319807 890166471 305994969 316266428 784333955 505686313 67831084 400220954 114343294 261244550 343190343 123759098 608764738 324890711 822881997 349763181 647927028 89124843 829087321 908999443 157450795 8201680 986886985 738022686 721576993 355560569 122836135 624362288 261224855 588350498 50112906 183061029 331033329 208624241 499327457 115367277 566826920 567158541 368104597 681170214 828403091 711294940 657445678 289684188 36185645 480327668 639447369 684112673 569452512 321051049 445628475 579419673 329252730 285031820 169958718 50829716 493108755 292794853 675192004 754333611 881145351 577821276 937394640 64695039 638961883 436722090 32578682 205788796 856396998 400683279 739475376 537316448 111978213 396921047 827000637 680224 729765082 318964365 537309263 151733953 640015415 982937739 731153626 969268145 120485918 901112344 872614227 613594673 193907190 400322590 220444643 927568907 978143866 157839276 992263947 469622108 447077733 877358995 675410904 303474724 130558634 267402639 840791172 95053213 664323686 520308168 95733437 246605127 691788900 633042700 398339080 184320674 468496798 129492699 6105178 441499082 30605036 878719405 55093749 77028592 279041988 128054758 4597493 109702213 285894035 849377806 579324321 732971768 579253160 107251584 888962858 709811794 374654223 582270389 804865007 891494275 102578551 900598444 138099396 646883817 386157504 536438476 831204491 707170668 518447542 837309669 148669744 401568944 716029067 56279859 478597537 847587421 184334617 335711396 957289634 322745018 37605561 389130314 55716779 616858721 348898264 797196003 179186875 723552487 379466386 984051882 467563121 334561303 737166686 605662517 981445120 123324183 994617360 665165970 683011217 513064895 502475632 831680961 914633839 71021058 740477186 245747735 918608479 924811804 433975497 728414472 100073181 471581058 970061152 8306327 940956146 318959409 805502330 120143014 895028262 37485075 104194889 362591376 372046378 693877941 820770260 206007857 669718490 815387613 871173827 352729701 180968867 226165818 36927021 948119072 149703242 777404208 46383167 68311714 554732371 480358664 649242552 654805552 951939723 471820063 663111879 745412228 790779472 321130569 865555242 538324093 358615644 822266497 900915470 730662023 368660798 574202089 789186246 38379281 242106061 512876433 243625348 423074928 739042251 280552370 223710359 888745494 910472944 270093526 809573574 317721674 750452191 311332486 972527226 554908273 783152549 488155465 300320494 426448381 809286034 18392095 964772474 20418037 693174958 718204303 751080060 61835749 144922751 392782666 100215031 387028812 905659099 196356745 810103740 497217709 476909115 33814093 238479562 239898418 156423985 48053130 557620092 906876176 211901982 382663678 461784442 847570897 870819143 614621302 126535637 532621536 633013397 91308105 553039573 178704715 662028774 156635993 240540464 806951526 549418659 193271861 46496697 307594117 389628607 856600438 804811826 719054088 742930897 43291382 958952507 899354882 943860885 516572592 658747418 8279226 899236270 120531853 855850123 622571772 587669522 982385761 7709667 73199278 926210232 413265607 251903993 440755365 569901600 492444458 100223250 971836625 538232685 146719948 279430735 927861292 3320379 84242554 499431740 598767642 980050309 458384240 350638883 923911187 827473198 9386294 932190413 579225828 982434521 640556896 54313959 422620402 622942650 62023627 495819680 401669241 475289234 747723674 842424606 897707200 92684491 942647857 869543818 630917176 89367798 1490912 411294828 945204550 938249839 910726568 396488551 918300142 221627167 747127434 694727688 49100358 609030095 479434461 628326186 443980975 119991350 682640146 866601377 595450366 597180139 214937416 997119607 72469366 962661090 692060572 822692932 55345574 634708422 544753109 686262751 576592586 546244021 97557572 521797129 337010219 860800506 918285680 107826720 82427666 517929474 802554409 131528024 979475935 134505229 612370577 275973269 107012945 147527082 142574639 554979677 744707221 210028421 404615643 669692953 172689505 96676208 344902244 80551445 583900997 889655353 766814196 160493576 288415733 716888134 534807072 625425952 430204999 305609111 733252673 512632665 823538585 388323441 496677056 655530879 522828670 961563999 931504148 482357981 109091074 926595153 37337651 706314661 136623568 441953294 228523973 161829439 391145868 573426217 242380884 975046865 315597929 9195074 135540435 604013662 578599574 522863873 229439607 8804567 828472984 962692280 373953598 504527929 203532080 723147020 160058801 726360750 684711012 91562943 61235090 646318452 870674462 98572741 205149472 7298023 393042401 286189811 21643828 784188270 859616028 264024713 759235128 27730316 125736153 747291929 631743978 704335727 122672161 861183586 565656660 951145146 676392225 792126625 455673068 879924306 515273638 468248235 458801415 52501010 412327544 520036506 551335828 283002000 471125613 756485301 142816389 864168015 42675105 164460218 648356278 754807500 428484931 260107765 782537816 554221084 859916061 266798154 111073170 982588222 127981733 529246197 933733361 656890324 321372815 241922788 389330989 689162819 710171024 700648771 741663829 122498561 73201636 145516017 258016927 544327249 902001318 253349683 408495257 797192789 417809901 909367901 404516648 698811198 21992026 39570824 105548641 881908087 306368978 216621811 864496302 286867077 745868008 650746023 796273767 919757189 745185177 38121116 608920002 307872560 738769887 203100190 282887488 811971523 348616207 540904415 356298765 103133884 794254098 617310389 752843040 64580358 526678283 9876047 763391556 548670309 49446871 868940197 283094755 208332215 938078375 107417 495199292 536462742 650853440 143989419 456219925 248554976 182110535 917656293 556427537 920880422 120756476 839315025 732851938 321889050 232735799 941667069 277539300 26989891 558977451 30382333 944086622 938172101 40258381 559994538 339358769 89705252 281451094 622453525 150553834 219529462 622560942 645753126 755992205 125930741 789742545 64728489 374485717 971853080 982384782 930913254 745249861 955657624 770228272 330618158 130063033 2964065 272285221 407602334 882470329 683779038 290501033 679073310 621951132 330759414 239067841 961309902 272981033 520518936 436279786 423534867 592564764 58840721 921804359 201073328 184771462 564063264 265801817 559257179 388432703 100702958 342686793 133682558 908876949 112915058 464300716 38939975 968395496 589102303 299058675 703382184 272881335 589559709 234971854 747348833 772835489 474039695 561175094 45816515 847074997 997454880 321867748 439639755 56295594 96188467 640713083 93583422 660251731 759031267 505356968 48684427 859734225 848043761 34883351 621127533 813475185 499184068 512583875 634387041 88286364 811642550 190285584 213684065 253718618 425257438 961032899 26554101 899297134 374724352 924886989 598888490 372179226 99271097 38528238 280991186 195459564 531757688 227090975 855711295 143305314 732447943 756912088 3039532 580491697 791795440 476683432 246483241 143495867 989267307 880870282 84298597 653426216 71155860 297982663 907144835 496413298 111531921 786215302 248226791 486256273 563618650 847115282 710951865 515406113 738159886 991943052 710865677 122433933 71550386 419093331 265739247 803998329 28521779 121295146 237006385 820317219 597978578 483489626 963813086 439762244 364359902 48111676 93188453 288032128 198610705 852849654 784445426 310142626 491581315 885188584 648915266 55199959 584820225 359867124 423122438 175496470 204326535 133988109 297930404 275876921 405597806 416186017 79875243 434119585 537481163 169397994 106953163 987976107 652887621 70766242 427738344 17247516 118877919 373443164 157796010 170004990 226292811 942241436 480147617 717874127 679946379 129062876 625590452 264766597 341446366 48712883 440263068 398289268 35217358 590709838 674166189 293331531 6895848 606557799 579967482 396893378 775955793 686920646 384869478 281359773 757686888 665124189 151123655 729081173 38567346 308919665 899086164 117376523 103677461 231750140 835250650 783623840 213329382 313357461 48390431 407292114 214586711 341169865 805581382 102320435 931879703 332263931 248168332 791291917 938821730 828135815 188185288 567293882 515056454 425571133 848653656 125259701 90695315 999777311 706857241 129262661 161213336 458459764 99155550 264890797 690209904 934406201 48514630 756055652 100280021 949421434 163347759 167383098 143107658 968929142 269703534 74987354 153709432 517871866 718795638 92531155 198524040 906980926 512341403 713580494 185068418 213511418 691356562 275763733 65805089 398213796 257542760 227018425 856673560 356698311 491909222 399399823 143620871 392940218 7971834 96417258 342361646 171319593 263800357 485469304 992765101 533503891 412973025 146474526 903892123 131768656 91522047 102416157 891265948 456379817 668513017 76334360 669891235 359869572 204614459 588212690 610599734 314673586 815231115 319789653 671371897 159656696 719189476 667509134 552596915 727161310 763926392 747474927 750997270 27726742 85460590 743762364 413746999 498433615 742753257 317639116 482718637 834275304 272571639 226500945 143171480 941084656 155351671 813062716 153470588 212482496 253791765 764070322 527156082 69022874 83859969 51044338 81195936 655565811 718553472 486309217 235243481 482479858 233784137 986240751 362722966 319244728 582519474 776469966 670194709 325272724 94109075 5429706 12064388 219197080 231930651 155235868 160281729 239798688 820814950 313752317 452281184 74606709 77822633 979437267 996145956 14198968 30481598 77341885 669764779 749035071 416167469 905008260 84031288 649951606 743765370 446754254 821712700 326284838 75740579 491907403 504073928 22366020 497337109 516138316 241563100 581784126 523890551 401844830 821582814 344705494 568113513 273863991 271828569 498452512 105817617 267974518 512651480 136299216 197832770 34932619 737850653 614000239 792457245 821881941 116468204 536222609 121152554 938180905 715023813 196893134 282604667 219097734 219259154 632458142 587752417 460822255 214242261 111642961 715183451 35825068 308864821 283296957 162205425 580693391 781749470 268023043 848667909 146917309 256838625 899017045 34366294 994689278 365533643 826823540 669087578 482001848 215562508 790240132 272699112 930586321 839649632 407820145 2200414 58908780 40278280 589952831 372247401 107036907 701595792 87430845 142861975 10460607 223244168 157583766 443670364 857510004 278123175 144854632 4427307 534961800 43871671 38793601 529651071 409405314 718133507 51255008 743923528 933696015 841495141 16622633 864282329 533661132 276959144 866482744 445086278 317237424 308951934 817333679 424274331 10547720 757280890 419652672 873524700 833041425 429752805 169711423 690551422 707875980 314566055 547495095 242837774 358437726 438805063 625005211 620359407 9454929 676260220 364282928 943150945 370271720 233421928 659949633 903932852 510381072 378948736 349019124 680134863 687900671 18869162 104409187 550964757 628666419 376578226 277005816 461707837 806331031 446717239 4775618 366723370 761283294 404787080 609561144 119721014 843592143 87082715 592596787 853047072 763342935 956879715 648714376 133614648 42818002 308664003 37547493 405715441 687612739 239082983 85850297 228029769 110468512 42775850 778994526 739134931 271870442 56000335 53359127 78201466 502717574 58134745 297441203 116517228 462921825 907002347 88754608 159030327 994085062 681351395 864593766 609944356 490747469 513308135 743559004 533565472 674488504 633622864 939280913 214617603 725222213 877647576 442647372 835690725 920423426 221641892 574825649 44810228 130158593 628184776 123011694 632876168 538835888 272969263 749393396 1757706 32487970 838148004 13304400 26573025 372015758 877898166 489033748 862763227 243722660 85109111 248845058 918211165 718731975 40642330 132828761 296470548 918289906 427992499 132161266 691229692 649634391 559503282 736039920 779792985 40204417 711567980 265185512 579040305 984537244 867095274 433314378 17025207 557759637 446618778 896114605 929775395 177033303 385148346 792538615 273272329 470257458 41383667 43999853 41505792 82025997 29344980 337976340 852832270 457337480 322653973 544061955 106971864 882157255 132618234 739281215 922361672 844186214 856983093 501401971 828723451 724078360 934716349 698265024 134354356 233851486 594379623 64129744 263401155 832044335 709184726 536673484 154818152 603084759 580673338 196323945 537627122 610018318 386816651 390459385 67355791 709470624 787037706 26844022 591627872 919655940 618641603 366505904 763842148 475624690 867907875 445081958 52219409 655140583 143346976 186573766 741508435 590242965 103219876 4909583 274803659 812404602 541583067 429621812 415489354 122256398 625945757 953116477 584791083 12762401 196092221 652146874 574749392 983129928 531507262 18893623 755302227 150148859 385399527 371660734 478289915 105823761 816742693 530509324 760964344 812606035 569599456 354989138 255365359 672819333 359898721 530169018 485223928 753998155 959790830 753229649 728770919 438252946 558862485 313561995 303531714 754954706 818225236 878281106 590600993 349732491 897174729 198419580 352397716 135090616 570080314 830687631 240914377 239339366 213713315 1878715 51945394 783312771 209384219 159827119 456132097 569282941 542512504 793872392 175797455 354819693 547102034 904568374 793072640 105964512 70646729 949120720 713435584 888871965 679918185 156552937 91120815 429609273 354972517 443518532 564699889 925052831 274206156 805614267 16908557 487919471 660009348 68853951 123748602 869393567 81197437 579880699 291192867 623709941 226269450 466990322 978529634 773371484 371558690 624118633 731852362 442205419 425755712 297804306 183593743 105673890 306873609 274714558 535283164 661846126 718233090 99983046 439415316 992439247 758113679 456323873 332875077 418123020 377694191 456623679 140032947 311407994 889020745 431225814 935117935 115290188 898216137 766163928 741178039 122291186 242798921 325546760 564496605 668554633 623351066 748090348 626744890 930224675 22804899 14544413 444587160 593554356 114527459 736518843 438509962 725157505 45359075 771385039 143280518 423053266 80525078 135829831 734461260 969545823 567055646 522095554 937352377 465271776 140775842 678530409 587562962 236091129 4077163 4575926 904645762 479944595 605182640 383907011 262685630 480503905 398451424 559789156 74058254 365495250 296307992 512568216 90652748 341667068 136469615 86449632 617236700 69511059 222279464 204214320 39056875 789335110 726309874 828925618 107123245 719602082 359972387 547202573 955693211 216565916 551778499 712855333 696510511 9477498 96762337 811712507 489981403 495213762 371501657 564039658 860709012 520326015 929124240 803878126 861993083 65593848 890327758 331746143 135104907 965123588 535960463 26678148 606975057 114786696 708120133 714098302 834388779 68092513 113817234 790081983 284658429 665595733 355453675 833685306 675073231 452216013 645397807 17570994 799946141 869415830 581610652 513171512 389741838 363251251 317049631 104251281 281361466 59893748 435997424 268982739 25017330 971957887 148177254 484508753 86744576 856297387 51123415 773649721 924389900 164940649 416248064 61564688 830536383 771701739 895249994 358125973 76434111 393164160 375696967 876380252 115096349 809823985 389551757 504838188 173075230 559117754 461605835 454436696 619011503 897603259 723419435 496545199 722077505 871596689 981053952 661338447 580410435 32177360 287504528 357316694 49634376 703752592 418881382 880170759 475454324 166647736 90813091 551888436 412328262 319026425 280785047 527424612 128850403 670336805 32262793 154441999 81970918 346384994 608878695 700982421 96504612 184814490 50043979 818582117 908927545 883614298 332436923 489337974 768308024 619941451 846654668 817942400 176210402 118052410 550629518 651664727 137216512 641442610 56069522 549544774 960469035 336854569 76969379 941835804 859707740 961748545 96277797 941678659 308133532 557672858 495177439 404638144 742487348 545221419 75736620 503931253 281352076 260689910 993269227 49660093 880631361 692440254 867602494 56841757 663009030 270748371 561022850 800225542 912190981 469608738 349770310 725176375 806463307 279256055 519528539 518687407 241004594 615806336 460366059 401654492 25995553 955543498 806292637 768482902 353281276 734545623 124930514 634633352 995235533 118199734 536809812 728383254 663156354 256928665 637741377 178681744 527677036 51280586 978907286 292384377 520889324 181193955 17560745 179868990 460450011 389605650 698556397 701454605 5411979 11438815 103109090 31407533 966982314 761918093 652406801 172779949 348980076 777337315 659929668 344215602 748053415 196739473 72598849 263726128 453668138 562856592 442407872 981345174 614137178 273831518 126245910 135026495 455025473 143806656 314895486 915475484 385928672 13451876 469446448 243857018 24890692 425071905 127780917 844389372 39506357 780187718 869685687 388486433 410041392 529615348 732702036 10611166 578871187 657817251 126853660 32539318 73190203 569261533 866400859 687327381 843093051 992646769 822353877 150634883 988969791 989765729 66110361 227414823 855733971 535556809 471271841 733141029 960628714 599052758 430046760 135065 231756835 299732441 241137864 641798227 681864155 973839900 504925759 260735336 484173511 631779419 145791020 557363714 53557311 864708245 97207454 896650362 709871374 919561331 47285239 551357524 761843419 965911973 778772347 617577384 353985141 250044181 203234772 167130215 849096939 633281533 19781646 80853767 933013974 260919510 575168360 467394488 87275770 80094112 728129824 571449281 564389898 726437211 981329361 617947209 591145449 78536808 367113931 153533182 850614506 266915536 704890707 612457918 232827502 483663047 82551661 586812643 586223595 285786434 753942858 287836893 919067967 773724504 221207027 704598300 34644008 796375387 24509147 121919778 728985866 752638972 545885425 145892123 331592542 379731145 763839332 922737991 458267953 130953256 76271167 161398818 397868792 633678240 773856737 483212660 117341280 708924764 70025297 556081241 994711198 676484521 843918135 766295524 302725385 65125155 323410183 189885759 714016908 347919331 164321903 295519133 953074669 562723694 441411256 284667204 942454839 205250582 59921554 253239151 188720204 988709094 414637970 586588997 622387327 41011066 69801650 592244974 749935830 992343320 842574 597163388 521344201 844760709 215975271 676585952 909885864 539385455 866471711 476419132 739821152 883309980 771938265 692895814 446033667 213349515 830079384 241004865 271116463 890000938 494244016 459836667 731226392 908881986 46425657 206130078 949893052 968743681 798375052 699828876 813603360 799217627 149508623 187463920 496494695 365483894 864049872 258896919 904869349 583037942 735316051 497206860 318864281 507254309 42619033 764897948 573120190 872698417 5902806 844236653 615215715 352663189 304073314 346442100 261545168 203015337 552572178 63954580 24275377 203463590 763783456 690395104 855197583 913292079 877859024 351692271 131292332 594425256 610589190 36161675 29979557 198421600 385884901 348843839 705675910 428503935 966258153 131312459 301202345 824677326 975549113 916418060 177340508 132138786 115376519 291402042 335154123 520465064 355356622 211945867 723928654 119140071 902340971 431642596 884948516 632716354 783334867 16240842 79657969 246440417 904918890 109637527 444862017 143320150 310997732 3054286 571824085 277255878 134366746 873026431 101933197 109915852 641960850 131790071 94571004 609853736 423192114 429725127 130318793 778548736 641670994 706763813 750205174 396528324 138406402 487670049 29244672 774257635 356427257 108902641 20698045 113862506 71056534 318076429 257182657 382054266 173647081 829006742 659310145 308013827 554549532 613759708 270446045 49026742 598066146 365017049 658880478 21258253 647258543 641715637 652323355 141445896 348479443 255044888 537974221 339402211 595231304 567218893 113659839 951658561 528637900 986874258 918037434 599694435 157467046 27736450 981748701 331114127 856743192 493575205 639127955 263809084 107334907 762090366 165352192 557917419 127107409 824232670 431692038 626882318 318464666 84015386 768328214 666944109 191576641 306302428 6346313 786807945 726037687 972522525 590982865 254675581 959396776 361536658 854370016 116863815 389273108 688635076 300494309 98532660 182210275 939622264 362341744 142061548 554228989 527693936 699978967 533852764 204442965 131670998 160735075 522907631 68202750 929063290 42368099 112295757 87882077 901230785 751620068 813919765 873753303 195119293 921111712 685666439 556655951 627998087 655046620 945929060 316633156 955540929 44461713 351359797 747679552 259319823 493421345 154424901 787013759 45916671 688277665 843973090 30104035 849012741 219397080 950823159 630592390 261765179 63118909 570990833 15512323 667255344 237426957 889265626 862374637 158538662 427448424 419030581 786536749 935011411 217476000 955686272 743068699 261937713 307046062 343264611 521257536 652983774 497689512 160787654 698900445 185967170 4760737 581520847 887496277 76674183 532343999 370605026 338439362 447979274 941595860 353951685 115234611 179022810 95733671 830125614 190077839 375698461 101672555 976614588 310709865 319148555 784817219 53778558 581086269 91863275 249559535 954860171 597363415 747249047 115647819 148780219 933216217 972924929 730301066 673228854 49599106 115161424 43833873 240554834 563140699 985429733 447022886 530891676 16968903 542756557 213533650 207046742 918455018 315206205 36177689 81681243 634354760 820994909 987976174 67957388 765374550 237535702 22817553 215254324 984784749 990981745 364034543 770517325 816423033 94335603 296262538 718538505 209497027 340096412 959093340 625154092 178042504 258632585 8562128 47527773 801389142 222095778 254574515 572360519 537301983 143268571 506558128 171656736 964263480 494534295 239614125 582154389 584586363 114948044 797408713 421887471 105929782 13959615 44921156 922352815 108295218 341183694 493407680 170308612 681280106 305017379 795462704 711838977 563649964 804024832 759366750 217555465 26120603 13941259 789915984 563422586 9726196 148990472 587595689 973989676 643524767 827209814 408660424 80627490 942157858 58585496 502514961 900604006 72545111 547436117 675473180 33356696 888619812 168880853 203665308 422416277 473898232 999128012 134255247 37548189 803152838 893621998 107620020 681789807 760079623 897536005 97728753 769805819 46526470 685324442 596311854 542567603 365050615 857488644 623195093 159724832 916074140 125710048 60328831 841135617 525662531 735802011 874492313 414282336 757199231 78157614 836698614 83613822 77285620 823470227 121162012 732954824 569608584 81298398 267260990 182204566 978834403 364989743 952010385 877877239 50314178 400838598 272961202 415364793 110843601 748672661 575089625 26917734 726899075 487934822 720569718 252561600 76253193 595062024 519360302 833452424 525736005 208575275 917066246 455537991 32045496 890744624 41009174 601654080 972043023 308270164 783858647 803393785 673259908 588385391 533787384 723574086 841740356 806748586 991455246 952583957 407937606 419061230 832018058 134836675 906996053 552587769 239914641 983249246 166152 759274943 816701663 525902157 967850219 586284268 981440148 999895715 477028886 22449315 454066154 301588268 183235846 90441160 104982046 856495754 531342918 638769430 432586199 373083267 298034375 424041438 178183583 705971982 843102669 10201634 693325023 602615081 415305769 933239664 585864320 415471922 692514600 255082342 793890445 512881178 841366610 627846953 365293252 170911855 502812634 819359407 472500123 686048480 762316933 429998536 542544227 293659844 68767959 975130427 519259477 219318701 251688224 697443061 777807049 947307259 707644695 471132065 549922333 122950458 256888088 988303019 390938746 949402688 95901720 37345550 314800226 937268331 665192503 680093478 960696552 168005131 351969244 285713035 854053611 114286171 715711571 249114198 260462381 636995896 76760984 779721859 856314597 180965574 477164913 486638005 128272827 37325967 957770070 530711526 12792791 67174517 519014539 256247903 16577199 614916259 293593454 183893791 404700949 958785957 863987269 217913861 126791081 215956507 503626896 833361059 182759044 219338460 934991623 443221425 856334356 11752600 222943277 565165313 45234540 552624556 51803311 173507367 589950524 862089748 704218894 455259681 929264265 75749792 711507585 798357830 543182417 5101032 982251621 947883367 963886989 698755250 18313587 943194437 914711757 521940483 629071855 97470794 741278943 416579837 393208585 450129658 280848803 616151863 867811337 326083343 21292778 772131015 499590711 611243302 486737122 56325964 66502977 268517746 132075756 630526928 66875570 527774539 635627960 901643557 328174265 452031308 452915166 346487852 247742104 220143282 868428335 729330325 170130442 462223637 145910155 563339028 912353296 426758958 32007250 632680992 752842302 53300028 404812000 104949372 664543331 891549122 13791702 583562674 12583228 145867458 66605961 79458798 526158363 702233921 833618721 854332629 6781588 139050247 200820474 107040059 359193529 69248803 836370384 529323972 383988806 982280540 92662993 148858461 261555857 124670243 781539454 866914525 177970271 38867813 971863897 695029968 930416936 985655599 131109001 943000164 984039423 197714962 874975328 362714146 899948883 561110408 217046768 759246838 700160655 270383608 866286897 59354178 192148777 702657274 441194516 576137584 537454173 533857509 724996045 651526397 511044118 506535492 518440915 689014389 545403306 342821172 236560717 328336601 180993130 367669718 123853124 17548913 565384681 851344818 380263059 317849923 264971585 449826193 77096754 965132241 720209801 943383651 877002785 912358579 498557285 170713660 488496156 888527824 704571169 66008560 540054214 68131646 572544053 911011496 757146035 970463725 106349027 993706752 151316685 287342157 213892830 275169809 157407436 779277511 126514620 537670495 97127427 244002571 987496688 26740548 61651171 560222849 970124199 938653956 472581421 321197843 109367609 813593943 62242027 666455144 879602503 602296241 734586790 304662915 365824096 344249185 275126633 472173123 190472296 426443318 759515281 404365126 554129493 916922717 36158996 533160479 307109572 133286424 777163051 147122619 160026972 838814222 707345468 982667537 629984538 32443248 156381740 591868513 846037191 218623767 110840017 578156054 820920008 845426807 882818969 39260464 42192351 10461962 511433587 85181014 436905280 123465227 489546140 991034774 40387938 525705137 376711612 200013876 511507927 153874656 199652861 671534899 992688879 906998330 506718795 475189776 791957944 663100535 67058282 490511495 881724302 177898299 68667542 555160670 875841473 951486511 594421134 918033824 961948473 105854714 3214831 251370113 229319942 345277338 94921246 122224246 723498841 471632858 174754488 235006761 478023881 374407349 759058026 323229119 133922038 265776814 798418895 925879983 928877350 865477177 416391471 663118011 895891843 337575379 218278674 771733309 141578249 812699808 542283492 103526716 771070889 398014690 207413195 390824 595808394 154850807 975131443 319307228 626483665 149885924 406830355 104507539 524293273 165888374 280253024 658215312 284181554 78671912 436611654 65575263 796665456 853003125 728693275 692557292 43094863 946971949 316806960 184673112 612188117 711606818 140716194 235775365 109621501 348129389 88682555 557946261 502980196 63813991 877253489 981980228 66216281 136600203 939004133 590509554 302488577 219257151 101241225 586670132 150445429 537852879 652245395 947110885 243372363 233455029 492184536 286467226 32943338 808991496 471140339 645131455 373114674 611856533 880906820 335252541 812502289 969589375 893198803 167998844 885919732 622968651 149979065 952136013 759568855 88983192 395161926 62057425 160756709 496403152 501243923 311202138 886772397 6005678 110829383 130144754 239460707 603013919 269128346 272404045 264521775 592785051 770051866 637636449 57157944 503475045 972888990 869660233 325580779 866087786 37659070 211500504 341572797 40154502 16152876 101141645 129137694 411314803 15715436 142410769 907717955 369475726 306129273 647006711 375481404 416958656 629667831 467458477 19972569 898796178 739862523 284494344 344097588 362430748 922130793 401255532 865905794 747536142 270915758 191486566 466140288 161091195 255503437 807713085 201245697 271656313 908854730 182899757 682971116 777086532 325310526 443205430 146562251 631439799 90212135 374560021 48398449 719879966 842018499 920887391 471192503 434397381 57898094 815290092 796828129 980028887 69061983 662733916 580081388 339977742 706736849 46221669 501068937 962240286 853934754 702314634 233896592 615305843 885214391 916867709 244908735 63041276 212589498 391470986 546997441 302801633 766031008 447912256 875197966 460565866 368799640 198906828 894963247 426697734 14196913 691791369 259242980 83258897 207041645 839324369 275753005 913778494 738062404 629338308 728535139 444513518 184169301 962431731 59819354 69383685 731815799 157244455 984941334 944405298 548715442 531938768 99723290 167262809 979851025 974921256 627828675 201167024 26344444 375308281 480381125 40541357 67099643 739624105 976316627 126657654 431464833 104585991 892952514 22043597 733924299 621487646 466557115 918093600 436435737 378892835 839993651 20767895 536137291 677451344 817689559 84852726 61906472 917412850 104631901 41757490 744850465 584976942 95440880 771194909 960285223 575822005 664252633 879901232 167962470 493085619 6558880 451943669 450187977 752027760 473987266 36628635 226031766 940544381 954722236 662467503 319437210 647232246 535751764 855574501 177199950 353441317 792943593 239106422 123370526 750091860 133380278 720737357 335068795 228821158 344448626 147870377 657159530 8701252 27771602 825122000 354303237 886846855 129582028 804491214 638874609