5000
1 1 2 3 4 8 10 20 5 40 9 56 12 116 90 44 242 579 588 1542 1334 2079 6596 8782 211 2119 16489 5466 17824 12314 69785 43065 32041 106627 128888 218 182925 170925 308949 340484 134337 681600 33955 773195 173380 579496 1702661 669862 944111 869572 476430 492906 1675173 989784 890068 1992860 459944 733516 4217295 1971031 455956 1259645 64074 805421 187041 1385587 1703592 537840 2600936 795128 2955181 848953 410971 2733160 119014 585113 96804 205162 385960 2862 331137 1155500 106700 1360928 2296310 364435 316261 522008 505890 1766168 924793 3896273 1405465 720311 139335 642303 651885 3462049 259284 3704449 2734205 201877 1836595 1951798 253802 3475338 215227 297571 390523 819217 569698 262648 665794 319724 2257075 864650 4757712 595054 715174 74848 25403 1681523 1697685 923298 2726027 3472681 134379 548025 4542461 610258 418851 1138505 826015 307764 1319170 1791664 825858 3854 1481946 878465 2866349 214415 231797 578978 1799805 1559208 192847 502133 1014384 157456 145632 1423912 1345793 1797853 970734 534442 303120 37493 643292 1575051 473170 40751 697011 1515196 256517 543398 949520 66532 582084 1559783 507878 706136 734638 1076810 250674 1119052 107245 3426884 1851006 255132 1366941 310028 1292991 2599050 1717856 730795 865488 35435 851502 724431 1410322 2073204 616514 208692 491909 3689811 2957951 2083325 381766 1354396 2571077 3582192 27440 3822917 1183553 3090238 56141 263196 553064 1854401 6655314 828613 3408047 765348 1853013 2618254 553274 1499892 17108 75791 411989 3925922 922819 3664559 599262 553616 978600 750429 1188341 2186341 848887 194594 363842 1809625 446864 525798 545707 1982752 858911 2428320 252992 2623120 95722 128130 4882 1322504 27806 1028654 564409 595078 414934 131687 149404 704168 1194017 1652982 943453 68679 6913 3890413 488834 775434 1861597 2148502 34542 3472936 471818 334323 2346740 2604032 1205467 322594 1033566 1899964 1960733 262398 7248024 77437 1764713 562008 189623 411201 1087745 517174 158493 161016 157483 22339 465019 127926 595241 256585 151668 346554 2483044 669619 317881 2455721 948043 1658320 1059732 1803424 295337 913676 2032832 127128 307869 4136874 797884 356295 1029750 3696173 164666 592591 268869 305042 2167526 2181488 2116431 16137 248649 907720 131162 1661994 1279347 2445717 145819 449033 112025 2043597 4047896 789895 494990 419741 312161 1223401 327005 2510339 35050 1562824 286762 1252114 809498 448217 1046656 276271 2193765 470124 3766159 1033148 432013 1252426 90208 1564150 1303937 698089 954082 166934 278534 365165 1543718 20339 239416 289410 668718 1104307 1868597 5156456 32085 880617 545916 630274 768596 1294238 2390711 247913 831274 215150 889075 46231 217769 802227 1199232 1179323 813241 2223118 436332 1529559 2503657 994243 1492477 800441 149719 126009 551371 1581296 6711 1539663 905916 421908 983481 1446063 1068720 494244 254542 429251 10710 4127180 77505 812353 2050646 761522 1036448 3527036 41461 518245 698517 2083020 1538311 584643 76463 103816 327540 4454080 974782 1090810 2135520 784827 4171623 500078 137903 449487 2104180 2263515 73417 804297 1865541 244823 448 4195089 538247 873485 1253851 577964 1895307 160512 338099 646320 195287 738782 2246425 292860 1034583 72134 887180 1957783 165693 837288 380917 2328328 5502892 2161956 2517996 1690736 72433 561117 558690 1036123 1217638 56343 1298635 25077 639772 433702 1879715 705523 529941 267232 501236 873141 3029752 736162 2484626 1664980 523281 78765 868715 110998 476263 2858918 794325 1916068 553182 547299 414538 259010 820553 4130458 2045345 35106 44915 770197 191478 1308128 1112256 2137199 604916 1221859 382197 1687047 532311 405006 2744476 603179 2068842 124726 1114439 2010582 1211084 725488 650330 2280727 842904 314384 511022 582792 250969 438325 1061128 271111 2302401 53956 402740 247867 841536 2372428 779149 2718891 364546 582149 126170 474518 175830 105238 568124 8354521 417062 2371246 690891 2049663 214343 1119632 21102 971565 2082471 341459 5874764 838905 330367 420763 445733 1320856 870003 3326234 3464326 960852 997152 352077 91805 2891310 33033 192206 1862613 1576196 217156 667216 274636 583330 3004322 371038 497465 132445 1564540 632035 2343428 448660 132342 357465 1414712 703552 287330 305118 478230 1514288 808126 163723 1364597 1927654 365778 4573641 1394563 441313 1495553 164900 968587 378939 137020 6601748 1314331 2208150 631076 1232341 66313 820270 2402312 468570 827310 1192334 1284596 982820 3503432 5373 1474328 301557 99237 432684 762581 386163 1244233 1071423 4446592 456077 177741 417798 494748 397542 276167 909386 337177 1440912 1201195 933195 134297 394812 695648 1331863 522954 86697 1242129 215763 569158 852626 480966 2280065 388928 1627604 994334 974403 1002576 73710 1200286 3255730 283936 347054 403965 390224 571289 786592 996665 366254 1297148 1356441 1023190 3237185 107227 1011443 345460 458814 493969 661021 59512 423633 148745 39163 320893 1453437 764813 383356 2433364 779351 3958676 2927567 1855216 617352 1777507 61153 2827897 687751 212811 1234564 99046 8530902 3500 1745666 236669 812207 990371 2094555 381598 1169184 1126750 829371 119094 154542 131530 241099 1678223 213215 260786 2369502 417540 203103 3492909 650857 1642314 484898 1633186 2292317 1908867 26544 443931 1194339 883401 2171576 1915261 1372678 121413 2930519 79630 333612 3979387 356240 228204 694433 620700 47300 1412909 325427 702146 55620 175892 2348782 1971563 1294079 1590585 2094062 103375 426007 596916 183855 248084 131664 1129599 926965 338734 1326335 9791 1781097 181146 454285 1423709 13642 975573 1870426 4778586 123790 61684 321478 994408 1157688 195088 881423 1695422 891208 815759 1505763 1443447 203104 167243 779296 1222025 887158 412796 150986 171294 4969037 263729 596770 97891 2110721 37043 52949 1951459 2474269 310743 218452 709133 382199 1293134 185894 611608 950416 304866 1442252 1486073 237601 561720 195773 627828 174872 227958 268021 151098 436228 46170 1315781 760449 456641 403424 1919300 1709123 1842948 125043 69225 590498 175554 828792 32012 2234309 1276134 388607 238504 307376 1376928 61377 1347744 3325460 614818 318256 585192 245954 706515 714443 1166641 658605 547700 1926702 78786 1459867 300470 751251 916444 1627990 1892505 41151 1429774 1197607 1510556 716386 171978 713768 475629 125722 85459 137582 47340 1839870 466355 1362439 230318 333810 503026 2172473 68542 77937 2097533 1850539 471633 323161 1864811 429422 148954 768375 700622 560845 1583048 582202 503111 270282 268827 1109316 20559 14650 39160 692082 33790 2372042 5499 1604196 801281 1302150 113829 284504 2208651 114907 1985483 241832 397025 193931 37551 3540594 1790742 59342 120760 1130874 824747 237729 130944 1278760 422275 202880 2991981 3726057 1226069 878266 419089 394283 49344 2359423 2054734 1379030 543796 1157301 336973 401393 1275973 976257 418285 1818755 2487918 1915702 1470302 334152 1041384 2396750 2070677 60899 234792 309828 18889 1042988 735734 161473 365234 1252438 234940 2259226 803403 875981 236553 2271000 703287 654431 774972 478951 240772 41812 2737910 1260218 941030 1853200 820763 637955 182083 2006721 1096982 1720391 439205 363584 34095 1075251 664856 4763433 385565 200512 765455 1540316 847918 1017772 222265 844346627 53940674 664894793 562983274 795660914 67540130 348215963 771963237 819156445 563339152 481640430 258013120 959835283 81901129 64978220 402784116 801255755 94621114 460690411 904408119 152567231 894255258 67986712 535243083 228862775 751476218 938523851 881373460 870169911 337426574 866130833 500995089 794151827 438102373 524295073 27622587 241242978 56560398 271310014 323416950 797470203 759256071 406729083 335335554 552020747 442407378 373684765 443705270 359039196 345913354 271457817 484042674 402739547 17268700 247808614 926729983 289060107 570365027 571546394 791885782 13231862 101296569 51978575 867384301 594750360 190216794 915889497 621128370 361887368 657170513 765857342 743547837 243330234 921328871 916429822 952474087 237127165 185913617 271900430 106438127 431930298 964404305 4655216 589701865 945153569 447190204 735837171 627017080 458843958 724308320 914323975 72126506 204754134 808863323 608018222 3513956 682071487 805071053 645209723 478687645 13448223 210923536 488548577 983951884 345973621 809241318 491742909 993691585 348700743 566459640 584055770 427015837 934412439 912945995 808095723 386057904 343463079 727285375 885000250 914768451 481788038 115053111 284317126 789237006 777875391 73243842 339745569 654960053 788847046 115624509 121910061 653885199 325405564 490282606 217125196 477923674 896656450 765453519 477858685 58160032 783275338 139253802 819735994 530685691 329565060 421501402 51587551 816562745 626290307 565071058 740489450 404945973 298746336 629740166 428959668 460973963 7857446 747976209 329836173 219666408 687597762 138373251 250306049 665241907 210397221 222564371 719620120 350117802 623005155 145788193 387239050 265607352 972752639 756970505 324819619 203675401 834235281 799482477 816366297 872593845 629220797 585632232 17383305 263638962 891637018 196362662 193044199 626657958 86466425 207039469 740441573 994717796 731210048 112745867 548764032 173141158 727861727 386413780 510615097 206139723 218447148 716446910 725475593 525252150 892617180 568789633 447800609 730271609 579277679 807117015 935307726 69402389 215528611 987370514 132669634 366822731 1392800 237608084 49037608 226381633 639224609 230454253 126922762 134527709 84292209 937908557 360978365 371067133 586067936 664048767 184112345 763177266 43258984 797427111 551278733 38951373 666346666 942371313 870447486 778911225 545496826 466396387 97864110 872850146 520921098 129349469 417671919 303720729 824657720 959417629 1560607 403940918 911397897 33657741 579695797 433304214 120605859 696940376 5797842 571486407 434222135 92813867 373912242 290164479 600542599 501317114 299956047 634385085 646090372 580187369 532628462 529983151 497062406 871685921 594609222 381296387 290203285 158470754 868534651 194259507 65475876 296753154 811055138 667890498 568902218 512818152 476146221 509583587 960566602 26751955 419309026 414180795 431428266 838445935 777549284 493245532 776485713 969732787 776120738 456167323 348039466 452296899 219232066 829072887 564371910 745305198 742831007 742763682 869374682 619582184 981798141 596248418 81252605 108268852 753547283 672835361 613516156 768452958 28562773 961956770 654288391 170078446 138367796 422038851 855313188 961815281 370074520 892568508 1544191 34510304 616864107 796552385 807257482 877874925 795729969 126570728 528854879 566154916 885937616 967722372 145098437 34543770 422932244 228205329 640402464 255051891 55085309 832323240 531619278 305651916 240291143 992108859 609126436 382271577 678171654 692437748 943387963 462155011 126302029 166394341 55846389 797813020 213721356 442535141 167442302 378089541 710154141 360690862 972889208 858685270 293701657 845576190 741675022 503558694 866691084 740331947 117858514 926000404 20023581 269030222 500383429 135796744 961064999 556591797 382907927 428711165 336013376 224364074 777789132 988065062 219035017 315293039 955120963 499154373 114544796 337928746 677920262 944391205 376885819 628555750 173034387 820466586 191644876 290748504 673892611 827703669 272826205 375092872 377745886 340888783 206813001 132831579 380802040 259189583 295344668 191084099 130868459 58800628 375437053 269423533 44354326 41998562 844702860 572511616 868259676 754859031 164454313 924496364 8492832 251251270 515293303 848762868 173888644 99126074 351886997 20348991 584765717 416656331 622906104 755986532 201444708 62003639 287728305 407725314 447609285 408296864 774920615 350247535 618289099 158054755 43958041 700791358 828918362 260340411 44134557 25392722 908324129 842103326 324660637 757092638 22134425 634132014 270435252 284908406 660305649 337266355 522709415 817403132 982453126 556672393 446522731 656506115 11075286 739764924 935449922 476368717 726649932 137021037 206691816 516801130 200978888 135140735 295181345 375212584 400031695 131890408 466307730 571793465 960775586 934973039 22703256 539786933 960434991 702665387 144056279 686917099 625338901 257368961 78432056 837835052 701980462 187118646 360929326 72957234 148000544 162447947 635830186 83810953 951307875 846155404 364684081 845235756 995613251 817919940 249637232 416081873 84504850 79800577 257958894 458616925 602355717 912520715 588631839 792884614 215060575 723766948 811714716 354603366 369770641 886466933 581200131 363067564 542741363 960221810 228401868 712354617 607886562 447083301 949453763 533605611 264085009 476968057 177765600 674536613 424246641 539291163 822511729 140479505 962047904 693579126 38548670 535899978 370580421 986766349 28696516 169919264 120960647 394612808 564157133 502467886 752597129 920734572 781958793 651709299 224504824 325748869 765765536 259712659 534101902 820855701 951701231 478880877 491460017 189349720 505044659 958295915 636440322 789747341 698406803 845650954 84245978 806645568 778751803 156516387 97304380 550791897 554781491 178804069 758994865 500888887 610561545 616303558 167743612 689638262 795920780 643445962 457503584 329021580 228772184 772745723 98926572 449267843 26428127 872338347 220010995 210085180 364912442 653836530 419370286 359018125 182844653 558746088 615496719 900229476 434108707 118663007 785133459 553589603 921305320 472229574 707362462 177861666 896547507 570799769 752092221 713026016 417252492 544064682 59509191 35126548 372764316 781007949 822910518 447838489 624987316 201833676 167449003 884205827 438257622 73207694 79047821 360584783 756635398 917530835 672241592 357495833 601606542 816316428 314804778 491299186 780810577 506603428 633569571 188648257 786163625 409957645 866069625 244436525 475103993 462599239 399207088 821820295 381799128 808707091 600169277 499175620 858241549 132788987 457928881 360983933 133835390 992428353 934119346 196023279 825316998 679008921 216365523 622321195 560070479 305667748 127448308 341684038 385981930 42191122 112903629 193236101 735045719 69974964 486810127 668822294 746153176 225239552 616648942 731068320 147257821 804088225 591400776 97675562 49422226 658674597 570033198 779788292 85688981 116199458 209534062 441438410 434956765 652044031 793249372 267397441 458758353 671546083 451082151 203215189 258316970 430071025 982187100 209677987 450524763 899482977 163544457 44091587 337374837 493211195 520867768 244447980 715962631 639489348 18467144 92361347 214189907 757987893 915382445 559431795 424706949 74958129 501355573 701259640 179970286 316298390 444588335 265663088 270141660 79931106 893290471 806605081 75895593 675067920 142259262 348754944 295415110 371869762 15073185 26695116 201661649 180759012 446056471 8755558 663265840 621112975 466626951 673993605 55893072 63219932 424141753 727960717 69081958 702457299 125353101 974186972 506118443 26185926 934653398 250583007 847526174 336094104 29703675 296453097 805273447 265369107 895853177 245287491 917662107 322519132 164079455 580315597 16572080 315372086 385151293 753985995 596412060 156545734 25753702 602614318 425529309 383687939 176175198 149438585 525334608 271016760 781942676 963440943 275811401 408216446 929413918 26598322 473053188 760960011 767096179 400096436 857013492 534740248 864631991 183099788 498469762 103053850 2887750 600612239 414537246 675488047 924033335 511982651 888208705 691113830 476849097 877708926 564393736 481958581 200240117 372100298 791108677 865229171 712472090 304675752 678994464 916043971 952184848 13856885 689253691 226394898 784012686 436565791 702713985 659271551 274256251 496148629 300133715 732612494 12735578 77373761 86265652 283589307 995297924 983520741 165127085 677003583 722121270 515067421 174052908 578531296 738971427 690976207 893623620 624861771 52185653 837184012 134534937 841068724 543703439 386956121 392903848 208596388 713511973 271851777 173653871 578719808 323114837 591359241 890842993 717610169 476279262 935690984 295770108 48039050 43912414 66784138 373927230 506611020 976922198 367887890 251996152 315170465 75075293 271625578 981573300 117657019 421533297 34478514 9804510 265478184 996194626 398579260 15961063 361133053 653002006 357036238 574889019 943980312 630231915 466657138 813910162 173140848 524728024 566407176 997156866 352608374 494126326 965610404 5086863 833612033 802056965 384045961 132641202 842469772 910409408 197968659 986609790 620949291 533437779 987823517 202618916 148515376 926029818 525359837 244466228 73851938 570250029 893970676 973041817 933681452 173273105 643219058 880312997 14932837 39653003 244958468 545165662 401976581 295329962 441688481 581561041 383589611 354836916 553520059 627764430 955007982 588701013 337811855 718513917 821293255 784150817 96881483 21138029 868553533 601909554 84301637 432606701 293343820 333564376 987246694 994315671 540027401 259395743 952987654 478662159 480238960 403868421 467035711 908749373 364168897 855819656 921542503 325836868 763454715 93232816 640653366 611296904 325696086 805165163 929966022 807535029 73708845 938594978 929674289 757764043 492591181 656426945 122745719 132385599 489885917 405519727 709006054 214974903 86688746 963539778 979899049 680509788 844625565 580266858 994663476 911999252 619663156 864799124 481424914 135168250 724426319 238517016 649763066 448427326 757516994 359244649 95513293 39918391 770462107 670840350 815185497 297306863 493481528 735807065 323518844 184406501 50073563 318521903 317351342 988938212 906275119 336130786 679428432 389216184 834472378 837004403 611907657 888602185 958318101 718763630 994891167 30684841 421471536 636499253 680181312 85423400 113744935 962799590 59233899 841639118 778253680 451907880 799018900 919862478 155481774 568788618 663367713 619709378 141044111 474011425 494241838 598301757 763636155 950854974 881348817 783336188 427431479 197278729 14296831 914335286 294328045 618477941 148796143 57927642 519671485 829431167 149775686 765700706 71021221 914313611 636498011 696735632 523491856 464908229 13278909 209626186 540096193 63294797 108282511 489079960 697446040 671926578 36901733 741808244 836319988 791867920 50834064 909518465 597512760 981565555 116129995 840048339 703697343 172197913 251769475 838766214 767889303 544771550 446469933 449110728 365877662 982234948 522317244 21895372 631516546 819427713 936645002 892108614 814182494 772345074 923786545 566296535 546227902 981677561 299685885 548586211 943623476 178353219 47254601 149086275 222433351 855604452 724051589 266566312 348693284 608817172 966180145 995395934 373915495 870458432 403963596 665485516 480098051 795857177 966614183 122054170 307585765 687240517 646099672 747965021 586378344 759488858 620384553 111911018 330805941 449460329 11536484 437402843 204492096 102387642 559589561 752977660 803783694 250190859 653318693 814995481 883883248 694785967 23793109 459081323 223543612 138685061 181151625 369450872 674117383 745742160 529180189 46015823 20278422 126126844 721211400 749080661 565304237 724281729 236257304 178499055 713948994 159674898 957824938 11186683 285666455 85419402 967053391 891518764 904214040 618791553 329345519 768305043 961140865 105238468 628743436 503366381 777062574 147285076 122525048 756370752 670496347 924196065 249964041 2960792 16368805 406382527 646656796 305110044 46482517 382078337 21672531 406548317 122153006 843012004 67046046 768511668 192395593 457791038 618564838 838900533 654776849 272047503 687828426 315443268 620027002 691442229 512693473 203555785 274328580 892228230 248407088 889893249 872916598 938230514 752725512 817028088 399462822 9187842 714153120 605620121 931953880 690935430 520190324 737764478 801026855 198276795 271157109 160394223 399171484 417330204 243935131 466616622 145514500 933155211 504942981 555628918 184700445 80885400 817151205 460249599 758283858 433642673 61125654 637665831 662420764 600506585 863428360 419129544 402245816 66053592 860289414 834702395 87405009 977643997 805702092 805992544 61544610 303313814 18021917 937473356 625783467 482142424 880578199 28464015 167179770 902602760 580526181 86575010 943691859 655423373 486216002 431455340 370676280 109942398 787339544 57603034 340186191 464440487 343833066 438177003 204501068 424686502 992168242 680387074 442528426 184698210 293468298 247290158 412243117 492544273 143214822 149719541 105039946 849602821 159251011 140571270 740322683 302664266 350102244 550454853 30175341 493133522 215717943 593243105 499134051 613248956 286656836 626551164 537179588 787788370 446973626 375645721 738380173 656840617 689390156 240260762 559858530 511428774 356523510 627242839 799453225 693503752 893723480 246981261 238623363 604765412 369743325 423956088 772401668 407743116 845921375 598966950 617506016 206745651 925304662 176329735 974823217 132221745 386243502 499103419 205908590 717003637 421378392 413231840 928512036 175513209 119330392 760025529 40484838 861647322 97853352 484101032 53745665 870170548 207423499 706655134 9680559 110263 445353266 554147977 789077340 49200245 734676469 179908495 573126208 653693055 765851785 381352714 634621230 724700047 218488476 666784247 805714375 566655434 436137757 279918105 773482961 698103109 287788281 855538504 222263654 566208309 171394130 247060840 86292663 364669744 440751926 455516590 60394757 338600285 943267879 465795807 214649998 185492104 269887362 468281868 699883153 574730428 367337656 710953154 77388528 599971015 546998163 995562523 378814962 192720585 554441499 583256193 745477296 642139394 735041110 502020463 372866679 551697846 32273444 934890839 123090602 745312959 875082775 143284869 446581373 298253528 106621302 977478915 138876390 815568242 792999675 340083923 356676329 683606232 15481735 78483245 335597356 770536258 914033471 896004011 124497946 628186963 932341154 36648695 601405545 121819864 307554216 322962359 925113439 6963535 54462298 830361572 25282997 527000382 410220390 900065605 615862505 569740658 841335760 125765388 57075468 377050715 181073461 755871055 653774866 648321024 523684882 11763596 868044287 23241609 344011219 323626791 127289781 237398798 617662178 862990880 128333509 787515990 117403844 497074875 825331891 907490125 104775950 965004206 450251807 987442786 399956022 148741708 862858049 278110768 742916840 387051863 546354743 263203759 79155183 879325748 312426440 78360306 495419209 337783735 309664735 357346011 903824351 520147728 890325646 833190351 635280272 903467223 608334601 243758602 794979930 370179366 381154624 518328602 950523599 264320021 146408476 520217659 863157278 17529701 384617674 719326061 615485538 307716480 742142616 783470931 489723370 999993521 497760331 805765128 396006478 242751836 712481556 39315630 903991951 508403178 862316322 60823168 614866893 996585219 477777751 945774220 681416859 303518415 846920245 743454264 4820696 188933085 579609838 401695623 691927875 752127927 996996521 87056657 941332420 410600845 476457287 116821015 256281095 543196552 903779100 111329626 964342206 606401792 143178313 17145627 465529418 434572948 621674033 245649815 299694710 754508127 341241102 875850053 230403739 410493502 585326205 714520128 416593833 7016349 690122662 202355531 839677104 442793907 828421458 970138651 978812619 693691229 328098646 116382292 739605294 738623817 984084150 141292122 240187867 178663106 898600090 56372658 746281653 897790385 192072215 787193937 322182212 390566378 292162525 477965794 599802982 641128453 266511343 953304206 143633651 687473135 755527548 210453355 575937110 186667842 574311787 615915092 965302832 970179929 213245640 331894022 135576672 329204079 187917601 769972727 876422024 597903333 705671515 901749404 144476750 53314549 214429985 326751169 908822266 93668583 739340587 163775513 760284747 733975373 951959317 658548572 339914420 961287569 574999085 201744183 657558594 243233556 898601571 968430836 848115750 553332018 569103176 39199135 824688898 332841789 450225726 830082008 530895671 903425032 808055495 395701497 311274842 518721599 821137879 682785771 465938741 652209146 719668773 788788507 507362505 884487149 646793589 986523757 881378534 819560106 860832951 841268993 120264039 830990743 897264664 332054522 174472952 695627109 424665965 600918769 562511893 360745735 776051614 595061545 464621285 334484378 455126728 318619569 328588907 376493105 927359638 289516769 921315826 479656 11815123 533546298 82803572 551265209 842582497 98149769 775850515 788951539 920754589 798974038 185203827 592484209 572013542 770507894 128258650 165319761 176011956 711982000 694442255 931148159 793772727 439911299 370329393 646723713 437767023 741655759 892030479 714096400 854230122 581096245 173907269 218186855 198417249 253179104 847042448 764247142 148298869 11867750 918910582 133577555 126854338 771534795 915597062 407999516 920359469 871271979 862809787 719888018 456761398 132219373 816425855 283555428 894739553 690469348 427032114 841071685 983199796 283675225 441937683 63829885 119561159 224089687 221146758 248222710 293372141 945321727 231066840 259517156 898071872 434480855 890511389 107355966 930738719 940028573 345239802 981459546 593400582 152024127 782196888 675202868 803227682 995054922 463663055 543268183 897993245 589501856 53495327 578157248 819446231 622472876 721933798 188591226 950215916 908210094 387749336 856299570 681198937 884426862 112169453 564154423 671903373 821568786 279405999 636037442 266551073 372642672 752190926 425390340 230564299 742010637 187166718 503768929 28317523 894435778 236368927 185554932 2124848 182502327 649334330 524325946 976928551 169246784 246366368 591153092 269719545 159826349 103666480 379713592 295144567 93494285 593767523 691853478 205481871 341212502 42699558 171934118 172557866 858568389 417531473 492629289 142004197 147897381 278664622 256220869 618749070 99118439 500630847 792248659 341950236 986062660 836194723 362026984 420673567 590649060 937199204 697116483 844997509 464444537 993129128 12522330 382621703 129319169 647925156 235258308 726240291 122494049 419903861 223728507 236011682 663027256 228771326 561522289 1575078 995947434 947848400 255250154 84153755 136838598 259224088 660365612 271229438 935219099 795082228 352885786 261413920 279840715 423487455 356583499 533221256 12299790 652018342 762372309 87963407 270592826 717084437 972768079 630927412 278752026 83319146 406227412 266561598 997410387 317440946 9809551 272025506 457448937 326879991 994956314 386162860 4946781 10980185 380246006 501783283 204193705 276287577 132171987 126264541 321930744 129155461 708579167 633107550 145168584 54303318 561825456 495400406 890736885 151200052 971596417 994271660 938104673 365977154 818541523 519912941 252816398 403148489 293819490 50943629 38519449 477221985 167164750 787832813 833621981 8248188 95789186 245973973 131950661 174533694 29470749 178188626 673737985 697520642 417479935 875725017 262114459 854008641 557289302 465292645 88674932 801022347 225930252 271149252 982428617 674535209 172350509 148827368 748741448 628525345 514674124 138439790 151372959 989272978 330867573 412376433 707505117 197589418 225533725 792693692 166821951 270759994 26097771 784519330 805189521 167302729 314014954 670380617 428927964 407726526 29314805 673241946 701519372 190147466 585461200 43609216 112042210 904206680 688464838 806841608 101983916 271936969 340650176 257496864 434074818 483496018 225022767 536149493 420349059 971628718 454826335 210072723 553985552 689302416 550575106 379593210 793998208 246171926 654936335 174669584 611033318 382657886 73725089 627994378 282021079 347844531 35140999 713084369 201751718 572093109 675348995 360069662 312598691 62369241 904340513 79610458 446313089 637589209 127588622 263119097 937373509 962720558 929800247 547022957 141100057 750198354 96179912 581042036 663490766 629889608 772848386 853827334 730381575 690101946 354595454 802262512 696255223 448701049 378856975 500952162 894432635 114489409 340717911 493261055 523928220 418807333 621334004 386909294 122939323 293789055 380246431 182777278 86825325 839796849 801228910 87074765 543766903 615142090 813023685 326991202 952836468 83105436 964457210 739757372 970218518 840425927 231787376 921442771 520805939 953592733 79224997 266283008 144407067 733752314 444821802 606359579 71373919 825068421 360219080 94277809 372022132 272150992 20918961 965382432 84218680 512290332 122032085 793167083 685684547 748945059 708982231 831785090 393594474 352109424 992988189 467867500 682436352 931062613 667718682 672842137 425264954 149847650 254422360 590083297 569021840 151155059 737746619 862886903 13717222 2719915 920673999 137768539 688419896 674329981 978918696 922803096 433358557 720565776 864996736 46847549 556302642 660764989 393286895 565945905 460291217 38695621 637862213 998555414 763011370 438593929 916928254 878099039 682900055 447614570 860106773 705138947 427657630 598844652 335081980 519756448 543500472 831254079 3784817 8659980 124683826 405579033 682078952 272944506 124765841 155048908 816673718 128256708 826035330 608198237 217883986 540127773 169401830 695054297 932620815 237085749 872920946 469858679 661770981 840694153 864829571 214161534 448363544 642086889 485793291 553663594 491746160 457393024 880117464 974626346 867884901 7019621 964060130 459142179 302355449 434160193 18256126 840962578 822479369 269097472 908972366 361175226 544889037 969761448 962291392 936055746 798322424 616683200 775706423 116385001 330119660 292510960 560841328 956875483 660830506 982711454 211771546 805736469 847457776 792549134 832750290 30432105 150497172 371912885 542102729 277993991 501657568 679241274 363316646 31028480 182235657 856543605 790689682 296988907 770056470 224771235 342580080 318257858 878592020 557289389 153972877 351134793 429888107 619818413 889197249 157791925 440686245 548097143 465864127 759943194 607918416 254791869 658453300 674349184 769539070 390663338 744758506 814977812 579933134 953520154 766999352 877832481 480929297 7648021 297547246 672826467 518367538 740630916 12579161 567785840 158622371 230705205 249836565 417233716 65481215 143788082 152893407 668108897 872019041 797044550 535652249 668355618 149890588 391694632 777793026 710240107 991904347 338142598 641021585 588503846 314303973 646184162 720693202 453695900 763260447 969576708 857725371 100030584 328168881 434512013 216890621 220565978 489124065 404530357 125968425 132242767 652978018 673970453 232839922 717821334 329915033 652694228 572427826 638822201 553847894 76977547 787429040 188021937 438305472 695009058 298801880 40306507 15034337 146069203 48116158 205945587 621014125 920741151 395249507 133465300 302694417 158406585 389957864 396303215 400984380 140362499 588429071 615813607 890961329 710714460 34719318 309887251 620521573 585367121 982112388 413600584 546062011 596247889 506368662 77081389 677765634 416471259 800677114 740349012 435238120 461294820 308287819 163031170 257237307 543346671 718163676 68622620 289185994 361986476 19629503 874578895 593794501 317291614 948152097 985439977 652894361 596083251 161929750 135900832 812899705 2240841 495954984 560118905 68298316 421635495 717000416 722504768 952662595 442028867 605473676 537098361 844806129 717992556 518763198 129539275 532533136 294635680 126148122 106072103 662016844 189205232 865518423 189789315 656816085 608455900 251684449 945018435 935345347 329082353 41009399 445698114 505497841 789277878 440322573 303573160 952431636 333086493 778198250 915901363 542251906 365921562 819922634 417000867 484989835 122755072 625219947 297424017 355890278 256037299 992126699 81477597 124369439 951733292 808912341 143874019 210605567 499451163 646076273 286608016 867137932 519229968 62000635 576166756 206407790 8227567 413406572 945304291 682683759 93350429 36590047 809967116 621252284 301855932 480370356 521746472 104847626 658217390 734725532 129719235 895244782 202548511 575181765 757891156 149577211 261147535 148046997 87358997 18112410 20139735 295629851 757451897 67829128 940930598 505658308 178418883 695113393 329936154 491286187 248660411 655053313 440969834 326501336 304172241 292979763 983117490 504059561 777914574 318212050 48298596 407387920 913913963 90957023 960703672 708214075 968072163 125659348 247040248 328950288 796051580 755378094 671780058 768167763 896217621 346827838 150684104 373285925 514410152 770551922 333777203 708958018 45177293 944745338 996673539 135990162 830814385 910402830 311524794 502012644 652642448 479015078 237548371 727208149 316539112 536660148 574895702 748315372 475236606 686899499 151851666 757332066 171368138 34166416 746110498 457035807 519776576 498653188 347278470 88311553 579966221 482002466 321127309 974458546 743987445 499415835 374333298 973313978 983779710 42335646 89831961 190441991 954907511 523425038 820238301 680326576 966007393 653634712 672387601 660858668 283031927 602881463 975892612 726662262 311412911 555848108 208482590 826210297 576954555 41871597 245506104 256598299 144504938 524488997 243473011 66883360 473948764 650881555 87911310 810404576 8306710 965858942 153902990 965673930 727237231 778213435 399465364 276821282 23498306 523816274 883337010 669121515 128526514 148286181 544768872 454281529 351100874 845950629 23436656 842807958 593114603 699814771 212080954 335634450 833446253 745564162 941828000 67063184 16056758 283837629 215370971 448438322 732994953 894999777 815315704 845781841 548716256 323654170 845960809 955398093 549366136 153371016 51619898 988999257 426347998 950513409 384519437 452883352 960106136 887903837 752342025 82585362 658689385 48945347 470238823 480967632 283828213 494532467 30387592 577871697 385378695 489108585 571259691 902821824 13305735 836385200 544071082 897860729 703779376 473901601 152004133 182823468 876921449 689078878 310705024 636634707 433178054 924227854 685807943 936100483 251870142 297125263 297927220 369928592 147396667 272146894 295159730 878341352 902275108 525072495 580836530 84880162 415049631 25827794 807354824 914885606 919991815 985675084 744683061 161680175 521279390 592637279 838162093 664873550 864354070 345223332 475703292 774890232 718442638 411460730 114829290 671910012 148041635 519088061 778413919 267507381 735577330 72539860 256167843 672338915 64224193 557569604 742783609 115848473 362405038 687899472 772213680 396807925 861772858 488350718 596525632 291426389 419264371 644178810 413521916 590115899 5280179 453686968 827191373 753384435 819811710 126832151 274632326 715750252 203616696 384494485 183348590 696199436 574406035 284377489 422748769 185038556 408763719 96355804 368086628 512822904 610440874 238476691 213982633 597036998 146975209 383500368 389401182 810306695 308813918 705572999 573587490 136953606 678869749 650344174 539300339 473284503 364109904 59565663 626590198 846373379 508101484 927529124 519516241 201082888 549469804 79728843 490378322 592928870 611069149 736000582 946760047 259947632 820833824 300476607 791587740 349032027 861837809 185108549 716665863 562833448 85715268 636433039 539625058 8396410 883573495 702359779 744600188 92420515 28149512 825118217 2217517 992491543 462644419 904386808 714176952 893946523 258880772 202136495 422253537 394045350 224567173 924809566 899269625 363406356 276627434 300220884 773945317 321140267 689341202 487341190 941971753 952537309 285855865 554056447 85221867 920790680 368131736 757619167 18096924 421170119 821037970 504744827 177214992 486351908 356108197 189672187 576531960 432074793 118097143 534447120 996880069 109069586 749948082 120389932 898286548 607000149 518591875 553133823 758061990 257866004 463156652 507049713 137327414 416243874 323713741 482136598 693274082 600171992 224444951 799923897 492643837 837245325 378974719 698308069 700986419 829083197 632341788 549642454 699681485 514182342 556588371 313102083 460472975 339878048 825380569 502234091 519865701 120288476 110320009 318124001 831096577 671688281 512676694 410360158 311833768 10416843 211134795 930315089 22575750 385201337 420092762 375514019 723011363 413725966 201392228 400342885 943896086 849871619 695847032 973169711 413046909 534418669 905849578 934469917 408565373 958646264 987477524 205922877 849291255 342413517 210471508 643265783 171413143 904728886 851422981 849858111 385499596 205227986 891680538 844498800 757555258 163432542 824596187 515083344 301173458 203753218 567481774 913918441 45570608 77575545 183332873 402333348 1556585 826677442 489102316 527594500 151078053 581159552 160334473 397205053 90567345 13516101 147067770 887413671 681465871 426046356 738703104 146873266 252009671 206445901 33621307 791636465 112952314 852695835 927573172 456984804 816374469 19671806 840843804 191505618 752909000 62524050 195554952 137619208 364384213 535139956 69544713 363262958 21424600 194728937 275647732 673913105 972718173 888753974 463315443 543122783 597855381 76365415 982308635 468969809 77756871 584703690 643980681 147313251 497343898 293073325 872990239 106172627 319738078 233222728 146941231 540069495 156794192 110793028 17915846 295488965 285729860 963883463 936277454 39350603 16895663 481330869 350518193 882757745 509754709 990914892 867390656 166655178 547177133 561361585 922029461 374142243 72584724 852933444 736213248 113802241 834213501 542934676 842305487 99648893 549927694 24811102 457730177 664716194 895365903 377641085 960648357 790509805 529540648 437454306 293350420 728508499 264552277 459801031 418570766 227376066 731095504 44324240 228954398 735267233 854128654 400883880 700072258 603347619 794034911 622059810 841494005 142804883 768388398 511747700 624480242 746301725 236952282 478329675 669311284 592912315 751543562 73190060 482453820 459570478 981497310 888674340 291718212 940326276 220911346 367496053 253419417 395062290 782605492 319928043 485809079 371364929 531875226 511002338 737856710 727905355 402325726 612896703 827867771 372499857 541141915 101655690 265179106 152252325 672837186 229537116 704681616 459572544 608445683 565617352 806122377 221838245 109800109 576727574 197459677 450777034 400236146 902276028 275262368 81463620 958695938 799243000 900044554 729722928 127116681 134283621 216768045 115996183 276946224 708393452 778668 240282385 81582350 426286034 310812956 382543601 855271577 386378008 229992649 345378450 636976452 522470057 606457024 405099998 279049852 322508955 234459622 711162657 377546634 126264763 711072506 103035334 741888764 560011199 899134345 166802184 703312918 361632345 591046938 445416715 237996218 4234390 494133893 985144660 159102263 998954329 131389683 315076096 263171475 460223096 862181623 693766868 937142642 491661873 343776535 437184145 497570978 885752545 351886424 546894763 566313596 34560741 538305210 996883318 908903993 656578099 574217332 301979793 734975813 922449275 273481922 45942619 755237291 32978644 11879372 663445217 173959145 941523956 306551225 597768482 215476488 253348087 922847450 284214038 178905101 527812386 435844012 738344199 333788903 474171862 398346639 615782276 215258826 334791389 145465021 812454722 53654403 323599828 498098825 408069171 571687418 350169977 852226967 733181196 726428796 192938184 466131940 966699706 526077136 168428173 420496285 951538141 522220181 963854442 145620426 927386858 475448952 774219912 679528137 948856555 496744278 471991406 95909841 837474138 315121617 655056918 538545873 945807883 370614096 726168387 462124507 345373026 15207086 167538780 684262390 671777842 953753130 534893966 849562518 903025960 602815566 128977889 137701356 219285377 715359351 277968691 243273024 526389744 75873542 1791721 884791442 794041496 834501906 464521075 257015443 759495208 605973868 679517848 583459495 100647879 507543698 144683098 726170214 417275309 508689219 132158541 581441383 416588282 197442126 746346042 373534327 949869539 367416571 187572358 267553936 304735763 93395827 970869789 965430793 781010526 453469419 391328758 715889381 274621425 416805650 253650579 33700259 844116328 703556460 858395906 131562843 49525061 735558764 842618215 984919160 819616273 479569981 169411786 798704647 406135253 283788535 877607118 254454416 704519148 383968488 226309448 344046829 250870416 355506136 846375579 738309196 100517785 458191311 449014304 38578754 6989253 199574644 573965382 542984325 213545531 763595358 938157697 654300691 347108643 574116045 183582172 364084125 576314883 472756403 225154086 205856697 254629407 133845092 962953186 381429222 937324963 351417014 187753767 723677579 822123613 780661278 525401049 681805139 635336952 274267649 522848762 802985532 711392243 464360523 146717266 349495922 358431550 257001066 129220498 320219003 687506225 445180852 400057200 112091079 131650870 565287332 818202944 615801333 759532408 104697965 102819615 602310361 504572894 332602007 459373411 368907072 860255542 201897950 435988787 283354977 923106472 106115961 29209385 452324612 28398184 762411652 194632332 311028468 718617013 133675031 526653893 941542573 168001917 951035047 200491462 708207583 905284691 586074451 341203855 225847613 173526588 447377025 264163427 35811267 312421701 80143833 201787326 11650600 983167206 455607106 195383333 559659698 13217744 372763927 937472288 533007424 459017768 789677428 346018693 34153771 415649617 309220937 216524539 909569447 300116848 642420404 309154609 804671781 973570708 540484480 551647027 104725186 671170774 138229718 889081650 561260949 781354243 986493613 83025786 261251137 719356867 381496622 387606538 725681814 920916177 208763832 908235836 879550104 224739120 574891362 713527227 974913478 838356256 36800449 139608981 226552351 989041968 377991028 203811597 576660933 126216814 400920394 359735928 688524947 24947947 21138555 73101163 832101578 746738439 911376894 549038683 306490474 150676247 460085750 339544928 229732650 809406444 413552683 736179523 217937786 381112642 883944972 856415518 535920209 988474174 127638914 329976187 818874226 208088084 525608677 751103860 813029872 47857889 293938425 878625709 68040440 667323439 237868126 244160079 667178515 878713073 94066533 790478786 760317752 966119191 558521634 820624968 309255502 923223098 604831845 189662149 692079225 244377610 432880124 201557457 693293367 197756426 550044850 224897172 838831127 231329919 567840397 527778203 734840314 134985128 664628036 228918055 395031059 723554878 44226963 857992106 979916129 677044763 127213758 434729095 213587411 313649371 402598661 858457109 105766759 109327029 343448126 807144045 339570282 420055476 546380059 617467887 973445541 105179274 968942425 622283411 100964281 913323500 434587500 920269315 725266594 102200679 192941651 406269008 149741440 15927566 696191465 844632366 950855323 906368783 607794143 250827285 377215866 650539758 305753032 716864506 228876578 62002892 698123034 623371079 656901622 476594465 652070051 981349231 417984617 283455190 911127190 826540963 814200157 342847854 43561039 271304587 219370461 568665863 846948679 315420734 281597622 658231987 959722370 12515995 897725910 457510208 962393237 952335301 639984887 236469229 623840767 282327443 299267891 240499299 49157345 729429793 542200783 488911255 741792934 716737579 657833013 512678065 624160054 282068026 711190656 356649237 320373201 601308587 561573017 536917163 173860174 281988954 287595298 74305529 873002114 292214236 74074262 287922503 313735737 91264306 884104721 749296452 925034270 588861645 980219757 972971594 410960566 313068194 82078233 966139379 741001882 953546779 165397155 753274292 653837656 228405941 743654244 234959871 433887442 706881708 817743463 329223204 719183938 558256709 992523335 805485560 769854729 589216428 298467580 565975411 969138810 648938328 384033014 313109497 308492230 968023230 314494191 721515497 149081566 602904479 432741454 486865316 799376780 927100595 227302191 995991322 697362001 180662606 992658970 61422369 818419476 224780627 272990794 706118574 921679413 712368580 218073532 863433918 590248502 436849136 525841306 891434380 158890371 344987959 88947753 709351122 910253569 260723593 902277973 21652784 289003692 661062665 284704633 522816731 236153503 413524847 658758529 682436578 354957431 927084279 177717023 442366464 613602806 155263757 607509737 599956578 864021834 131478023 880001336 917802090 89061722 72122593 295494964 595496051 283106659 764116011 804427763 61168587 245936375 533335741 100997465 513648256 318013528 85637526 587634265 838602697 609081393 415781954 125508321 625581863 458241803 321258550 857011135 316383495 314814571 361258076 632994788 772129983 536679908 556046224 629286568 843848006 470512094 198584827 629390926 616754716 26584933 185113504 769263981 974115818 277744697 302472946 180709388 467371760 526808810 769155249 353099550 198153375 536782223 753399199 931971198 823696008 734549991 129339678 286723441 904214005 912885988 536060533 455566796 964509994 756164400 943164813 945475249 923363326 966315434 533254232 193802832 868330451 226930167 249853228 567911986 788143402 691591469 724836948 260915237 573447291 983102100 929681819 223134973 348290193 40341117 904194914 900010538 718821171 877878120 955439430 986617766 755644790 373073580 124114324 986142944 977895044 419624519 973992915 79828371 997381298 769203888 886165431 358896918 729858406 578918345 643307585 994680163 24716546 192040399 533479293 643749724 945825367 795102446 103987336 413684119 165146538 899824461 484186104 352800753 96307934 680089720 449808416 211104137 816816501 890947680 178584970 379414643 471384251 607553220 249311532 942289825 143661162 937763616 332033679 13264214 2094703 92982698 704387349 284752036 646830852 488681976 174742104 861113391 757704053 14770439 124994630 302844807 257682495 390175347 879085909 272009434 563622608 959538064 285247491 167326929 111381367 805985006 145525648 648814407 99085461 645011617 666973614 250613649 930162291 758377654 733814067 203258221 59288959 854255727 867863615 479430881 272118091 446094633 511711628 956442163 163453527 483379087 636231128 674961715 53879648 593155015 905216150 762766975 445661329 446158126 416437409 659172558 996489125 581823671 961397912 989659839 814312372 624761496 858518813 783192329 481573359 281489005 361470112 305187107 269213294 292784382 879899670 744635381 81683969 44915495 348280954 710809691 299737835 148183854 852203996 676379457 327731146 709781762 2732509 457708743 319822413 630747088 856615845 910953394 935426660 715072302 333830495 888990769 812772666 749333764 875874309 728399139 699539534 395558030 523156706 182679677 205606277 555425112 916923399 10364855 461095985 797279435 879754115 351199715 419141293 559026551 54403897 5147602 88157370 405121581 102704536 85226064 225271626 268464548 114892991 176588933 930133665 597217979 300613990 210110550 135618911 498526812 312558221 963751044 986698885 161337177 102156423 114846997 380894594 426151542 292690792 191034040 190202256 901407511 355446571 405737750 150690676 602543901 204851457 247433391 790717187 839089072 598172530 383568115 919122524 929177943