4000
927365733 670610708 299152471 668478334 442739632 305643555 495506575 740398954 448492420 189415083 672090718 111156092 895135956 325812447 670989355 845769967 860529688 132615430 882524972 460433410 256951610 374104062 343214522 407895434 644196789 359501973 465162200 635454588 113264496 443232586 853244466 13499364 328029229 268731913 246104185 313961615 66515460 981666415 546202653 373288138 812206759 76112841 812416106 587066057 140338404 9307588 609056962 950421752 808543720 887021831 675444277 160290292 663754306 545573610 121844449 224478893 338749957 258526669 401421750 880495649 721141686 598250623 274031141 614376592 13183576 212358882 298277112 813554940 973431255 81870032 174283782 594743337 448964988 96559171 929821100 349789776 183726756 669167693 234941936 17157567 22342908 166548677 660522699 130346294 847965057 457608045 326765268 682870882 564243993 866474310 365428717 689086644 594062338 521504618 601986889 123397305 233175922 355808524 819142307 472228751 648360522 815869682 60555437 995557079 238294975 803090362 490681780 364139359 223027457 385336632 163438673 288865121 839517749 462654949 976223905 415507611 22069917 969536278 977472187 342934948 380614844 814271636 429888832 39006182 733249894 656804000 493702814 434978946 837378643 19673388 879548632 559497653 310985255 55271476 933049997 684144750 379111241 903370886 548526619 934351982 140357070 122411891 553286752 290076316 542613613 473766849 710754919 290997570 343067398 76229731 565728222 39934041 144859979 266964953 559193676 674547493 259090583 875305749 551255464 443619357 231006855 449881478 205301339 358351423 872015591 796745848 80581466 667552433 394251445 530886531 230210777 565358445 228546370 805292577 950503513 649687627 278346753 822117102 109465864 195797203 716013701 968940146 936499338 556427685 46718085 888088164 111840615 57471010 264621330 852088173 304829251 75221771 314052019 113945920 28575861 653056518 851075131 37605201 685136685 497391175 786072249 922977131 230818066 390553369 500825415 108498771 562403518 796821295 27687442 330160926 886414367 749354511 840992143 977282765 598799729 15198475 273200821 800516122 850991292 157774487 22423202 791221015 152954607 722899828 548406592 180489564 760854249 897712377 426271985 429800598 581392567 260756021 354086513 759627418 700062183 754783549 329392923 717589473 206144280 506226336 272805554 860470356 567411271 977175776 164247898 291045775 363605733 475657126 951761518 39205724 614775965 891331623 588420261 201128350 134474620 256875478 788954581 628152562 635928250 388953064 311752310 232805820 605184476 387126365 369017567 631232856 649179783 400133278 196621408 575951117 507601168 87333794 46480114 961089866 989461102 855417399 879075884 409601219 876883683 268405991 805608329 981125137 155508760 252464267 225681936 858922206 844641683 560109796 838722077 114932850 111000356 904188104 747189457 474685152 832344762 40704910 583996408 234210894 144622118 409137680 671207244 987034226 219953046 518781461 230931621 69944620 582481619 879661895 261817110 38474813 42335998 944346249 872798080 561746814 74034500 241344184 771689262 968768203 751305223 861087208 300574711 688765665 847525801 243725101 899694216 261761023 953658763 309279478 786814632 736552295 694852133 791995139 230300015 393136635 519737124 189033647 914942738 134263096 91872498 791761352 638991556 617870301 817708096 890274177 989922905 956961440 356395977 14569296 953305020 799421604 230280968 99026944 561861224 276918288 607542822 997370084 650329413 811549191 453096284 537242413 832899336 250824744 690213710 961300431 354152706 943940891 937747926 624811574 356166439 824071794 72754627 145863990 772625542 77267899 452719919 14262626 699033566 45291039 123740583 484708621 486406256 867342576 850261219 269157174 811280375 357065160 855465368 524486663 260629621 449008492 654804067 14358321 124895970 270944199 984581454 637379074 479831220 249855070 107173693 178349063 637665329 619712734 698365262 689518790 510396830 82606340 436499348 182332090 291375004 736868970 973641949 141860941 857174007 450236512 623866290 395883690 709682824 235714253 390481220 959435325 404949400 199414111 194980352 628840214 811183108 525135554 365417539 525276760 459763215 956958593 931312569 497603877 51460984 490399178 12283537 625272285 205240579 517325882 178636212 671573664 432017402 876654643 71592418 408995174 792729255 491039233 377615551 903261352 602515239 121702242 892936005 994092659 601771125 211774881 439170735 939630909 530824080 820748846 822791054 880245088 871648289 907604971 610280977 528858932 268014273 419776317 11232478 310697309 459790683 392633115 912031450 707135656 909290557 888737960 683723814 726431609 986688691 185227416 367539336 105729217 270546843 705183744 853643513 849502377 19739363 362683363 250721747 257658891 894539382 23817891 538057966 573536210 846899784 466542791 707056155 3780284 851462287 328221428 775030091 38420926 510250583 361626236 964766655 482829285 139408956 727339244 896250956 525453550 29252339 754424346 749056608 645630698 579893383 795314449 678123128 298267888 165653632 12971411 312570266 613233456 808821702 685559069 807244668 557142113 380966697 353614804 580569654 917101189 192239672 530771358 54298508 730920918 320371760 722181174 888325102 583474517 308757370 557305167 30178988 992694694 25217169 294131629 538240419 887644911 98352842 103805980 685262623 502789252 132862230 542419204 418828391 606794502 109918031 811729158 305450055 512689334 964958441 893571039 664080935 351792792 514839187 911470733 200922431 283073180 179722104 319131016 345568293 35019777 134917487 198281766 345583397 922846665 378103456 396526105 399531643 345748675 236601013 597004790 217495935 399350423 607973977 380942103 976208212 100275884 755658145 8053471 581743853 394836368 483099685 613358124 623582651 182398577 964775241 93786778 250738541 261345346 65295664 912245836 315945266 60884785 628077228 270423392 493420367 739771363 992685637 795173176 795868031 845493892 137492961 96851084 727471885 82985707 306329893 623891436 973775260 544197733 935784779 444184578 637812109 790415394 378339229 312347560 15748043 164085211 676907557 141541185 749777056 161399350 608533370 767774050 394036458 556358731 181548302 202000884 863558084 986385739 693560328 452611223 148462557 668211153 662347962 587402387 531927655 313848021 338442498 193593887 299039501 133625092 803717261 108749902 473269141 372805988 361392067 268346381 678970389 352742123 386023102 549889656 849650009 975221718 587524559 651216150 636907207 505107284 83587002 40730922 675046907 827671435 254507548 480086129 456604536 189315501 889378140 639229910 81672541 92530110 38655091 977032716 116836034 652334116 728684398 866812183 503842689 843365024 969277720 519552381 715847423 786753573 362370733 408954127 392140406 214858037 772683480 860179570 71345932 442115706 56535078 240784202 894054850 709330528 597137576 396204568 593038232 919190529 371793008 299072053 22861751 772670416 333921901 955348431 878128922 631532404 239589845 314113460 542576612 389452522 585759583 487178472 386728494 862152366 829116246 691441867 593926625 180781437 852411338 106728930 532227122 151451284 338821068 430165412 121343274 110502049 797764536 611607959 897517980 350566973 60606813 275916863 112217849 417823870 636257583 948693197 273946567 626329510 195190469 98771717 504518906 107285749 519582701 367545673 198017526 658757588 114169646 354010846 534907036 524003821 972581773 564993637 577866999 44538613 703590704 309397947 600641900 502247865 545233253 113756523 320426820 186744 247463108 776348147 853432476 38309435 624158852 29692638 521626972 675462561 135078495 97703272 923994827 3013433 649889165 252068200 706907000 229234055 840336356 870796993 237804673 230605042 228307777 342419019 749325680 57784025 468969512 209979405 488556378 564682412 725422917 679778952 884623353 720885632 555858388 428531565 786620962 72162720 852685969 929513007 389302231 237475322 356084574 931935543 744218847 99556473 772131034 734368489 623475836 660621142 317831523 669618776 532450837 253203286 910694622 453591578 505585852 621737082 773743593 808079478 592134710 450364752 934659857 190016986 963115321 687838618 700286850 140336669 95140801 504203297 753230310 27837226 415659030 811284235 990851084 875216824 10180075 900582129 670531030 914251663 260062429 397017974 35702023 37718101 179093557 710943067 356917029 642286901 526841508 102873342 254466757 148143921 316692945 601349002 919888762 70451210 301461250 276703034 687922833 165121487 263289330 276787673 362805852 362630295 652261132 66033365 567408553 953406305 454620109 600645280 581624374 466264834 213903578 967062633 358013342 339982055 200068046 896612535 666914495 932184280 402857123 451135235 407096667 934004454 884163939 30108109 911902719 978650363 206582773 690809379 20660491 1016151 108218080 291080070 524406418 346204758 226690709 198096725 793798450 867527942 563667426 839608195 135942637 445886210 551087180 478689474 572587779 834211862 122339504 731142871 334630756 711936082 395262543 919858862 972264491 394065473 553061674 365147450 662129541 675263345 43695524 318771077 902842176 912326379 78295779 608097713 790095610 119725971 470543085 554517071 166305243 810355630 349054900 973965995 480985496 102142137 140498141 965256514 150535276 137947259 947486438 517453371 565698589 734268787 507463858 498009778 846087703 276038270 681382244 709029491 714286854 322625923 631299201 708639725 984199229 75524545 810587952 987183592 292578001 883443181 659602984 986173323 809239598 686403525 574953674 86131146 846265570 789029508 929749304 807287328 84106846 415235135 245784981 543741825 981767289 93419540 634884471 257565386 126818585 760543315 551355383 201169521 918333160 915279674 875889923 343441132 178785639 786681437 824651422 83542971 618773141 654737941 405547808 913374347 812173457 235218134 709641063 356456335 412212660 957515806 272823262 905963480 890242910 931065368 997623727 459681118 369306381 721707779 680789280 287550593 964458876 27354374 184963148 628161162 798289306 388418960 819941435 370121454 160707 49874500 356168029 68745960 577906138 576939168 219022588 705205439 764641831 567795518 576876003 270917012 173271185 940243914 413006695 692555628 802490979 524662652 300373574 893480658 772925090 35419423 596994673 258380391 7781756 684257158 80115575 139049934 144849612 641874669 747412221 30809500 47583635 376116963 9735082 305838015 468416455 265168845 152655928 26128549 390736954 442317378 967250969 558443618 803063249 264265606 785838695 346508095 496538463 768275382 433237638 461403914 915181186 437577031 736718100 729125811 424541250 888453987 480021089 484255871 944873043 210251947 446528281 765061414 860685582 195492519 149816562 417894668 276492695 709014523 311826373 520416957 668304659 31089164 655508889 861407027 287085622 126251566 917896457 171884557 288021220 753296984 193751092 56235254 229845498 935478642 366069596 748801254 28354583 180935734 788809417 80584836 862161572 761884036 974752239 505938330 838056095 995148359 945707417 143095878 91385641 94703024 953286090 813003786 522283912 116041413 550800514 170379299 465929883 146368293 441088283 93255463 636102066 688896643 178794466 240458587 11446646 103744803 890887294 533991922 322344863 236207073 708058809 927160848 949472232 105044017 195722935 987575286 367364638 964415283 55086117 744790427 409393486 776931833 974968203 239170077 469356459 764826680 914023284 772465975 396311273 635103414 543566085 679559824 436451510 547130574 764525514 687441075 561278143 476257838 515267354 124857007 16287173 51375199 309001893 242979164 311972315 404125523 669147606 188844432 150658023 31285130 370425330 273817526 880134265 317529618 394190116 733686445 980542583 320179294 542970057 605778815 262583570 204840519 160359464 898838154 331450345 686309017 303403380 399245214 579049104 722209919 548790801 892015309 235349750 670497902 541677288 329825451 312003588 113358416 160248345 835197169 233798492 46532566 345644387 475030630 257637992 974873897 884671751 229346091 939294392 697410651 65421296 986520858 506815246 393907998 989621957 602650450 145501301 4612445 334224233 423993842 680139451 278825371 406044944 537650541 207937018 414283581 628737112 713048120 232357501 742802332 908494342 2516048 585515106 423081673 457066067 15355844 978175493 845881913 579470689 743057746 155760752 852081534 432154584 130217618 821598655 617473388 978560600 83522572 727974035 51884133 814446085 446813618 848868034 670570798 651467777 302640895 867055061 386634289 459180954 694947318 855218668 993339834 908308404 463214541 833840014 820194600 728320229 41833496 625195358 973605000 306794545 375569499 437760889 446448158 34399236 288042932 737051027 186830423 250625174 381676565 818468670 687630840 245702591 682992120 235683518 113824138 131011227 849877655 343739704 632160520 981589610 91631303 981458287 877666368 127663046 247976613 383088408 722665109 407773928 950428123 296389473 61925271 754384980 12342668 880061437 797958632 374057669 122244047 635368621 679174012 822423466 789217153 203180070 776933899 138832184 554518805 240257447 292744227 587033079 837985097 982206069 658069110 868758130 204589084 818238931 279464475 905330634 564601615 901351217 340041967 952779850 131617958 836478634 713555096 631223169 276615797 359196889 507133686 706478480 651170448 904531638 112602497 477253877 455264233 790356234 616746971 282694777 2890630 751027839 918174790 738223552 647223637 515483684 223310446 487012548 862301294 498493385 16829912 809566166 929713937 576454254 912661370 123123391 142284729 765415475 583532961 160464635 502811189 714924282 357942580 618115510 260371170 154263479 940082072 194858912 432525838 190991157 713802961 716304582 315413934 493472286 862425946 241839346 84130224 435852949 988746441 353733642 797898040 725925441 857542581 314329557 848650717 258312353 515192226 897167845 579195802 957791192 938912832 407395713 214963202 854555070 318860271 963409452 616736540 187712003 339742111 471735888 512044191 624131177 631760148 7878706 258988692 632894037 271213370 268202773 98604048 433082074 524787543 336657222 765971358 764461140 896658667 473455934 919429366 414526445 672874639 261765431 467851327 924429822 649205724 123531680 807014132 843123932 42314015 453871029 602354002 103072633 135201990 967007879 286801896 611937591 750266587 17994119 346199165 858158474 58703375 120382600 730236220 833983987 852115954 344991061 541383060 642058220 993873091 348317452 882246913 189259363 319277489 959603770 405299747 253322632 870078247 979820658 124791629 457268410 95095302 526755393 881123417 452037616 338812728 452580246 895579971 783768255 311528695 182063470 630133450 148911196 25559976 596470050 161923218 691506647 642568244 389409519 314417328 301395726 796993266 553921346 556885176 939836841 57379131 457292426 673814998 250689883 222480985 891982890 654491599 920894009 797843759 734315498 496766364 129888441 884286107 967745737 679647119 993117564 780072002 667310745 156647815 82980527 196234650 372753186 633364418 29692399 425550549 482741524 242151686 320757544 755926036 101686477 430348435 644415378 14909866 364298785 785761328 514972801 908511022 216524988 208730028 73551961 800511786 684502824 792552684 299965636 149524323 499195308 967685096 977694658 608345788 313501101 301711528 244936956 510581789 866946188 505522113 689241987 781728862 797556595 143631580 831385834 987453484 952806574 776717960 263179281 501851558 919058287 647254498 697726755 94704053 203367195 143807855 438554552 861983262 330334990 504489747 27420233 179665900 350744269 103188152 865201007 257799996 329240646 543015680 684453031 96419147 809974279 549602281 184109035 837170390 534721298 611253657 2877267 187565586 768292187 373733120 227408434 346550382 261773109 292686554 106215764 358033946 565086166 446523327 340795466 179628986 975128681 542747516 677435087 24372132 907451553 427204498 579835996 896190657 364396295 929623875 278614974 707653324 194595504 968110363 326300658 634995079 42397959 707816954 36255235 801238150 817873833 802715824 918687426 726173362 287422011 55884877 678166055 209764940 282000076 356233738 616247108 712289684 90965197 8381391 811031465 896197717 801849946 135624558 707764139 455610408 866221159 972016745 129430746 814029536 310156019 605741523 76208785 460086455 897902637 491272281 138909771 862812398 491480604 8130214 90628111 222032396 106086173 14822584 752405642 600307309 174169779 517703358 134806420 805931287 8587992 357508012 824552604 306658232 416344170 166855098 720352791 864152911 972992951 577263472 755228789 841859054 800840290 52936604 593616117 859238856 962362283 919475326 918089816 256081442 394174091 969730481 269635187 267513510 482986063 707383462 433737121 888912439 28325575 696256438 806252778 899117017 524351193 10817131 894304197 642760948 623668404 280296113 310450839 700326060 980863946 876639650 181756070 83423996 603402069 314326420 496884008 926221317 465131704 649641839 641625636 249351529 51290828 217149662 41528376 906010843 148670122 125026574 459530546 580875349 496911403 584092068 825598309 230935337 78687054 480831859 781223857 51059483 677234969 788065370 442321605 561307485 468000253 513790867 929741609 233483801 360324774 412618600 2035636 581517649 229978685 245540312 100773812 9375153 176639966 366952562 467353794 764821326 211784371 144411814 731305154 163975720 355931413 770993581 830083667 993734625 684021841 132485215 647181820 399171440 431432102 119190750 768892335 535699177 497697339 663926344 878499166 102510752 15257564 903419983 692374592 211361113 326321798 838830358 776309075 661191221 72909403 113925904 794234309 169732105 128423560 363050442 655825760 985542147 905562568 791542075 719021670 97229782 500787087 527948832 972139279 409713467 75366538 485872548 852778867 204937872 669939867 515925279 233121176 166258573 936492685 899400563 502371037 274967052 158631668 485090893 125335433 215467601 405469788 463523243 1104382 873807171 988121215 723456049 803652382 464611881 474205572 746477236 748887806 607596145 650179837 983193385 704637798 528313401 50352189 848702057 322947569 353775626 499453149 490320113 172974253 823971027 803052047 525001281 580867110 427997698 232148948 63005044 4996864 782338488 929522194 184335206 103560040 753071414 654621766 353549209 160122030 220562983 598488920 36463895 750698366 672511210 181284111 98523679 772527293 141256490 350384609 731667608 815861302 562969865 243851762 91798202 401292097 132343016 879934469 602742448 891523634 597353299 847805218 708591986 633250064 79057521 152938628 500058738 722955448 412229890 75131184 583763668 853316714 597381855 105265106 388580746 157417652 862485283 57390712 534622382 543744184 753703449 721019789 42628652 156276642 857347272 846549324 930970553 817804883 832178452 73755899 36106070 290026364 413205614 10052970 478483176 344070711 723324019 765671602 842253517 645261256 895755938 899492353 760336648 743186759 266299867 260904818 275701953 974052191 709675205 890080427 105578808 755230583 215820884 868623533 687161897 455969158 841743268 506307066 381301046 905216172 866554286 204035079 339898439 467123199 30643332 983589510 350897513 552912427 939223096 390360536 92383639 385991219 500898594 105723492 415881064 54139856 310019936 672004651 864659463 382263997 562585151 214833982 334682183 376675253 412719641 145511459 879062099 775684526 374875534 280545282 389775266 751539316 786010739 141956862 967836686 477949491 724994721 419362872 845905220 720265031 181773864 839169881 921023214 542203135 81111118 745190727 800064239 910674236 531052460 508676442 35958524 120251936 840376904 273208526 912675057 167095516 721342895 133554987 955974819 393766398 705431686 205212831 574481913 837805986 579428465 993834909 197113278 335213696 871405461 79461618 495285822 909166266 957701023 488870431 986238146 688012030 584707162 574763416 697484916 711886070 915658197 315591823 930680111 937747785 521542802 391131884 583909278 99812689 340576994 534912798 864658546 718166315 186356010 698091477 537086223 388590390 982418746 992889054 89961110 113794855 796195885 535970589 377816745 366677977 784537780 212793842 488923884 553475863 241841364 687085316 156797988 708832158 890724320 263489321 312268898 684666557 667628704 298492873 543009103 139591194 534397528 940696833 842970737 421005215 996591943 133342479 657522782 387809756 20837266 720345034 196389753 766682941 788963630 647594086 650685755 201632260 862575646 374611356 281938805 839205428 525604927 940253510 892586368 858536141 339871661 379812728 226895620 648129420 773207796 239194451 882230577 918257612 129409832 433532607 654341911 804894177 362396200 208214650 973155055 929212076 453297780 625910767 102390919 657696171 843214884 302636659 269686528 633557824 243829680 351683511 813119696 703141509 634505163 418940008 339614926 475546023 148276951 71145904 109612824 504178177 969647301 520192970 221914492 868817976 732423116 761142320 639321377 407046475 762202845 634634357 311648462 728728243 636203008 522638530 83007744 273809923 540676434 665420605 795071862 27788033 118511619 824384638 529098829 255144634 173609413 959488408 492317019 305653387 833566318 618353238 78891669 664876386 467084160 415178651 477715581 214112193 782837738 873526825 216091378 295654406 292888712 281665879 8112459 238825223 354969894 552328550 228537408 844752273 784074673 945040519 280185689 701985488 858071113 574909021 811498984 393467434 916300502 38299054 107842898 124961514 743531390 914716888 477237712 872092331 853680428 942117056 333595522 225821211 80521123 918521539 129860706 481545636 947602560 830950331 365758315 254975104 4092182 878284534 339373978 53943772 209163757 984584371 399023188 398625191 144267049 991310009 972827317 726887440 904476042 12053075 609599095 649399429 732386524 232755556 128705886 976782294 42682829 894126350 504347783 480073558 874355081 476533967 623825326 272506866 158202416 358176103 590077767 480478148 185310687 983121444 301926630 81252061 326195731 408905113 656907885 576589877 401653628 187854906 171315265 691422696 949795491 236660462 286747303 354240684 981670377 546403977 565131371 166225944 209380075 938792890 136134375 939708223 954131324 569206518 995626828 99668284 278377699 717413389 892812828 813941256 132766887 972368798 37729386 580164663 773885557 324320936 428772712 34139146 511276324 47883532 67716932 982261996 429341359 144623666 979212009 135669454 620267852 860395639 472966808 985007211 133715684 551800929 711407595 900254632 448890615 229634176 395195123 874932203 395698004 8000034 323538723 186133293 836014743 522545101 941359956 472963966 511947250 277403316 837778510 687000014 87999638 459203411 539784413 503939690 961725971 755239253 880868411 390440585 690907396 318857332 319724480 175748010 888192735 693714755 764559458 650384141 758277821 330606436 37308680 618362107 16232241 75402879 824628004 834683925 456995276 343300394 256120166 949166038 330099245 339743 219778062 191630097 266293674 862442038 688239850 139247530 940296309 443919238 151642586 350513647 739037622 387191984 899775930 987666385 797650041 6005271 111307785 429688566 383860353 861676001 243940404 833079168 877412631 759608786 942256511 652572080 645150123 592051465 153253413 367707698 665770305 55827687 853149325 946728687 175231065 7973048 453745718 356672678 133941838 750571750 894410891 661453031 896717863 812970637 516982729 92065387 765224182 322265453 991219023 611194309 598154993 744585680 272304269 844614741 482979986 142523423 200029482 676037108 972347350 75219115 6813932 482056549 42609778 41785726 746261202 678771966 760568103 940487545 46676295 448893479 57336919 146014915 666418005 182380539 461823208 199747308 936472506 918071573 461142854 216038380 41017801 765210932 249131694 372229094 292360323 95175078 624738322 652850963 456359113 240194151 412324640 465324763 542269622 496752595 198653851 865102183 317514861 307513410 4668639 584325545 369965981 287618570 892659436 777954009 103653071 782616771 140858304 876751720 396881474 754027732 535675039 758605746 650983453 132439196 7878341 458616585 163934689 324504993 799084805 450843294 791976479 446952404 994178990 752256880 898002036 99175140 598663581 446962146 55091565 256614659 277382271 544573613 981279871 285402085 201122527 826595008 682717512 487933542 269882982 346398759 623514065 922220595 663820254 473382106 806335256 343275561 92180233 189691125 234519388 868384336 469473235 7532783 954783664 631085140 785407164 458569638 126899746 978340618 20331243 317812134 711825834 326700083 444975187 476501164 124835357 676096137 985584902 236370691 334585287 528138890 788783033 850818320 49199959 370650762 414580668 779770735 234408196 266662632 500273161 402852605 437420562 414201219 960266291 724288092 535441400 540139742 662042896 786010488 176198503 194635670 161078590 560506327 629035353 830504577 966278880 215449715 130491140 166170325 664293192 393533781 855589302 576231560 797979861 930953029 745799274 956739872 693323871 45530371 373882187 723316970 261855758 23451243 769269316 806388790 523932264 777835158 561869555 421593090 200271176 172920714 76931537 325603866 435209331 10689448 2560390 36575277 510753944 120115708 960518118 564176483 685960027 938314961 684861504 56901692 756678355 467945006 874753270 517849720 215548770 789063210 960701244 629061608 707016092 360271433 654958963 923641458 72830320 982667335 216279091 218146438 467005965 736483418 502409890 213559 105907817 618235391 668037606 863312305 121337111 178468874 493374937 804665247 498844775 37387008 286631146 787061846 370912694 132359319 990915735 108850193 938393580 649839656 538681893 177124548 705795866 174414873 232899760 74646331 849313441 802796928 69895180 529830252 703577791 87399271 400602883 934952378 550890676 840797890 521182872 217930336 807885 544226060 187930533 478229210 777826796 701658421 370962764 568153056 150911589 887370842 329717308 83474775 137954093 279061764 484020371 64024511 255810646 634363259 911668974 382090798 189766416 785171094 187667029 591844579 27762647 29010834 422685726 473741569 951799577 34975631 485904156 915966179 439327467 37507253 604683346 974371230 322645464 155213895 75632516 193556365 901299050 972526055 48337606 19943610 646908269 878007414 458921580 977746231 238783590 676354617 166335923 202392230 244222686 639675993 551078985 571036947 372446995 348623976 93875276 599022723 844004632 510218115 923745345 864692396 305590821 467119835 561013164 399184487 811794894 855613064 149382804 300152851 384620005 563973496 653376678 988085024 960818333 654232835 516580778 960774647 990981363 533736091 955882682 373584336 193850401 396440343 846778270 604632169 390793977 497696965 194541 522134332 312437421 70536442 173254676 71944614 249496854 210767274 871593279 3761048 7450399 513289117 804333859 625800182 552065165 552453638 18532599 860979789 568340376 738779641 371712772 448505032 35810254 937953963 793820867 556012276 32305593 331911455 486427614 567932426 706083913 879496823 71220037 9028 179975543 942387319 899651786 861412224 405396246 551554427 774185286 422515973 206426644 724262402 658492978 105388615 262153763 118946346 9948117 555590866 146218361 214659601 297136616 556109641 791966998 877077231 379411791 498947390 676095931 506410620 579886359 881017744 994093295 579456482 934475622 29440029 668578786 310798553 676106345 570440723 764308167 380666732 513100868 957443106 105255360 946204676 764131685 352920368 989570213 114370104 168476242 136995275 304289362 572969045 140046291 70903931 671217278 967070484 969294344 828304766 763644924 56069277 606528178 177330087 400093456 118098170 969262841 574754182 468799380 856300594 840118030 349633683 774677665 529070138 676677116 665564515 277529061 75991724 382566907 644870562 608984505 706923966 557300922 21064831 615059105 224278612 178877669 655066501 114804188 345260012 97869636 244829148 167017229 800974443 124436732 369369923 615379555 589845128 956373339 156104210 371616631 27152276 221604711 420339740 936514412 83535026 982931721 155975433 643598288 398582259 288454544 606991003 771088524 752781996 973176983 781926604 549231105 815236110 837742182 413886440 497939834 119398447 312457558 160426243 455723254 475238904 876991037 398842122 114276760 448756607 104697021 155484037 684513250 16454062 495706679 610969452 798339889 750716806 556154483 883717314 142988522 81891443 507286815 439241655 900847247 543864886 46021000 388995664 622770662 684341812 169683729 811956890 672365752 396781597 716570781 796872080 738249568 731387828 477722902 461859639 784330838 574034700 771902692 275546778 38489219 982852875 562691686 6872650 280046362 890945848 471736746 250578310 78829325 527752243 558291942 607818125 386281693 576055970 583350948 493167841 797460644 902291849 641131163 190887558 738112021 545826653 799267597 858643860 223924144 40715823 340758788 667813533 354746231 900821217 932811937 360553024 280615962 937791980 354320278 856374769 403120352 588403772 835280751 113573150 467003476 603196495 66580363 872879606 956642707 729105830 846390810 990856525 923048603 413416404 953163940 693923988 316443199 746597314 437656196 366771941 682088593 77279789 431538701 920771654 48213918 143281328 291410297 805612274 193875425 648224353 238659547 114555224 5960503 724908445 809595085 604183595 383909083 792583409 484531758 573839753 657585840 449606981 194255464 373044935 40862387 375729616 441894785 910645193 226510806 162377830 554042433 672702873 848627056 858845942 184943563 149574857 382253766 818276502 394208416 712324054 800750869 393056865 611047203 876638632 91672908 191086546 122090587 944418542 507692951 490876054 432485043 141586096 663879902 937784988 129532826 826772290 548082090 236914254 664971971 270972182 365231825 327581812 952611137 597708113 37004368 386198587 992456096 10478750 196036765 275187625 246511855 827647009 560539496 941093444 730234268 5766187 339488139 933539662 491171615 950588249 917138433 319131931 707572627 776917670 532971373 151394328 106175582 202459242 347884371 530389789 688568333 591063191 59101405 809923570 581231877 803755757 699014043 920355 187327096 104964070 372804061 877491158 995514475 795119568 773529655 263348782 586056915 620196218 911715423 473795782 173938734 235761282 329374691 585384586 290716120 748983502 687791011 661188047 696753864 150052748 341708499 94489001 885616930 866109183 883381241 947168554 430843542 688974493 486884377 228655677 452941286 780883902 622196738 101036759 351934319 538242454 551197266 302849023 63710963 932512314 571565285 28559335 944742166 636060071 538960702 700483481 911482303 315455177 475798825 227291936 430444943 243716037 53473196 800032054 87344066 163592150 170163886 552020069 739554059 737509364 318176144 81820541 412964810 442044787 343396049 235364568 443633683 167326342 947618513 559195138 624775229 147098998 181415574 174076688 366300559 963454558 346856794 241976324 228022109 524665860 614680456 76460379 35709391 666257249 580903959 463880623 453276575 303785286 481266318 229960140 965555755 582922591 904732990 480742513 632573509 25709279 997146628 107911669 371488409 352978419 143572195 119058363 542344285 438902713 997454258 302643443 780394891 202502945 931561946 694797969 271920070 113595285 949397779 22708144 95114196 673447275 64043277 953990828 418553893 787508950 946236969 178769757 819883326 978271550 127570060 383190691 550563290 512288847 613471596 496599918 170558165 494734345 96588031 484204773 16176593 490630050 637944824 564571526 65055155 279270824 296501589 859791474 802130787 983782818 379409944 734124373 892509784 421627491 281723978 400809991 117306475 108469927 813613209 580988010 966085505 64613163 151504906 256250825 653675175 710351499 392727916 518953427 94184598 747895426 820720853 487069822 783409704 842325783 631044029 310818683 657691321 781340675 782010621 137476704 534451142 969701470 234069107 332301990 147917584 850888640 786016136 350712211 370983357 113535487 866450383 454235907 650759474 94523025 596663407 379092927 802812324 519605546 440694552 570628989 569784057 318236387 858056071 688981081 187369658 98455434 57952330 605912475 336202764 447564641 216556014 972814852 801886976 833873206 611917202 990363608 206010681 943476882 290183718 342472434 743935776 781695316 569930926 66336692 7602540 195596828 525594445 278720061 528144315 974509470 864147491 562424119 499114000 289722068 678925501 221156344 719509352 297074179 517494241 313908506 751650272 627613809 244340727 888995789 544503036 225335009 802368464 54297633 392335415 303476535 161681250 107048050 855578167 576953257 303503998 919721851 440616567 599461247 721588637 301685330 748049306 683091731 830824096 621972695 643710287 277786821 314713132 549050447 474571325 621003914 812752655 494584727 806059631 402307648 785462747 425304071 659538505 400655497 519061959 279865792 713492172 85736769 441816504 345928650 633147151 226863611 331531874 136010214 422502071 382898211 118010477 672860320 411293502 494736951 295983057 528738927 100545705 536742478 645552348 646484220 692575768 706891125 325769413 378333365 993478083 942190532 557079522 690458634 550582019 739316455 829468962 938402100 119887177 588012511 201721350 65044570 324144885 814140815 25749714 311422490 235253141 406404976 634708395 87022596 419821739 936579752 141789141 930281731 470068485 182503464 899976184 634793388 971387270 558628582 899906224 342437829 263534570 275180193 129815499 88013942 137195011 48646106 204552222 206826857 651462831 5799737 861508746 968669044 238224146 367014434 389406993 430706471 860873990 37927602 181187231 24727918 457646233 757453362 80431112 922996002 662255590 170797344 460258973 692991345 537760121 788129768 66938248 814051252 655889273 861271144 792456176 68976784 737853222 566793650 518326974 787514765 310219258 719954143 326325971 549296538 948980718 956144557 496260407 97773963 371562059 252143909 302723276 825505972 611826486 854368021 276012463 305246929 750777371 902811505 618664513 47441878 837171609 417465196 837120641 396387071 414376225 439800561 267438811 22599948 977960753 990473874 96904546 766787694 425931678 462416389 78751686 499215820 212381280 136753723 284658298 830149332 937564341 371570338 610516175 74971860 299885644 459677026 576183526 373866765 259630862 886130249 327861287 313598724 827701933 299398456 846132707 322662946 846110658 616172269 988401422 924823215 265517334 396625743 247019095 796205188 205447691 585844209 771379025 213955699 19807363 215702427 447566766 718880888 213081862 623260723 213761266 959416573 908176284 304914399 392443187 383801202 449872859 394657010 529373458 301415611 88424687 277769210 351336772 390818854 412996963 796323759 976926179 627711198 658563439 288416953 590267020 719381646 916006585 373564335 203315742 832249064 799099392 467965683 296409404 563657869 485540681 425590267 879815037 629946962 587911804 901129602 562195859 970210392 316817149 686192911 257421117 567052863 370987574 148423899 188530264 834036982 519511422 293496521 6950636 937725552 209770529 599290978 110734854 910194441 606821662 494056024 468786198 634136114 558612103 370883913 143204968 996757108 320441793 653143098 332358087 966453556 102350213 354627244 948297108 115492886 450724811 898842683 343133475 215982360 414579428 105866759 646757133 181840008 761844052 574501647 249967760 120536972 635684976 328332300 894958253 699339497 648926591 779629588 620530383 372563280 287834421 142280070 654550753 408748657 327099442 645031922 235755161 624995720 837857937 73139025 328248018 507769368 332009984 586730652 405400570 146957198 250667828 991107619 933419150 118819944 3667673 241699445 558372635 46096410 532845222 877096517 772203025 188284367 624337733 747467681 670659256 413477889 459606390 394954006 116674040 919438004 27574059 75583116 353651399 325147207 410652816 445211293 166620876 117172140 846936296 826281648 872988741 514122061 852779061 280387056 241264334 658799948 978142318 103701277 461633039 901539924 191302417 490493803 47290252 132313244 604813050 403076761 433934035 369578159 86977553 494839754 358687977 231406086 692782413 196240047 672700755 380444961 764672972 377029007 274116749 393962171 501211557 476478220 598636604 809486556 223090852 36109943 811855564 424342928 132351791 377926439 983772070 426115408 668294466 574718800 292689609 952038060 399758931 180230470 716309225 241636834 943766685 184810598 804013958 322541943 748538930 964093686 159831534 7858151 148675218 180826620 171555848 847576632 209236744 788605718 726181421 506824545 116173752 413709946 238427379 597490468 280191252 846078986 818859586 247335776 654388822 299377008 944933943 594955679 260484888 273268381 373905001 441036635 985347487 990766234 708773430 426674721 551760068 14336184 510084277 97985405 207435233 210334653 434084896 285840901 155387625 277330389 690733548 510211742 635017702 888745038 839960533 707146962 236208586 790905249 158312229 5304301 602889065 928113276 735991944 944550138 858690150 340329893 15550222 898097646 85299231 619669423 572756462 187320823 229374117 980296327 460070939 289564923 205712825 190479904 160265997 511394658 20055839 72447156 11019400 866137725 627252008 292270089 56650270 803431036 476377879 255795859 406098484 890720173 363374511 17116664 68141142 97062231 56864618 377391381 27891507 702267720 672329689 828517717 560326019 43920285 177927062 979401599 57143723 814724890 520518861 923003074 233452304 505278788 687103503 963612238 864193344 842640987 101221299 454317014 705651426 58782358 353383869 611880604 82419571 90074772 534681237 835378655 458635584 99974336 818678071 794408494 92606409 375633254 224490859 396248200 86700791 303308834 232426003 810603100 48727627 579351604 541962848 201508345 746756188 986707833 601810357 100140469 516797853 546931978 515840766 147618317 713650347 542655334 226755504 298448540 179217344 291942352 771558796 612039888 221424679 530638534 92194831 290714214 421459614 503398398 486754529 994822658 452777946 794331298 442270088 301814992 847255459 43687317 652689833 348949417 464057496 176472669 307785655 621795378 838809221 198395314 711866542 39211157 105279480 141075596 827318023 740769765 947299106 741889023 222949408 143204172 220188013 704744019 855340908 706204854 27859562 119961110 805478341 210824841 187153714 392433668 803494310 456564491 734592155 703371283 115631157 369430141 907317764 990346013 937213438 466863280 373898331 979374213 233213361 326268020 706543192 677333965 67549620 447380771 575155595 402602982 933874147 253778523 431129993 160311828 860104939 849486582 239663721 733607548 249602167 896079062 823163832 651296751 509804750 200887648 551343310 991923086 68235666 405451702 914012958 209620024 906759182 383957189 679808664 687134809 268343603 297401183 725280690 742831685 150272995 961758537 842374886 183332415 105804129 812010498 496045409 785145904 597044225 679305989 529754987 209288221 809770868 217529587 883509480 382789148 913754768 4016974 245784600 884519957 128781115 346237899 393383394 537468174 229165049 155242905 318382029 255394128 265691891 629686189 112881610 121527665 730620232 587297756 266638237 737032186 620094673 70628264 717768407 157496930 921634787 905001165 531908111 387586324 207540383 878705121 647140769 357953613 792641598 243933328 310662827 237996967 990024996 217971805 814665219 736449382 394402083 543414132 79586741 67705638 929774134 52670202 898069473 204550437 980711596 487398006