2084 49078808 443885260 497456914 349176135 735711378 301636760 260291713 454128589 636174802 90926039 441712462 897323882 619968535 520944536 586167541 778768757 274185193 446134896 600220616 413508715 930645927 968388732 359482756 148410397 346511159 736893740 550141516 183299147 449007263 172271777 949904783 328034332 87457053 210733792 691813110 204162972 699008168 833717346 55300918 220964690 715460490 131078159 54546100 771336945 755951163 901580566 890100143 166644242 745413429 621914518 371805760 194466014 797018440 449015928 372741989 745928249 428861929 258730945 966727552 247714015 901796940 195599441 162529932 360121126 471612786 850461005 884915023 846210488 452110225 599859348 329576653 598169575 597073473 238393091 889590128 769286863 630282673 917151940 952582934 747016893 754544754 629960091 383174056 658163334 458753706 230879636 126207558 410402708 992774208 733426833 446864944 864992065 696004523 211576229 516431994 961436053 60157458 343009535 618386025 537867986 293222945 148952231 220980062 235071188 257280443 576616249 318421347 618617089 504143563 853757774 553987624 540400525 978522423 143890468 352684474 602171001 16729741 374166079 257965120 43925552 999365890 86796292 314127559 139909735 386751312 559083430 675500245 629810415 639043669 219684548 804171086 95406116 160592699 603851773 717655286 763931385 157461761 49754601 982028983 785964439 177703110 767109393 123148197 448862723 327555154 187669023 395892740 9710552 260522902 19488165 944904338 880166890 951515351 856668966 285847849 671747415 503392406 673931109 185693883 409620072 103259163 816831229 951132691 354075234 974425650 61738309 304523307 485093990 939433883 282945234 329911370 804414767 775647805 123642053 144812281 341278892 743513374 995719639 509748236 266788884 892654601 521086399 376908507 116628202 979814812 923679299 890455082 763492112 212607650 671489555 468650090 176846035 345441900 732290077 223051057 232179849 296787705 491986646 753895802 510545690 944129835 110169074 44592084 736304647 556255994 166156537 552159580 707442275 142538792 823817866 456285919 669055962 616358775 464074499 321226035 382760085 511115557 999843930 228638100 126590980 630686199 695636668 408190411 816504861 517430871 583492958 951981118 414272368 516814547 782190066 846732174 837323802 166464611 273522260 965597958 630703990 794573480 269571142 823496100 103420795 139116482 277675225 890188486 121842492 231278861 716828078 698905474 234750356 262952023 619849995 31778337 667973433 20260071 76688186 445004835 475317054 505187596 378010251 764863092 560141476 869873200 476510116 737374075 502697000 889206263 551848235 668121601 539685317 23781744 767125944 681340624 940243117 515514168 382238827 253009582 722549935 589060626 157516396 822963663 524080405 993725949 756950316 557883863 989327825 734001724 359322165 456618452 447457075 569885774 894915487 828104130 418064283 879818763 846432238 300234975 934876384 696521016 889402730 281295634 794664736 234286488 160829142 65592748 517726863 928120137 652299207 767261340 981838949 329361520 486069907 707990101 726390057 4842826 860466039 256777745 425027537 959177591 954367632 870320896 169334302 823963048 635911560 609278184 21415832 654128434 832065956 13667898 843098646 319003597 187441319 710116680 809968313 477688631 263061700 502601581 721642012 578654052 656206977 748364096 135654141 424414858 173980407 113925641 28585213 175425451 93859106 356063324 571839134 16318262 921063689 51400109 313718161 431495167 831291134 302390481 262418249 395327762 590263507 351629984 615816416 549202775 304723069 681543676 698361743 208451886 74797048 137888646 473231292 911744181 421101956 821710899 711408571 257060687 817764769 304064839 94098745 431226532 967789298 157859734 394748972 874558602 332328665 173018880 294033188 38505483 354301681 867237999 418391754 239363080 58416139 826940799 943311135 867561329 552685674 54888995 907809013 379838115 406327199 598588664 836124409 936141840 203436368 273523372 403110899 200085414 215074089 249206678 817642806 75969482 342812127 766582757 914955167 899149980 442190934 493578966 557420345 689891657 529440779 371301098 675895641 951059089 214779494 722626508 244829837 694097982 94071208 57759771 807508691 582709185 797088774 198786956 773948679 193389512 965680455 388243359 805922273 723637240 22932854 663692434 972542882 893594362 537641830 188615404 978868806 35798476 260302449 465551947 402378262 335260882 121858279 392934680 825809049 233427936 737892215 616071766 407169934 314552271 139693987 705283480 534162990 752058151 645203817 204832701 180569194 257936822 93999391 428975214 746363475 128931327 394047651 104510668 191526275 393544279 884575090 735618839 937683995 812551106 375063777 987284331 507328578 321637887 350674435 767820928 485906154 950981901 471621134 20188382 878605125 635979677 546945516 584584487 940107469 310632805 298711813 322021086 511648176 558527724 278275557 493697536 946674997 439724314 550366694 785769995 41750496 661560759 395935029 660916947 769809441 572368725 713303382 353302224 17810489 295638706 799245788 887608207 9546806 979112425 990475532 389169855 192043565 459928481 405530933 332509070 998119915 746068672 992680929 11194996 163866994 576801477 50676485 486094343 407191396 638508840 861072796 73103402 224018723 294533798 14763084 549520913 845052022 462208211 171747751 680366689 954297350 121929203 812006310 82867239 81401897 684782448 868269192 148355216 424877645 872350767 556878089 274993709 883451462 652735924 815398209 607039366 293704902 273896220 818300331 295702761 195337889 274617507 256747347 589064907 446795977 858216393 262374709 610342737 239307843 476505573 952411411 146674716 965379885 607549628 21115832 998599827 431363195 996926280 322510825 564598751 46419043 566289866 974683411 67565022 723397300 969044421 788165766 196867032 305497651 747826449 592450881 822362408 634389684 832208059 125531107 933301351 481015175 307724609 481644254 289870072 58297901 632373878 393371021 587473589 815811274 453073914 283175235 601467673 321501479 831756552 179480292 252753944 768591236 979929263 4843670 318756857 693476483 7521736 77032027 589154692 890979565 401274461 900085786 464117824 654427486 894709796 618063823 916738807 973494493 791284925 358818090 671661444 452405890 12875918 619572882 771745677 965262451 715023136 183488135 711889780 368041092 424451264 586897407 884358981 90696262 412940280 869366991 166326922 759838652 801280756 202983533 955320873 19236582 676086835 903892353 652432071 189839359 685515279 811968902 178856374 340572082 347654923 586319537 428328586 741894953 197755705 962847302 975411191 106142824 408076204 109529330 932818257 157846979 41153655 768431410 275276258 786487455 374949808 760148660 116630819 513979851 734722095 933809143 136713861 944589067 859228236 721463227 349371892 647562816 459551657 823386715 240727759 807565381 438087223 515904311 62060250 750787222 519387913 908993243 498077692 321141996 40134919 814483258 107556582 446762735 35981039 625537635 668223352 238408669 26842027 221409940 672700701 47530726 208070593 746273252 202130227 683257627 950773348 41620543 857486138 923047337 177890278 72176513 745088551 699433586 760189273 148858027 968440533 740894357 342562400 837001338 458711367 314194579 485140496 258539969 686128351 837103036 253024700 30128164 894107006 824023526 407201007 580389545 568726426 870236002 502612732 459602281 177090974 852083731 452108176 346525833 681365584 515854299 908131270 733024800 94704573 990195974 496029283 39858319 844692045 177315278 194672436 958036331 537595233 577295905 39068103 321711397 172362631 975229094 584688236 574656887 301960242 666861534 557133285 985127976 154230768 305662920 1068083 416904578 404928596 699671534 338857039 816765838 85260713 762535386 636754465 295047969 741184385 214867606 602658415 477062790 874092257 958402785 618611186 858428362 782950347 98714915 670002610 949785643 115778900 889113458 438991817 447658716 345675422 386181698 458911596 98491074 101409671 529225062 50533566 382344679 485134688 289178245 403281700 954933924 987890940 838610434 993744355 343125513 668079877 545002301 479146943 858240090 771706362 914170159 550512004 497889454 418732972 361780894 255968357 269590537 99693967 947797145 659613437 141771685 82815064 281188906 576089960 334644509 918635684 600267327 390381061 68639395 546349212 644273075 910864725 369194420 545354815 682540907 264333817 532605740 510685959 73590067 705676983 289672194 204857176 478073759 241714436 759351025 192330892 683578502 171883629 746089103 490461113 625562044 217668084 262285411 209294094 552438922 573303034 166324262 66100692 635585047 86029438 902669219 801622455 168932277 535835959 720955130 327249714 661259730 844521772 24701436 72139934 7703077 758922629 602301487 765218453 513345978 341094390 145698140 400198310 415807380 72350654 188824184 836924863 830523112 92335079 55774929 107756447 830262659 205679969 703649116 323091400 82288838 578324844 18899923 825524320 689571129 975705988 492150631 842065072 922259231 970931977 373117825 675147361 146652692 383639935 950904152 366628488 551712424 206255562 573408631 804876927 766150160 26582950 199148941 249504276 269213717 395832262 582505844 671561600 491958180 893929865 221448898 857386161 644919197 350263556 540262604 962489374 870554877 435332435 484216303 930414713 649646475 608382767 690257515 808729335 449400595 837937531 526311433 605746036 261588744 81766317 532179833 76886076 275863580 832118958 438457508 993924462 215892867 453903752 94282689 355794795 12419535 821744874 603056507 488311044 208676505 504469820 656665534 400612063 1965776 650294995 621640401 776437094 533147256 79889056 300808941 748350463 561262003 142438396 236429989 478195860 686705464 277280340 5575171 852383391 803337258 842246102 240931482 785626711 435059037 328962070 587469742 519090922 973613747 199272677 35413668 278655064 171989418 367475753 487805251 8098757 856742750 337893370 471680016 294758255 325828903 111636967 979304771 574509493 582173100 542522059 76930256 86076352 610497864 677463214 9929392 820325594 986255373 529814539 265653139 320665707 222733622 638687214 120804898 349990640 534444791 834880681 157104322 471944701 653282379 406526044 324511018 715668110 7982708 486471879 976004850 995422327 615028673 377494567 352741198 843104491 492608990 776039987 102013417 767132739 307123574 4195290 648743313 691750134 799699152 678942629 648011371 799539966 425366219 301125896 12830456 65196481 666731654 400893999 691459763 266754301 8889138 902355223 486912404 605575046 754826574 968034153 690438932 386151434 754474969 871520548 112213431 43253775 898025152 310449758 781140655 780673147 500325357 752119664 691922795 745749839 527884411 868833146 330782658 838809403 86326672 240841927 519968211 326101148 877476535 668356040 326580770 387750185 963972041 933973579 20765472 979815549 394461298 664723312 186505879 101297124 327739049 259278462 656239666 77330104 953577257 447773436 327023182 326377390 348218624 5388061 613310565 638858960 979038627 371032653 639914125 409487359 734387893 762222001 599128702 924718854 680543794 838520099 175596503 536389366 11982657 549432232 59912330 943377603 10186714 976868444 56936264 396931329 217094987 445947558 866944157 367801398 929243794 349479813 956139416 829471682 429386055 831356305 784465533 953932435 873204406 378650516 558332671 771490728 162620158 246118774 690298581 500543082 922658769 442955239 721387492 831471592 939480716 703439671 93128383 184088679 908413216 323173703 553559076 421145780 896608553 860152160 61524484 298934062 893354926 298883349 47873813 508256606 460803496 15287708 605885996 145282849 270537838 169193897 522476683 750940619 595914021 395607032 637124028 341314737 213398156 360305307 869718802 135097042 273836512 656615382 697616203 569013871 356452788 598504444 762522921 697389232 618209701 135319892 655261891 967418333 272935076 147440255 336822057 285836412 706207996 926320102 160825818 248766466 498974960 154209738 477195290 844009917 414829143 822921887 290830277 291555290 415922919 580361906 539453078 174882885 517155032 837989061 758430705 370551883 991250390 749299336 563884598 167054946 309602819 528744370 979534319 786245146 751261208 744636803 399964147 643760365 788548073 531915466 573447041 351126458 523077169 163980709 55307678 449070116 64220959 630847282 777472463 942108185 585049321 409088016 312641849 742045321 945687891 940601977 222351846 379675681 637602323 133025892 117146179 641331772 67757330 778983611 401932104 620208606 557546537 882621355 634266468 804098085 758021211 427994146 129679288 277640617 909892647 239461877 766289781 508896317 239574751 602045614 376818743 119631689 815400324 263160530 690519214 584128182 79515070 460066031 40019275 255509068 903957527 212714731 865641422 340104435 379901634 855717994 515602714 1613604 590307875 923898042 302748203 887464228 380325556 51713735 379237731 690353818 527109231 727937133 361890765 286028782 687276692 201607669 759005476 572044900 603628304 236738105 692026336 116638912 301985813 8870288 994987464 532711793 237441784 959299340 279412951 732637301 578281335 239003645 620260111 729863028 908903587 596263355 696251487 95399941 220084777 626446040 442519085 862100303 145131093 351411212 321875488 464329874 349682884 769188609 730560781 993071589 641901939 66124850 509095175 324324075 97850379 429068004 730955549 782868434 513165889 322089086 390061644 422167117 531128615 975816084 571027003 809495355 491055042 512080260 580858341 925185513 65385839 350191727 119820148 464553251 457356693 630911264 637256087 408235146 925238308 582529481 572855626 13472854 484039919 123719705 692129514 918328362 17515391 660831719 159696254 545440409 962867798 759184592 344961022 461683464 931791489 463296163 134642908 192269482 404452655 910800637 872079728 692420453 662521390 721669506 234558530 492995776 474157274 72743729 541540794 822219196 365205168 367512607 272693543 764122154 995748532 58004748 34947545 962338085 486933224 426835104 847528328 622043594 79277110 690699217 708724796 785811516 307964216 376453485 104302605 508925247 456569541 163274136 520524583 156590488 324237107 765124710 72502607 478052378 24527705 20617438 929624759 838240717 746285295 350912948 475180432 760954529 673462884 354407047 226997638 521946060 379268667 292466921 805795951 750319325 757981825 971479286 280994286 624381841 792866696 254678962 879349436 2657685 787492172 294957198 296949310 639509803 820207785 205164349 272513293 302861206 923533393 94449031 334501124 684625224 995948268 807088402 937383509 747289806 274085163 468378838 493132010 511285321 497706152 657198578 212414641 215920437 846946561 27778659 615289626 113919653 58551404 206184156 769290757 700518285 469594402 336134468 422416146 721115081 836245170 488199590 847796608 592403067 635176420 456717246 960487589 332304597 112198547 653520948 293797867 206201365 231930134 334148755 476123568 177211452 408036655 383406595 450362425 202302468 972244437 673617025 839228831 113606597 605439806 588295764 509206124 647170713 64466509 763605842 228585257 104525530 165935209 208416932 190192367 981830879 554565477 783208352 351912689 875848054 655337869 36680185 370239988 813477613 844400497 175814659 984485586 664927361 129514424 135253018 109272029 712882646 415780622 894759508 648344046 692583992 501527117 905689550 451379714 384535826 511467669 149259134 220754129 74602337 724002999 778459501 221181170 428540567 158940715 205295608 282229555 690212875 221406906 141697790 407827409 484316310 202675197 265966867 161254264 514435512 241699599 175624377 128254099 945914347 236899322 362053252 152416389 688053886 860994488 821917464 207830182 120717180 369040099 119258339 20309606 677210253 736917508 937987414 304698816 783285432 891297841 857990488 405255831 835168533 116080023 832907386 786164112 717348959 160249471 990388737 362274191 75868766 550882196 482014642 478539244 175347358 533024949 388656662 903689831 997595865 928782187 469408430 81986745 981358827 67333053 381662969 897860522 235131348 64343295 229848012 155124110 612498618 159317074 116283103 883021174 871767446 253653796 936571567 311231084 107873352 631033044 827887404 695400496 394867870 297148942 902532438 347565446 94818123 366022008 211285779 427585270 757309809 655771340 354546424 110099329 694404597 820679758 800169042 252558305 599724973 58011910 658847035 194181191 504000006 730019298 398211366 619343301 645056195 331784931 368987747 928325427 876033006 952401859 977403044 773138782 397700322 881034723 478961756 285928576 769583403 232090128 301073133 568602981 705916110 285432460 450441150 964407586 509081561 527237953 20744635 233165417 824482849 908365053 566079027 454803878 816374509 842798706 127354019 185474305 312509420 171535337 137109047 266366767 884807849 344083378 694930132 962387903 960252135 486375479 443603729 687018992 286916786 684848185 289647375 473050405 253182677 271198719 675806001 8334754 214701034 594948467 377781466 881015468 846087119 747209821 587926418 360687066 235033643 707933486 443382529 452447684 335215122 953148497 980554453 295204221 709499973 161495735 779378090 644825764 587479133 877236284 557299667 127207156 803332044 583717538 57238649 345132570 338272468 151002262 853869692 432562360 710056736 446741558 56017163 92521554 314664391 711099354 50139996 826125580 174947008 451647455 639867434 607075787 148788693 283115507 336641176 749866888 756780635 965470027 686519936 862365590 957568508 367193056 725298598 534141291 299579806 220154372 417494821 979877021 130227961 305539608 605295744 168754553 595448134 966351965 784234261 298825281 238255304 723063669 182827733 665387776 508202920 887136502 138134319 173317101 378487704 246464486 592654510 987445930 842498103 293259590 433760627 28005870 506823546 310060004 625554324 935766277 519729589 945703225 416830331 60510202 99066815 753092914 47070915 300605444 260668029 496618759 243102375 125647112 61907989 122611961 158281731 564928825 78094898 558224159 207845187 197267134 432592324 591291675 763690144 401768458 568858728 758239753 28651321 275787088 203927155 285447907 202339401 827898124 311397453 174789389 518068191 108828490 843912673 637760607 370954562 870436839 330403555 228763630 672014625 347384667 467427005 16762093 606961067 704312731 120489742 384687837 797134924 419757996 242657217 482895046 608762129 585928665 236583045 222713898 969810109 23890294 683457790 282207365 215779646 492099864 36243635 152122573 270705721 777373598 554043825 132353835 958311686 822217030 841079909 467506273 646537404 732127913 707341869 660620626 839366721 872684734 819955068 949170532 964782032 867098216 770166313 555557602 499954166 620993485 576946520 501160911 78191257 465695930 694826242 144193210 9150810 960364497 665121066 263936216 388768122 863761067 628830005 471857063 924588321 419774540 529486390 391792185 122717907 632598150 60359503 977963467 866839203 467024564 764706036 312973579 158486702 295893493 285468342 268582155 429784958 700106466 623547257 881579364 76454897 465007821 448185483 540084891 678612667 513152861 709707072 712679617 240232912 728851016 999613180 397970193 502883292 633996961 472977355 692372887 978517776 725908652 752168669 605743583 209020040 206588978 455245181 754737199 827267406 768736904 253119053 937319704 494693513 122911120 176043391 829033973 20125497 204184607 779620710 194151408 589280850 797982455 17501662 477150952 991185825 841114226 707326276 472440809 568262747 403892367 418731541 879533710 565872767 12187162 859421482 47954721 344299614 200346015 775545180 254366781 623849357 181559854 862853765 409846173 539573904 280963147 620006799 81595015 660322026 706590377 11555460 558456138 47486494 306668896 403418721 352744919 655632877 856264349 804162591 571194108 962849707 672972660 966656687 318650561 388243512 329098620 674104070 759194099 35263137 527480286 783858550 635122206 690585633 788225354 420279877 816093819 235302058 96390551 459053440 950722255 952223447 713799731 836923205 284580142 656014764 3359456 636162527 510065829 945761886 378726163 639058318 570609708 821677801 864630332 295982257 61751414 632563705 235290231 572933179 906160315 83436809 496383147 232306003 612147906 262434771 617112448 24581396 833228095 5317814 363812692 930634619 715641121 482251839 147147279 261138808 526013992 642567848 249233220 853379585 860027469 156172999 545014725 54005125 626352361 434547616 489660350 237088958 794641013 604516957 125694476 880665475 141150892 196121122 669943462 142840242 734910818 555561504 707184118 879350758 74282323 445245124 147460265 336220892 635969779 672677688 351824093 317944993 896838370 452709100 213314456 927504922 582533410 618738212 572076426 552513965 758485342 706876949 516164165 813993556 306999748 213479153 931277850 889179932 654136212 654714551 5872859 169582292 984552583 161006991 308287692 313577546 510188422 421021289 757250563 48009494 682950051 943424969 556702259 861676039 670703281 561025684 10341096 561316276 685654653 757403138 51285594 480714274 146552855 724445855 419074491 242444472 511256186 18329924 485167302 392543409 34795735 512346348 627447005 254080811 548946244 75073494 514019090 644543334 14756389 446158689 478978989 988760754 778161727 757456695 811178871 604197369 879837612 969984776 800823357 344920885 905470511 973711577 208539340 576313695 398294911 273702680 505694525 223453748 606451692 425854476 774966874 925157431 8919474 865345485 818635384 529223773 34409518 44642462 813432895 521260021 808953756 779888259 258818187 428442429 376059369 136014716 515087580 366907048 389288380 47960265 279475860 122102552 870981480 447166612 912914827 700974132 244549065 754166245 109525674 374556805 266743991 20885841 283059402 304175719 983881128 258881090 438232790 193580975 635680325 846279375 169675342 962167320 421054353 944773436 645403486 335525851 97867612 249480595 625447517 822411443 687061698 184000700 839984305 615733601 116743432 25923989 356095944 582974019 840820564 952538663 141294870 57988271 579365826 921213711 575471069 10840085 229922706 458955215 885291218 601693012 834858621 591492715 599337742 978696624 87610582 112894516 455569528 17583975 688557763 162905607 345360710 182304322 495114242 992936611 118038842 842247811 277782426 262574679 410247255 13914528 491457613 52526198 625831733 184456197 363147394 975880957 404883323 175202617 238255117 923496127 809883538 682870883 61956266 788930337 39519040 197344223 669597528 685101249 432809830 416166502 379775939 934596315 797325166 305843845 212712845 344250485 324080714 502167494 110739403 838444662 340471512 476167547 319672804 173810875 950937582 325306561 548655009 29204184 487263294 95051541 371182908 895684741 357701363 129582015 684952510 351545752 65196693 63354665 690923765 52017287 288450214 598827144 686238870 256063402 347961250 54788076 279007504 196405107 421502314 650516450 698305934 957289728 270564564 932621593 919825763 702977314 245039743 388828983 472072349 106860619 68858026 632287107 311997014 723564955 97486541 846154326 63908876 469760746 164035412 404235027 459442926 89392886 180010180 539901332 886892294 643543066 822603727 941359023 762788243 931431001 425998625 255665573 966454946 614129594 736627076 230158000 837077940 411321246 373926404 871726456 832585050 334337608 931759879 839448331 65100502 121655884 191282351 911635967 847147624 426855182 417486124 607507386 622379964 387549665 727308859 530451753 608043260 319085494 552713620 700976655 133111146 167261553 363207896 417789716 746398009 853286311 996054849 266568089 929854419 761933420 591880976 693388009 110437884 550861202 132141596 311044923 97031017 319751396 399725742 116958790 824445191 385857111 610538734 455450158 818640003 295869776 472497592 708265349 964118974 803136720 520402688 353367389 537939810 262675664 780768057 453812053 921661485 92915045 222487756 933265117 660875122 304418286 864537525 325726071 365947669 676819896 839618834 482992444 706268333 218646414 999282262 809049139 315801650 303308361 936128473 265787502 205990452 342793993 948262982 702749632 375096365 732682407 509057565 201180978 972372706 202648431 945927831 15050379 13195843 938192952 67930827 71396758 92370784 862982847 575929359 589568932 3565698 381879786 533447661 139792593 224966489 736207237 652420868 281154341 116696539 960476780 661946663 478029163 112292293 113785042 601508754 824868113 513161812 795541105 314668937 166336241 577942702 33626685 588687411 968727079 915099171 642934420 519124009 677447264 423761019 542168629 583466905 358318233 733189434 693432605 292119244 699063971 753116527 242915343 704025407 98868208 871962717 601260198 580050686 726402142 112243026 680825813 162527986 749624960 811898836 496823341 77395892 711103687 489738999 99699505 398499043 958439860 3470564 489692371 90035113 351653144 727037064 82130917 491934555 569458592 882839294 994883417 833310721 161331390 428821659 750700746 911907172 420234350 248511898 542062192 709898048 248544506 321026836 240839793 703899507 337051352 169636848 343559807 295729456 748494141 524761099 234887766 34678490 769375928 169346326 8512248 924285630 929558605 704026014 908200918 615553811 503426933 686176124 269929030 810749730 427430380 231934556 16972190 922752590 717605390 565209326 895535469 699865527 443508815 155395117 57137678 524291277 814893000 975042895 611182460 87694545 346688984 535056518 991321838 399395992 606650574 911666683 46065215 698439923 783808170 153880442 434579221 713466123 658108080 652512934 21546939 154692997 848657972 556994532 306049091 598227774 918078456 504006842 288932170 311670562 854386846 885506028 508605897 898129586 787133965 779274934 239601655 989198443 584171729 879791671 441582873 526706291 966940240 503007961 273067572 626768107 564402136 226750188 63476421 149306236 425299155 184357648 110978031 663228056 742782925 967282764 332358888 186486887 904009827 424400549 912155735 141568754 39581803 664687969 851190507 226384267 891911789 280433860 691897216 527971925 961845474 87392674 995120438 579481604 598644640 481651200 868417280 289147766 913025926 92531036 673641940 592539177 762380678 902545668 289461188 238473506 211635552 48791310 734674516 134117462 942153588 602023308 518630569 43850206 167847658 966258548 187484146 726060999 633591393 881729004 189172225 900423943 393747318 641435201 546207104 7177818 606970355 799097155 570995084 582812621 197219249 682541791 982422929 876551840 893346497 841224045 12874104 175203642 906243971 330087331 228519371 300420795 988760577 348922773 458993817 646299384 280053210 120750773 363454677 509300740 487234286 76849372 893933829 777113625 810754680 830810012 47844064 606312152 662268610 692333184 733617186 276510171 871477770 306183322 456878232 363447428 131299027 571645896 521872450 778344697 970399204 225225644 376523512 396297709 410554324 770143698 799523821 67719517 315827002 291641225 402653509 132047264 410858705 494809383 800590255 447016332 708608235 361596281 267155161 971710760 54266853 782207111 126819391 188779402 260452348 348861026 847302341 211200703 758952582 694604642 997463508 363031105 435683592 296948068 317996636 694100762 296793073 15987109 666824680 935091209 225158172 475843299 489877810 183163007 996420739 582731100 98475264 680407554 599290406 845788644 995371759 379610326 183663032 170295840 643411995 449841733 261926657 402227058 907326650 770561641 946107229 739355865 283885173 351721356 657714650 752404006 328008196 890252615 29214 465412175 422285058 813938052 824252696 796307209 135832522 955983920 931980848 571084003 578288560 640163535 772880220 734333675 318691463 497785177 108390194 257560665 642214980 25618097 244261248 459495639 111605553 183526042 799876534 373698903 409858595 867426179 8706890 236502049 833641626 624511847 46862432 665265832 669093940 227702802 582754848 81592283 203149460 784302589 324038220 123003666 486563358 975808380 533641292 367707616 262498150 228962231 206741323 980607741 547247685 754268053 446849318 141444067 575404827 55568840 587437219 506518145 176658120 684330840 651659776 313968745 502601041 671742961 622763019 294366889 940199519 232692837 650235261 536159691 865775179 998242672 481084086 713231807 487860848 793145074 549357981 815284843 56120934 409232120 372164087 446338340 627277373 5781468 335090446 96616369 916018472 839545212 553841833 909375356 695813908 361028440 574714107 781796628 555108015 474527475 621188181 993994978 399760478 564060725 780323244 502484891 168445837 435461660 675436299 882402939 451422639 275779280 169536893 451246380 721659129 396201345 173889185 274604444 98039420 59371505 347547669 730454034 555086370 623850732 416835129 568855090 519253209 776475823 840826981 874361569 632486809 231499798 74548013 347614171 332300886 854003457 385841917 822246361 708998758 995729025 100630244 709974082 271635914 551941289 418268062 570534472 767708841 591935214 653244022 516306180 772866283 29185027 463258535 919843948 630663395 511191381 239797585 323224760 233986725 257086727 740340762 9013703 683578217 13913985 961865708 948881748 196248572 131622097 50697413 542628546 35916769 80253441 180171819 152088694 909365562 223151281 884361311 844376249 815784143 430327184 714765860 407086166 700417265 6040134 985300601 571485708 822458906 407166842 154555877 718652917 992779208 31794397 939635168 77572024 934739842 922982867 529187599 887278354 58132047 67572619 397414891 720082064 198220608 93968273 733552583 756434169 168980199 257681079 398295489 351543745 334589082 842271703 303268434 629003545 622483045 353310430 310642790 149496578 66604422 98867692 160103726 979350541 273937406 521689694 785514230 190524725 621704494 728900629 360119363 456880730 18098743 885676471 186131433 339346004 210839384 645127761 15938936 353922329 993307497 9493781 21500748 931352714 46615406 89132123 555245573 375704719 639759213 181951713 698096878 502116777 928836152 664048456 675029068 57028328 484291942 917085789 291804893 830917757 961093812 512134895 959854345 652571525 79649732 275288186 176643371 967459898 683834732 200808573 737464527 368400180 537914899 970344568 559016745 516869609 205025464 805926024 165574807 555621424 946480622 42038675 641331142 228169829 228440084 235977502 335353377 484350579 825120993 968764819 110220064 25282894 427477389 173106266 504542470 88877531 95694188 306850755 313368069 308147591 393577169 962283183 393948212 407253186 654873931 329544799 407612524 614085199 926817248 564873110 658016065 632914713 228131785 938997911 92238435 970932024 465166954 24077526 300363854 762457974 370264407 583000894 409092569 355895220 95510102 3672003 363647436 327636742 391587535 177343025 729351527 920568993 604900526 55724155 667537373 216814974 85415227 204409410 978192854 692774611 760212863 806137909 88411939 427134096 313120666 281658419 972889951 918146390 160752488 246101910 280574943 939947049 653530163 583794096 965228246 384945738 172051914 97049634 106011673 64975141 379780281 318993785 612246999 311132883 215376035 512709572 98939113 985279775 57904953 133029791 141109094 885025851 937070398 819054098 679172873 30209192 936867244 108568588 224730322 846257440 598761247 441918209 893484041 490329564 253645803 992155031 276675261 109361555 205001068 944709672 42879426 814567362 718018650 259065606 90149132 91851752 739510905 149308302 277650183 53027836 18251213 358576087 45892953 533971034 587519119 514871689 721207111 482517554 382099485 556726546 619550521 97047667 625005380 288762322 350871256 228330007 220506158 640423708 563091857 296783208 26653210 179366948 967464045 773369620 203039477 1478004 765960887 726728335 927769555 574072693 570887837 818380644 923390645 698670628 499724683 171556501 233752522 355027189 841706292 388100333 644245463 333546009 711613413 736351620 798782698 514074431 654585809 109271111 726521644 228190660 84239605 655649736 999184737 455839058 19483041 107804258 135428410 813486683 806377481 600484434 474064692 688213233 259749053 252980475 248421070 915388921 230276471 483971943 463282799 404634923 306226993 776597910 25813370 342813278 508960109 244429434 5142829 963547271 139632802 348896519 796238692 774540050 693955092 40331838 3360415 47667520 239161768 497636679 347629828 141362644 801441076 155187804 791032927 433983086 968416159 961977537 943944679 558887594 357638805 428724386 405942446 111283062 230391514 696987663 938892029 203979726 907378638 79675100 216314686 896384855 936176627 651066286 151082849 63967203 648489239 187957366 478522439 163570056 549741877 440580370 671951626 272023416 103396488 11368743 374958288 271455918 340898796 568739116 440278969 579494135 176736658 278916917 536261281 408692646 11395514 547562180 155640594 315175514 556727707 154399379 164990236 697890168 124265946 304684886 294929397 568254792 726051602 19497571 605445926 815645205 898023445 337902288 560661042 673078090 853759104 168098933 716115299 945717265 383999197 981339478 841430087 829422033 837391439 667972498 611638658 428195643 116403004 800788357 721844087 828678943 977226682 908036470 508110756 119549307 454874150 615854179 728623586 407755601 599352088 368650768 866378245 7101646 299821736 828734950 868054685 999443604 367287044 459928413 541704672 908247939 737080495 666936909 531734682 996084800 410107513 492825827 560235894 593709584 577744565 669583206 64229387 533887472 468218559 109877309 321926740 667352224 337673051 699438188 515340668 91355837 279783038 241631799 753736636 387012295 933161720 502242139 529794275 740124026 334275997 493317621 450377972 345603095 973301082 809673909 872444905 784163034 797867379 525969003 398138000 331381681 210469444 367996849 583989180 475376240 450192908 379335967 135292681 516245384 768385107 288853374 534853434 375589856 631049171 28905782 284267394 185120271 952902284 791589319 717348422 38233018 126911562 122742615 531563416 722677882 251121683 165872425 525298655 163614993 790586606 26636890 628273183 873842197 699895712 70488309 915376257 855645686 25144686 175888782 416548738 307432166 291424072 379900783 565421284 772246838 7880418 509975909 489917443 346418898 799234268 351089025 379287249 489977707 73285495 225601330 9869890 846389002 880799857 452390448 783246439 333143430 982267142 910409859 812126462 30304262 527303623 431613655 48595351 808717998 401002593 802151004 912602557 472940450 794504496 282599875 781034892 457832864 259800200 574180990 295970771 157224914 632547527 822206848 420048234 413632932 685445087 482191707 578861358 528213199 247268281 350669026 150298639 870755518 331266908 434410939 864811088 360878499 591893615 17189608 38821490 862583713 883624633 320258943 502479733 963880704 667694100 159561751 518437145 530294970 845805554 93955720 713404566 98911240 161141098 316287108 619775749 640238439 766696362 343991617 969472688 828883915 277695107 906819256 403564453 484162302 545847864 993389516 259618637 778114535 546146861 259099175 31751520 682100763 495870703 930519089 633865231 825367908 40690912 956457416 751336683 977061443 386235932 628496049 40010941 105412343 413128024 96733683 490638805 729149047 828268537 992754363 30495564 327550076 444161948 650856777 392772692 631243407 67315326 108850035 120091016 867833045 721527687 838179197 616150161 765774804 28895844 285680309 45653982 355628990 576276663 830723861 458092689 183128975 571378391 355525110 46584646 319358161 825612596 490507701 799293929 199192735 169018313 306754000 716068763 261046662 630039053 478290894 786824039 420935063 829075920 851611960 566431660 810270385 234641072 390542692 916452493 469793260 197302431 845087595 821789384 409256207 153483882 688075462 932270383 724255737 276728227 889077407 999285395 787203714 265891987 516018287 105999432 505961265 845151877 775098102 862253437 808491006 594252825 159247542 943537060 507312974 773405274 554796805 666292318 147367253 928624532 86046461 98004197 118370421 675577897 786919395 43290510 709930822 778731424 345635712 163907779 726930643 78203714 215569690 986793706 974511341 141539888 153182607 784406181 177222684 756794128 134495468 27225248 795675450 101213607 657683741 476619216 557357894 486455243 761119221 74071009 606608205 934570827 344621478 369025917 824272548 311034446 493299310 392370034 812131731 330562132 546164345 614858424 389243789 514131128 183051694 640941729 148593191 363598258 812435778 854658693 757988756 219814123 936408514 351369020 539191847 611467005 431471424 610282667 824665444 153749744 112442898 872247092 698258835 502337048 947460697 175246494 439449116 916718689 958451580 309193797 210518253 704653127 311497893 339790807 927895324 575755017 249621100 193791239 939190801 305691347 279281432 649369103 793831969 412607991 580571749 773649831 898328071 933929609 923365620 910033156 407442164 568272246 367096535 473197448 225726266 261622134 645740911 850937671 278337247 380610770 975581341 100526588 378874816 559521432 932781037 537515487 932566157 998144949 993445317 557175737 77743732 987734717 467020215 437122434 345230342 963561265 372599339 606547305 66994421 339371866 795822017 882258053 870251117 94088837 161901894 778317316 299809150 970527578 664098303 580673538 143005597 466102132 496869391 400997361 688163316 853878789 413371483 79144530 303289438 598087396 293566453 867932251 832927008 216756371 401488000 968782690 756611444 430267571 358510921 123517502 973182459 975248052 612490818 153329110 658429559 578216110 41097213 660092128 710859125 49680717 355778157 703169490 347164828 805337919 534072022 685556110 15706400 508755821 504109042 482413365 775756947 365935311 983938213 169864859 410187097 459596119 225371808 69865003 86724366 77571613 56756871 101180855 449147251 10775813 826698562 611550623 522814673 289795412 964406561 115531746 228204744 184963922 473693007 587075005 351005444 503421721 575304366 173398141 748970434 782806261 13765115 736406730 785289905 414841931 877026061 913499051 243548681 767293645 170802461 135735771 468225960 205039788 26056190 443648838 670491061 186234042 590714543 104988307 781573441 688356650 63086233 220522225 224203329 56443518 8239688 382184413 662229896 416457729 373299465 503767759 84721757 435839550 184090372 346554646 996455630 339387577 365344670 451412316 780726 628150288 947646829 541267110 425932936 491936572 386406744 261723001 647742462 207505277 122114837 99055439 689352658 396377554 676430398 17707760 931657838 836414683 914572127 552515938 846817473 503955031 347154594 352412256 205486485 981438350 34542614 838720485 507657564 572905915 87339826 132704974 971657557 975763279 986017002 124571833 241356940 734335092 949364648 843739099 242947807 147969674 374785836 914063683 334535273 505103837 391911104 670063110 430456605 336244309 163969945 847376912 404607905 41796265 247240590 35022619 46176870 523074339 854372709 243681577 426121551 824768617 204147096 257394559 97938359 941528613 945882521 524578302 359421626 935749633 684073976 64221002 973342486 373824896 367740377 852786492 808482559 420086927 701648164 654409139 591551088 897633393 238325715 564117786 442479512 324247034 684605155 763513642 918245357 114505114 525493339 143159564 754556145 247246474 772392309 867493088 241692074 481453291 853415819 455552007 7145891 633620344 448640775 655368133 289514506 603260973 952122860 981649941 182722555 827084938 472512244 376389758 944308327 141682040 632202875 797660213 401158595 110949375 465049055 272580693 734333875 15338331 60323729 769011964 143579543 379998261 399723277 793121234 526676969 34484494 143609554 111411712 675784388 771476054 310150093 328239448 148242508 266632030 731370083 536388362 245733746 856084807 555967877 576267435 524658170 269916447 237596839 651703141 870119839 461317712 800936894 481581766 434335418 402558559 942559091 143998965 461279117 658895236 759907491 29872994 724632579 810260775 985578807 800698885 939768486 604316641 773724656 485622143 369530754 945834721 24038626 39201727 15719518 971785823 215832515 369987973 497026291 836488358 337681452 607759580 165350256 308899039 659974332 9441606 905590440 296978545 238407120 472608411 206315993 447457202 918601245 525132707 277167721 198890817 449360612 167619920 273250235 589833063 353223751 552281156 992353281 424692105 943768411 537493567 33483844 399452897 803348607 66584286 514210416 951662076 116398349 944032448 240061521 562337303 781460685 963575292 596638209 694129679 830650066 939212174 501553555 502517111 748353248 803916486 693416703 533871560 388460565 953990564 743126310 124980189 910253716 186408941 879525630 574296669 987208979 914145457 588411252 47013494 953437054 539281072 615775161 525497553 740447040 964198716 1258752 804156841 523409579 70156109 984916830 958888652 637376672 457609394 41716426 220758603 590959882 790203211 388017538 879524133 363208394 682850722 798625207 500137547 188902104 325459305 616860297 32657739 81245006 336434620 225737668 628739347 659049953 340952577 670200522 312435205 929361420 629641310 953624552 374659428 80090281 603348743 312285642 1474142 337653161 446069828 910340719 337099877 55899486 459503076 262870939 594249790 80379647 227611221 44549009 388316728 484465276 567289215 108243264 364423322 914543572 189472210 962042255 843262144 519425978 889921055 826561663 187369789 342607356 953693772 737375066 757397965 931183360 714013366 991572809 681376210 289437704 342282750 125086865 670113785 568288827 688953356 173617630 887662101 745212749 550327616 384925389 181309568 389263348 500484928 328101716 674574829 403359782 697038031 381598697 524844987 970886335 114356276 289103673 767185895 714312243 44147588 697313683 78049118 186311636 143987878 230930935 906916746 239295544 830679586 81251478 54421510 59252195 182443342 756788337 746830787 750377947 137662261 335043045 742419968 412645107 945510109 275537362 29007453 503339008 600030247 409792454 334228400 239800044 687966868 80690099 269188651 221836859 104447338 343377065 828718908 412738754 756178880 342750519 95568610 914846775 527823954 761016535 508191365 604154770 92587954 882783127 961648315 647964017 935375794 860024161 398299505 178157913 355314348 170289269 394983808 344796922 108150448 491578866 798381354 279091285 492481754 523312661 945901415 540492712 850646692 694376056 114500620 692990974 384203640 760017900 476269108 827518610 879933265 341500171 406555225 968404344 667410874 215728503 594785131 853573405 82387679 468509512 102113129 630635417 251308074 904480581 901230259 193047456 437013180 152003640 357209309 387979685 875627835 140024321 693070090 849986779 95593899 339839289 30589821 910123459 742653136 833561156 65387843 540924411 280474800 171232356 956659985 251539812 7534325 402147906 335499627 994573049 202864746 296930206 216191046 598924289 366892513 265360397 56343071 149261326 780326446 862186946 148409513 26705827 234702435 346924430 530557664 675082217 891452287 848603017 29192632 254211109 77596041 918986822 699864335 489349956 796893059 485713389 790832719 390978941 217842175 551695747 792391374 91357441 591248317 866989329 717771777 390660818 624460456 108359878 724715411 261299504 94805296 561046363 48358675 96635484 337998182 999686263 728239633 585493033 324215912 30883075 684418340 520953976 544457293 532818142 974380686 540187686 506802133 838130721 899814346 754033053 33655383 49085568 469004976 731236300 532204399 570992256 617359426 973002315 69430886 862432161 941123875 372361025 737067306 562963517 857673866 814232136 531227789 3677680 826149065 62603997 332556208 587698486 22109580 815809205 660374236 452311273 286992542 480529467 422178038 480176939 170225766 32380287 234649162 328660087 176998362 84704163 917582685 790560339 604650691 802882943 143459972 81594422 484898681 718228342 441337109 285721008 538887549 422786358 582226039 482897434 229755441 467266339 387155515 280991596 447423526 112359314 567590333 627576856 111927438 371497507 332512293 892614684 624447072 804228600 464611720 567114516 308907356 43450037 836924655 958545795 938098199 327017119 153812434 338399745 994477930 908981174 723401977 709572504 144837497 646866537 279540030 482960256 973678258 262964390 47222101 314357154 278455821 250040034 69573740 599483723 493555804 740612101 750842292 988079742 66148350 605069757 160540464 223017083 949942094 864829577 67627246 100562295 460271693 229867415 558221919 63733020 997798556 391802072 473679761 266129666 901713644 429838022 492472697 979855765 293192759 356384798 648372428 799482262 918760852 635642919 571142301 954944141 177133463 323917223 927306025 936008923 777384421 990889768 282096684 91975633 234681725 464990236 687990619 405465862 74435655 959666298 257225218 591792310 520559262 392046621 53392478 106403135 376987889 731968826 270323817 398076251 632311556 956899083 438406260 983058819 213667723 126837860 165275835 856417898 410666309 827377916 496137794 152382500 208453600 112489518 102110728 253398433 802715118 72791290 558008976 841519232 97253333 411551808 104601386 318338127 544699000 59978522 389610954 346864018 686791957 760023067 864211092 278442773 862211331 666886845 613338890 902360235 465059212 594131649 616472665 685231084 899763627 857437835 730629124 926472544 891945805 91791401 5434387 800161611 939968149 393768787 807696270 22449043 391638677 677694079 364805644 172896278 769850748 441952103 576313110 245470390 330871943 340064647 425570620 264192821 933762924 495226516 200384056 524245485 39895542 729960697 396326442 212160176 902484159 542714482 396444374 987580746 904013357 161490518 271076411 658770683 781088692 668718654 321817364 254926147 166300888 607979621 613144078 338940382 50023675 314194107 176777562 272592297 355113988 118158252 490318558 931307462 628131693 729420181 680837237 178871463 113781074 625216337 608360229 687471880 859692704 373175981 169252309 826694082 159119091 740760530 116561638 522030953 235937994 700475863 936150939 621036146 459521595 922249098 111277590 336189786 688902301 520105385 183766799 757957661 609302863 342200338 774847752 155770940 371298453 311887874 361762639 86100513 944830436 916667674 694991559 693164105 174496887 17832967 957198869 288540338 333459496 696668895 551665495 213238407 232426075 113198973 724864701 586186300 506043742 240548800 748404080 502981721 83426349 450107606 264432981 838155362 865902969 937560430 270920863 980154097 186086967 583007085 174710836 152844213 95468354 605317881 578843374 808447931 350525930 934347029 202325779 612517875 294339701 928256475 125164545 942506472 534580266 399563894 835216199 288827348 312064786 151211837 811139882 510621486 68925367 566191118 570482720 657360715 554587895 602968655 812154757 200870637 271420062 147476288 783971912 908372656 83744654 304021236 74231306 649626810 305712406 599313329 331015397 977495327 552412131 477833106 986226831 972836820 130815840 431871885 82894838 268503095 969065178 441326463 776014774 419089041 797283441 476689043 533840386 545176681 306249930 694854395 868718136 15800023 630663518 670716339 990354631 383609259 690095468 151985890 457893223 958792746 398457566 530659417 44163923 878499085 235439942 338510734 342826027 437571260 748526885 457946863 509357090 272645408 410824489 957366231 797835962 462711129 473864037 276025139 740396403 634588940 534717702 124509673 655591436 149344949 80241720 606118676 4577567 368071413 726297585 558955638 306353800 92709628 161352221 323724156 54137519 533506357 891013419 343899798 381329337 585279260 290969765 195222391 443854304 735333253 707249883 209649843 405272802 659243400 728880924 593075816 655053239 218336350 242589501 558430594 890192044 776520210 398874878 415149475 191880705 789886319 436007244 565839104 836739826 349486348 860142218 241342184 837489205 553281487 3220790 461768561 861135456 5927522 47569747 936641026 668435041 620557678 412639126 106303699 75088273 877862645 501976298 610516663 228095767 141827400 977340156 880236440 670432912 808606921 489790314 32670702 406898115 36801808 470231858 772547030 993160166 750835563 727674240 285434447 907973768 995035583 398490137 109705802 892210639 725321356 30848777 705478506 371548418 639027422 889704812 121533106 603145676 524701470 155386321 518839110 747166380 57744395 818907696 460253122 495027389 68754588 616358979 555691384 740238186 321965669 99872348 865475408 98010568 546386863 399127039 474190288 582666823 554475222 92233271 205493447 149992796 483579072 822690786 749521317 168383094 614234083 924380897 80238585 403413419 729230093 698598308 485248467 774206727 473256056 877193403 952842774 901234071 959136631 224274 309487615 802464558 790521669 573080006 75678272 871280869 281195676 996461717 390710901 189139460 453408528 508576610 162237327 762431581 679957749 708939464 871886885 676468727 922826475 600472614 695336469 693033429 579213058 878272019 488204480 274547808 526873368 21803544 221947885 974689197 758745324 178081171 56376548 794252621 862714838 254401088 59788548 96060627 679072570 518426666 596018422 354330398 648992585 366066061 112213114 221097948 537981533 847475325 100056119 662309481 106023528 707247524 705480845 54795597 4836868 550367128 876371962 639783259 304940039 613639538 893790858 401398829 511291869 935627176 142703853 61038514 582621805 810768148 645776146 56837989 590357756 476745869 220670963 42853867 869446736 10098732 993415813 328680410 262197155 899980468 113147943 495923742 172606488 404747413 449073994 160509025 412415537 877770593 11460344 686045595 137465005 861082346 484554949 446625796 18314664 837851481 668848739 22230737 224538737 156400866 721393300 197943790 589784944 133255971 43796350 139679604 897146077 409477048 985006375 488082929 859278928 104900070 576474019 870495195 620353838 267194296 588672396 743758353 344983402 373343291 136937136 716409716 396533189 637324656 59518505 68321204 11295484 643335928 798690526 318243868 168366539 702479448 806130614 688806998 617859461 227102152 856628285 318987961 660231774 596554796 185953978 309304778 146046463 342674900 470071566 149985925 910616437 601914480 235180881 426289061 713005792 593327971 988123833 48793045 589375860 945916229 571733191 346454390 46625630 426329734 426739882 429844602 264378283 992608307 216430149 804498319 152433735 337122593 315714844 897636188 520416311 947104308 871261 123949831 134839795 551384503 886208370 796889099 746121075 96783400 724217020 73760873 12479097 815410326 430646746 499125271 98611885 324087486 336975555 312835800 434538126 112673936 54212178 643855832 973689223 997723048 319520036 294345423 693649210 586023821 451630379 161484150 114804612 28142980 450443855 571941272 328216681 610812366 494791592 783677431 493616713 755476786 120504013 911612907 806596165 410419135 421160603 419632729 372187679 218392298 623713067 96319601 128442320 245218126 146345738 383773135 753574053 522316478 414935595 729304203 418109139 504034655 851818246 686859834 47310102 702440363 499167642 19418832 470242547 341895411 282592609 37190393 540322174 222137925 297883636 363470285 932488061 396588352 191491234 739477003 431575829 369974924 47755966 688986318 22184450 595653815 754532015 861299767 282373025 198115203 283654937 96355559 485627329 111475044 832058408 738455672 670967550 918340116 51060376 228961529 471488629 746761010 390275445 890276227 264500038 998438604 473458343 773772460 610409883 806861420 571050459 765877688 434547794 949168558 559686723 961801091 81107328 137637102 480206007 437221835 862532420 823629682 152114623 179420858 864084508 30346727 462281926 95901774 33518425 704475432 253940577 932189943 546417267 317464479 506992987 368105240 781898793 214125410 215413552 756502642 397595085 672380837 135252767 627407923 758332385 269852478 186430410 303568088 39071690 857971200 195024262 958902061 355492887 375844493 608288594 875111114 439321551 952292029 874072978 792305707 860846396 878214563 253788441 474228606 204749856 934514051 273261997 70126772 393999731 692207756 503926951 635757221 662447512 385888715 717053300 48747508 106887090 683811629 134200475 816142685 740159967 821526171 733796077 626336632 850511276 347731906 899207393 892105417 256539609 563033637 387605537 32725155 386175287 717245427 281209617 756924737 595078161 494891300 145622366 953546594 914209808 933329852 774634567 86926782 235505383 616994626 661381396 842391193 233064396 107071108 680154701 57994552 177759632 354238632 7793775 313630488 715385117 277640705 249363498 632617184 668109872 928560913 283189257 320425400 181279613 722105905 518917395 299710369 362368688 960712115 919313194 70510556 562308862 522116044 867505173 642397996 917332625 77695719 312847105 739339150 529901911 386521100 564712952 845219330 710764995 172239814 665936762 795313116 22762816 450683536 226747547 226845537 760132430 799773674 681928014 972636471 139868603 580082255 996986207 645145026 434547659 825455452 867683188 367271367 984150905 552377155 135386063 296610742 841362040 107462567 383401247 653651119 541727775 383953666 565400498 863953162 504705746 410983778 677405468 87071855 995415960 214795580 194098206 301434368 560237040 712103128 542282496 579768449 505318434 976623083 974392371 258249384 980400301 107523084 206992986 731575903 187278819 746870714 953740182 502743350 741652154 692236923 804273738 446242994 992776184 436449879 407344071 574082390 938734705 952905715 443656684 763545463 670204726 234472050 980664048 694902634 714268716 555885952 416241142 691018844 881758648 567751861 245088819 344427005 886865509 676429236 955319450 784325556 64446842 698835681 89045861 796867987 38649833 814488552 746833721 67131684 861904088 947496315 468854653 568597594 888644428 310236626 313951822 314692622 210732920 630639622 592592322 484833235 356392631 513181951 739445583 290319029 705041336 94619193 905149855 65589770 279098061 805103740 730034812 497029769 354501747 643081126 182644618 347825298 643418578 590208080 381072482 467560487 978442905 580100632 686851982 263590930 352704120 79949568 663903972 15431509 584582208 841472085 505420177 739117412 950068843 528771038 99551500 399819369 332933268 70608112 335261950 280507192 732211684 403850 893773623 770916402 157556159 675477954 689506605 436427890 217702230 790332128 665440521 496950256 647000270 340025561 714964206 576663688 366422186 536395557 818102037 198274999 181698598 265039097 376691525 902124838 20452370 916169134 453219866 797470590 290486317 84262150 178187690 837941590 189113553 58778133 809110551 428337271 55890429 975671592 803724798 647529711 951832209 24029774 570147319 147545140 385755548 128475250 812380067 447128651 645038922 524997441 475803435 148170846 535624876 342043509 440789922 237764249 80610244 881953919 451353208 933835210 776784083 668950596 649726209 368516517 629298935 188965540 66424997 138180929 81204873 461163739 453107604 466857651 125020136 396073022 743976473 683600397 232338334 22410091 922230170 349407801 94512454 727194450 415345002 627814593 232585840 831768517 501531015 696320581 78953576 832442344 435992807 83085518 120028221 672724138 435429090 923739388 816966130 890396477 706532495 481402946 106533349 543827241 714546250 551626491 397584181 908116607 634439054 761537804 537081719 880758769 117151942 463619480 808742678 153835899 436262807 710636023 582844258 176817508 915085990 209553733 608226958 468215599 459792949 504295660 354708686 822171017 350736371 805094248 446924571 914806642 233212442 628430727 3138619 76481835 60776025 68611758 389650197 681284794 61979235 125091632 112415793 785386730 830830459 843797247 848114883 68279973 381476636 185174986 632889907 126700568 294205310 976079022 384953881 341442039 773370277 124281580 158017812 771393297 404052212 798725078 395884257 51935787 823229381 669205306 748139799 46342946 436904775 659110591 31625704 619242457 49859962 15741935 445541148 620319397 947075402 489339948 167644906 416193902 527345771 49951679 981938083 426138206 418023553 13495434 789337546 213552636 905361607 574269258 884145491 137370442 298099590 234430889 928404001 794793136 10477815 800449512 560503812 110806428 214342151 862392408 984068395 886037809 943254038 201612254 815735490 267668791 451134658 133050563 131408840 250104559 625553384 454785021 166341227 196401432 26461836 62124903 107734722 432712673 911014142 245630300 975425340 523303074 759171615 131899682 936127664 523988853 373299078 638358052 240731443 132546688 833134543 832864351 5483530 472064022 548151249 962048126 924469242 229971325 902750922 21429558 669104101 114045862 843309645 565774976 731623184 124385590 385280993 292691891 967581145 612024045 550971058 417692763 646451500 717633615 854558454 846693392 244374627 80522931 29741535 401986440 891269839 421810218 585169582 900777984 280519088 627563226 595397271 659539968 995614677 693658525 347415373 572332986 723904143 854165591 312959848 807023608 555405577 488173960 792938632 494499947 814748824 532380720 881828287 767089645 551857715 373554413 612015924 827083071 17532319 417018070 513253931 502131746 896606327 469615268 185639409 389599750 617295854 522515697 471630376 468858238 999024280 600151664 680237720 651651748 578252506 828187905 333830978 659101269 696835151 221654738 424385315 262656529 815472145 332797599 392107969 808544858 889152849 470649607 778102264 736679700 780503334 653550016 559976767 255418373 658210531 577678636 345072745 480597442 950162841 95539770 638298650 516679818 410516497 479661222 622376697 774862846 871306211 55349827 349019639 164594189 867852800 494773223 723101004 771273279 352117159 962159225 92258380 669708746 47042910 986483306 909842572 114925288 244364615 940662189 406058805 913401483 443178334 679438083 138154616 464681465 381878311 631622633 257660351 656676503 154364250 84696221 68871343 461495146 912882374 196788711 328062046 586939749 742659389 374803099 766184000 64130236 741260971 199844552 259039032 871832197 810467157 144081811 218425356 993859240 4147098 892767588 154195995 284994885 381973499 238908269 513728281 343972318 47270930 307974168 766427683 492473122 929023282 768554129 901482235 569635191 202939877 269402415 227930440 47650017 71954033 265643949 954683540 495815697 682210544 585319845 842654768 912476579 71311969 863240472 185900618 223980506 756886877 477679305 821266553 671570130 644581717 722461245 62775359 436757275 369179556 343773372 401664896 922731754 530215479 377774792 668875168 889945293 18235408 380146149 355352574 329900595 19023991 876552203 394555757 162565644 139332384 270662754 328673489 320346471 551933943 37888498 214034742 453729872 116551409 700897468 583758899 54441194 991671499 818720526 555141275 222209216 896289942 57350854 460022073 999613931 769381995 720070370 586917676 265563995 680110231 676947491 378216645 517627175 665290349 94094839 60784495 650909220 718219100 65719997 637635068 165194096 931291606 322439407 655329725 983467596 556280869 790133587 381571957 760633158 904074311 572329708 13843387 638446488 966796190 844298206 690670208 779259871 529070741 79768850 976799766 712022602 909468244 879954891 785874936 104772469 187722730 973726042 99281702 78835199 532369387 105942997 736923099 518443369 148571762 664572595 334955430 998198966 384185629 624561253 516460170 727427992 505051219 278475888 417325061 201219782 163684232 704949190 789509389 641244906 54149362 911916363 438171409 513922850 239961449 613751813 365235577 46671505 559637677 542681209 809208439 465439455 459583788 630732450 929574781 122174460 335454407 655892151 983224249 478347832 921078321 827879774 290870472 909333214 458353570 902066313 717590048 607330508 922481336 642416159 464080870 311998760 245896777 738281256 450439947 807105789 232849444 506250204 163347515 342318052 897696700 211033490 504244274 442734077 528280592 620550006 627702762 457164448 883627716 741376131 211544244 17369398 848987989 680444577 255104242 186354935 87076240 484519761 782845549 765510287 527459270 84781654 96204268 867117004 635596605 965961553 399448905 767099126 441865015 41729922 395507711 752056919 202046405 690710386 199403647 215161434 44484509 60608613 481854351 11358633 481545597 548401786 988092523 406632427 779947379 243794072 843998098 905954672 251077637 179175791 435964167 731494500 372774280 973293371 32471120 888098330 457468424 155225040 602295108 296831736 62154189 849205973 559877419 25412687 145299293 22980191 411326436 798112991 726451006 323780581 198808626 845738096 339235930 248299527 64259053 184063532 277632093 545314652 352830899 400190132 331770891 228138507 588178232 393485341 996511819 441133689 76375028 617177658 521699629 14230591 811730388 629305569 211422681 382397577 140059003 717507646 912335203 523550355 799150862 678900429 180867892 606914852 932612478 808060337 304847255 897704961 576947937 507264768 988003874 594670658 416875638 596561130 577884601 553872839 124317550 165546593 911376352 720022609 962413238 217769485 348809877 308417904 659803212 872373711 991592861 49723981 122120509 308360110 989971168 746800945 82825014 91789321 767842929 215497541 411880302 90478975 835280633 951505157 217829248 759483805 720216191 37973472 862728528 605547967 708098173 182887445 460220915 775079671 110330082 207103286 878595066 686794596 673864284 763275009 640024682 469878876 635682385 747811034 508593250 378702805 752652411 355236219 278188596 37239256 799457484 396722908 196970521 320958569 404961809 342604058 606037124 963750126 521865304 920867532 606195447 636840786 641738981 831869826 596396163 936542090 224224506 579567831 328654622 492126125 856391826 822919887 459880643 986852308 245221047 908362117 134168493 967582603 818922460 50906073 519666970 530152734 501037575 414419544 304496144 618463046 639799796 226310356 433493880 936909789 132820084 869327403 321786608 717077862 86585111 890393193 724849799 460880942 54642330 348185581 517131977 367442389 203117435 85616586 495676148 206077615 296586049 921840676 105106616 956727252 542488286 185906308 781367403 283956903 970165075 108716405 892620137 217395586 501715750 242035466 333796354 24182959 533214193 213604587 732052129 358493655 272881577 999510976 512171309 12760798 124324234 821755275 622516959 826664615 135107399 998076339 111138059 885939381 675297631 71851390 518994027 933222151 557603348 25683981 563978750 422109913 338706675 441640014 431757099 326670056 441267255 983708815 527932149 455668267 258049097 240899503 373732044 761324566 105081325 212595318 41022295 276989564 582617099 192491506 622340152 941559707 814013641 862525668 203717862 454922391 91912304 382697925 649450904 70468811 631747258 235070973 564022093 148925212 893625288 652244562 658163625 900266278 236573888 362019682 692964838 876326068 101058911 659994325 187099216 87494563 653619379 886792424 549205685 279229388 839499768 380027811 273957282 529387056 949966143 107942530 545399106 225652463 800926568 227087902 147028084 817907296 813609036 627223578 740925207 285353211 237441922 83569824 961846024 838114639 886016158 224553913 739073120 827248614 721426673 919338564 444862572 584039677 546337292 575551546 848567230 44448613 386404015 493932315 483657599 880859670 97518521 15578813 841338936 500668971 468134046 664315408 7187254 191094331 155103346 473483710 586910046 964697154 896866858 180240757 577184234 871157713 252988533 129073396 905374460 510253225 608488107 450441578 218798365 6740244 908201274 711670559 588619525 111688689 269020487 766174599 843384919 79744961 226323334 237619113 571625471 449557346 32691549 687161871 903228791 432191134 432621671 60944381 742354472 127589561 485858 142856809 404760625 450689854 855021034 319149748 172850959 557766016 518752268 478288205 422608051 681489168 330251438 24668983 696071365 2419645 636526844 992065893 804732398 233127758 737236416 37298131 295553610 735806606 73051719 729222445 914450987 499346259 836202045 275141479 422595280 559897406 688697500 83598125 950050716 734200318 97677402 630263088 68940479 276742201 275037885 890502641 873333084 31056135 711853594 372414446 634494284 520902738 505282260 513251689 321556023 957745221 214847325 78301948 842599297 695227016 780726161 925874984 30337263 654908635 584436372 49522691 373609017 115233378 436888939 893576379 712145807 578920351 131188363 497014669 266832198 732472783 735392287 979792504 635314899 451820974 734660304 538068753 540651170 449688945 412172697 797751758 122018626 642282429 577268741 895927673 436193885 331359684 818900041 860092374 586253331 603968417 906290214 296394095 519501667 38630383 67965421 834525444 509482225 640345302 769198486 823003045 205903787 22042596 240923550 76558202 212469622 581558025 820357634 149477061 348310114 547557120 194814868 647064849 455815920 257068263 44630969 629684861 651102226 799844674 743493790 381246374 156572642 962374935 859528797 211237236 914484376 46656504 762805108 377500678 69473272 550957524 615737612 932934606 108853475 923971463 679796699 549552486 888577004 390145482 289206124 493298509 449260052 288931737 909492413 654035959 521074503 46746613 960210000 545140387 688286948 456929739 523685969 116123584 303513366 780583907 750016825 490167863 358501953 24538674 708605073 12539126 90361091 174268325 519319979 480767121 224433235 554002284 16304169 683945002 736744603 260375659 24151984 32228021 122800095 518241378 837292729 451549115 640942247 969981104 413823571 492398157 729998782 383187626 223229622 50486720 849114097 947062490 68575206 689572301 219597223 685222791 529749226 39966964 958475383 113137866 369972155 617333895 230877252 275968684 444674567 354630800 273546319 597082679 445193139 95131586 449304144 137592177 911497742 717896368 265410978 362005813 777508637 456098988 461282808 377775007 209430335 226426719 388905698 609930479 450316707 541749076 2630262 179989821 913450034 22519930 210316839 838096100 151547759 606620104 466982779 937862807 552912306 487189023 671277058 790019120 49918863 525366198 634076624 439560925 400443361 992661494 32709054 289402569 582543849 888074211 852954857 208782447 926685451 678195840 432809832 418513648 79367746 785904886 572715927 145994582 455640022 782809074 874542729 84336585 566709130 636106144 822369254 799736306 619826548 346705680 667821158 906519111 185581240 99501481 451567210 419520148 107661365 64182654 178805414 22426010 356878185 933282820 744912017 635539246 17441708 582692262 805757796 801646881 762990090 24282668 426622568 58454507 277803235 841284234 274759615 653426100 889946480 980370386 548391638 325276727 18488105 344093451 423788930 383675297 785528296 460577130 852809499 565638970 99908900 264285027 927705306 885792384 556130920 935012295 180950504 132608472 457625322 456850470 390275169 175815128 702054895 384174208 971322670 982017163 290483752 786327019 509361486 893338602 223853435 253234179 565153820 749361385 806791664 689918083 43080724 511649591 897035764 599616867 294004357 736871468 297046364 748749700 389873465 27141763 726159233 245651532 974806301 568060622 700092219 727240688 141333266 367879325 641930290 686877562 911950041 121987229 547100687 415246298 171945565 645217013 489261218 70783747 853195893 645117787 767631343 821364318 886357757 203172693 920427055 136396470 673878078 745795513 82717805 404191206 897100850 344574563 178806859 458322873 109271639 843821609 324181614 575591081 724918694 952617747 860765071 29850967 180354425 149789292 823204158 828176171 788938750 288564699 54527172 220007957 463214884 876784358 921857722 699140925 502830792 503061874 298010506 694878962 835025002 621093937 387161250 590463301 758881990 373915365 561832637 41321628 330691182 286765178 801478368 104639684 828355762 149032850 990848418 421927989 308785761 874625802 587461165 966492972 22285677 961923880 439868406 807682953 428544791 739690294 580351326 248354810 648677946 859189984 730762929 876793772 453171531 24651709 889635506 986629826 220173923 962655845 370590111 224395086 388181108 240227153 648865618 284885517 668066808 438432192 490747906 898635977 575523543 950087611 801448559 700580714 52980920 638391797 162009856 149503729 314165141 285346919 491876873 900697669 451310737 609869725 138488952 727025530 478488880 731727999 989194728 547151929 457491507 327502599 296751467 152852808 18183592 376808308 584456675 267028113 838138606 821956352 636721733 347650825 154642042 338046167 339740683 611297935 835156221 918059060 85857365 759548258 266474219 320027323 201942733 118914425 184241993 139552002 70650035 939384869 760135354 57538453 250323643 518792911 831936268 815551948 80860073 583702105 193927893 738525795 766656168 837676691 416205986 288304906 82872746 980658481 383710957 930438266 561192279 578478843 868424590 83455302 285713427 508152872 136031682 239179453 957654092 328825392 41845465 879735436 211915059 360875848 570086769 16865677 675076165 854150562 388172785 526848371 572859323 300380956 117029635 883952063 671675581 344113672 676323674 696200506 480386191 966216896 855512718 300960861 125931352 138014883 458117357 350053513 731076850 318208327 942746081 17288540 536436545 858017725 770488231 378456417 446245267 897928998 753383781 384338072 621553448 653084430 570256556 630752055 140556335 832819653 266208939 86659802 85927583 298220641 17391166 491017406 558016094 537844326 464453326 556330915 748135326 252226461 797034507 109439393 152928722 379418224 69404256 620658337 521576588 19982008 206171120 307793609 653746472 939499097 678335628 651265157 423298567 143314521 189601498 884606248 564720459 574962219 460969090 212532544 996029230 154250650 941477466 723882624 645717498 254804286 252728661 68925381 843233948 498166204 363033672 77410409 140014245 955872059 689490609 136856170 725368164 101879352 620398783 312484735 824374456 813290274 909287272 283067706 857657712 211603458 838323573 390751642 835277302 661579053 250909407 967686439 394419771 315679816 417362035 638766754 432885971 324100982 495747225 550633362 104880610 118576322 660974319 36723214 39289018 22320106 302187253 866229844 686441920 829834739 351768312 399105703 553274885 781445171 75352843 309014133 137892443 94947715 210642319 129023414 348615887 67491184 491732247 719241063 537135602 937140642 835875298 215015046 986910844 953991679 94165672 172548141 552153404 477159333 561968638 100198307 49008210 355639338 960650066 953421833 426643962 575236954 370274811 973120801 140690375 935634259 853035689 886804385 686953799 526241924 616033011 838749724 915994976 550637013 696158934 774165144 69712240 780774681 714080 731473094 115419195 956269254 38271653 861650360 754178106 540994450 357563770 304015326 353282669 872012948 809352102 20611014 44091967 870398468 107737856 91444506 160532790 885595222 494848477 855700107 824634500 523836644 765055747 713808817 402530610 875604566 332800405 347260385 4192283 961376200 987133426 783549966 450586270 847442791 178669848 326173989 394378271 660929700 380749257 41101620 397266787 322141983 330967035 480417125 798416315 644727369 122885338 773962616 62876180 935777238 881051181 351985591 519887158 266689018 194950649 482620580 761858102 498985993 654093203 795956360 879275956 453131006 21278040 291000125 866474436 864576852 821647672 384573164 959278050 576237134 508483906 928456653 376644253 515793526 898545437 476123977 66293280 571723084 54023439 171881346 419835431 346208315 149524221 847667898 602371874 398254278 427025596 768417684 743484608 413019416 72976395 85472585 840012423 449967597 409585522 164044121 564255901 751653442 515033281 2426886 21316701 700006289 799091075 185173587 838980935 21780089 532092965 474320338 797952117 725167488 372611428 678715273 814040096 673437298 59667302 512081561 776996697 736564321 416680104 789243405 585507673 410649228 839794827 65399054 466897555 626011252 895876332 768818336 101562336 276967800 453298287 714440374 39692640 631204786 558896089 626264407 237782889 539007988 416424175 600520946 295880168 406375053 783278841 482110462 585484839 207390768 276237544 711515598 698468687 741129553 819447271 579858327 807829987 523789853 652577223 126609993 20953834 752042105 684162377 977190140 403536038 430564688 191227694 814766413 363413436 33301438 245372930 205251615 877079054 754160543 776905661 692343223 504795501 76128200 969444160 551603292 439966513 813088463 9192987 844128131 845080005 909603781 210265359 67923849 685279570 12710140 40478756 539332115 903669326 551795198 76171249 601746892 634775202 484591316 492847017 108605757 940473178 144375015 533610785 951306984 938662156 82661135 724252245 683494771 136298243 125464890 844171991 585243625 807817030 322855367 452562898 615722443 84160614 732894153 317485059 657763569 474574582 896081187 106913710 402984105 141065936 608554951 948002478 836638965 347818224 300908363 982873672 35757709 876995415 761343765 292470209 17014047 427853030 960281167 431386688 298745077 3050714 578138193 996332939 15326916 181233935 110092825 797816813 432327268 572235281 985932002 512095317 609034361 771378638 421052503 498353148 899806810 748362039 32787364 720153635 989213080 426716477 168608751 470712703 854705875 144635959 544138477 251852439 629472617 533224403 225415376 715056310 418194118 536359318 577636345 575998975 529234730 738468345 897944282 808344821 906213212 976642523 328248658 585614699 936193939 988527209 834431534 144892203 288693947 681200396 529756627 507306311 966948879 142299432 417812105 668803814 435065790 381078605 561230536 35476366 364180382 133380386 943706971 832072571 425350440 936900707 383309100 857310315 49651631 484347581 482855178 457674449 880034930 631912686 447108056 457694871 512055539 833216230 457905081 131200386 396980599 73519949 747810691 51902662 196635282 193052232 394682969 704588410 849811213 955786366 194527854 908734394 723965947 643144262 610625731 131276829 92914720 835396424 11785335 168077303 98530907 913982572 320858635 748118851 971409474 866141017 168380201 218187082 606441194 561940924 601068465 716080475 123872412 798984509 434332909 69187777 624212641 901906852 917860314 254570662 172331973 958628279 992087962 723725487 684993559 862223941 434235299 135399671 525636815 175504762 66049752 69618221 617124645 905674040 131314177 416771011 578709613 752446013 88609316 962395716 581859458 879973204 437160857 512122537 835807130 379640636 300786297 405046910 490302150 881607454 51299727 688148297 848875634 458782679 814795244 780875509 725433281 95893847 936442861 355820981 833279773 772905887 699490414 40041816 188577806 979781197 555838406 659145917 833400128 422538670 25486773 22495313 564109769 689976473 531387727 747747103 37335378 736704987 214158046 446391062 138898535 190392606 8920526 861517170 460667811 827798444 292866230 62391843 717389142 928492710 216994956 687321518 932885214 568097383 188397378 556320869 289367838 452775141 422598308 182863001 564234797 183676948 428340948 790351831 519907557 232236400 996156788 876027077 764279608 857999387 146292286 66196784 695090522 921612581 269396934 682017595 795560394 810613743 470487350 504535550 740090944 232287044 139088509 114404218 833745409 653050428 424136643 695609734 642053063 896683713 918817239 218041949 197714556 662888457 26012893 146378205 948212231 957997231 923804454 858125616 783605766 275508578 120716432 901408853 267389192 855817062 127302363 712558193 313950286 149872184 122969001 76276800 19469794 918628879 58014384 442401533 116241186 127085086 650850618 214229406 528080071 821743792 313681185 363207757 8749885 885149722 886477897 299466578 508689068 623423749 605895389 304971158 477738748 188062647 909474824 558209167 735044802 621303561 280310261 812410466 110399376 100828319 917447911 816584462 977250212 199886859 479657985 589310972 680192000 349258295 237377210 923955283 242773958 536131155 530587868 968559535 255700849 916471455 460887363 306733206 776101507 125715937 900516849 523545431 46773529 991404142 924144869 562161317 187427479 119727566 754349906 796771271 983393525 859000423 766036012 443290853 574449843 926240093 604591893 316396858 846119984 200085964 515822920 101865288 666571079 223853678 93035756 163943339 671193080 82287707 533471840 231074554 825106634 196129315 275551426 409485947 78331121 399505916 35425820 353021996 524766376 859818977 886986119 641360694 210076040 149505364 112790622 301183952 547956458 182950794 946829704 858114078 67404881 769694442 158800247 76623273 518238646 853541692 566028736 14187892 679428881 906909026 363097188 726223956 97696415 827115549 280716082 602393819 271736453 263205241 926052600 950634402 109593097 514877059 9985372 714561014 90583387 914020732 179807075 443142361 794450526 923087800 759304723 681945172 331077772 66786948 732140451 855152072 238898510 204104983 631002268 541344280 165579156 399855144 156151759 40834332 781047548 640721609 242486948 66926416 212122648 217209629 188119702 950834169 992115311 476498049 607842639 655685710 367378455 136107533 224038311 558413122 56181947 580707855 604043208 770978034 56289968 614489715 512430809 92383756 502371343 379654478 697341440 876823583 497026741 488419240 245707541 337208280 193156220 681539845 249336103 16032952 760604100 339831824 639341832 247832945 793200048 526236127 155953184 39775596 221517100 956952972 627671504 640606784 705128583 268662831 855313361 34896005 926100777 17455840 445922588 819297541 214532894 765180164 130466990 86268805 680716429 234094530 386269123 207550401 883265110 4736571 205702051 376747057 738282438 23819635 392506162 435778099 892182913 767724155 131142350 683675943 81937969 462943657 66655878 213876532 157203806 436503676 328882278 715413018 55568883 598111168 308369221 441344580 591499229 284029303 827024724 283764209 560024472 543725633 67434386 413519234 50189400 500585706 650447054 237227472 903562195 289445394 154321925 137751877 452366999 740103003 181520630 879349484 80499293 481224566 80644854 815574696 602428342 401170751 596209766 89203510 436271282 844125397 289359420 44032945 470341057 223208326 802214536 12068647 804831668 774082409 887279786 487129286 54750359 321561408 537285236 297485192 226852150 634164112 507668973 433596651 385154890 567702641 251455491 958196818 131879550 379961309 120635086 485961575 708223179 534429912 891784969 553090759 13570138 229741003 381530997 52585303 60451741 5023717 802383146 302981252 779726373 858468938 830675842 578852189 319277959 677367983 643270507 927962917 509670362 886739157 18900706 160502552 466441693 539142448 684194239 194349916 350858921 523742298 799395520 624975767 892025115 78134721 745406457 533624146 973514965 264841460 190428400 283398402 829983767 109882308 964029267 770822565 390189694 527359848 64609271 698692637 497824378 650704968 973338775 293845473 233361612 30071079 946167504 332738245 927970721 653327172 615460562 365785789 751384143 121650863 110192811 750082819 782085298 351486348 541206074 956051600 306793036 361484720 320174013 203916620 372601080 304980335 286202007 442641569 678741951 456576240 259634866 73451923 985600816 649821687 750127144 278512766 397926480 126797712 43969478 516546824 189120133 500715711 570512987 103761320 652723249 869094155 999691012 492173431 307403267 356134825 244317428 719180517 262161744 549207672 491630011 113438770 764188598 496032970 464616068 507890371 640166919 653407216 75793329 686090352 544217891 461241307 855638876 411112297 331768908 123180991 98332447 93218597 96932154 696211012 938216628 526849769 472439897 222105346 327688881 403956446 252277764 3540547 87537843 803400300 46192050 441787894 498183069 5137337 874810243 215397577 146147448 599933031 837876689 736743561 592114654 322612104 227227524 744868665 606619771 547133028 324736955 102952031 545275149 751717651 504585081 428558720 406310725 646181903 784219998 362082821 663623509 783626828 457686120 374184606 103865292 354827512 914774224 652849727 819682374 712742311 414252365 354757568 534191276 751940745 941200755 326495616 8099052 543023806 208593934 275141292 907887268 716138055 922510122 290753537 160565812 736547671 881178451 869054668 963866235 778019487 811679906 643462779 72851600 123893711 755406704 871681141 557534575 76462888 920163442 330535315 798922674 171613053 80100197 38450403 242299299 205599716 961160415 153015070 936771330 426040508 851820497 472138868 950437375 62068599 523681886 777083860 507603149 548841529 744221169 773642056 345908951 336288062 478645195 453570679 736464877 872821908 216371183 90992491 976974031 418241861 363183396 679648270 242627214 825128452 103392404 738239869 572559143 324225897 671386641 799952283 554770704 136063430 705577968 847568436 797858429 19801178 577383274 500318104 614411174 161610187 173231750 173873047 289917702 862754506 323760536 589930256 703238432 499864568 208374816 168204823 880068787 697573742 974040182 719471567 314049587 696459362 593976645 7719531 599550619 414517490 388943420 222762682 597469523 437889800 13710167 16911362 652947144 939267984 508425331 27002583 542538475 884724664 773009750 854150352 96448023 572491241 337068741 522861727 18437373 30852000 929191926 933237001 69909778 592631440 408896791 588636961 755426212 632860257 158000520 114075150 15835430 159440866 233582112 547609792 776218332 460515507 330152061 400016797 569486709 83248808 163637689 606660748 726866493 334763090 475177658 475905261 333725347 852325050 452464122 44562808 427015463 420526980 598603348 945979729 880645334 610849572 120576289 800717985 188210262 657246170 331783747 897409976 559490611 733015809 201944417 25004945 491526580 566518526 307460368 965282823 736645499 561678155 428805835 842759283 9029230 389664557 295736466 606758724 609417131 764788101 908516330 862156580 262475206 782649703 90696581 320742746 90015866 501389156 258496114 867098613 190933585 297576132 861427973 422625333 958873748 85047557 61239442 962559815 234562854 809387151 542351210 539395413 886944085 63665842 660179500 189260675 922302006 10907822 994982001 763586334 32930513 705836929 905358984 250749221 153333748 766490573 977942537 522967054 927124312 124100022 954419068 162048481 932081155 695953434 871230985 400691624 913507535 248046013 366816699 926019477 907912810 980951935 518621609 140997929 155231147 439812633 483225274 293676933 742791218 637658996 629587550 865769458 596169232 304094134 984135236 797896192 30505102 487235276 423210221 21970881 254174750 415236720 75770578 655861179 735867765 143477973 228193494 144399591 727576424 565729689 104860906 985248401 115199542 406231894 877664651 943593777 90389934 119938261 442820115 90830622 279888271 196980314 593437176 290054303 664143345 741865926 386274519 874515816 715253745 538274231 615429687 29553281 55706214 870307615 484470501 431815497 415076666 9651400 719400704 63659942 693074953 907381732 873341890 108832144 253094567 54753385 541714917 110107115 275714575 773394335 145601894 21524766 942469607 259540666 798491242 189740244 551510214 61004660 844454546 796779975 842795031 448710557 872650574 152093535 627962888 664669060 912131372 846170122 622710396 29655498 860377183 851299866 381564334 446985691 850700802 761624698 253572693 937554299 172886666 361878214 429157097 278817901 346700207 966475635 352014298 260003411 406060984 431883678 886954546 334007887 820052237 874131866 443724120 669665433 525709831 646860026 608720201 153771354 916226311 216531658 649141730 478488478 817405510 706080408 735855030 895448952 115235752 314581971 898109040 289992182 564511991 326317164 777762735 241366590 527024964 586659818 370087825 964805429 454228647 751999607 187386873 705234271 129807600 286690825 341109689 635651353 913019343 38105097 533013933 633054269 629333665 905902712 688783638 727372629 770475912 356179165 792062373 435438374 499752854 355436939 124800770 130291728 447881852 134332149 254142172 287846673 861049784 783499788 424000014 927925169 595809632 823418912 509368490 948997267 720115881 743882896 28586697 615805898 860663149 290173330 741282527 158670313 881335318 245513141 542899558 743558715 816337700 69798226 24056597 453857859 15227372 324879165 980368853 403029919 547048306 310823847 443826416 571637925 69053525 849438716 914724987 850662656 860881401 560129882 791194867 63980122 691273755 587306418 14921200 7092086 367365883 668580382 59612144 399987739 88901808 502970339 689845459 794604653 827502560 113125744 970060179 795625161 871383762 468765238 621638236 361779178 419673384 520721022 185029265 25808403 144918507 103937652 848210917 993717871 646995927 879624813 873271901 242881182 566111293 675057839 104344812 978257359 70170250 174132857 27461321 297943869 247031435 625473230 236275480 70360296 349964459 844393091 343038460 420034899 287390985 325301790 533562251 986532123 763955164 326214621 857275487 324548053 623004461 133832037 159500229 164569203 909329788 227046216 516061883 63861343 499848437 404204474 264806468 944179069 795028977 375096876 212002214 650509588 915487573 974058269 381034708 425094921 597160451 206476649 820805405 41853660 779140641 560073463 552750905 278797731 619050430 139215419 791745917 648117105 631835591 983222068 500227241 834103182 224633402 342420163 887278599 353855396 957818581 456639057 411517015 558455244 645504016 692672518 350895507 269640925 142691970 505653781 589190930 759477290 485726939 37611573 350123757 452891390 195710790 566579364 959960313 439780301 118221528 875926858 300664915 419755476 831763544 79241167 826570875 121456824 626887768 11753835 430615081 973318221 421577497 543968288 713259729 648868760 334353877 712855047 869642412 648349715 501259679 368149789 859336386 765361987 528793405 837231360 831247707 841864493 47213317 645234239 98151155 778266321 926111416 516064867 300924759 406411353 281140465 29960172 184592841 473638952 434305312 479007431 795731691 717874292 777871940 160749953 867880207 503746402 675355069 881385971 809061419 745920406 943637406 209759030 445354569 359967218 778850271 521681976 19865883 230005339 243318713 402525825 252519326 436202679 132609846 933372250 580287677 206100099 73155543 45347293 889994849 463124393 190731902 82060653 933238996 937736642 982952009 464186167 915041862 426325633 836676726 372285386 411078882 714929985 127373391 354225368 588200705 88482256 414005040 313214258 121205399 868903618 695247884 127012372 673411383 33518337 949186254 487956262 968953388 903863614 573939392 739592559 300555962 76025958 451443553 139386805 53566667 650465797 616438757 201966656 143438804 843522765 992660583 38855449 90479395 384398091 723582925 529665769 797798307 58285662 259092127 367655375 617700533 383811973 377585708 397218681 899697998 416386968 655239518 671811427 835336138 272002474 280567310 703483103 443672753 848134399 906371064 557982466 174621984 13191325 478235369 263918663 631291074 200137489 474629546 995596393 966329870 273720401 75642085 644664857 312166969 421196385 523859154 800723082 540403452 628854522 23314534 367309131 736007726 8457303 817756346 596456594 120972984 948025625 918640715 628114360 662296574 275715704 146670629 307400260 188120569 907111578 511806465 575437459 812829776 937354427 958525852 533458292 723711695 435749838 710589403 562108970 176418135 313012369 916869305 839590549 464201247 257026251 172669620 140023862 584909023 196612667 544446350 300283345 763369703 955218705 635695249 840253893 979767543 303960606 795479122 11377852 175278000 98508849 196764460 852266351 455687314 874396586 347064468 870996374 492809710 766526567 942809844 761909938 328808435 393052496 835823226 223573267 722616902 697067608 391062308 614725464 182069553 451717250 217142275 815027007 70723945 523856155 999298361 677946147 824009556 592259414 571176681 591628320 643545925 464635651 723523562 564568781 917058321 93343938 629919716 742385366 503533276 334508851 26073013 752115171 174396702 702471059 923164584 33807746 952892541 419117026 343902796 52124830 751081621 607823630 344805464 690216629 100095308 433723693 241292244 733156593 420449729 898567524 953573892 684246374 885887399 404374940 499036893 669156482 392083082 893984950 213862892 649126583 802691495 21914325 86917951 198477147 542497836 277827253 831298235 868701828 703894783 955464818 891310675 953817271 481097805 782524377 722416722 893273935 591127478 574698023 922935453 835930188 671620900 348591651 239046832 170182965 67403238 37086871 848866240 539798521 229104918 978059272 535027134 261518112 881470623 848998109 63344165 653671501 140476542 61463796 464646322 419011045 86441265 69008478 810925603 931315112 794632201 118990972 923683202 934519535 386425578 329563958 366069339 7916359 673543035 884515673 82605389 893628860 314255543 451535259 629783764 24786089 687162148 504437739 950340166 317875173 512093963 242914644 719488033 108523570 279239027 3248057 788238555 382049284 382260360 446198767 620648163 53213300 235048534 279012730 291331214 953061495 837584651 887642454 555562399 623662708 785752218 990177694 503046870 569057752 934171103 579564630 631961768 947825180 551186775 49525301 183742382 380990735 338388984 180508336 341216709 423392060 463465425 71638901 42585950 470324180 625839998 621542458 730137753 576309477 668832389 679595917 814202302 648813058 566202774 133078276 350155038 938196485 103994462 544049026 509396183 939577975 887315107 762960052 32409098 282747359 515574018 66577309 499579058 482956737 629890240 829441172 374446868 531241312 811584685 290745635 69815615 158384272 375378037 737380564 499676650 809488483 591711638 117000556 390432630 86579158 663618664 891024817 532039636 9905208 575914245 886301521 448758138 383327778 971603152 55322754 511016769 104171763 400894662 181126090 133979442 673286684 109167032 751518795 438771329 61993222 835486226 406748961 319263594 417462774 339613033 46737683 221102993 763589434 721849018 193736095 992042335 464424019 684471122 253425286 129394741 342811041 295308615 988503009 227163096 193124749 123335246 600120874 314755612 42982646 99395338 345397774 408145749 354963281 158446618 141919654 71774315 272504519 145967844 244798451 22716197 612515161 349755908 598556632 776911023 125876605 795602583 126391535 675953329 235359080 940245633 995453483 214017628 85111635 926398382 215407866 276862819 783610982 417013802 987345953 807278201 288132138 799894527 716358879 398448175 615712540 160345336 924021256 88246793 76100710 901932500 566724446 852330083 353434863 321138023 355008519 379817289 355781433 582083449 74457517 362396598 116905865 301041455 136089716 189131135 21056240 248906619 157588903 359288173 484023105 694408534 326030337 220842373 992916355 330270373 551633504 768262141 19735411 967279721 305606458 643310020 890889682 42087031 833421726 239622094 875624233 236477280 230972193 595716009 217872089 999963265 979504276 172635783 668084572 391564890 417529968 362875555 680804888 482766000 234965329 972982232 945170137 413450526 310827344 665866960 970864465 644044688 282560676 20927261 895065776 71392342 649770552 809825807 252373448 325214825 705768746 458321523 937341825 848814248 5215706 392715426 444408040 268765423 540628903 774538388 552562083 21828727 809139369 27400594 248379905 299289012 597717332 421407690 361106137 538289086 951581871 975590605 905887740 295413225 635492779 367143377 912327068 271386591 607980321 949979843 282528882 650814691 131444227 558533391 209079158 694900340 190844119 404623773 12285939 356301674 835247326 691524111 986846132 671802499 266258727 375866362 460979621 648180872 432048385 295327883 543195125 355946495 708026295 150550866 683428715 986732109 202857330 264031527 53860866 888880494 859160454 288451689 582662852 109675491 542173862 100530109 366424771 819305616 776458011 525318965 347880272 63997704 416690550 324667358 944711821 426031874 527669344 392366863 594273981 996599694 801269702 767556115 987179025 842881744 615014857 82667936 971409026 976685672 711564974 851506730 244480932 222296230 285943508 230171253 499468070 100903924 466285496 442999842 581346342 87334409 218158494 995508141 591743487 677538772 185641816 911085258 94952730 785326108 111608261 727380861 909476355 876847177 201502685 55421693 470533305 996078001 357438309 965958211 319611098 886814301 89228034 197166325 983152323 656394625 824521094 542978481 186629855 261174380 517916795 314026717 668704514 190858375 892712830 329520735 460718364 160277120 46066154 410967335 298659797 376532723 900505379 217628436 357554968 158146743 176874957 267546221 581362307 882235596 352558103 13570133 534428996 274246842 968598298 977500256 138799455 750041462 281892232 910323729 743935241 804227438 152445514 904601040 767144037 483603702 242786455 620586263 273515107 350977060 760835858 163050638 363374591 742491927 426529965 278741995 340073795 207826637 415998482 131340917 135554433 925776126 829194680 666475489 356819570 375438682 159046380 682794485 72154107 565893566 661742289 65947816 688914210 693048888 124321873 859173219 154895996 685821984 786777357 130204437 578067635 200736831 291086101 37045729 624399074 350893674 208266847 987392557 556642365 982150119 676358817 30892169 521303814 450895104 500608093 370512700 593766137 968637222 914665418 252049669 440552963 422730470 81058377 395752176 220355560 618649247 131484454 685116169 169743768 445642077 403057383 621622313 673324995 256759829 385893381 164802466 407015558 944702306 149525468 440846963 187098347 120434290 255196111 155955798 857645377 602825410 916020529 410689981 16251879 525803940 592574069 947169136 911776904 836298216 846959196 783541867 276396562 783140615 628661292 825395722 885207923 943551196 641018198 871354073 138296703 334419285 392663056 444706608 635899312 379614491 205087681 746275782 948336555 517904177 110704116 11192664 518325635 277976504 542383598 274376624 477493791 359365982 816398987 942798142 350109386 907803583 343090618 5976062 602654712 59575767 772073618 117456838 619464538 591776558 34312211 321972474 303884434 836355252 977036394 78673861 634157497 172619944 239079280 532284730 930813392 261565434 594227381 595353130 430688394 29730104 861629663 299728906 146063623 150626418 140297607 988249821 481458682 516568909 429771486 839153230 571496904 335556612 339648829 936619567 429657540 938953286 257660847 286359149 231000443 127280501 846657507 592493847 603319554 884127732 796784654 844680057 850710158 43522851 48720691 875988004 422874654 10547137 990147053 197054258 426437451 304597729 449014222 301791424 825662006 542328078 309859883 296386875 533998222 450207280 21898353 88509095 420383056 581441832 211375177 784498397 92371577 376932851 940045838 497842614 5315270 749695696 332403653 495415827 771136376 45749753 393817356 410686374 819871327 684112288 265148167 127422898 1428792 611484354 879127772 978708326 717924004 555209458 488729684 318526179 870248859 371674617 938287021 165842611 341159776 737024503 307477546 701178850 353917762 549467769 268995655 833782615 326467292 940448015 410119000 228980640 331496361 244854362 100668310 545909665 150392601 135094767 356212221 790692570 863217579 354261501 473351980 346094060 177737132 577691888 938135092 735068670 114075785 65884609 674957 47264607 340651761 131413456 791034940 468220008 266929969 800694571 806611897 329055843 222350662 323294512 129082988 748592225 670528677 696869463 578200191 607990626 27808907 557693624 400870126 46821932 119946711 796358085 91453153 426395199 615740673 816235857 355550737 317966496 641192048 511680322 469166803 416073882 122955723 620556409 928437692 861204614 685638347 67413822 166345143 275407369 194228913 333175133 648322845 187381309 975308763 620275322 287288086 56031169 190362302 844038561 488632850 154705735 937286520 897378218 594869667 861374510 836576581 776462530 203947059 190997795 922400111 412965621 118943547 932526661 866986515 881258171 186768053 30879191 741109136 697782659 167447757 944972193 596475262 21941020 395198452 658618902 272201446 937189809 999033620 700044440 810239968 432041360 271235263 505574272 387667013 856975644 233966611 506372199 894410875 128792917 638544883 95909225 311698727 884095825 166609189 840412521 890934760 23221102 5106346 719089451 742020555 790270463 82148932 267005719 495114614 656187862 341197052 285330452 309837933 612498784 675381180 160416275 838100707 822821860 136877781 508277857 14143388 67328248 788905034 685667938 690420727 953884862 167726508 853520809 289125438 390644854 598990700 901731724 909358637 76068197 230239686 55680739 113537799 644612161 376246409 309512392 93057595 288416099 952039829 786784161 691784608 863758274 743795106 860978168 939207130 600325390 508961500 724821999 700674602 860623969 920981878 742573260 937508432 146162267 360090881 678721851 511666203 117303859 911693517 351039763 823132885 497708368 240078240 226619299 305235616 543473278 425104779 556552774 6865017 392215304 240345174 848229914 682380987 810129774 520302553 6386102 817735125 704489882 271593086 373948215 723553630 229135287 248324547 869182996 402701996 315659200 37172933 669903330 991879490 808493959 868609032 449833429 308060776 617289664 853957254 490438434 542553733 439264355 532976705 694165840 991886853 811492359 830456340 542981807 434659080 374211343 404463503 767094977 647619428 692547929 455520190 6805393 919490306 652339483 561890306 718663892 402654367 979732037 361915571 188551630 928378441 367390845 416329094 169578573 139552941 931097762 525364832 867044867 476822619 775925951 427827926 433969036 727411666 560315437 15373910 385343268 19290766 573506750 738139189 570245864 15582356 283124047 732868439 158623167 774669436 702061511 797130781 765173345 857178737 174944370 581313221 409376162 71059170 782407001 848942991 344087715 776805564 851450239 12039148 463719040 124545701 553459147 881326207 919023741 995206838 290182064 686841705 812945701 376675447 37296974 924768087 624862322 402752280 154486729 700156626 434647045 95478547 252543486 251669102 242164700 9828713 828512720 869429448 100783661 948181722 917125070 957473760 375860522 248023264 779921487 518539726 646994159 939193261 117728661 616415012 814644510 141179256 735244714 793748323 37380557 889593925 149977761 568116324 89972693 35293776 766926605 983597019 927884818 38875141 527087952 936906761 118158102 43201231 22473873 50826910 989362843 879744120 68233028 116388515 314267366 927178729 156893779 721953837 882716632 830530956 640383881 997309807 892030583 233708567 407215717 709262897 55028988 961335991 947043496 196220005 488928665 835746878 141118147 8911273 415941751 87723085 967095979 215581472 956551881 688314494 164618532 513338162 75320666 149535788 117753335 312162073 667707071 906772508 413382576 101593477 781438663 74964091 974955612 839222706 953845143 448387057 862817242 631406687 883721845 365503739 754780560 200124886 556687487 307229807 615990026 688090238 637896994 347937096 834903547 563880840 560575930 446668135 393615746 157375698 813569533 181357082 221795202 409214069 559562224 100662471 959991191 308199898 436739983 518204749 661724442 577608125 675825886 176281260 108690019 170061473 847575538 492476873 727647221 703869808 127506152 889472871 789699803 954765103 598337499 647495655 987766672 680313818 918444045 890354180 772227185 556937092 238789984 455858066 916093023 568860584 79020869 728069157 776885464 321269411 125568708 474853344 599079958 712739273 367264335 85864089 508775945 445206340 643218475 989323327 441938605 174041385 861901387 350689634 368898310 214170010 185615459 223070479 42254829 53615719 435956385 152151571 786416644 595700412 750815406 27323312 927415506 481950804 167115737 954770909 601543160 367706101 662796347 142569183 267153449 765060505 564195702 625088857 652989702 78433248 486025840 253547260 357046958 206872052 105478569 335692437 304443969 989869373 550982377 623793722 304843430 274759219 46167008 887673468 304324970 311930264 252477579 354629311 437806811 357701204 757974014 467930476 974644761 57452454 136460633 444658352 539456658 315489887 216343972 420938885 356992577 385825310 38906439 242928479 669301290 212670335 329486022 553546031 653083575 387467038 714967423 530567839 256772712 935445111 362212844 114598966 786327846 197385583 878430547 812727309 431001650 446893805 593800544 738161500 765843776 202431741 77715102 23931013 282500211 677807616 839180862 883176740 517063493 493696767 240283491 921441823 789114529 565409936 719187692 945763684 368659953 427942169 82235947 995578531 149553041 449418511 40924085 716805937 481917495 844507166 12542460 971378077 660041376 903318333 786868307 767283325 398486893 774525126 159650907 691267065 825462715 703665449 718939940 509389320 585730553 97535968 736144284 414885567 476072534 958335646 780147129 296021918 947221337 277078151 408640740 710073276 636449212 110630300 443761739 111110937 926813775 628938631 120071306 568087028 825713815 97526779 433252620 580166323 215096816 971100627 659033286 148578847 727024129 240718007 999456527 593388912 441894036 147074961 129699535 868429537 578264611 163566581 471141778 178153853 327853861 231955272 492806376 722864655 522084100 786520079 947032950 584472359 670397015 564841195 546265062 190306524 133878818 180413622 879385794 999439364 996236529 32363552 123813624 102204019 553195893 107800507 970342019 832967653 734867732 530098627 443137703 898727594 902992592 91489242 964248470 300434841 634987704 399197742 799858706 504748232 270461452 540519151 825558218 562061914 429160858 104692598 976479776 111589120 768848163 706296526 573706314 942810391 655103586 836780836 168974066 907276610 235151517 500912598 682782242 682704465 905270923 673205281 541695240 732404536 13160773 761300039 805316895 148378484 812223574 342172569 188421928 999401200 24886608 392938198 763436677 389913579 223762539 451924149 50308471 402503156 203539041 741967780 307052069 515730586 307801913 128866429 816199832 561853196 202736685 319171204 330889389 444399407 430940752 18784966 641160486 543852346 697056225 407256143 204019363 541299160 38351825 123136566 469501379 612852609 889792363 238096062 935935555 152909620 665091857 316264927 469827984 659742672 516780426 589728531 376274524 507662670 888185220 633283944 463411900 337854211 398382583 894201536 956930284 860954548 405904285 491869750 648336774 554124916 787458790 289400417 906293431 829246006 919491836 917271915 254190896 284925366 516031408 829552420 725283225 903028016 297586860 483878555 86295000 219801869 959702252 837993277 263617865 741072841 883279998 714585434 170034413 38931184 694467494 696228105 240474410 226435170 243704783 86157710 572407255 152508002 938617915 474977771 770437854 922366861 438113298 596419157 776011111 181536240 91169051 962844167 540887637 43293718 771374538 956096892 266915797 758918559 132427364 251832072 888843248 658693835 626522548 118184766 115748528 399666051 815240884 355766342 333330645 394350451 286891886 47988743 740507987 369982587 579010924 516870299 206823795 653754646 66298834 622549795 777160977 297596860 128185464 805721894 293517399 952853043 403253341 686285396 813331926 136650902 36682490 710034330 808509194 457933523 812650896 22357468 62716614 780366000 768621448 941518396 2750835 930986811 295004090 378022764 973282682 401879861 238965595 510542566 393697679 840054095 836037551 556201691 173610349 65843223 16108826 751039952 120416388 364452613 533947607 923602714 58315774 180486474 968262812 252630915 320361715 765095443 773306499 280452918 929348530 223222946 715029341 355075652 928101897 53268722 997649736 495736118 513985157 508588983 731223643 364383935 645102509 831636566 232132668 26728875 106599916 678603266 29548 716924701 129167514 568382585 85588782 48176197 898782931 175673539 855405823 582969926 809548249 46907240 566050328 108003338 30179207 287971780 903551111 345000531 96348365 525798785 504678098 124322761 953495902 101449616 270930942 674945155 569292494 853472923 669624479 773122780 807301616 496576610 877806808 717232110 556252403 170088611 945586219 101919726 15626356 207064847 69024100 979675512 516251143 852384870 562238776 252266850 559284667 283458689 415542616 612047967 153156724 51935994 923329771 457995889 389076165 216677158 845089598 569255427 614530462 160702843 646330842 6263349 950405137 805449288 464168460 732964815 888971460 845396308 562633755 232590607 304711696 93410881 17022513 528218316 294572604 642488477 401724925 610014338 6008592 454941789 680858190 463522926 35297161 323805800 664299816 644230166 416052693 713832392 679502893 903944807 789826577 309538777 718836125 559382162 204051625 643812083 248900798 33438121 839591672 147905504 617129331 784515178 431184516 940056773 479452157 138662103 647075849 405581158 596124282 313953184 464606115 411605962 155771369 363176692 596738507 720970730 882806411 932084206 87345002 857774923 603591299 137014400 427019817 639909503 332357590 377775965 202442419 361104799 142833894 398440918 640127301 838225596 279706412 178397472 594518033 236852739 890386314 480366012 534856098 780239773 808219417 793516321 658635454 743790594 765049763 610297560 538276548 145754856 947322408 857459002 842937620 765462762 606889366 604189543 210197353 555132338 14035323 728465582 165066017 974929192 829304784 31782639 20426646 625943752 34916882 556807564 246155924 371413852 198198630 979178991 681922714 648954351 391558130 125995775 309575600 346140248 160679701 496988210 675036592 476083517 186721403 774168226 672962654 205394819 861734199 104738245 205601985 805132352 719324435 542323495 635704055 631140169 868539051 909344985 882749258 936726781 515799332 93449562 897993828 541135372 519183976 249909555 738468616 159521880 777087701 785621663 583515811 519223482 72290108 732969246 833195191 273040300 318145541 668277951 737571811 937699290 356782768 284676293 677767619 896706139 36068599 600289183 664035822 986799151 461008844 627454784 979372572 631594515 864831247 34403993 861875900 669052737 220740814 683532589 808665507 528345766 339094435 659903966 181795507 955523535 774951878 49753295 108851684 45364380 561484191 542336442 647488534 579068094 206979261 953068520 699571340 353347677 824218044 541184841 585280379 719122285 634829569 107427296 867504833 131797228 50477370 536436624 468624111 488287718 851290623 68144665 194652051 176878525 578881066 194892380 552464837 880348359 932399412 21931159 637913640 812443105 820691809 769480889 484792957 246683193 249689486 694266714 16273201 964879653 844029193 963183360 439025857 315086802 264887308 870150279 313611066 362645056 166382441 133142734 761382590 325265177 637029677 974344793 723124173 649254225 134111118 20052785 479190859 853165604 76555991 732592920 125762165 510169851 439511126 528249886 830544531 915459921 585999375 126068782 631358353 311476729 323902803 924960262 550074407 399285925 7677462 419214859 414786936 876058727 816228007 646704710 269119185 100656631 398269542 925943306 323488530 323543578 879744289 610888934 692766396 569290440 56419793 779380336 751077693 298262286 110330278 476012876 808918241 304183271 547709513 328226973 378998579 221439680 461876741 76666532 488154487 138115429 134013101 192553918 640679324 229740914 381591021 986086090 198019001 595119787 974295020 240654540 421262705 586532131 750009630 95684790 860809524 203449153 450393013 527194052 664136714 128993 182024811 337791070 915363758 735793721 553897146 919370365 792537416 667566987 859288606 710043171 688932615 191469190 798556946 89069757 407242154 851178735 146079245 863967305 794629464 467135431 905691613 822430140 595491660 494472569 293444928 752350932 673529515 289321327 393308203 350864542 663489835 717784791 54364935 517905742 203575880 463022174 609073316 937369199 823597071 395897401 270017382 722969985 493363165 906111984 558814343 334124626 898974861 50530031 721615513 971536754 281058395 580911639 137003529 228203341 935808466 312859079 289573169 686735031 646542089 772719650 726506558 963946658 342767732 356548674 842785235 626551668 378972558 158844558 797779361 342322226 932271024 993441600 321023507 631041056 809114053 771899758 49771884 48103003 32300108 316544397 997547920 21854432 115725745 6096318 495366070 486188777 429297463 148830496 367194848 256285983 244677299 73861984 716792125 573670919 927025096 228835767 905997725 37073854 955398616 380169514 71854108 859894203 769665796 668835013 79489903 476696946 284298654 425678524 658853310 966764803 372330504 436055488 810291215 606289895 462978814 794383022 138465416 447894229 845425917 387914461 847269341 896858974 507960364 270909657 890347631 952957411 32629516 498187128 545983189 503985555 691380637 199745000 651954521 286739535 243530214 541828588 975239673 186661513 927212446 36218682 892543649 835020624 122497152 353426314 584985269 340549886 665937403 662152373 189048385 685331076 982697075 992600965 6280593 411388140 786505098 710066393 114975867 154121485 683768576 283579446 657608318 197455991 121758084 741798846 813951011 875941811 124698938 808056469 560965264 47181973 932534754 953548063 989807635 325948504 506363440 816918878 946837870 276669841 692537771 369130334 465547718 605711724 320223306 854703695 167308046 659105850 401991331 83586835 807930683 448090793 703927609 718427176 954029020 215750295 916494467 476856473 338369149 460029473 107295253 275056918 531426229 601727595 150439416 811890988 56939070 232271825 831979640 572242893 609718390 878895242 715675100 88111470 393712139 775664165 451479921 516856465 108076366 953501102 697771982 30980813 139272261 534557688 440845378 404094283 484635568 316900187 350600800 242362418 983992502 578206522 476259850 264312633 678663487 473546260 995218836 710794880 706033161 114461090 492053469 416469648 956070357 4249973 26919770 92857599 893218706 853438530 396442846 702139414 530130032 169059468 853642279 600943511 625248924 873622468 329079980 687658087 544774557 24446956 407918315 764004508 847366541 890414639 963687775 88307669 185009716 636113960 423007779 622424861 417473054 783561418 314565351 873985427 458191402 704518730 102368810 951496425 696099124 623571626 795293153 138731525 480207407 586311772 752040151 147792580 749481294 651689739 501009171 966558739 647019624 832293467 171799268 918821389 629912310 687034053 393153607 371111194 383265192 526994046 899551455 900210394 820846833 850076186 362575780 283242144 422742529 898770656 514024976 542582010 583751167 232277060 523322041 263136881 98945979 309059289 303370259 115689692 70780803 324047661 704916398 370301198 946586152 988215152 622136091 364256815 548820605 888754727 556032639 651695698 933757703 709860531 43500119 771568672 396332176 805133918 147345687 658248591 349574827 615239522 490069101 434657671 1133774 926661785 319047596 865742411 386456900 65811426 333059272 933398334 565030776 519246089 32478312 174887074 976594698 118922091 268880567 547851052 959369943 7840614 36620107 643480938 536141342 363326705 860766846 811293046 468922378 555309379 907425638 29736143 358386406 29159191 302016939 63253928 225694673 846349950 259553095 193300484 603488529 254980476 662953629 765577444 217702727 23451687 764465807 198575205 400600120 665190010 118891208 774942827 930726042 627309184 98608442 714562267 606816446 262449312 431133132 636962856 293796232 848327571 779570669 272550870 661063174 942137153 651873274 492202192 342710703 500503023 282621190 35606685 293528444 656357018 205231189 19458041 937582449 454118728 906897795 443043748 39111796 463036674 303299077 817669295 889078815 290254716 407710026 889035850 659179578 157382478 671507966 729679508 210817280 170059731 331355588 472567965 200671529 821857073 836300658 275415119 136264867 984539055 829821478 588559236 457653659 201565615 825067646 190712495 812644003 847013807 53116106 32295242 816863521 651474291 454923423 502950110 704455438 651598679 510330666 496979381 743881325 281796700 511103490 324247284 555646612 511851780 296657653 662881464 991290015 178054651 182541471 856058849 17098393 442623651 819560154 80031150 479856902 973088344 869869158 623315437 624861952 80828751 561107708 564209293 866172139 303073556 934905968 981042342 620420342 211074810 440395669 901075887 400819317 583103592 664694878 941612954 543959294 872956141 265404865 946384386 200597246 470892558 751707372 596612418 322287743 974048160 442199083 453362290 905945235 7950540 410695289 647382306 687750845 524033773 42644572 544369599 953269428 136733740 171039295 780198265 656120538 82504716 772397470 678857866 221294632 504782544 69878561 656265517 266106566 752592471 648999177 298036897 671278120 885021864 223633536 348743639 49385438 97780223 103942186 372824231 153593114 88858 263250677 805832900 889124383 448316589 364955628 933540099 816116715 750466987 753732729 401357039 504737794 745635862 724586017 985053874 244863871 899539852 802257062 242130178 768166204 630148184 752031593 181803817 565342878 757762482 689495974 91891027 227342033 712353088 638911666 331186923 82278423 228091633 631594532 228720888 875638502 313020380 660360408 11713334 999099759 928688368 203522648 417301172 436497921 483100764 365065660 849023813 687601529 381717405 219734706 310201516 612945927 279030194 385880819 211923476 569517657 325076765 454547080 395037002 101117447 928169037 311185018 199982364 440363834 336443453 96728429 427483317 364454372 720071551 157504865 296563323 884686096 929594573 592168933 565158807 11351404 347674454 594548928 976684973 599881635 151508465 303321085 423829553 818043334 840967981 526797385 410039498 460944536 530289150 508012978 81134030 556831692 823613379 617284902 471723803 492958989 30373185 614075694 823575041 755566951 864471824 652736994 135390984 98357884 375487165 529616827 252860734 74277457 587098899 410631786 787479388 130953131 139191068 996113025 724508038 193937286 15749490 738214222 342699289 554212842 490679865 407128272 121793551 585407897 851517011 443661915 484930663 338957785 774366304 183779542 779228316 859702857 732864753 125217946 255478863 95000256 558643639 621831537 912062264 595841027 385364468 609166982 183881809 509995315 170235964 524364620 795095522 492771156 423079495 623554997 817159725 317218926 819827919 829632898 458526495 136857402 250094319 466356515 316620224 977387815 404918006 971706658 8998931 107163249 131844841 210521121 211349121 5916124 101821111 219035720 344049492 75197245 42942710 130424330 44769768 434407467 430255965 844197261 634389129 194848084 644270431 8216870 783793709 196777681 53900369 959176440 972571151 626908553 978876040 346287353 125703207 550429378 686561499 715902230 546259543 975735998 261304016 631999411 69022337 95777408 847789800 184021498 937873269 741906790 562873460 270917687 798308481 414442275 49304804 386770571 809297055 43688763 917395133 502863258 19866472 646691445 501145469 50470941 953779608 585948358 254413306 492883685 453127899 809556965 273313268 895513434 576037381 418245464 121499349 623634195 122544661 934143757 144496133 496364017 551517386 171945206 807997076 992960942 828621299 589342778 337660802 388337438 816201304 798699258 681713944 606106948 315005092 786180022 527035419 909482270 893162393 828744239 124359862 968238511 22741902 832118637 302060404 711918176 908150368 253532718 738747719 897175439 344936276 785721421 812732695 212421142 139775309 381628634 746449278 303799552 668221164 694145107 720087205 262723607 456057923 805911895 738692489 382398364 598920577 316501128 850631911 303269315 79636622 698167483 543253608 514239663 251910951 341514467 965805782 248633992 633368571 367355888 795197820 750521389 862039286 68186016 858762668 951299109 252529926 739103242 481956378 786589763 357583261 242604782 267734638 974138677 376246966 818869596 660644503 376579292 514923713 226480156 228528324 214621447 952406297 514643855 877655274 553041882 867566433 792588907 174700818 745414734 681479369 930182555 525550835 742473105 381557547 19659886 580012002 501318905 514752017 938545201 784114488 236315676 140669838 52857309 433087569 170440402 634842476 923089965 446545394 709677774 433242412 923824633 225453689 644940811 304353881 169460627 651876296 75117083 237760342 28114353 144571845 432301957 917231672 912031463 954810484 842484914 108020521 582274279 864934430 403444820 800837257 812736353 120194482 148500646 115161719 31746646 500295870 208064419 42696279 908938220 47904352 640243198 795152696 503378359 162803718 937632331 334236921 588075958 564077448 998674246 564086637 196942810 552452475 751440860 630453595 51273547 539301274 943719070 560272479 68486661 917222688 996445998 364498791 741873124 796278410 632595662 235667213 899208128 416150870 594413117 396837139 902897124 34521575 286794971 687237831 301302974 966498240 505196566 216902029 203961815 402124009 682903194 2301347 811901186 287218921 420129128 324167116 839200066 612595200 409303077 205547949 788931980 197795900 304481345 68806560 616386171 997412634 985490455 254468345 628023980 835566144 967993413 421624721 883199291 363710012 438824584 417025219 470712264 74291814 874011609 558314804 438271507 368911257 910473929 860555145 217297656 787417980 824826613 363957977 740073718 458429316 284657095 186207236 157099765 446246857 670643663 680809069 353853458 588283319 513360491 54149840 498394474 742907275 186933820 418294504 276185470 82925975 737459990 894027465 406051811 668102458 799005280 907977709 767592745 831507849 606008310 362392232 640393871 847656950 214062184 493311000 875186156 207983605 786405918 736377776 532261111 469901596 277506874 957060321 343472786 960404197 552351504 564319465 192572780 710818610 175064936 698053554 232320358 646910302 92950146 32714946 502971170 593655309 730934601 931654467 457474806 509728339 820116113 804109304 751388779 715975817 586932986 919106604 871833722 629407326 354297862 946898410 76902868 633015338 80445778 285906615 322173733 342640532 213558865 551239743 419405183 238434843 988100830 743906538 612822953 387378102 522583106 179504824 304596189 77513459 858879243 462387287 804636039 661627989 278068126 507921775 320355339 997447498 818145415 483300375 944624908 792129364 194865958 504827858 456829095 821378571 323863762 893935795 541420217 986934087 623651767 961416371 47788190 244546140 818295685 2231955 844856305 668575225 839376932 148603743 111912656 159307590 919440040 870307793 1111734 362816381 496275651 607563320 664580704 465531009 502404491 193100730 579965458 368876888 470121482 234043654 916988195 843203634 466120302 329988694 449658543 243571952 206548293 137587522 289429280 11658621 608167180 456565177 3079142 764519262 919420173 720646690 687430673 659147578 30758798 810617543 144150670 278814784 877220690 634051482 285513230 875449795 778202796 858674530 548867038 436948328 425194275 984694695 430480084 545612651 516750363 464772096 916863168 336627667 819824897 275298105 981520171 14347425 132405606 701327753 731254508 409966702 869707362 135882202 965929110 148514423 963755644 947055855 104347218 83598887 783782955 992199463 479032588 195396988 625755983 205858869 910084665 513842673 270568233 542624211 527003760 204473592 228559680 463304287 156062856 656004950 327122457 835644685 11241454 101461489 351241979 761395771 72315849 98747837 258013051 948631464 600504788 377301593 679527078 388113969 180744293 982000972 551988624 9928680 253428302 941920853 779007097 24485351 755319861 393780709 99506225 649636563 429595614 395880011 154878048 527994047 714407525 661787315 730273692 306316277 704858935 75098111 742112148 512462354 14971247 748539170 98032296 890363410 671904623 901194610 770913119 867008141 837035301 860292667 917616123 104851202 959142571 624627615 460853898 242158560 455671592 877789871 323167789 949819751 602616332 197189718 686477363 744856180 265286990 187389487 502433915 701076103 78607196 702417940 69612623 679478576 274987300 927596646 933843617 441622561 380454288 759655675 838865505 875527862 176743114 701521914 228373755 493654323 619075032 866687797 341920115 720973759 217767091 649447415 788966094 610588106 721454363 532796249 22937967 316237118 752134466 808023479 951346 993793305 239465946 541230563 45290282 641476915 25166952 179736686 23730653 146888519 625406620 74060411 357558954 248075623 615397971 771738365 102417540 384360379 685038641 350138073 226457072 447211563 904488210 386276482 339761415 694758546 777162060 757636466 115871774 275490463 452481488 716563734 733378359 101325682 619314224 971943656 238084843 817495525 871530592 213424568 214428914 368030629 458357021 200764653 89038534 861133643 609377705 598964116 906670677 605934492 617550946 533705698 6949640 94633342 489105076 574659129 347050277 510759709 972045882 586640769 309970924 146653703 177715694 4517278 729772797 773956275 748859272 832683108 380145257 10356342 945874445 252238528 470777311 414664369 657821451 712748825 385583125 297820498 734624840 125580121 48549038 62666808 477405547 779138705 725734913 895000273 462215403 531908138 172846587 252775885 463100868 915564073 150448380 64253739 196454282 725761703 801878567 967961376 907423119 309577884 946427728 286604288 431721873 540033099 630236373 534736606 652478257 102350571 479502009 472661877 385371466 719704263 601146209 79024486 269999672 843684137 740873458 610734834 717230025 462874288 650159085 619473588 860913956 809933042 540573334 143810894 896895006 924339398 567488548 653490281 471852870 92428926 880960853 575778214 121196659 382490977 976105909 207213351 938243800 868173919 334555570 742104033 985518778 310593524 733200630 124070339 98791237 654614830 33888110 237345537 476743224 739531134 457817242 583967326 205920624 302105555 514761414 261407801 131923536 766447400 534452821 436662141 850094359 771931115 800051812 211988289 912874500 37882308 666410150 660936955 646412490 536505728 294380619 183723476 267090610 654729342 380187735 551176964 716858668 665377343 361047669 983415050 345579513 572013653 797772293 121116437 616177399 750504139 73625710 152643661 455029596 379804021 426518014 738095988 279182561 696183495 978601278 56677286 176247674 205806465 171995364 289614212 507040619 846756870 888988772 173570708 128404093 674128775 272487464 838032362 258829699 776278520 397600108 602580837 881256266 632116104 981537154 483285052 24778304 765120705 570556090 9745070 694200624 943990842 278573444 837646960 620955546 261751640 218286438 360028516 625033475 253560187 194288720 348045435 847046929 304234618 641713910 810006812 155447346 629731893 886510649 906786186 568950447 733719942 475635838 771053162 251697046 494175889 889468472 696864695 154439168 574479955 837430904 906585294 933711487 634725752 141711031 7559800 69735991 569842554 16706574 809743665 340743566 156741294 985429204 225248849 835918846 523380800 986529970 537530472 565004843 499467670 999082187 543054634 786156255 138071906 36443936 299479417 3425493 26164116 44685476 344389970 167709285 545815629 733584154 502582631 568498311 706775762 188437534 800701084 382188359 811649201 849441397 293891642 608050131 746062424 96122454 647714821 306167164 661806512 82107992 37941927 432409690 381964260 766010985 752124004 255245367 885805689 459712895 588944490 687203535 148014605 604608259 653191822 51894643 560336777 877949128 795196869 999967111 730514250 608332270 205879701 112123816 407305756 318304768 549242907 518543482 893035369 925531721 629037000 571797778 724902585 174481615 590032786 656756957 473677329 651965193 200196293 332577736 879336582 977765826 515311082 104612255 354461795 283028294 548482208 447251149 432713926 271343058 395943618 193904031 793282153 167789511 430276778 246395821 32693991 424472091 913422649 247202438 458587701 656789239 113343706 528904340 539091787 507020170 723839632 969065914 908209916 836461087 743979651 258743843 183733345 510841301 982195328 213945280 504738518 626054205 69259257 687485854 716940615 762387805 586969405 52399939 930304700 744334472 869485799 838215986 441737689 624685893 717811248 329332622 344023083 471485835 868653425 693488846 722843210 416899982 117622466 456594493 181069194 289336370 135433040 808275853 949006078 873522133 722119285 705970417 854440354 311399075 248481282 790321479 445877276 924817318 185793503 675466837 47398872 134287033 192710268 705259176 518472060 229902356 954694585 672106045 509018088 563544452 978891348 47622456 972464228 130072027 605142538 190162182 403451030 808657334 443472566 934659691 496381574 729958413 129879224 314542054 233580557 22488203 520054274 480528973 565704898 96888860 496612400 235087102 307568543 431813516 363924129 230935717 621436763 498861639 572459869 356013155 552215069 486696888 856724852 58068004 56641068 4186167 232261644 917448179 288963403 670725187 650835552 763340179 326779044 593371678 16477213 157031317 411911386 962187551 692579328 839828151 994335727 369260526 392581993 244631730 950883553 168751270 17999355 798519711 576151044 187095006 99791178 169119434 737755991 946381594 364926285 226565903 643790976 548177037 341376218 552155364 172658281 674094839 40774279 786596282 463590710 411985434 248106805 525053224 606057578 33152892 491835504 298760636 74503727 333026178 916816414 597846013 455452615 22893315 17923712 85463903 728548481 587914114 720336532 632048980 343061513 418390187 511380515 21134526 923100522 842766253 462101100 336435600 454895951 823993041 317502500 480274228 776272943 328950746 615668467 700794848 652876449 749081911 16314546 452269761 308037349 243627864 410599693 131547408 320106967 354247017 832705328 28575325 829044506 866602027 934119927 971133949 97722581 327528658 102279121 223323268 61690694 169942913 578030422 206991831 618044031 92701259 928167029 261145278 463481465 380398280 62985335 952669929 164750830 549079139 646160709 462186391 862671488 519303935 817723642 895364002 132742470 747756026 258746445 672485935 510484860 233506546 413204644 833498931 407803489 512209525 291456829 736765987 709535607 275654609 376010637 862466746 471330017 953855096 162116482 285490449 805167775 674481942 322510248 127343513 385481574 380772411 13902096 582422408 414735972 930901704 25120128 948930837 590655701 623401726 164734306 433632666 621226308 442224285 281028956 547398605 442833376 936510981 473432561 923080916 39355513 957541871 802560519 449101131 116440602 386712238 879938067 714626092 768933260 928679781 157111277 230936592 168805303 842799125 398048465 853148387 347988515 35567275 996119771 152568671 826701607 345202760 475633161 402802128 530751637 783102494 695325379 690669121 141737233 46612263 357058997 523786609 390736700 51891698 391153402 857412123 9208582 810085171 309365150 257995905 448712051 789786279 116252721 704470553 577128000 239739326 589749837 267459408 49345114 627439070 3404939 440661194 601840050 642657035 921285712 882430718 145683211 444338741 21918589 648831951 482576032 79034574 91938015 868230281 738753960 26326538 652245931 934621768 547606545 959052725 942480338 29765888 185047166 676444818 467248220 441628010 563409816 711515044 79323084 967886504 2434744 787257069 993167190 545640135 588517829 624112843 134763981 285299842 892200340 510096610 167954226 896582790 992021996 423303518 881980544 650426918 604305207 227772175 957485998 691065182 14257608 529289317 32761335 653970731 411456495 824045397 732357676 408366322 102189541 950214913 138790984 12098100 887494017 86805111 586681090 483485945 744723021 29058590 773535548 576696610 884322256 289895461 740405453 250371747 588606485 393532107 541024636 198489322 73157318 983976271 607828207 455404672 678828535 746748388 100242137 866316657 479147515 279469244 657435251 260955343 443964183 160877393 182384566 528741464 23780525 105948852 262047287 984599082 632528882 570814086 157878782 423745609 480566046 97617575 528373800 73556935 68774953 792294288 72111326 833272692 348951333 123359057 215132615 409378101 628014818 430456700 375766812 579734239 472744164 576078947 91792359 485127219 356269306 464015157 278219983 589947182 779027215 747910714 481605770 117450424 204503514 44221786 634753417 385420901 296382238 935907054 439348105 58649818 154114255 412154673 267850143 777928838 698157449 858018940 403290203 134165002 78936922 671673456 320839413 864767793 466390712 400212993 364952756 42016658 422899601 586837553 178886799 941981487 222974863 1946816 945258391 630314293 899516061 18222511 846387330 42011295 46989605 27857147 802513902 509364541 75509622 163412058 344560987 121038526 506076433 93029363 233111247 893639509 615108224 783619802 379915038 910165732 528184075 237953539 928790769 635381438 143221577 377226197 370745335 606139824 946508490 39181434 804951487 793089501 701901897 774073543 949462681 938634877 959504578 803008722 579440644 915258719 198065424 897469976 146134478 701942210 27584532 813959213 890840461 232548797 282559495 68829875 268081323 113654335 129031574 575702785 978969690 741054838 640157073 991281432 621129991 903119095 93240975 295442485 25163125 510704744 648894046 476349308 339100363 311148619 628136320 469046022 78278344 266063868 269608401 178979175 44132768 476369315 470793567 896620648 200075321 251228486 151924925 74889224 816740375 774643948 68963479 371474967 360123548 467607311 388235362 557008421 730476595 768229842 872217559 641823755 691852492 184074823 563015157 18151991 543078554 41858773 80359495 138915953 241950841 266952286 681476445 240131526 38711237 56243807 166576454 134765709 430630722 110966044 186265068 448808554 992182922 750568273 911072771 444654706 115790671 971667854 846917313 846404457 135546261 403257494 359815556 788546706 246277740 482670525 471757832 689395924 274459238 764108985 317776364 288319920 513177844 853896655 395732980 138445317 600014648 545840438 588607701 542741410 315789753 391281180 128140749 166067589 273978538 53132308 111479700 354631687 784610215 651323185 332836937 964534200 221064864 369632292 389487125 401498203 970396718 906126475 422698535 513000981 115854021 255290418 142077541 908928 341513936 595450755 236299043 76589087 536662777 666203992 718445745 937141113 944253750 674870162 300838316 493308088 998395414 793186486 344491461 941250984 66324917 764993923 188779540 582808252 975285822 969095508 813857165 309069501 545489213 575020355 209978408 608752610 812130618 748933656 434899734 313234233 209556549 444639009 823826365 306876782 856217918 388014724 287912330 417391303 587980738 373971881 657998885 261275745 50944205 284858521 614883249 686370085 143518693 456890828 194670971 308785571 286993782 649314644 322920704 456946382 286824937 272394865 997576781 975335454 168279021 85698080 934389204 166769882 299299698 830777266 994087829 875381311 939200713 183408502 156326943 447582993 532319255 254724644 162490420 746398858 169967552 858170596 497802378 142554403 873562772 620434508 796936718 325786539 185618179 491305063 479857565 68604471 446581878 848697121 181700295 518805250 855875267 242505260 13756468 229829008 628019294 342051511 550605768 152901565 755380735 203811434 132379083 472707408 762902559 886417872 845185438 640456168 729209195 389913153 368628580 640761465 306995777 207670694 937215202 153640638 902823937 359432070 503041935 566025486 830860125 377133713 274658537 324448157 926483782 631894350 623349369 10050300 89151927 871829143 778770144 775865634 135623098 272717843 215415867 610077243 882276362 482558711 802485854 614146873 344946013 786420340 373957441 251491525 72750506 317400959 873840198 683665345 144455040 609234452 501177798 960850871 497321660 152568618 577172721 835950217 949630482 745339507 492213015 132774239 314602928 941783952 167726372 476566814 479136532 807966957 536739073 249112424 987932529 87066828 420886987 58379912 706380470 606683931 695239368 604469918 739794272 877213986 838517867 475799127 690273882 71965597 341358473 936025125 1467528 374670364 542901639 429542469 675303845 930513870 41713178 806809788 907579872 595312288 68656427 286727505 195612517 967927617 424942024 210901839 805093993 110807466 641009418 192133342 892061255 677176407 496586302 304973668 573484139 450630407 260753135 393924760 902509390 151209277 66995889 882919045 670012577 567814455 731476712 862864081 943891857 120001395 561469522 651849177 603681221 341779730 147524971 244157160 413633001 306969519 812864957 977939662 353322740 210328247 925091306 323605699 20196385 228366696 982183461 490676340 117705691 105286726 366247828 293137686 187959373 842272276 537295167 297686857 16167722 488155364 897703126 716773154 596188257 415354511 15215626 725915830 158077921 828211158 804606709 875898995 185924978 657603401 384954683 60662996 454874051 430227500 966459902 271477308 130145650 748454945 168729456 95197091 396209094 124818035 960275443 965178261 708627300 696595301 868260864 547146866 182480945 737175158 491734354 337979004 64788144 967822393 514124920 462188845 163699025 139645624 230975622 39957531 969138037 561318591 943391592 977819790 40182165 97838918 472509334 41333801 894573610 699507279 305302792 4723548 903351062 313598533 33460403 371999188 343730061 215120211 212040273 692840174 834039209 359252358 483055629 8470121 474444660 799120967 793935968 573411915 872355509 944328824 278290216 194216446 442207752 689823744 951936064 314008248 407523358 712443345 490656251 253484715 208613698 344031652 77976430 402999439 554084261 709591789 61287739 200008447 120768907 683757645 717291334 239964199 577070693 620123460 576307532 524607239 876878544 912974413 804809681 478392691 886524979 526328684 542814598 526571436 874793243 319318105 167191626 806419839 747650947 979954236 628713535 222926695 807825405 355006391 43170535 673303879 876796890 804206586 532273673 908674445 758820187 872433125 688256453 676525396 941726053 189049848 894119425 106583779 840698064 791647348 354500659 90887664 27195894 867393425 716932254 466132208 593230604 115600199 84367724 260754350 486169143 906149900 138003766 485860953 849525585 108813833 913117937 20255808 32546777 233043665 835060573 778651306 566569983 439742057 648802667 477283009 656889722 686177065 408961919 754302599 867942428 796642125 851368716 492200358 880718884 500060141 810692625 216931290 136578351 740803537 245492907 999987998 898325467 866530982 540778414 470799142 665544987 900408686 588071965 548685020 214570271 493801984 916291205 535610957 784699721 591729238 552266691 960978773 108683941 697691993 191811242 924948913 907170936 493735119 901851175 998806308 700080312 485211231 490345111 978595988 8574474 520996191 919125006 642702594 982143624 166514112 198688924 698587942 783177420 662578392 55894824 60526797 104342857 673256598 953078250 773203530 129043075 881824080 53868446 771621670 523471196 943223807 905754388 223489781 85393313 876937369 864483365 10294943 472032842 591736034 501845101 780499674 786917560 948795133 61314386 728868498 510677676 538891906 474753317 794439490 593100684 114486336 482238691 476906138 488524047 966229420 162866144 741002443 715316305 564156284 278833118 966854981 795810724 968295075 68546201 994204180 822880885 271844715 208817030 879680081 489118549 176245001 929214811 207377253 714568670 831795413 230720738 493422354 324660844 786972178 780864928 164543114 922336999 94822097 884146025 633762996 14877601 299586568 382722217 890612534 993293127 510488203 604725142 971547153 66932615 422457551 592710690 658504962 939571967 129180322 796913731 887984978 70522944 757312664 12081098 393153980 283406792 710943910 632849321 789455891 998056969 225384550 701872388 285066333 486061657 901016246 292459715 525335857 161158030 835355560 383848363 563385022 395213432 979991268 127170884 133083428 162041231 31281983 758497100 31751804 994168754 716381504 28795066 225403698 511314959 576066063 52018936 215514734 427264964 749416167 214819579 125732945 574945408 111282822 686924730 866735141 439353375 575266127 892079648 971758037 118180277 116084929 95228416 987320462 456004011 43728254 649105125 103028988 926632588 254532662 37950987 887615143 900925469 966977728 207286175 983557577 145266224 70224321 138139599 543510764 420971713 791211971 646412512 777351120 150741694 215169590 452318508 103394685 392270931 773794583 665439311 117718161 326218566 736870941 707819473 517717806 659526468 765773038 684114154 455955013 776268219 705610367 451078255 519541470 83267048 218286854 71555309 855965373 820436963 388548173 953472100 921938472 663507439 692542881 101020481 287544784 691423751 962816243 509375168 425601672 3002321 939363256 120306879 178325055 469454543 752459066 230844443 341441211 756389363 315200784 309741823 107862314 119037360 332698699 774663605 25417891 731691426 951504118 796361183 667404522 127738402 869654770 634686433 482186737 193798081 935911041 411729050 166015256 157406993 884089213 333241091 788109588 839070560 940730984 902253358 344466916 465187906 368793089 258049686 273724324 188077665 221180246 66407176 126838118 50976881 420177820 68276601 597996057 114441187 659745284 492435281 938640574 819891303 970136706 791359591 686935374 280348571 892639729 471803359 340242679 102343264 83735890 606687873 33161620 907020285 278637985 295003472 864625369 222717902 608292147 260263251 508484808 639618560 670659079 431216565 801432864 743950936 122013551 414033861 668169290 477094423 161166354 325282633 650760916 684555143 191700842 502390454 874191172 279794135 511991658 124136566 224740165 286959842 309092812 566550997 578666713 852064420 947034436 714006487 587753209 544396640 385371087 148834829 799453867 20457304 703098087 538266913 813499548 44150847 80777206 525274307 296404312 45987976 839298651 117729796 875918887 911858256 442145009 89909025 367176561 388496889 825869497 187175758 352188322 13416581 777218591 345878392 991952417 439248387 456562306 392629984 92252503 925303067 564346500 966007611 419121551 475252641 62918868 663629696 28597870 32683516 20849917 67373665 92756762 616141033 890899719 822962919 73807402 634928604 728402414 340268598 743294250 721389459 498752362 182335421 159554151 593394937 764869133 918554624 502844847 152537835 180832619 244221268 652123234 469001362 467352489 698257473 951242760 929749874 905485174 374652298 113737795 46214356 511711903 75820547 135050078 369785091 918533995 506588658 102944476 52795529 684778494 443744586 93016593 179054549 271510242 557016705 241938870 518971126 137807762 970111036 939455274 493763183 800519056 428047277 329763523 328618560 478358215 855717401 181942103 180125992 338733832 494113831 669864974 316912526 101713120 890447922 953226333 793664668 680604973 661350527 210875350 230217469 500109551 406435384 436741671 798603528 641741128 447186494 597377230 307275897 377437321 159498844 526927865 19538293 12090741 204265710 264964800 62834852 169550691 144228172 198247942 966332261 247343002 338790796 241186566 29930960 354792115 562619187 64074335 723381513 554469193 805828070 601467764 291444988 921608202 764745365 892383172 943511279 460503400 891742755 660018674 505286037 583345768 780527160 911561902 102921970 818934255 920001883 580120464 302270909 674789470 257469206 884979100 767475977 423454880 331569046 288127725 964259244 808585926 900330058 900453462 567069207 944094137 178142782 941927851 479281669 620066572 357614303 794142015 844722521 965077196 312870893 452151597 74018558 964646801 905226053 144159618 786697003 412778434 494423836 53307886 929720930 782967783 408391979 576190985 389790537 706765179 820945824 38196330 412050034 48749042 587461241 966481144 497784584 842429627 427264939 745223006 166052038 898927199 909707559 50157345 815381357 777460823 715622596 290211704 360396591 883765222 513742475 987285248 921569681 691535494 10346791 339616132 825272876 144904080 215089266 488353489 946930996 711344632 8395133 576090445 87898761 710214656 117856576 600408228 833602171 278477732 232554506 909729650 585214539 461193219 917421522 523018172 461852744 900128135 834588355 909510077 861235568 702075702 270310082 858296586 194249328 206728850 279532610 674676004 360937816 954455565 758310006 137303522 617931829 140438527 631808126 871421396 204016879 345319034 586866790 550281774 843130355 919592698 385486577 347399819 69063449 258056846 779620592 229750309 51931399 71465292 129665401 389163922 163576250 902809800 857694618 186509599 290791450 602124066 171326792 460815927 846475501 991523411 788605879 955612712 240424761 971076472 539972249 812664133 35487944 31208030 328738654 152831065 872343887 47771023 242248382 848069075 711739640 504936501 100026829 380083706 149908337 145805735 421237738 129047997 287137122 792326879 400389841 5838560 812427545 815764362 713333927 528314366 534703493 915875795 176803314 365603274 778173072 857609065 80560165 310042789 513268908 317991116 578807949 606276395 621272632 450649918 453976521 784034963 436057130 755305695 496183775 706654568 378330079 416115039 845277993 410438782 230574025 519946070 57767931 934796962 363165583 863433944 90711102 4120798 767874199 990832304 117508985 8210598 698475485 387643107 761643127 695371376 220355419 126012792 102591217 268092015 442873836 927156212 672634810 147760528 789948785 141383947 548545749 770717996 746420202 347446799 126216660 649935511 926901089 622491351 563878286 680454737 592913606 157203041 744591052 431021693 726149420 360711371 713086323 989045360 173516495 712318563 792613230 212745973 364336298 786943798 247013306 101952633 885598497 382864739 929857553 40480027 917568150 912670011 663245165 396178439 794513396 474821631 393925492 878041676 383781662 121409878 239149015 947914777 961316171 178242619 698784134 670026475 318394025 715849550 277720986 226278380 722386868 20828910 3926115 309648317 140768628 581167396 324974003 807468621 505249631 978303156 601265451 642128700 201600789 873900421 280521037 94406913 522796614 779049261 702601408 772769256 423680973 92968803 51928132 788679536 670395751 207212686 506870909 427638064 151884222 898939900 227462860 271695346 965912006 374119743 707971146 244696537 807052423 208166707 201996939 187227930 312196394 612168679 16023117 996980095 78227850 284938254 504869128 986553481 689714011 286781674 270768133 920208217 110029514 570718943 374706614 712973272 909722077 599349791 980940004 634793682 771436769 137535873 834641565 152504127 882165229 727849279 391291343 514243143 741743249 718536162 948237661 357011065 489240138 367710897 986706535 534676702 507535791 835259285 338480261 909172710 457348325 749152964 53382279 903130519 191867719 317423410 623437670 65317201 658407049 331855475 922120384 207145211 338621650 878685796 16917320 563565643 880170148 467177787 238230150 368997493 616216057 975386589 478055621 631594307 430130032 311031137 827596469 639892269 374983564 849790110 958401396 176567441 999381670 948562562 302919483 199508390 436029029 632453419 592914816 10946301 295348528 366550462 121561044 622082931 551450653 563187253 918188248 266817687 689557228 134676284 339009441 214443554 893968464 658311085 648195262 658824234 635163557 144453639 576750681 96361747 878000128 687122387 309351495 657731672 684353183 46868206 745672753 635311654 75390569 148989834 685777668 862635352 822892631 317902981 191402472 412305528 977963630 216945356 51366054 766712537 911190911 664139407 972054322 722340306 760706017 499354174 248531487 810280746 294999649 909421349 949128469 82668576 105826854 508113799 592573444 618667921 706292171 526298972 730318914 761922236 801519167 22495224 263570269 168148684 544335836 150690193 136106298 29383618 375652998 865748906 723289036 787507421 223152247 40950743 363443938 783236191 17292049 90500222 637769452 843377070 507830779 634764661 960411228 130085667 963695968 199793026 240398607 397222875 794516149 617544502 152806551 820137289 411204497 470336675 395669510 11864736 832988750 224494989 192372991 194181484 782917503 211206246 382355150 160662296 54653241 157158976 306507240 520785134 903235984 893171903 274196558 587352107 242832296 371073702 407027646 835244592 701492991 648301113 488123330 212095360 865736191 593380368 176245009 731716181 170779176 988084584 829266055 768220328 169296254 633617421 914438070 607813412 57957268 24299609 626988234 695063894 164345969 754114535 295190864 959904780 297525964 645535858 992271071 427136427 226376921 656848343 353738592 697184245 688312033 610621838 781826672 591735253 948299896 346065549 810760227 288646266 647753668 312772279 585117633 743382485 181194175 867485551 51153640 770169737 798530702 130824615 797772205 188916329 870855775 430855109 845568703 610527038 146482957 8913591 520410609 233605932 844356525 352277925 881740008 311636716 447495208 630166868 269751644 232649153 35405264 463610682 241031481 603301831 64154774 504626156 221901923 944315846 133054353 846811658 242775126 783894749 592869148 583148563 167107007 890430642 287076058 890624187 586595976 242225169 617030954 206466221 927485733 81525809 153852720 762962288 465761099 474614272 291341762 875727729 198133801 387192405 653477123 758914465 375603719 765957308 911335973 334996213 990406321 41431285 304372094 134005104 647176003 247471728 341909069 77229140 233052394 759336773 46603006 823706913 664016896 627227336 581784540 726008964 214722545 159556335 913224897 755348704 341150656 252279310 959439782 138186199 612741669 102184076 829188238 823524888 497606376 254672833 540440167 616461706 332189035 813175534 245701865 24455913 442416036 799939969 795974501 555351872 828791612 934414542 983816453 112345388 362322554 574155517 256770617 494309410 957802189 636222606 937906156 245978724 392495771 836232144 622757156 331835996 712871279 305819488 348776560 783911815 290065222 828622981 262435420 793235915 314417210 26928373 514835784 271922624 166634698 937812407 81444418 456318709 645527685 52888161 530168121 964771841 454446888 568983086 261846415 453171890 927024634 99393680 383739682 725506505 512341452 984804682 405822610 465387103 472854069 259969282 191503034 275390858 141121272 849879709 928656476 162179319 863487256 906131713 748614305 195714409 446345157 741651039 411904040 879748292 636124295 39648960 722330641 558074087 918664490 885713306 394129487 312953100 946230160 488286343 839364809 349156184 300742526 449791951 284573626 447622328 179814622 429525154 400366784 457581666 835606523 90681065 486217093 602301651 323229362 738080682 274910752 192868584 944931075 175795512 515127663 815399890 50061607 132790958 400350291 141565648 438824136 413704818 862489502 852403450 598420928 120346031 583752530 689948798 382655166 435842420 300838085 442871320 754112772 624669551 480289135 539635761 677310599 933993910 494654085 106906114 743492253 952242059 390136273 548212509 909517067 268556664 579809915 918739634 312877244 792053534 488050236 661208851 471686901 313140658 780089664 450153958 816911246 485933495 200025331 451567184 460996460 161459075 694391885 991178798 357723050 506153015 120187042 273080919 796985519 849444126 864446059 190419272 608896740 979328859 223791744 803405298 124625078 642902219 28175541 159837620 450402901 917813116 42864078 255525308 380064841 437353423 16716590 35398095 180747244 52082247 239030216 717816043 79672089 873877308 596329260 280157426 207158518 209307591 783871001 803297900 946906203 843660998 570427690 657205834 969089027 728265633 907179999 150428954 628243367 155547167 273332503 430351256 217068841 25458500 483825658 53655478 744682391 820240450 243229069 587711507 864083432 471855777 351803285 542183216 140828915 39889771 953778343 540418121 160008703 620696258 607590598 681570923 727816214 342078361 677629618 972565838 700006427 803138222 342514699 964688304 210111095 79315289 239612991 498742822 782300502 743002227 264055133 140862535 945840263 391540212 95244583 407304186 592855501 805575888 713579877 566523048 662781167 315569313 559536705 340078107 398370278 870941455 805031430 719658595 411805029 998993612 7360780 527271281 797874243 572293275 341840970 769193634 182835897 10892714 985623435 160764369 138142875 718500732 314690077 21848480 528568524 288159748 38726269 303144175 363592907 286785148 119356588 780359655 634468985 221153319 301104652 725313623 411209198 217463940 103006403 386987439 368299154 324747159 10818495 161264604 739569545 335555598 297215766 838876332 397924551 315347458 848489458 469957101 861728372 624279739 110159577 564369203 757506288 175313088 283029500 969545874 538588418 34422036 449023121 287067879 453835304 304519844 810532485 224685017 294413081 482178831 106944235 646290042 677243051 479792893 876439089 773030754 284426592 313613616 558677968 6393735 297140504 54867548 515932365 415911378 707366102 191864985 578904018 277638563 399546234 236134408 772299448 518619729 44847966 766068228 995857672 843771193 557301199 739481156 956752955 670944191 505772415 681548053 975679671 439219535 745996663 74200231 987416596 547133242 701266470 943625704 853266346 830570085 147473806 944334775 953925774 150635011 991802010 832651827 117933865 94670929 766949421 338669032 525444446 224319140 475227592 404879956 747486112 364583888 717518938 79701877 305155338 905350960 800176415 903548054 28969554 664988683 835248372 674601895 796746398 673048758 471947438 77993342 798963467 248515629 754374406 412068427 233446180 171114688 651208254 343328051 901778665 976319675 669192326 623639621 981113465 199050213 981758085 107212913 366227184 655970717 211015 519538467 988313636 758521489 668792433 778414358 734683002 522761343 717394908 362265115 441170032 551283713 539192563 798168618 388191330 851677375 388197552 382397752 842708123 661915357 925070035 592580400 896828085 161604948 635029812 826224026 615577169 578029470 93011364 219024741 257058314 724436283 137197964 906862888 480116585 816638438 592543340 34252475 413809408 458187382 637203767 810351846 888290277 771746542 214473475 677499915 12294691 66860713 997996960 813378518 898882147 12396146 583844136 890007789 359264406 849708056 447034509 947089895 921831711 361593783 346593866 237490262 953117111 947487750 84698481 130100654 347259392 379650973 228870911 510301511 253505225 561211820 452094110 961787702 276196046 337895954 705283883 972590468 945953672 294219139 815215061 958574175 634346588 1895600 325610284 450980199 983330864 813311243 962299498 962813225 793793582 214679327 964329703 952679797 369378976 674189934 29605186 878673599 184027097 215731024 125242597 544522118 93822965 485018305 740684262 499829392 253634991 726347929 208777995 978091873 421403761 361818912 602289492 105229496 356933591 510919249 889803217 729955275 549588731 731870871 712594983 674881059 834284228 713556691 905745312 196199382 356160625 706348317 98409767 175735633 668280751 28251645 668695512 982026723 949942925 70677901 568014670 422701250 984357932 618681434 955731895 54950002 977771234 648848454 436323295 850635764 714219075 415577552 541092984 94293549 778229386 578201294 941382720 986923076 702410575 638866792 186095537 637738408 249283561 289335671 787047858 471172066 986024684 578301639 231512946 780055003 203624740 92024809 389646316 756592496 961767879 221268455 807465649 411784313 569368170 354776887 83303157 285801817 40248773 776290411 542792320 786163545 508539662 98196828 172216580 139714898 850246152 63250353 492888920 253898483 967208434 184815838 657358942 557511172 209558612 418287680 469989023 885459037 244778368 420029655 553968601 232788960 206769679 225502050 746726873 523490534 333153613 965378677 864840814 310459664 656006038 924914021 712754230 634987312 562964112 307772407 319934343 185643737 727572582 621093845 886876049 998633568 628375497 220233643 869246976 649358526 166652939 694367274 280012433 21944842 329142152 9694305 39601626 106322191 779613937 79205323 144363482 482699076 914665770 722813499 135657549 885361819 554434027 294134276 101605464 47445796 636004820 599694274 208519159 718578107 343249768 24782902 510577765 923281475 258310363 375153495 255914487 567975868 578981819 259583737 975212923 660194348 882624153 361792705 131580850 473161918 480410373 681916993 599418636 884215433 599471316 568307447 657591914 200034694 585553290 938386769 324155559 860311611 835613029 873520600 927658755 102412428 839808136 721106469 781010948 939066819 647853355 439653808 457829668 499792355 813776086 854771503 689358256 38669517 653110160 60249411 241569628 475636273 164730801 94709485 888538391 934082200 114449210 699015998 551259509 703713765 701969520 501729037 859682884 909758303 374897470 232193034 161349295 900270222 517411041 104871472 906002032 564615400 878942048 496155432 14105329 474073361 302226902 662475673 495310901 769634824 388120359 697616523 982148545 131017879 172506911 315767645 903451094 609005647 556627832 854241579 423309156 850384980 221520037 381689265 615423761 10546196 322201677 298362661 246469051 280140068 89508921 983625534 703795270 655646702 199606686 240814218 786241351 216997447 15973640 139841561 140250812 311580626 583354834 730514250 983797441 846696899 906196216 963421758 811738567 74071635 382693783 809436472 602692903 573061848 994239678 441648738 637970124 639731412 707045136 947724414 145335903 478019988 468047082 802839116 289608432 364196394 8690544 78196671 753046292 150426137 765402914 396976117 37115581 713060275 755642344 441924005 884142200 732562515 610865098 475744454 444782393 190824635 450865776 919607997 892071811 46517475 676265636 588263219 389778482 423384009 575377304 862640429 928569567 231896182 295075570 571987221 555829555 656096468 834525191 369453253 334201182 137390791 937980315 6576795 237964658 821897868 349228390 218136445 582509042 230885770 481318450 801329242 392808651 322686320 71870388 253678761 206911047 775285334 863938978 884428589 335945413 437050874 140444715 422985005 263139995 552342759 289939856 729362808 120414213 547402245 610057550 710276104 795892733 208100230 13616417 643350112 241796483 320791573 137631037 907785539 859735884 801670808 315859136 372245462 392493060 886730062 604546240 838256333 354531743 53623087 490433234 332766327 218891663 63285193 925122511 941627130 34936570 716469829 361625694 142553579 191786553 621589818 962814073 305301540 912725651 273341630 522571258 937392037 654888580 679935793 419883744 484070661 453231257 280299146 330059600 373077279 594488064 641999393 49857546 126288141 852147198 348932728 66210089 544278439 565876111 504771109 386089098 503125244 490825380 815202495 988663183 612751233 51186366 111897144 69168501 326310744 76322690 676120714 370364135 380577829 520575752 760867345 305085949 456511963 533718023 50489590 103904400 203566820 806348857 364391863 945906030 147039714 675969999 444193553 594219037 932853722 946265832 330931001 972428464 37909910 485524572 856370960 756525830 94255956 161651820 813925882 702212225 190298566 641115514 163739246 870150263 154713776 636791375 326967021 621810995 41775528 757176426 687167425 988113270 252842670 929178596 79561628 612838296 880214690 880439267 765908559 613852142 455877854 631505279 538889938 890141597 723515916 549084568 789682635 157934493 871610162 823030406 999959671 511365685 547157156 835427965 108350754 103887779 128645890 778555084 636280682 409938666 80821869 879304400 809400211 699123314 437746887 584552844 682644588 354399220 285904355 710495910 367878583 454408880 249431101 231414483 347432752 573811789 846022648 629914967 381482843 810867342 963433976 40319544 520892258 435698435 827476472 492522537 19313106 16031056 624622663 164767439 834136351 443676450 186729492 689421002 426496632 26404300 586342148 337002113 863041751 532147798 321842524 919415334 9521113 826802647 883294688 995126841 280676462 930622502 313154123 769484135 97570545 351690926 694320514 351911539 293412877 304313625 167765667 827501833 970447417 422090172 528797443 100042553 445426741 543715671 78281354 331645516 298785493 647149700 737401432 299930033 127123456 562081312 950257610 297384842 984280119 542891054 899649682 875947406 429597091 876271742 874343842 624191682 802274836 675085168 49191776 314447347 549143570 18394506 856879577 532640139 116987157 822639274 236084223 400849414 859920990 128140117 280182275 504394986 333417465 621813391 836249094 528464831 522213355 332684819 222360528 899805013 997769030 787847892 563797149 29060531 500570556 363310936 419367199 130478740 770128462 174494580 118798009 422768472 148286013 69818987 680347919 579785148 845486282 309329784 277189929 171798893 885953485 193337942 463211651 938048740 428150306 95219135 738985550 755067668 669017292 332010629 279203104 238214558 446826678 438953829 76396091 833936599 953455334 15224007 956543645 536959458 260377510 82245031 464656313 13076034 29269195 358871720 304401708 249345402 65929092 796995796 963544461 239741127 769676036 317188222 213085820 760265284 344215718 455820205 141180508 168239238 697591312 585588992 158266208 584347648 225201325 16358091 257947061 260690489 650476127 616631187 410049108 56495906 828977104 44252483 952809476 603898733 636238905 728823405 530255428 987706616 708002019 147094787 987992282 8002942 887752317 493627729 779026679 911122530 298235025 111168848 173024710 310854220 798355433 954668887 20155395 581422666 241300608 968023381 19663938 781593651 481922508 146128594 176321138 610761457 86171813 204284046 95703360 855408520 664693210 305729422 327278142 902475572 513673688 944184304 988264502 650075144 546403931 922667834 194062890 198788583 601041768 704494485 294539552 815325486 254003090 566741312 802981207 744680693 620537201 95088574 491363283 644520527 981352521 634472417 545300701 955865229 893997075 124370281 156741442 724280819 385136574 587657629 235295344 725473873 470197859 111064679 487217488 870763413 557475591 925475571 375683313 966556322 612687490 616308193 875024507 106733605 79608926 724600331 172045777 833386489 659773933 649307504 547190861 194217408 614292328 862339438 348165694 252193016 530992972 636166989 700357250 136511279 818708232 998760432 272961572 836782966 538342395 437367013 988001402 536986127 771656576 977454527 875592379 997796480 699391406 722736594 87000234 859915942 30578282 342786746 194639165 342453598 473621765 871248295 459732519 88401812 115200601 745544975 404260341 403655195 524359792 875254569 113498098 738536718 581625069 790767563 712982874 7591253 162758627 346329046 715261444 798198324 295949102 595422495 541985896 853389657 994453394 418676658 476397445 860221350 280361444 747693811 132160811 507335114 292838379 283015858 760904393 37888774 101729518 419824902 896827724 21640359 806644079 553187229 83170600 126580631 11414134 310894403 603622157 164832615 778068592 168379293 541840488 134956515 134851820 249048121 927303157 731171756 818029569 269213899 933348400 296157159 684894673 595315659 238995681 741312906 27216918 500555983 680423230 587619947 493085252 673106838 105133567 905716549 878948710 519478451 633237495 36289502 153707715 565048001 496386690 422826616 559620761 977337426 653705138 807551771 69053491 852291173 204914170 722175352 837152606 89793322 490289032 990261674 232132933 320877850 515885344 25988448 253972822 526192972 684672914 407394185 453980184 227857621 444328832 493651343 638314297 133144699 100485616 689937169 877886227 774114578 472799260 285254841 155346204 151659325 275246246 25054111 393490483 489690648 962370784 61756806 926703847 522612665 433392798 649472808 676560328 999567014 691450848 765168404 553477059 339794047 499356717 682372097 47371172 114787439 683504083 34312223 906272199 514949910 882375781 263011709 36271691 32568701 423481706 427301982 95905006 375556214 359580653 766161454 457128562 938987932 477866306 431900760 262630698 14107308 894397140 712775071 293233691 819461749 956042486 576604904 944554980 560725402 544015768 859110515 334545926 677256854 608896820 851022142 743580067 812698188 312747112 867618480 695493365 803864454 530406807 600263699 248483167 52966670 774892154 985485196 139355195 436697646 577607211 316048693 539913677 462457442 916957808 513159448 646085437 709622618 161333670 380846592 418408867 583245099 622234491 220461632 455375512 919020061 330876808 748411470 309993627 90264509 758237123 412245473 972916556 288029579 515146150 217049254 604185630 110392915 716921503 442704926 544581588 348100102 582659928 391523082 267031940 379951074 240583073 123938569 726989351 60630333 363222029 626819158 960040972 84979607 253834384 689398418 925718586 270297888 16198886 285552941 924187607 322096535 384520022 21270532 907586698 592524305 935895690 181000173 469250127 751986590 751793506 844430808 375419189 374006035 773118812 94773893 765957117 673750203 611974738 69954776 452467173 37615544 365763519 656265317 136415208 974936169 817911843 81148105 489855859 836681207 623990265 680569792 996857842 843056716 34502736 184974322 440116585 68659150 427155876 392058130 879452284 944970855 365544776 62196389 771184829 508136709 85335871 752258392 240939642 775618876 984354462 783371111 75989888 834512912 933961115 638477224 457261002 551822124 375164056 507160975 825605486 293571746 497274891 544520320 440080976 319212680 90268235 21934553 359138003 190083817 556732545 777299690 601859366 401779162 388386064 796588093 868519402 298475968 490503082 115231155 143608608 530663593 666712647 710284005 870116292 545520954 542122176 198905559 883733155 602248859 977648653 730744752 626340284 296007015 892344355 309203900 514141768 732243715 571771542 970357409 952343190 171421726 956894972 134960513 970418356 80580515 284798437 756443232 250095936 572848293 934947589 809869651 978862616 538775669 376556962 314133174 949030535 585096801 156974046 321282345 32067120 375370065 682279121 431173441 751915447 101362392 918543934 786463815 194653305 254366721 266259509 87011563 794413194 928164437 924093530 181773671 967269832 229596680 536633374 487152734 169749450 87856302 960987337 794748330 8524424 599585941 276228825 115389683 670777372 619790652 692211106 129292160 14250034 366527992 753508236 175203362 160212640 50286214 745868788 92517564 582338930 448598125 616239798 922812845 268029665 545170519 200860328 403149947 162761131 130130125 223799432 93422471 228083688 122282980 234297187 427555799 669257764 505462158 694272543 866334402 499937419 96942119 310879306 651444380 503521192 484215318 718899404 505562497 285223869 675055066 191643718 840385806 842936475 814262649 332720693 46796812 870912668 99556234 831866667 372136938 261651736 731351065 269923589 980998251 724438318 15377600 23258351 283522584 541533038 255841362 791666436 870783517 752172612 222722079 333323389 601419665 694530592 812777307 389330698 218951813 846854038 445096771 911199093 152283327 543276702 438459309 339793182 987569876 981216469 603203593 261447080 433567072 35437493 2775774 179111150 903645117 440249798 165368285 349559353 125366783 163476623 26841469 889392241 318006932 512410056 49227460 674223623 301471842 460559984 738341041 313271704 344476115 748467206 192774630 726276569 273496596 754204676 56853786 660035758 576267658 778946828 387816298 475953812 124027866 922153850 719269227 274193119 486993236 607635975 579220813 665086084 687052304 89868056 189852298 254413515 80719736 758030313 122346867 220520640 553243427 709510064 908634804 798133689 501874751 341122535 565986172 707083545 851085081 690866456 680702088 411136241 120674178 902813995 200078405 521953177 342395202 648386183 330776458 655165409 972699432 95578831 21930314 453464286 824214993 560900193 795744391 551997955 691749786 231004924 951648633 448754346 733446295 305323152 545136548 986052880 536484987 74965192 218257665 411626504 605033687 504201950 653987216 360352428 333817648 13791908 744211911 124873534 233805666 55783850 666322794 348434511 429394037 978460781 14087889 726634529 312580336 152369520 62789511 129162642 628644271 984363137 332509892 520124473 124715716 887037686 727256857 524755562 710901174 969489885 214910945 494630616 13773136 27081301 688556563 40433273 625592389 98354111 650282622 265652458 607246040 697207143 631762485 628329528 241192758 117718068 410871994 248537042 497406536 224331930 461412274 906232671 101257546 560619361 649302784 724872255 234593844 196632761 891953739 95982784 39696960 677738610 854970011 430191082 373166606 510582176 436089353 218972371 661859071 202741589 897483492 244874719 214372572 29558599 862305289 425334545 376515286 199310957 252518054 135037046 577686741 204234303 343516359 884086942 931335251 127198286 899320545 974824073 706657793 657320426 549823827 9344767 762416560 407454951 421175974 737140703 747045716 700418069 503113578 405884903 646649431 328633794 997199066 718023115 784305732 864892806 893661422 667267681 245804768 828150908 632480837 224961249 832578738 121860028 347642785 643111147 110220506 618375075 411859319 190632141 950119378 825858873 664478494 796140667 23741630 848165949 522155223 223221469 598945975 829961311 873346206 733270613 830711446 546430782 198267005 739893443 315789673 938946045 576861005 751177558 928405951 970778356 291669470 694499289 116215893 413320696 256428445 712344098 519254970 582739694 721584828 987960079 281073635 848131259 884870595 707489142 516459464 733540809 245511000 740172478 188049544 830445022 711323344 50696280 882842841 180220225 774556619 936584865 121334311 21779682 413810416 633853881 980189884 580940906 343394718 404338129 341192703 419165641 87804505 319987820 272198056 169507029 715790899 135576717 951513542 966115677 693032812 305100041 164732054 24771995 667466889 920495747 711446544 447378495 617305607 483012384 123724406 995323015 839776892 38298396 696213143 458028297 49020276 380839954 446448884 149647254 434843532 166535051 692160314 312962337 408032352 763998158 426038474 725802691 877755753 748971003 865111157 686087636 68034862 731655303 682726098 752282022 393350333 999956734 12959137 483527522 416344741 120961054 689909352 300300997 167200854 956089113 601671068 114298473 621381630 711017459 695170614 68024911 209001376 611259531 35660118 883553159 609115789 871353910 226033530 46189188 762959846 2545000 861398725 363340890 750527539 791859737 769797265 839090746 925517322 417748158 729028756 898085511 16547208 252801609 933981117 368548062 694550269 949770662 603585667 26366268 803253180 413568325 97193526 39100312 696210952 338368448 113407499 223299861 826637036 548369720 345336539 252046288 395594793 265365011 902236235 163177192 483806399 113172730 102014154 681570418 424030121 855684344 614712267 699035071 202405774 789739758 46491985 698265551 342714847 360578872 574095689 764343787 325602967 663501166 258706890 362400589 964855738 241405901 45437949 907332054 359306681 272082842 887046939 840618715 454109385 20998981 87925002 87681039 272764537 68586284 650153422 546209196 776675320 899426013 442341499 452940812 48661367 863812347 424248483 520685596 145150568 131795421 915695807 189331608 690052867 154840252 97654232 831199876 565765978 703939286 704827873 721655018 626343769 215387115 376726644 737651292 121192923 476893764 623166431 23184004 175682499 335501619 398587879 163702824 712202236 869026777 565320623 658043781 597104978 262020149 284657556 697918727 583139961 731990833 61662667 431947718 910173235 458716979 457458476 232709680 503172144 758187917 13333620 43349992 360314211 600785434 415988632 655069805 38930125 184981410 212709303 464694999 282401893 985700786 475200086 160817076 385614865 868581233 809416556 673050125 731952582 827633546 8598864 569763458 649076148 93629280 567868276 830438931 499945865 251418635 419927527 463068949 635432763 432069003 855764478 524562129 538279243 95070888 428684872 558177969 854263131 655456231 583150543 662703597 284399475 931886639 305615273 876664409 888845403 172995088 367132835 460361167 361453222 204422672 479208311 569579794 357398647 56180837 858960313 643028623 943564408 504160803 457686533 930573970 205368462 618577159 151017432 853687870 261104775 736685640 528662764 904237490 347649755 971955506 791015469 51263920 220502083 168021131 371388010 661515847 429308140 35666412 889923209 13221725 132873691 117910922 99695767 672773349 410297720 815181441 306728520 221879515 112419320 367348283 949028827 498876750 326726593 812819576 718662911 835726895 500822293 1844207 836842158 573771958 316120747 871767708 457314021 364223689 286639340 642863839 110344080 720482181 819156626 110422936 885914257 404646729 78408875 298227794 585962465 282864356 863182871 199263521 71010921 622145384 903287500 64930744 989072571 837535331 9346820 252750389 612959847 696121032 749762446 705976044 281372646 794190643 805284042 790359988 324609453 381644053 782444207 194823447 438760883 692273578 9770692 813807834 442406421 726532810 39881937 194063740 709521984 476833924 992409836 913099881 563243201 291701030 606431653 259214455 713135338 809107850 394454317 227447456 325599281 696415720 550060221 190772450 569401787 991753842 906816903 328417061 809415196 575458022 334269137 503021812 889921885 237219749 291891943 527713313 687047736 221822074 6957472 473753759 442434670 589081057 812777617 787576943 628490254 644902068 425968702 476899554 633086911 793272973 96265083 716677590 582345508 444743585 292461375 403100588 405992952 29561221 167892251 858008213 730743201 316633317 439689935 833212296 634102886 896817341 663240856 28395140 380031081 469123767 563808922 34019012 537287499 519299759 758756551 715846419 139968580 453486942 427050827 383884072 293479493 664737674 219525278 962162385 511380564 871702598 168017437 792483154 61818466 630574461 834922400 272630562 918623745 89201983 114096982 820609877 334249147 358213011 389122296 670894388 108934478 268003960 764589702 895031274 817504641 197776365 991410247 952434748 974018710 991889833 957877340 666237215 485481566 23992775 904446898 685224286 792395649 220563891 142857137 572701761 458557767 648986993 974367008 448669866 701963339 544119688 401841410 126704267 11724440 701639473 174186336 209073617 562419295 416680979 168314040 421263568 859217819 757046751 385159722 343942451 61102055 38028098 935196831 866402045 425061707 145161360 904465144 763770637 519382328 513404736 295353743 232197267 933125803 394161967 250414125 182605567 891878611 781457043 777281193 463231943 703445886 610620446 483801111 179256799 89258085 693473445 370572192 16911173 603309679 636952023 227174731 229055218 16972627 789112701 711286101 326615503 760892685 235856161 205131950 685960064 288725600 793873494 929923322 595128858 250105564 64697483 422081182 300131021 991407179 218886594 647465334 700696191 980286711 582517359 514268263 107921061 281205523 344989431 341890365 807025168 179724199 827418199 311698080 512204629 173373417 685058373 940556691 761433657 907214894 853314388 659907150 136885279 677223805 231656127 300955334 366235219 331680239 756423839 28788129 556821212 479673833 37310360 675901098 118135952 758624779 407303472 692732048 444240146 298271618 228467355 638985315 917376315 215183914 18930650 275213994 366297566 607411156 747614749 844156626 967623219 70801830 731426111 692133590 591805560 551008117 976605814 617909138 11372728 987238381 173608820 917297837 394305281 359722172 550503541 896416499 979460721 238807027 767220330 176506211 108203875 859130090 860847911 854090672 322524897 274286662 429762061 592372272 518819070 599697649 969021793 214034386 3633182 250490531 899912023 498015174 770455418 19210855 15021828 593128246 982465105 280108880 882737111 606904328 733718775 206536716 37787744 95517853 84908799 82726141 912676726 929103606 457982136 430345829 446429425 645364100 443545433 695132559 831409685 512546822 225213621 405234527 327013794 535126176 917186361 91244666 697276786 275258186 42029470 428418349 809767370 980780512 290096797 550392535 352330544 734301796 483186315 478396240 549716742 359611710 356101508 492465652 121787260 497156822 538504486 712324303 33733927 499080905 879675764 315734713 469451028 478075030 790578228 743551682 69263154 594337441 935925245 72236566 565172372 268672571 888948401 358872662 532205543 892752417 724553694 223141405 872122378 707148216 941867820 94271109 669423104 801579000 247087187 55823845 310874362 702811146 745859332 349651968 243582641 60804333 57762522 144771288 626311846 526007645 101007301 561558287 364280983 445397346 559608520 913647726 317380799 304260379 525236149 574516383 129131269 16172904 508636321 710666727 479602221 663608175 137352395 106512517 265860013 639246471 92333365 800515433 842942356 176767528 280461209 527429122 887522253 832974426 770280167 212252968 199601846 453645469 622385472 581203499 547306224 790922085 342317507 936548729 561460784 747810528 394856099 511859073 404791505 126280506 626410443 97641841 156808258 436419801 198902487 260251223 70287294 561399053 353717791 658457379 127319286 394946533 507737799 395416883 637272403 462138913 600330337 661656870 762858757 957905631 857713754 103036217 278019325 544366471 501669641 958701485 748010454 903910654 822640478 944910135 172096524 562426481 445162002 171853733 984030145 380886818 895209943 105503702 521929803 83381751 295012880 394299675 262406327 428686422 296691554 385193033 330554715 338502978 908050716 789968141 58934018 234094682 615820003 997648507 763344490 952670054 337154557 376787811 674995962 808112033 494470861 96048319 430524197 580071805 227170855 311566251 811157723 529335284 73591413 125989907 992178449 273165395 366285107 457511103 370365064 696906973 238710402 489762368 202293903 362521999 500680548 971679718 714285449 680303269 524683145 423959337 798619532 517742935 67114716 593727502 119699825 960145592 239231654 612469487 27751912 895086906 943017485 808828485 258563331 190985587 849911916 729785459 920870968 296472744 817421072 957039518 692593120 462915442 971599494 953544328 937002137 698304780 196308986 987150945 407725237 988317667 40633694 36751627 747374608 612346166 803284393 741448165 675903594 586273028 720053358 686979290 404615747 700044160 55114727 181036738 786504124 510294294 380828795 902385813 133987290 346368761 463463365 667504317 518983376 74637066 864165377 769081244 163669083 865286027 112582759 585116609 369241156 178956675 805456279 153858068 19166062 271465329 641901455 605509102 550111270 150402984 131221295 290077654 843256969 600225663 477274572 621031779 125024726 217236560 843317785 513074419 317802668 218804057 612041155 823453970 12261949 692735558 26196974 307006923 641222876 317688873 593194713 217303033 140403178 993843856 949823205 526764610 303879070 487078498 581896114 510023078 139372732 840009369 642891891 45156189 550672561 611266810 700059819 448298301 982240417 764315646 711960814 772897658 781337763 366903110 90527335 92421197 592555029 969810531 360561892 661843027 145309979 45953712 171693992 277375063 772829693 842749624 380466191 274241010 296915528 608641959 48908962 671483186 668970402 573511062 213357204 770499601 868211461 312654332 763499564 877349013 385982760 901313254 799475132 649363386 341788572 174384200 80503099 838505115 503818798 824391672 725812132 9705211 300087107 744717923 52550505 96634097 853524034 126031367 653477226 537012830 790682079 542444058 271989580 761779274 115765994 483873717 155256421 279859721 495832703 554168899 303011402 453538109 832434787 808355235 44419344 784952969 957985510 422708373 700178014 824373336 39900028 156747268 720919107 531894222 208837571 288281915 112434575 632465584 282050424 331184640 533366363 777470909 858868202 959508586 499193915 485501336 129069343 54344858 706414939 327050651 188328928 75314190 887248473 8542371 422095846 544490951 566132365 321451432 270749824 839081901 854834559 949826573 587917926 361750369 576727270 720647487 580951371 469822480 219810879 901531062 366596841 866790107 392656130 625474102 404537958 288015177 731605258 202804860 811352316 886649240 52698819 451306100 348986125 99808657 510671878 439894946 918886972 446693882 721418414 421619409 408006384 100221666 565879809 278301310 979506033 956316279 358103869 348868631 965097944 553554226 900635569 884227801 374261953 903460159 531721129 499461004 63681552 103915325 579118512 102781596 806396721 460391040 826898600 165924578 200285914 119570301 570666478 132642272 510184766 722879771 482391130 236849744 554335635 447873047 53787700 233036661 517074571 771997806 684518066 101029176 966078862 812820181 675356604 312305473 194952768 183263022 682565707 509967157 962611630 649536031 637186995 819945660 83200897 896895982 446900774 940062170 292207183 557295528 819576677 546977674 617979047 222274959 322613873 561144139 66938791 510372333 879000121 527544631 603374193 20988894 455574820 754293442 174787645 334111702 87708415 848731244 854236481 488748344 891144475 435432824 456690935 918019329 462547402 521667254 612043083 432826207 35120402 830189565 405384073 481855377 750006890 936363804 37034237 777429902 943184239 367671829 321148598 409169644 521574574 503097204 486333822 497466006 199199814 691035389 219397882 868636698 952668210 398631738 998102870 253024057 576424204 10484616 154814289 144602782 944252290 637468657 325455487 419319557 936420534 399932362 25329258 431347998 324407611 568228788 385385005 960821222 983770281 330603942 709333356 948780789 560194585 591853889 82783949 878667823 117408791 620421355 185486611 472571097 586688706 218323077 261876177 95233575 679412153 824765521 994288873 848062298 240852151 961753639 586239774 121765913 75017516 147990339 467690420 499480336 797170616 236449342 963611408 156682698 217267094 308836997 439651309 188566603 822387456 656395802 97716333 564121070 58792517 823744375 471873587 333052886 528721375 42319390 889992808 682130333 657921153 525220444 934174158 251918883 841415835 45511212 991642509 129346214 935578779 443952282 904808442 724287993 949354794 41959661 40130568 21424792 205419091 207634632 975780278 908199703 951943695 620240007 487762930 707813153 630209051 552687753 767689122 693169404 688256170 789921078 909048056 477321664 544024406 826934524 469833530 457166747 43221847 335687076 30323837 285065421 536072093 303726695 393766906 923610521 997364788 928306209 842229123 797053162 516671248 997369253 858091945 917381110 573072613 225595055 480666256 862200873 596354854 135345530 211029052 22293611 906706756 437038492 460251019 563425083 4441060 112641829 218022523 346793170 413652970 120904124 661200369 701929307 219860045 750414142 715260746 737594679 753220075 478722701 263704801 927027315 738287901 748736544 18660088 252050589 396209760 269896477 327320246 964838621 807341199 708953155 561794403 759340186 19411899 242533357 568640220 502993814 894854468 708414268 887461662 37894475 667188690 509172054 888819669 944440421 815257573 82901647 979505518 574554951 509826818 362856688 583903105 249503915 252577539 507008321 672396280 874337979 635017125 376134176 867175292 562838736 130422715 862301478 709444666 942505552 656968592 755130984 493880129 101435032 118076478 721837271 759773941 423809392 941396079 618579081 90299238 966768997 672199652 832610631 196144670 245564606 477425783 450100892 15478244 430813970 240993987 792423786 481675769 463862209 35430216 302605206 974784032 341467786 43370606 877421279 719951 982524318 37134543 80594961 277843584 827371236 76787768 714922539 517553333 318873554 556701753 426468703 439299504 303044450 567993254 828848997 451269323 633011545 310888352 457941107 418253684 721871868 281066725 82480371 833922879 469236676 924406502 15739340 606014775 767415239 562461106 437211065 576421200 85531880 458648916 555063336 740077736 655748936 365372273 409049077 564274627 392531038 198453624 582642130 717428899 199378678 676819620 585131756 209656179 81826967 589547081 284132661 108772861 857972535 253475161 295374454 964633200 578263132 449414461 521308463 726435404 80108148 410956101 67162055 423455630 654385242 345981536 357791626 953112213 495181665 360379388 678649360 357550318 581516783 942248775 987881811 452722256 487280000 120937688 169328205 61585759 70316867 90372083 728180060 644618353 849174337 584182864 536104700 739498052 290869928 848451460 121931452 891388199 975480864 979495725 174693959 219910850 271247757 931528262 71337754 315654435 649545979 164523952 673700865 386587816 890584882 545077904 274098486 10261941 980351775 210651805 44326335 212052447 164380738 264895214 914791720 851163152 985604140 391208665 490045552 801234037 46057283 439900442 668795708 290204978 973889158 62352331 545739406 768901817 318713098 185918811 5963815 125322087 481618069 300174769 513714058 78069393 521148114 719532651 720155761 176562218 510574763 860798571 811336267 111091907 672108498 815547411 773788677 549567316 295129779 126687384 242510101 138900174 369257629 650112344 114442451 876704241 598007343 657028754 94690877 454978372 879830081 931706079 472418081 65350279 223555442 699136626 146998104 667087095 656964541 330162854 890125293 808860615 496039294 342115680 531028723 81747512 625700080 132921954 311666176 348592521 700813444 592959111 631834450 399750592 709657072 61574109 933120161 518909887 703674327 489283363 486152962 160394527 677741187 276130306 587627984 1788239 118189917 139188570 46261552 612038151 851511718 681237212 563866692 869216217 466904621 920116609 719881940 661681361 68395487 731355720 630502494 659440356 560011819 140290818 105235925 770025453 717174440 783277721 565988552 943837506 434156454 911612086 189077648 448649072 943275186 116738761 170664763 166166414 649381517 924088897 154106575 192641216 35180500 283305684 365029092 391299513 371027550 371792405 656524366 606237759 290776345 285740242 169611598 57905299 628385951 119377143 514302572 571824905 142288008 412600906 697317626 332090068 718592675 108687945 786871141 372262649 62476439 56269617 972876804 542382736 270400930 183180839 978211358 64615230 390732359 343811538 811282247 638785012 714071888 322176442 52851338 920533170 308151547 918935124 260147440 785295670 426826615 428385616 327791507 236673689 671490168 768113094 159678571 199847075 90315007 699320474 218328524 756268724 135143876 370043959 627272819 129027576 991282103 160951885 458478928 612167262 593244791 777230771 528015088 728002974 790219926 129036672 128991937 551574524 221096161 367254679 51148370 291468595 771877662 224101722 471474566 43655063 320984259 971155284 691046274 278911415 880414514 736145166 158323070 92350533 218926446 215559739 271201867 170148873 764761088 554048281 184490009 493783208 167199522 952447748 746202863 432362057 999231426 100766144 977536915 266458114 622753006 97857585 740542540 154722987 171280756 130962829 185992731 842622345 83196289 62252640 637836383 468231579 327793882 746568950 538475104 782308840 250464274 526112402 599264678 511431050 591357064 535946674 683843452 564201117 413718159 982347844 10965870 631728213 251010755 492299853 767609375 318227827 567510179 279630071 351339631 656270791 596029141 454265620 478153201 90038438 806601346 242069855 535102828 124240095 929842618 25062009 430472036 995375384 69468926 885975300 15892934 93741741 53520401 598642589 417544791 925019703 137992355 823976399 80981898 701894229 63139086 333617381 508450438 171553441 372193188 656623858 770239464 531347058 172179078 290129982 809008930 726964753 233450707 490581975 400784913 658823772 406628350 834564435 442167165 137268392 264946767 143763638 623206519 131479020 238547019 519532231 954806667 990616824 665764533 320840510 161671640 895067083 980551040 800451932 764349739 324107887 793466115 371473496 861761476 965608258 784051061 870724194 984559370 168696855 900477927 330861048 699726804 596488348 408104946 438800132 434598574 296144405 231433614 152019196 73356770 154904309 808675591 562231431 172202159 861447231 241563439 757226049 165542760 783143669 73342811 963247457 145999532 412068918 26798680 741956632 595633132 889551436 592529640 956745454 761934667 963615359 804746643 552300043 395074358 10771919 747524823 271172469 232171691 610171426 111517630 472220212 883743445 718858263 163831251 592762754 29971330 586345737 633855249 47034220 378891968 337277745 322236477 348867179 973030301 889244961 209961361 717998165 533220112 359728959 511981308 527506042 532444583 954651733 493818310 334176868 206727545 613735268 89715532 480688843 870611851 712251776 310557446 987442881 42040312 12255259 764226998 824023698 974491736 482502384 972561739 916727824 79465758 584033914 468003052 105610697 716331501 963610035 616164776 446785057 579898426 221230815 16354555 472614378 965559898 843828681 266521078 492139348 769721162 359562559 72276744 74901817 276604031 578181866 240734868 484830599 174308467 276236686 860795447 789586096 294415824 864580056 183678820 909434054 524126462 201379760 280814727 942466092 594787054 394934975 92054365 465120209 918210715 711834553 830624880 729910629 956533000 515515586 516851658 81038443 705328159 454697643 63481209 611981597 896884323 392525809 446731975 777884933 566186423 297148691 493081043 386184796 28626280 1125178 294944082 165538766 140653757 990813610 434946407 167934927 887593693 957771750 376591508 673838122 890153282 873108841 988595855 212495397 626745826 470596495 591398990 461337326 954769449 659926198 208488196 170077158 847472528 35521304 17094419 351809725 931232669 797677328 527876446 614286004 425503070 249740086 6598571 416392754 731681370 375917095 108476066 661396238 108599657 399849886 144542805 127331892 97893480 698300655 297062250 387256578 910034486 953643327 750179940 155785561 599189860 861615450 917365100 577910681 938206692 806429806 197694462 707875780 556358202 556668820 180261851 990236255 582593994 5844683 715116213 775939131 413618247 528764337 743940223 971674084 794690987 203176276 453007170 358949124 311415805 758104732 817024434 634413337 367482526 830772923 986470969 207651239 682344931 387543582 427371706 519440656 209847830 226768361 999267009 807526799 42311783 834671537 569747521 505172965 690705406 513182102 82630798 342118889 821816150 749187830 955399611 113466066 379062880 554487392 967402876 551049256 442195210 425330298 316871874 418668429 924702500 865899401 378427139 734092225 130080224 560486282 513554238 231685061 152179488 372049694 546964503 341605109 708238857 576838083 813011708 597469858 782191856 607487775 170790381 110076254 272897633 236598102 367584331 415113803 887018613 327476033 86370403 155839132 277434672 390233785 770643494 688166371 354506863 221291134 407606241 220867421 275749735 176903523 3029900 211783449 564380937 404978133 96870080 80692539 880097259 238232629 438727454 11118576 138556203 695766243 817691846 811943744 969150593 386142770 10997972 750664213 239979218 406696795 336561577 179763697 564483263 452749760 338411671 648575787 55403693 877860374 177015957 154034213 862640569 276528513 941996668 880609004 518306039 428192047 461677962 845884244 936057414 551424352 534697148 268104564 415920725 583176058 520748090 792402428 702237890 906482334 647621657 934640819 679356817 599003938 927704526 815050948 230644798 102875984 365136738 11023848 662688736 404683323 1993629 123105467 630285006 451368747 285245013 493955994 101492536 740081504 896648293 859117748 93385445 229604234 19261915 970765233 123284690 744438576 849883230 62898755 14254739 970781477 801205996 740637315 172571610 304121561 619871730 94649066 639596400 272375078 855021478 505172967 541744326 783275779 688199714 606991482 692979113 107996437 900666692 107242519 88858830 122820873 963092158 706488952 934464819 342044513 910591025 425683153 494897156 833572699 651809811 56156845 844878847 274618640 691863096 12879514 623127599 894951563 303144633 930421660 995984357 637253250 898630727 552618653 505001887 115259104 604285531 246101813 108999110 409121003 532111715 11230400 404642033 824765104 168293261 434792180 247874708 17320465 462800240 384837217 38906688 770866901 644131819 26633477 48592153 672054043 495559207 137980036 391889463 859566669 370799000 641429978 800465778 489797011 154803786 831950695 729569683 377550784 16432998 670645556 800266263 853752998 66638073 17879163 244725173 458594065 929874229 233219613 210168963 756851284 645660387 28247522 925652185 151794122 150780466 769226427 273527355 465719749 273426333 343950395 479794644 122310059 599415752 928857099 21327557 555126408 965673239 926448359 388986138 623937202 285037982 390300616 299761570 424278642 136734686 553745599 906976336 44290943 640492944 402863238 924832178 915016295 10477163 870597312 402118007 395015561 608924058 230216701 778243399 435277458 437814810 959544220 261808679 292693816 888672264 325035834 533464116 671757480 864789292 58518715 966732897 500979872 244066342 931948319 394483890 88809089 818624391 199032721 747713821 579511724 493565123 106047443 803180284 544280139 912604155 3493820 723010018 342483914 529730772 628080724 581512726 469700574 982520335 299984515 303556295 382194356 22921605 632351817 444661572 341605822 365163912 293898658 775392136 277302436 573977243 112055042 768185674 381342164 852523693 377971608 439386715 106296605 417847372 958789190 976096439 312749039 452563718 181658860 348629175 487922579 488704741 627737991 125737497 558333002 888408305 373779235 646508005 101982797 130858826 667324037 940447140 165221596 9680602 140989085 741000313 906347252 860514599 579133070 354013308 415615064 784934079 688974176 78078749 528946819 823400328 225760189 159085564 264901462 810694599 524038082 730823708 683595179 260947749 66584204 495299448 204255874 638307380 653441146 155007038 270331274 852421837 975937834 676023101 819655966 209819088 885475139 909766379 911271099 913841222 925896905 636677440 331687665 496741923 711761473 511980843 885248124 51431766 19181250 856633593 610350971 132025323 603167692 873035843 780227957 897046153 413872398 451184823 847225705 7418180 72957286 509471809 966946752 888733311 115030140 973044753 574121700 182213748 534606982 974786085 28112822 884834363 480462027 690683617 921338302 216923426 297598397 26490073 615211440 934307830 127435004 419923044 317424293 393200198 705343658 732568435 984047434 939870634 175691835 994517447 894639793 491313128 786061205 977366475 651745274 226574830 146752269 768722903 214813543 409894684 812870529 730378251 356261289 494909404 913870171 40724836 189877013 795284597 501114082 597468971 684127236 249657785 412038338 517309919 918488692 379389103 733796372 699790994 71777447 444081998 923798905 469299778 420165779 63368349 279437152 939763249 997851823 956329878 98742360 673545327 380369994 37837144 210093402 813838562 948858594 108776720 717834261 355008426 177325665 31393951 256855833 416425419 864678841 880778795 208307991 455880493 677284518 914593446 594421450 248549230 752611008 202326718 231984999 331787483 875472058 15828845 717346811 253203858 691700333 550769890 789929791 659817693 677556867 281590674 454542090 510229471 570300495 141812076 890379436 52314633 721668784 510409949 212282456 740997603 456936486 55914426 30553329 872317616 792779745 403970403 266965185 931385929 781899220 351878061 205988839 798796142 42995753 224268688 191629837 49327103 380435761 451224592 131247276 747489006 323327147 605514061 192768420 101472058 86565506 895415132 893167029 256462004 26270131 189248129 416302536 213305441 293129961 117602803 999211621 714573265 560940491 564452842 161502934 131552800 667316535 90257046 877746863 865035355 954489572 727018083 244336531 549364692 872585692 423481233 615908824 790126342 843313341 595428809 471340023 180214851 368605057 168974475 960703289 683024379 581376113 297167997 914068317 770490802 651151645 869754697 841998636 625734030 555474555 195125340 885799276 546691987 161229263 519870393 435480675 171280822 821618872 965784355 825620285 838335920 739899919 433346906 384799765 190327857 542816531 579942465 213586658 757855944 185277054 661863147 787110470 606604430 811260934 333159725 892850511 542942088 762311498 536933533 243649647 555101152 795265429 36056146 605943639 250784360 533192578 339407680 193376891 593900981 36221978 166276908 802365914 956972781 446615490 30254242 875605517 161820162 973965324 38766174 489530601 160899336 271794461 701202749 502920177 81172864 2747502 198258922 614075840 612926670 176014211 844851112 425032988 953597594 792712341 298591024 815926214 54573794 266815209 455982624 323703597 715341907 419208752 777590785 771946103 734802716 797068703 524791258 935829197 669319581 488821084 768519190 88906909 552265994 871686632 755778410 788419921 998226542 917933910 274118217 767972053 293205015 483699566 856355755 795648795 336392810 775929600 215517789 541165036 156598443 399925238 478293761 998415229 62977511 44699718 958621046 365149937 401999064 884979390 748236565 663257543 536897192 567924871 544147539 781131584 986221477 191966809 6948938 433435237 748377490 632705536 839241247 214897620 703334978 241252795 785472437 506232244 361858709 739765620 348149209 326327509 329078983 969911757 122412025 217058474 909069668 956171818 451031916 493279859 63149563 179207917 420488217 300499383 46105492 512193620 303802238 190160202 762339474 417319810 684911123 829370909 139010861 198593808 323212571 238450424 257165048 98690746 107210791 950629548 585039980 889199766 561978079 934451593 880676932 862955946 241345303 197827139 812700677 30914546 734820176 721018342 669339648 854728633 670940514 659628657 415454746 224294183 410380487 296683379 669784694 490512558 52164875 660688311 272803280 306817075 281109233 628987074 139339582 105479744 258938180 573189301 858190446 448108812 80407542 952196021 574421897 484762875 71088808 127226382 500713506 75436989 288311629 982340468 181126949 570929803 986783503 694385481 676655639 38856166 112237343 939650655 839099296 896236591 527364168 110618135 274552657 7916268 312078077 37099673 47150082 754915979 241084720 167817645 445631101 610435930 327279853 851771770 468384216 403237784 177031184 167310592 977753431 711066303 679298299 1800279 453238016 368575349 20229637 901590310 320562155 736787184 182114992 508253049 195760021 253362964 258833175 825509860 636469745 662907002 252384990 784415643 494927584 698718155 650902572 319474132 105606923 251625039 463574074 627326776 333151925 302681769 326938058 571192759 48484083 55272564 302116992 526959339 599991156 967139869 856390118 647327773 928294820 773899246 941141344 796943323 941691951 402040099 900712741 332082146 255320391 578600316 98437075 946173979 621099552 464982783 346597985 706832230 446047465 839893962 440283620 161476106 761066125 544587008 160696194 577397855 95576050 909565978 227994739 199082251 509962514 217962379 19601495 999316772 872302880 928340090 328371746 100121262 736381507 376502695 530571479 533444358 841980210 271158603 190843551 734250650 501266059 713859936 264158285 675629578 946388522 690442785 559190532 948296523 345488455 709405138 227253118 121516678 727885521 728396496 668119861 418307325 42909790 87093310 688604916 59353480 590539923 538267452 456580984 292955176 578007854 422036614 75321812 380564079 618287342 284411599 52358919 840033418 490693431 939558259 10223675 822262217 535820740 18781988 939845531 935863586 708141192 917794378 513135205 684569108 208459918 216966860 810787474 187735596 338393364 208491273 332963562 277997585 172841018 990842833 351412695 859401206 773671275 682176467 536232595 867143325 954913116 591631814 527834114 122858974 278345684 148820700 896887969 789319178 846559119 718161776 861995731 825388540 530563568 22831262 938105654 335402695 92302786 191752442 856498423 966365410 734243221 325219303 307499331 548903963 175728328 734686545 990834618 322265383 878728079 805514537 548570103 419527635 706139148 510676463 661210735 221274223 385073283 711264373 46270514 797834426 124291353 769260170 166827302 282517794 83402517 856529218 578861292 750896716 59063503 856318513 603420706 487564496 110044916 827632544 946979454 284932918 812564710 520379893 320988897 69538339 754418846 747298696 711470026 994476233 565431834 114202531 183474152 409601544 965447174 482185335 709211328 920374609 699257796 801309697 82623149 355560992 141797237 124476820 10424231 755456627 290547226 726272457 346358130 842452167 49493694 282829798 2503976 428956482 356060579 410097463 914592606 486304583 458948171 385456089 814556731 279381934 281632523 3965514 795622467 738848113 102751434 764344543 125241708 376074701 168015606 634087204 571499353 726356333 981562987 361126586 213847831 121041526 36940344 642261511 564510180 582355441 277263085 413224525 505319787 697151059 544860674 788747811 274284701 711979075 224595448 405463720 732748299 300737340 593563938 990941137 82582736 225999423 950754821 523122832 663975707 237946219 457680877 400882172 337585086 614234135 448912831 949908628 767559859 858897260 695126821 583642936 482428791 303445693 235999685 667457384 637274858 171106354 253837084 525948750 123067275 621108616 176473705 681163421 934444722 425388304 504738419 37875842 81822316 731985455 215826461 787816063 727925522 400119967 772071409 995824799 340207445 786107325 300806152 257949795 137688785 753875451 163570327 585557027 481337971 155137899 637233361 135030323 919724888 927309651 120073791 996296155 899742556 231697482 846290516 693311020 686585945 472209818 502366956 374217033 900869207 401177604 49971374 271577037 174707468 554410131 532207463 503318293 321334559 555216991 460632558 861210102 938092672 539506980 654439082 661826165 336120997 245058462 858997363 956126145 652794169 465355152 167731589 783011491 87863976 91973640 514924000 923590824 207606742 365552281 14384740 712282621 486711876 411927494 129630289 670978538 569908539 681293889 792083844 765930384 583683260 825870780 789498156 700291581 268426453 974815805 385858746 302948374 814859117 375701101 549706098 543641740 241003528 224769175 488113874 524753228 751225743 595013159 100212545 317637297 176179761 916600139 744588549 837931445 339697191 52179459 298556321 266776386 540592906 370847964 983753931 720422151 214400654 843704555 795517824 356506948 393967490 291569521 870953921 700533941 446945778 228136135 88885912 71143959 717994363 605246013 153128222 393386014 754019864 506069808 813912066 232526830 438349664 267988327 557334456 595855 202522146 248690159 910169931 109720855 500019853 773092698 65790300 640650810 612012914 501190368 354276896 112171906 472690744 15262783 206311117 772929143 699958337 703122210 851275339 831733777 241151111 131688565 909866647 557928568 179896674 424587888 283335496 519997245 237292630 860794462 538412499 405460821 469681309 722213057 14698465 860351630 92252297 314041328 831539574 911733598 765157536 59728002 304387616 390170843 526337031 176835215 278417248 302070137 852656327 666853758 392905018 553527648 102165334 334000013 957058592 470746839 680964181 547670338 137071777 417274865 942635401 553709567 677563877 461594667 412186373 248710169 900841631 667334502 327864757 620426438 858941983 402663090 622027217 592751797 164953581 911637096 114104782 293967721 26260442 953838279 492500867 308401642 443307087 808978880 876173340 157728446 123458880 362233120 209562860 911317699 803921347 488292664 86377821 749249028 982188544 803666279 427424412 801291517 888789725 786646599 310268032 984802494 274862815 756434759 55125800 974243648 230621570 444962918 536299767 326953411 499421284 255311241 983933943 112976047 166466740 902524363 680410200 827231664 419661919 321856377 893027547 905525556 675281912 623376225 446105355 83055798 864207278 50413420 417082561 264807055 2744912 636940547 28731183 295238412 186537569 112454237 624757017 178359981 251460087 308741064 849301104 530091839 503689406 153776254 46015020 797248058 521331597 635914848 983724881 975957395 258683211 594162344 496075437 430768858 902997762 609237769 450523409 443782695 343574305 564223436 432505257 392889741 656692587 14068209 439607508 244365854 602263850 502441375 986494548 17041574 810374335 621984100 481788743 172014223 828811230 787924187 161860545 884026093 24107381 631364651 677795234 869957904 659058479 238156618 892309593 948757752 104851140 733716408 361680482 506277668 699642563 610053478 580122028 10826050 702839189 789439243 734022636 307310021 231287392 726511257 301407323 881634681 798952159 463932593 114581797 408357936 644293230 269968637 779969713 689797068 756331822 731367146 876502219 28175570 711713434 626957234 276510636 914996639 571846725 955054192 414533596 482663482 898527956 419726430 93142524 652919277 405754548 571280364 643960542 855713436 783400717 120932354 870623891 711814680 240742426 564486853 923808160 226472369 219689954 52887674 887035811 760423732 159556676 486530952 334937852 836727757 576267641 701040230 744122210 414173648 209703318 962861509 365250605 127358604 141677999 937283549 225582971 881031478 958821350 228085590 519322493 995727306 484061043 598224417 576275810 36656676 301221361 435606706 798401003 830590996 730075363 615418237 893009378 369936562 117481161 934391379 934049014 259158458 864625582 123131650 670280308 114289588 852522559 134003130 773830726 70626944 853606505 203458046 598696349 719177226 499036474 891288894 325088436 387654692 187930551 223554973 557650501 921347191 642216833 757371711 448246220 471281624 446052004 653000402 458600318 602766231 613971941 556051213 152904236 227958159 442652080 454093012 42017484 439966201 705798020 604621011 676329403 982650049 327529340 266211142 577844714 327565513 243777738 144729273 561901124 391803699 293412303 604285513 732821096 715474399 90699154 893847666 251922628 721916190 244601076 170266428 691943498 805129889 491064213 830581901 500751979 312866721 352824407 75701781 304815061 493642453 375164632 30259313 986711816 577272764 224291790 346313291 120684177 808312251 523388203 250175240 751489740 156093835 341564303 482617600 974972345 44995140 373965346 519952955 618169505 277348443 452396157 31600297 326007656 105281320 140151368 912131974 203393067 13514120 946076296 515022432 701768658 609930708 380450272 838234718 596229566 842429748 512743576 658261670 886173447 948536230 59407422 50277850 348533236 304239347 887997543 153073963 698467628 281026772 926885647 785491267 455773562 678809239 282516206 679971091 217507254 880343367 325332915 446072556 980103950 172468755 923701930 934388546 358899390 484497064 972224500 707572836 895344560 851506737 318113344 218504280 266552574 654091451 754369118 75885806 230689033 226385691 86133521 69629269 509829079 356670721 200362336 524591168 632628879 626556567 568290096 42552361 832090853 318510584 252973669 653404429 863549128 947017089 851124784 962257416 802750852 451551343 747610396 959365682 257760393 592436299 787484408 525898744 507211923 512744309 864550964 334975076 571730607 403316837 692503602 259298481 585549446 244136227 83957409 598155533 466967013 283430573 68129531 200854022 108579650 824530242 736632103 193578516 948256698 868474462 675019264 240181757 276785933 983552109 414324102 235601699 183620832 59739260 224760582 634325191 927066320 896867798 771868006 856990267 727089470 163600779 775747015 169107100 62171102 450988281 314170356 629831657 431784593 859241378 691562655 194875508 430266560 207888743 856518811 927311143 265502409 368826098 156380547 433256380 271880811 117538837 653447988 203058688 590874650 939697228 709995147 370176516 760399376 588662757 227606365 301145243 221446411 51051327 276095727 326642862 107313226 838456283 745418452 65285956 218060672 451458758 452498090 494996998 341462795 938546708 722859590 591511515 174763381 813149356 730905106 774739508 118360188 964957894 40625154 984351029 517691337 772984791 921113977 395043609 21524896 872096451 837364061 183841340 842626967 336583749 888055931 70027230 866809638 672156063 88823689 879804256 335785866 477753552 439835535 402070613 24707991 314680953 440102828 495191697 990204869 418960699 178743670 86987791 93780505 751154840 521998219 112501221 79727459 828254879 781148942 196887023 912428769 419461890 413638199 255412130 394314142 32951962 316541071 970226106 177408365 623742855 538651586 758608837 148543701 539628695 978065022 587306116 200514959 812623457 619090517 561944203 777481847 804233948 316871166 592583511 767056250 948673551 141993782 733219180 383686439 39440536 670209416 138818747 605335269 640716306 901617640 181424319 788246314 82350113 280014351 97368578 829274648 501747865 386895247 121025131 364401603 150671218 919841698 979538965 593173357 822643443 633015881 711647544 308145454 2241804 116299425 609057533 843164811 282217192 895053656 335955686 984641468 506587024 309312727 798332568 544282432 647861525 18075112 971580584 628008544 983053995 100507421 980952610 183483148 615607121 214524294 976112010 151776912 363335785 956842685 731607429 714423885 597614856 728892202 132358621 699917291 882951499 607738401 268895368 468789054 451856991 159994950 705006872 56032015 338833772 532531374 972028625 941586762 964867149 365188653 347259167 688492528 3168497 182467894 253421192 469161581 430106019 631562728 198630197 607493771 922326589 19681327 558138474 194062684 960231363 680277995 145919844 415375610 60298366 75992023 630981204 497656041 32676387 319780603 92897163 558168508 6565543 516810132 963933382 561063699 980460137 584312493 546080227 733799562 755662673 166932989 524650636 196209263 511778737 731522288 188123586 237290320 783681201 249074693 895192798 372359965 255891623 50096966 934508696 369669519 651242690 587236793 918598683 448337693 78474934 818211109 563814583 145472005 334684141 454801045 898669104 654008597 244429010 556646110 888296294 839721169 716977412 182265495 758769435 595156992 680648123 607302359 819372084 696706711 515295003 640689119 649411750 882257901 420360357 376859904 802144025 165026735 991898132 643331382 570170347 188968210 234462098 622062497 299878536 658788278 243358720 788229719 9079879 957288076 602166374 694748398 11687640 103141558 866852659 179148245 767295340 171977704 138590842 832098911 739929111 175681972 238199544 645074455 108934076 787576730 226608549 441153842 240650280 742917519 591045221 254477858 36208390 451369658 782905163 706314276 677828380 959484924 491544022 161366445 489219821 982780021 2412453 256819206 860899256 956298208 258602663 847403974 824087539 924755152 399380500 127882178 837967907 5073783 388259946 145988267 445758510 963308315 932675153 207791616 733911168 518349242 514119494 255049255 290822101 496225390 218517786 959862224 957500431 391754553 236757331 256953147 520018808 839640824 387427366 865176693 801165901 162101747 320701591 989744492 257377560 753489819 242626081 801059819 573141649 754257319 996012560 455200659 17089395 461709557 1821262 299763297 892710447 293632635 799767710 232920347 611037709 70708870 213478411 338876886 811631450 200702283 241186202 520418471 617546902 325673512 360479147 122578329 244652653 680859135 354364409 376549433 108225052 317199691 338993817 137228481 866069981 578279448 398577296 906766105 365093544 333195634 962865789 660748085 592752146 181779432 257448157 830766957 951387575 211199483 738522575 314107067 892239653 360971775 942237436 203199411 100081775 218656803 151447037 173456489 610438901 462352972 503288104 141544874 901811138 684330016 869720075 276040895 908414721 232996179 640976527 841116643 557663527 176009934 911224907 613472053 269917900 871294359 659059914 343500676 327031347 758910189 502710247 799201617 383179557 896804939 750090946 78540755 284380229 295085363 735060378 905746041 4816790 936072763 56490611 901318843 221628678 29033558 831074325 798846261 417259699 703227418 965434798 76490375 297632732 668342377 782098454 457438614 499328601 639534170 254285871 944318085 371644203 798461950 537933450 235353022 543598461 798339605 331488933 310294099 975961212 68875067 312415358 155233764 985284663 6374524 230402197 449895245 814845664 731522834 781519367 617205621 76375478 822441275 173675051 969033264 245610460 571539904 399366677 884623224 394442080 970039216 789278087 200051778 691982139 820939134 566517083 847082942 839688953 122148209 613962505 788943840 655536378 316123135 52865669 454301280 152863871 697602092 655837491 909901703 150727457 515488776 767227866 461235216 182432901 608903258 815082965 309630261 417664279 731940855 919925444 873445952 863303846 475610029 764382511 875841513 809819631 843448780 38865149 139145135 148559212 333456271 703234328 746891735 823178365 549984110 616025589 207461357 236955493 845113395 594137537 91898764 587382662 606836 235299800 266363028 444286201 231782539 530976590 557692451 813380476 123573967 854123857 460505114 652569978 17054635 40311416 214990533 232062970 3347719 210852108 303048933 55833537 615830609 469398526 265611255 552121735 404741163 318048907 169828532 663313179 592141962 997156805 42299186 381748479 320479115 746402744 168320433 741232957 868142826 179537931 631587027 95289433 463610657 590624802 423912908 583535735 80100622 207343376 953915147 258009349 488421104 440272754 196843341 158889408 958810460 402871835 241376604 410246696 403231947 322797975 560268200 429376265 253565966 43211613 15274808 599689562 877693660 337816585 263186702 628849059 464319508 305640581 174051004 151462141 156247960 87461219 358304037 297220912 761229516 247139483 513854474 597067871 181354833 197206584 682707236 249686660 363761746 103123126 18899291 134543400 768509824 928342157 146343600 79246928 670264614 981687496 577158393 219496569 538915142 752887673 930244205 795675549 889002976 854302554 679442657 671898008 822649854 49117518 965048210 561085098 333512494 810004397 881828462 103438287 479549442 370435902 297455903 221653558 407888765 610180909 389830788 742400580 777227610 293274830 517808885 464887938 572304093 557529994 132682929 603978934 510792684 379346441 109452500 116915466 465329070 281494010 447533837 164227445 156162053 726079554 327037771 517913498 465913177 294791002 228790167 132529960 442537626 473676190 280494779 851676701 361494882 272127373 417042846 911385545 422794055 201249201 494774720 764490243 545809169 99069534 868904381 332606257 593749444 480972586 899720102 114452895 930495542 585707131 729890300 330431332 93324679 214598854 253543202 700067233 286847548 437067037 826468635 571448945 122562429 356794209 939762867 592915517 73751679 806771412 215438682 458489381 340360146 938747062 178252021 152304485 123501787 439680422 337937753 805805502 143442333 808118301 314528549 978661728 801596836 623125320 93490544 860772983 811457637 811052655 178771201 609742963 883214098 579746396 526571999 732648689 928637256 407863208 233670503 171165107 741147056 17874329 296408219 528036236 471444342 395781202 144668243 931994502 387160570 231116933 756847738 362942083 28077970 150284244 400194095 844729562 540772483 90158762 417078775 278998696 329035555 687391514 198575779 501399281 716931289 964627438 728385294 431619401 957764083 29713247 293418464 899220946 671734778 54841318 665390703 546219217 40701296 959276517 300757279 693899007 505996019 709498050 98660324 32161647 57949462 427975519 242101352 591031823 638907423 816047877 963955306 260186241 696588213 431358058 235856172 61383039 870190071 835608619 330267321 571188346 116405496 919645234 188128194 86068690 359706970 547827380 976910219 813795269 273769665 758527636 626967166 649044711 345256243 169086978 650191410 664215941 109852283 283651250 726100823 809956766 496403945 667529483 444519630 944960485 176931263 628095556 268944059 331537207 394346949 510298834 239802833 514680659 469823306 45392654 330874159 211202773 673039929 939964178 901531032 802899086 313433325 197477002 787722053 239232946 744125746 388912665 805723993 805760946 72371016 313633489 235481025 62782674 316536794 367700805 19411198 133776661 903206909 759974969 143310078 623597676 171713003 514417571 172121172 358849611 832558296 731591383 271579352 626700776 226480296 461555 387537680 934231680 674111810 386825378 965282412 414317661 872870763 601237282 410359 126655526 921940379 616751312 503742721 85005042 556753217 278203256 510303070 595185325 209250272 7192346 942217546 701090650 825452936 338019565 809579045 174321976 197918803 786511783 743441868 229447141 277747652 396311297 535918982 908287598 607371614 807195916 23266667 828280473 476078944 190014597 756122924 243016653 890551854 613571324 305415713 383586815 424708618 189759534 386895657 48392953 857128164 897418227 221394909 469983471 251223482 617978005 895736213 611326836 613446927 505968314 78209187 504298902 767220158 169255082 817583871 784104421 428891732 966670043 187491606 123164435 811634528 736210362 203683891 279051630 171632604 306809990 675827533 15579579 859668797 916198814 515954290 329388765 766888022 213153915 995454606 765188437 322933388 374437312 902705202 976949979 208686490 368935538 120867489 951629266 966355926 374633340 455249730 664181356 557073258 158598972 90839656 776068516 884840150 213816179 806328415 653611858 524121529 81326185 388577952 313874339 426454222 657764100 593532852 123416987 463869601 275541607 121017823 351537674 372665421 294274511 512745796 478995659 121725096 914661779 336273182 802441366 151348168 268696541 447796131 452167348 654727854 499862639 63337380 196025421 141317257 81248750 950036762 215510073 265335670 538995680 261591966 468165967 930285827 830481440 779618984 20110516 107758288 972576041 85424406 943498225 38521571 725597210 374713266 264042911 333273691 284804726 756965495 33425544 594874347 566692125 429778496 819476174 305865508 59544306 411847282 140049758 528471228 296647278 35712162 678776183 588584709 197228549 544586275 964849820 489441877 996873807 152402813 814349048 577638122 118254091 261791546 89292982 422163989 231131166 228060152 552899040 813838859 438163580 302676851 54664052 437670231 120542129 572571482 267573615 718313341 786979250 269542730 57896219 897742157 840309464 712152460 557457393 85840163 342732219 85019920 416406730 724326336 554717192 487548304 262054018 783621055 525438520 492692528 357294224 14602323 399272053 764521399 629238916 253363158 328994249 599696900 278344264 272090418 993964759 310768754 675593073 743214595 538877789 133682689 255844142 208054113 289866689 509873348 940526019 679525217 769129288 315951358 585458070 560443428 646574051 741463673 333972534 213598976 883317555 49617201 814722411 999953422 382155350 202372415 770374466 470991721 149198993 313063880 318041724 116084757 920931797 209266602 263256433 56442735 696609158 843903925 980323375 783108052 252862414 620642696 423615776 958251684 43081477 999031254 814219380 114549197 783701411 115064773 249813386 477072496 115583913 135697937 741176833 234466654 432559458 591009413 706950190 174550584 311010963 72948718 261587804 245612541 446620672 424071031 679383508 731664536 629528490 89652421 491595347 701216283 631244275 491170090 164790710 915320232 92129619 303229535 114828959 772090779 572695934 171922125 91095255 693492375 722078782 778542531 463386522 13240267 813368160 224995032 900971522 347437472 138611001 367692133 330262776 838395218 248575457 875183513 301761082 839438821 836661910 799231148 685015526 679602445 380524378 486682751 196411397 94099924 316042004 658504787 57233678 889308431 978297334 858955673 998198531 390231116 76759576 153596080 165682479 843399091 285302745 657724201 395925183 60407544 901603335 693702636 856960870 844845633 955023971 161990223 206726262 28558798 928312364 575994793 916886641 648056692 919119687 672455823 649060293 912502747 281739117 238770080 960460247 444447368 490328632 553228219 717292238 692582382 303701 358759205 219679540 968157851 708531076 623735883 35235306 16761842 539761106 265046347 110876692 700028342 998257491 203066410 585829555 292708740 706559021 561547625 258399627 726910234 797593771 883057413 999437049 512947715 301095460 91339709 590433063 348612373 487708352 571989655 898235790 655448882 733387892 137562334 931168127 92696266 802020545 189311703 665279533 940801993 632433666 195246459 714034941 951902094 93789356 807274127 210109158 794942854 982694470 642425542 151963650 216659092 87236482 111548193 397416235 344383605 464281945 353399773 957931489 889837998 40835101 556012162 984154453 872862854 483740077 470284445 892174936 718286471 46002504 697730361 877477345 596560449 431305984 895111481 735956760 338572190 421933891 995822609 888319124 697640207 822797274 238815167 271843104 857550872 632362170 669601307 558019930 52392299 40877127 27316811 469762223 141287833 768072887 730384535 777742555 953535719 43336757 167531745 332898135 316449033 749903369 816366585 372517728 589380080 670725405 21068634 305057793 914337010 947483796 188221202 970427438 263055038 344947141 941363965 2691037 7026700 814758438 438028045 168952503 561433331 533043238 73544654 82906109 145616394 113801404 512111581 936828275 190550669 956266666 900416323 366411405 669328168 530576588 988524330 720270324 258488135 391347598 17619070 524622650 931929972 971664678 731999047 930236508 617448116 966873484 252719122 405609573 276026290 708002970 920251680 46497780 778752107 971605220 460058131 508428848 195701925 894938023 878336873 318146826 566473384 887725310 566241327 481765260 298500159 713687503 895122310 154010391 422519027 350708052 36903741 4480683 884216644 82468553 224149389 386630016 604431928 462260541 942154300 607946441 628187178 615234423 827002935 206034225 834929314 477661978 672230490 687563881 73037208 347261799 989839224 979782811 325414958 671763777 315457051 236339429 470732299 459249659 686570047 975422061 703326731 627448953 252729345 100883676 980803111 683610561 590689887 142199355 964251528 676829555 28943266 110131953 936556170 523478617 483798464 988761433 84074459 40680067 498623136 866997228 130565242 451967352 958130892 265243247 90121535 742125926 561555252 53069245 775242867 370661251 53433138 303203446 30034896 832086372 549443366 136672844 603881278 731841089 420665380 600501613 808046374 98916688 454004901 447962699 374397842 31619159 446748825 260653909 496734681 539247943 880655750 598585864 463468712 858347189 419097134 437732560 76661358 904459245 673300367 140131665 919001027 432161424 71706778 253059724 925116302 957507082 486078569 967794814 915272263 269332271 224013566 747060811 902822177 920726039 445899427 18170016 581755491 59280077 429355297 255332496 39528946 247699616 392616923 574400254 191789626 335505832 577553732 525542130 269993498 896322095 720653623 246223056 466180965 501383758 761547970 423230363 218491810 250284442 677993511 239566877 346935316 190003805 217776502 398849347 873204239 56541137 385701670 615716319 777155816 609783170 119397762 175979077 375174366 308736676 954113223 882573568 152293482 813901666 763080936 98383852 327421143 20325290 538380680 865058405 938971017 561207491 323651167 360479193 979568390 798268618 586860176 608319534 582141801 993688658 292257203 617462829 154875215 229799306 946719476 212186125 569856851 25074887 594666920 304523332 477270956 679949465 98513283 164873528 372497990 112636185 562248619 472361785 303809121 849403940 215457388 796074063 322614338 659554303 268991250 277741631 60176792 665967349 282974786 949612299 582094613 894928858 201085345 447322492 316083739 315011328 264348834 566772066 485161977 60678397 142025161 84223257 187574973 408195983 697780499 564082739 977162578 512149719 177647090 283565579 12340592 835315468 292119728 542075558 565330433 769588198 784300571 129175867 16666343 410744591 800550970 401409217 666527613 129891542 970751558 216431145 806138161 431487312 814700927 567769637 922933224 661076601 581019551 272674025 224982216 289613883 20456421 140476813 223608916 604387957 645926579 174883322 228299314 118336124 180001503 664251716 835933637 836698791 345180940 791398379 422043227 403956128 841709190 544534059 688888674 110544201 153437148 502694321 324763175 160744179 154891548 708971514 975687990 899354135 974588759 356504271 727672326 52925516 797976882 879901994 879321792 243641111 698040633 994652094 985341970 500408507 148302518 701976486 554514580 547147805 827302619 413115912 75477479 603974949 680401569 226954520 215133957 473474259 348956968 111057017 249410256 28847333 250294534 258977083 229980125 143061968 908658194 21030872 65776275 278811755 443052040 290005439 180161732 156351115 631230776 665181183 290694161 725292324 972264011 916821338 648835614 126622304 814020415 55541558 5680260 894522338 427317302 951375711 965229503 834556636 265592376 125732386 264819968 485588350 826920960 793298455 991593383 656228519 791153210 309478625 982756246 657281568 169126913 968326 466145550 177613260 937342044 913827133 827160729 514105922 959370331 962564711 435636605 572456950 434471268 802143459 88601062 761176132 397467877 589384955 877081765 78839488 235163706 644475156 976727371 489701322 452196330 833976343 327510560 987760293 33375261 779780273 143373766 611672054 939639422 837482002 64390257 431426141 223349824 165360589 267320083 697335011 265851197 647473867 324497012 628608573 748655446 726137823 981487900 589313090 512381528 46084280 277265164 443461048 94854684 163882323 747722627 800526991 788417968 726138749 663043583 248467149 271802961 676075627 542349865 217882126 270675209 614254454 269824365 246231631 107096543 709047083 399492529 160349752 430574286 664928244 738160430 564629513 107508310 628194215 3243321 181626897 861990110 814578895 146232322 975453861 82283102 591526831 194027478 877422846 256354957 459972980 8699683 926801786 504810194 52241089 312102253 776033607 101700281 405033866 397892086 177712279 871561536 726878155 841461781 634380382 753846178 273475256 454837769 605039719 644507225 778242127 382839020 132282102 765105107 224793455 386388793 920547904 460257632 645706828 69110716 246506070 85986570 39342165 47374014 583125903 625031607 5171839 937524493 997165061 376686154 370133302 367572251 733396594 894037789 730060584 843041449 528464947 194318172 916665337 689032662 114633467 397874779 979400891 687357753 9849049 411615704 112987829 486630286 447263126 378918953 800192116 865733518 599729422 489543270 675416237 541900718 197801730 800905858 800728610 684077393 799571164 774918916 633027519 540740880 382253872 374616763 728973330 685666470 384969650 824605004 347784072 289204864 567296957 426657733 110591625 406307549 313657786 611400250 698628560 1107017 156464413 228897299 296042538 315659880 251817283 96925479 914880372 630381118 734827018 443854965 26269552 767296145 182457310 111536431 613215667 978001402 34819273 379701176 365489545 491875204 519878986 339356797 312944889 953091206 558446413 494435060 227483963 304822261 4702959 220730079 982599261 904420936 776271974 467975069 337032175 559015284 782843214 200062450 449337523 588898975 328678527 161386030 30390191 447789160 778676260 19555625 995808335 342735532 384534322 399622955 224349671 384535763 911941203 767111750 233785745 71726163 681157507 881098096 72914805 991869239 356380315 807524818 216732123 31858617 415810401 161372901 516279597 520497229 886546728 923965673 976789509 963568066 205955945 246267345 376941214 606863632 222967681 581519741 236117451 823681948 29631807 891700051 930955856 784323508 21297927 609622286 201206621 104906501 275395720 169216217 799062971 975068003 494636955 424518214 385232955 97046025 693247610 236955156 113966640 461792688 619816951 530927310 886906132 299139826 133499827 755942901 338159104 877951842 879246397 223251418 740140657 440808397 246913973 35133667 957876501 781369044 647173082 582195917 255556574 858898955 590576355 783869885 483506736 567632370 445652712 506638494 276404112 849916221 615234903 652316359 2483983 614888106 900465882 820892645 240576136 477419218 708358820 544867953 791964825 732052971 428304460 218842728 293325237 149579251 499042772 899883939 516011152 308901869 942948781 103952032 407916932 177898340 414864718 519969166 863358606 675478930 438030728 611587016 783365941 788368949 591165727 396991628 76281071 22561078 408802073 922809604 911729251 517880113 477311406 29506713 624994019 240521864 359487316 783252036 666784569 525301264 751408217 127293951 802298907 720957988 245774520 771828885 219709724 382812976 199685026 805459727 336966940 431561239 710527517 652379180 663119748 691757614 420471910 897488825 684141226 277085324 898551735 744855792 305384688 386929779 920395037 328475052 629329312 765206321 78601465 601614104 462401426 464856091 378403257 498428816 690321507 990042717 210225648 736863553 952746002 325932977 745419906 695158432 662710906 418337121 99541025 988574680 732128220 958529587 405311608 333805343 271705220 76928911 109134265 122029734 911199085 859860293 482854865 360883331 103397842 69303982 74018612 178929899 960950839 325490214 943427267 298950744 54411295 185577548 583351237 239511315 880740197 577220813 225128847 582336399 295531281 30258213 380413689 643832664 133069390 386274093 523114925 838608186 732294010 182100882 570348914 889961811 269912610 737565770 17129165 317351405 551387236 505036426 226862438 210940576 791313930 127202126 808059277 854760284 771709850 353976385 468826185 147884159 601817327 779754824 70265010 98647115 383257654 172866236 973274962 264194090 420896123 400826480 751795415 141827727 604812697 11405072 393074723 207797046 902145679 946952313 444354906 282818347 794408159 9078998 589697958 454180366 141031581 466691996 891048132 601559133 622419572 953677580 987704042 321223688 506416103 921032859 547431253 630946867 368208261 636772708 625017811 427610120 272476898 433847440 631397107 705316342 559391459 346980733 532679935 876978536 207253370 225030091 154206550 862988542 324643146 302524931 816091333 41505089 124951986 378374955 77202790 287911771 734589801 282046910 50490394 246816456 590531003 761167441 426215632 378660277 946176742 7518900 436435620 553671641 474045056 483189093 493872405 231095027 311825402 445998841 727247954 529906084 922691755 372170018 849251254 793296244 404904651 728333906 301957132 229387701 24530385 575298455 810432618 612861728 395224804 111518799 718736131 351462755 588235952 930364667 504075729 223061747 458440940 129783321 777431743 423098834 867280924 79414769 13148762 416022706 85448931 744256936 821585995 203448937 391396098 981203610 412423300 775771044 381370923 824324614 972759762 254499812 253008387 827483519 724238425 343272214 565776498 436536493 18912880 708685897 515389588 965695445 55139120 735577482 410131528 323527352 724700331 798824629 242200036 898885348 734495333 325536539 608787285 631757368 15584771 854724158 1238798 712095602 536715184 286603237 459348234 188978986 260571821 142645038 597319914 276377856 466837466 319097181 423371451 227533315 214917775 203253553 979746067 955264000 687643195 54943129 616329327 161775306 179415829 43055236 509507966 305896589 349775154 505741111 937983072 815283569 206694523 619022537 834831519 209046623 104354834 436046374 506145433 779760105 992469282 561465446 213451425 794200547 578687282 163199698 877975600 573476423 220338984 109538372 825704224 781184130 680278445 769264198 487990605 118457106 94340416 62366427 915645394 368670546 373190027 738654018 593366877 743705476 606402005 842157197 892316265 776791581 168027479 151300293 257269705 543627947 572767619 209088020 897481948 3391269 773458202 418684779 792774691 456679161 907094549 435762807 418105550 227664324 834019299 861978733 444126750 334156461 924089109 592224905 389398301 790206378 39974852 822154217 43376544 847091149 119610456 280890235