Problem:


Score : 600 points

Problem Statement

Let us define the oddness of a permutation p = {p_1,\ p_2,\ ...,\ p_n} of {1,\ 2,\ ...,\ n} as \sum_{i = 1}^n |i - p_i|.

Find the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Constraints

All values in input are integers.

1 \leq n \leq 50

0 \leq k \leq n^2

Input

Input is given from Standard Input in the following format:

n k

Output

Print the number of permutations of {1,\ 2,\ ...,\ n} of oddness k, modulo 10^9+7.

Sample Input 1

3 2

Sample Output 1

2

There are six permutations of {1,\ 2,\ 3}. Among them, two have oddness of 2:  {2,\ 1,\ 3} and {1,\ 3,\ 2}.

Sample Input 2

39 14

Sample Output 2

74764168



Sample input:
3 2


Sample output:
2

Submission status: Runtime Error

Solution code:
ans="""
1 1 1 1 2 3 1 3 7 9 4 1 4 12 24 35 24 20 1 5 18 46 93 137 148 136 100 36 1 6 25 76 187 366 591 744 884 832 716 360 252 1 7 33 115 327 765 1523 2553 3696 4852 5708 5892 5452 4212 2844 1764 576 1 8 42 164 524 1400 3226 6436 11323 17640 25472 33280 40520 44240 45512 40608 35496 25632 18108 8064 5184 1 9 52 224 790 2350 6072 13768 27821 50461 83420 127840 182256 242272 301648 350864 382576 389232 373536 332640 273060 208548 136512 81792 46656 14400 1 10 63 296 1138 3708 10538 26480 59673 121626 226787 390144 628744 949472 1355952 1826464 2341600 2833632 3282464 3584160 3765600 3719664 3531924 3093336 2642364 2010240 1508544 963072 621504 259200 158400 1 11 75 381 1582 5582 17222 47194 116457 261163 537459 1022981 1817652 3040352 4810720 7230928 10360160 14178912 18577792 23327872 28132048 32571504 36310464 38903904 40028724 39552156 37457388 33941412 29314944 24179904 18835776 13777344 9452736 5716800 3211200 1742400 518400 1 12 88 480 2137 8096 26860 79376 211811 515308 1153268 2391936 4633331 8438664 14557048 23874176 37407760 56117824 80906752 112162240 150052400 193572736 241706624 291576384 341323776 386160048 424359540 450394992 464545584 461528208 446428476 413557632 373573440 321120000 268449408 210332160 162330624 112550400 77788800 46540800 28497600 11404800 6739200 1 13 102 594 2819 11391 40344 127508 364587 952559 2293742 5126898 10710633 21042989 39117852 69175664 116857024 189256368 294745440 442503456 641759376 900689616 225195321 617201401 74227554 586823330 140227131 711888699 274217080 795069832 242715461 585116357 796764497 861974465 769155485 525176285 146566301 650715556 73773796 455145195 828946802 226153586 685663993 216281593 828705600 536385600 309484800 166924800 87609600 25401600 1 14 117 724 3645 15626 58741 197280 600215 1671266 4295107 10259436 22922995 48184950 95816051 181136304 327071752 566117888 942525072 513281017 349163810 532145419 154557773 309226767 88509354 563257605 789064441 766807654 474675580 795689314 599134613 627066840 658988947 307608398 337632800 295701193 44870369 150212311 705302359 336038622 452522163 797367958 62674553 57993322 777736994 845298906 452367755 90655804 810196653 976943895 564798323 582118351 994783972 869862386 697759993 660441600 381024000 1 15 133 871 4633 20979 83313 295803 952299 2809009 7656027 19414457 46086247 102967901 217634463 437195525 838372452 540635289 722168530 638311860 640827391 196046908 898688562 478199884 793020369 808862771 562236075 94791602 385333320 237794527 197694759 398043392 504456766 579736664 78137089 793367253 961295251 280517488 179779783 947563092 901772777 859566930 199212409 920781370 362900807 735004334 297264154 482748036 653703312 140400674 623159781 320434095 373194802 13313867 205909676 360223815 570584277 68075848 372652149 961247580 23084534 261139053 151302323 715359965 625702393 1 16 150 1036 5802 27648 115538 431844 1464468 4554040 13096378 35069940 87969166 207781760 464351910 986188668 998611836 879505923 237509223 15110629 621334822 88677622 257578542 963016850 235638961 442107823 429101453 483004748 329733855 718448185 266304376 413950543 256286771 626720357 318467482 59069608 81901162 352730851 104241055 503595237 956355036 534522134 457799859 108929893 887297322 424614770 265024591 876853471 515703045 692038809 210906163 20070317 468291405 145357835 797577421 232358134 747771239 343859985 833879609 78548665 289896769 449285934 313197004 379603290 397630660 609910102 442642726 627950853 722186028 705163253 998661511 771071664 636940611 1 17 168 1220 7172 35852 157132 616084 2192506 7159090 21631676 60902460 160707468 399489140 939796228 101060910 481320121 151453550 952463061 931694473 957528293 554162053 990142499 644946993 651797781 791594351 556120466 271969917 107619398 710253075 280526462 615698879 99748930 775178221 257586036 645364809 806795120 340635512 801741075 790520661 68328385 331513794 351728404 931812262 91105169 176869824 445724501 370449983 359815736 918724628 869062973 659791249 657727222 395793733 32692523 78858425 151369211 628504487 842750087 152091477 889718876 908002421 944598446 656459208 712920845 47550280 92244967 110652620 951703750 217822851 901098263 655149074 861896271 859184013 992613245 768042116 807916959 335381553 909568095 153171069 827990317 681893483 1 18 187 1424 8764 45832 210072 861400 3206786 10957868 34666130 102239488 282743580 736889224 817936097 262532028 534038590 412279142 965109380 86702267 846482566 945052509 644517943 548776024 679330947 152291502 882910517 188127435 636778925 902059202 132531208 193904122 893705022 246193070 652079051 958060250 148697872 504141990 371410212 807466717 514477363 565424570 560794838 11419155 215137208 665710713 791504234 359367396 224050172 509091270 125989128 782600310 957126038 667219607 386301613 605448653 296557741 618019404 194294675 222923480 765962783 743934970 24324611 512643153 214242880 286900578 228877964 91240846 430467141 533029377 904804693 373207899 916503101 83598539 560288494 363356684 68282446 152683809 284461190 124425011 167972327 428909487 373215034 420008537 513304383 874743039 487193257 97337408 532639641 184378261 955976093 1 19 207 1649 10600 57852 276620 1183172 4595034 16384606 54107670 166643130 481442164 311240781 381378831 288429444 380463632 370477330 171662912 688513797 626045604 789881798 844990830 70546834 230422087 267733218 970080423 75064762 104073936 888990608 393490487 819401315 362017415 197941501 97730360 491049732 790022455 142301163 381999002 81566974 255547256 500580164 503785886 874661360 953064009 357278689 416715628 656421867 311332859 849655408 575613107 850236831 533549113 255339339 611845477 501164398 135987981 672393680 678611757 552403430 470027818 333312311 203812034 929380798 133842121 497262544 839881753 29703780 133717366 249364505 959337844 632980495 72879056 356819838 662140760 182352973 260787823 329159184 423643610 488600943 164109163 8143787 184454683 684285006 693158498 382122550 488552031 777204359 564238497 598675373 603916585 720234840 93182262 238936257 486420235 352604922 958291193 880928218 736558676 163545641 189347824 1 20 228 1896 12703 72200 359348 1599616 6465450 23997032 82508708 264654080 796563486 260832418 76986106 528774007 854313906 307546108 722735109 61004626 805619536 18191861 511411798 993782454 401030744 633897378 70862649 96855526 314416445 92910833 135520920 492052755 24334887 643976444 574388511 317610455 122930943 637889505 255461238 950861369 48876234 149504663 198682481 942670278 866921314 563621302 960474580 980132644 624295523 399490883 351714973 945626033 827908349 157456205 481861323 472454109 343580291 683697065 95059407 841332348 464714941 596887160 38681949 757883329 590303711 64921694 730086270 15240461 714742087 32874447 175996750 277466516 788882909 11880203 95097385 778398376 531252352 479554466 557013590 609738833 798714176 859324339 721484640 268442938 861267595 806087188 31691029 950412807 580575404 849451646 691790951 264837637 967322620 365040170 622467624 456436788 658680316 60575186 387550026 215002020 31349904 449373833 559514745 640364153 807042078 450172023 562637973 109112418 545193132 195217263 976304283 1 21 250 2166 15097 89189 461164 2132144 8950214 34503182 123236828 410729140 284813823 790835929 594736274 153822108 374418504 157537842 147846917 133568389 483576696 508616649 656867821 84463125 640047601 955370715 182167616 49108700 229345632 795610484 502493987 857101031 142485158 996679960 742503997 723858587 317526153 365342533 250775491 442738912 408346120 881242865 135363327 231979623 347291745 824934645 995772018 164592917 354883487 450805745 963969802 171006181 92161176 169883419 961669090 26844445 393784092 571606470 464707158 34144520 652396373 745405475 202923498 135935314 703695236 776259115 48310283 874186699 219390686 510394758 751965065 418424556 8781061 736058807 674014147 674780706 590530540 4352977 803825827 167292329 541083402 260679638 665083995 939990721 816665296 886017767 669822229 694816125 643235536 937314556 115942268 261159535 687177905 12245758 694615643 977706180 217949106 118952653 898868241 856650616 42954342 330321980 535121720 982503521 719423135 714354007 18745970 333448882 302037622 935654015 778423936 317991952 284756555 504736970 155871365 118263505 797065125 640838446 258037348 34344762 502389803 911086550 1 22 273 2460 17807 109158 585339 2805752 12209406 48792492 180680070 624410736 25734764 199973794 977710523 571365953 412869707 328237414 214863466 633048751 257394955 317735309 673309005 193600985 704135816 514918834 650479735 33606857 490034801 698396427 67986999 220797055 218864611 931163713 940790978 675674698 85542051 543018292 61247584 910803604 831296179 923943160 89478028 104500393 161998091 254912705 539249258 547749719 357852173 690014841 206926249 893887199 747112232 382059625 148865046 301618706 260333115 442306036 247371284 782005651 233300621 920894203 317455792 678639547 427050277 482884001 854060466 980543322 860769666 701293636 771136168 670745480 486701027 168461356 848787800 289825171 498776317 33320170 430165721 821516580 115533370 398776967 333310602 563097053 553134182 219816464 216637272 206027601 933677337 925510467 267639197 43693887 486722546 270929495 877730912 261947307 375318068 692508932 989184491 226696206 288508969 739837562 849035543 782296408 273955665 801085382 431898190 935043965 202752072 867866169 151133676 67940990 78118516 742654574 165553271 254022475 668960857 929973305 656759571 877339826 925206924 133648890 623964326 796176354 256442424 844384225 955053908 35821657 33969824 328610099 171474448 265634834 954990510 1 23 297 2779 20859 132473 735535 3649437 16435370 67971642 260491974 931772466 129241853 915880695 773220207 21124907 663657824 89235883 562087424 395633225 79602143 818737728 503346111 923762587 810187543 71950684 872552891 722894374 788701216 792043650 839896539 577542972 345484502 350106805 159630680 594479078 806985602 451202244 562057157 345406448 404888318 371479292 122121086 196184273 855722413 625056343 209132008 580725504 234791519 683270249 879431955 820639155 890517789 877206124 780147370 943542736 532169988 134361777 389279830 486085405 212150153 60309713 36144061 220641769 167907687 433032241 672669299 4840381 543970499 860603358 920463673 899153827 269139419 99866794 833550296 732963165 649634036 220976898 948879986 81746947 249278044 943429751 227240067 617290217 857759442 317672542 702411387 392102340 598392406 771484657 20769431 772211314 777981688 103043307 336611982 922346108 46010568 620920750 740298345 143296430 127113300 229361025 452883985 298773134 583669967 430943791 878469881 498554889 377075156 399618101 518539100 610655946 762624102 339746521 193491143 582788075 58498274 139175929 439487543 659039143 969039085 205473123 149794944 735361805 144310487 952281582 885994682 290034640 449859219 870975475 717604104 930837761 466542500 510501275 368063612 61813298 959329905 938922014 660077190 12025968 335011033 657136343 351072920 964781583 196462283 1 24 322 3124 24280 159528 915834 4696644 21857553 93405656 369882084 367190881 745178532 541448535 237690972 408537702 191376116 678513161 493570976 397907192 9101765 658714208 122356973 514532531 911169029 6916896 782796 910119724 942560918 62371227 773940129 523667340 669757203 42568262 891666384 467022993 486796667 727294526 413613585 787453753 599953158 417187968 359849625 117069116 879478181 12380000 910899870 838986319 102687453 103327364 376800830 429223538 780159138 706916356 587575355 971169352 36010810 483798044 344462034 787276711 359714668 737585540 514856433 506547585 7966248 935961 931790046 725219981 437246235 737823353 539625329 101294921 998345360 158678756 14552916 434899855 58679632 771567929 908041362 370603042 958461645 473954165 329932246 645017860 950250115 632956030 39737256 308287817 593859369 848980890 73354610 67983312 794665532 744501399 571146358 79777328 768540650 301591668 87146707 749547055 542914952 113807115 981646049 443442346 689844336 226785366 664441023 644644459 65534356 186334852 433121661 818953887 687026114 344822747 464015963 110899493 294091084 65199948 37449794 719226153 501099656 413337315 725255533 799293560 259962068 954615054 373654234 764439094 914044890 22085466 539035590 698634111 313016212 98993468 941478268 955683335 902077766 420565422 767959775 128648986 355285226 534029655 104714136 932643222 778200211 56428536 225880543 792355687 449940761 181471652 529937629 325235521 6575392 94094707 441392085 37264955 911557047 1 25 348 3496 28098 190746 1130768 5985744 28747851 126764795 517958180 975500521 75313899 914923483 611051644 458281681 932346365 712529240 185024083 463834094 950836649 286357381 871292163 434939852 58330077 629835295 27932676 66354549 10923173 590226200 526183672 176005584 809584977 222348292 260397896 396327746 178971085 774808076 78650222 507195902 144802453 299847298 581537053 724817078 350425193 503589319 654904119 595937600 992781673 82554146 868891604 769490422 119334199 287573489 85347169 118147346 949694675 540939467 927324362 545027201 610310429 769058023 21423 262519735 786795808 240407039 428554518 447092428 788617633 367724192 374279457 343082569 856162651 150954733 962857235 700751807 895999415 533537747 537990547 268357366 869434038 633081543 603452058 947934680 987367826 743179254 710352935 835787228 706586787 845202323 238777269 405136472 480736674 155194042 871452828 677921910 616952227 984554304 602482844 894952109 161534829 782737895 850072208 670793244 828100052 222399146 284700626 231919567 306545173 673216888 772842480 314744315 347738200 25002680 730048408 649455506 745857274 196252843 529935260 419302767 276709210 732855171 343508231 624945362 861002432 484757974 367927715 209929226 661865936 531107025 413469524 479519565 741904536 610072165 606639245 934344602 716197790 587584177 185414563 306822687 841034662 971868532 919896238 158358640 773475266 936203252 665923149 911486615 197651366 774528535 82937079 883806524 130206852 774201811 995994000 245370199 842572718 793423605 740588350 687616120 657690139 857790226 37323118 88399209 523321086 117621631 71036645 222192424 788926021 202125596 1 26 375 3896 32342 226580 1385350 7560544 37426495 170077814 716127109 814596482 388283574 187079164 480126707 290089727 38629756 54115650 64891257 901599546 718222041 911275669 323565019 817912019 805459451 803612364 201797073 732830955 80380678 23464457 701195891 272214917 913862649 132026200 669751010 759341231 973676755 794065196 967438659 308299894 10712690 949669597 781686555 88559004 727530543 318751597 278470531 434911202 804701133 324324750 981099143 232682614 987104568 776649739 786487389 442468777 569068005 663709268 881510700 203686642 57967683 568729400 236001193 623959074 703861418 908672716 70204475 867825588 827103298 241630317 362696969 415618616 805038660 598704556 10082872 643477587 415164213 703084166 477367476 20036406 629980785 802614294 952521645 17601466 311433959 830294700 548394039 535645146 521413012 929141249 283365227 727229980 443388093 410708269 286618040 319768543 938841603 93475597 394693465 931196821 495806189 902879580 707905623 303901454 576396872 484544924 486011674 564305854 311518869 856442237 372745088 366968335 813470622 720542245 551543931 596748971 778551123 354920979 984250497 691689872 327423759 52302396 920309409 457393341 162758194 401889329 760192486 361045291 58998809 845800809 8575285 649668894 501939170 542308042 574502757 192463535 690505425 204738512 689813836 483570629 525148782 216925832 952334594 68584858 946061868 229986068 113082103 705545851 563504064 430610853 209937938 608555345 578039088 750439353 944169681 417934823 74422181 960090808 568355902 435674968 894299009 15861008 618713868 509911155 168869978 339481775 369451744 600513141 71634326 781507214 857107917 106564183 736233715 362800524 615467708 519437498 342065337 206666492 505918934 308299385 20927738 106279730 457391057 1 27 403 4325 37042 267514 1685106 9470830 48268511 225792189 978561725 958557158 38052071 919433401 254995547 546697380 704487939 32839999 508901654 551556389 663564198 695178769 814009554 547143595 371559020 945387943 670094820 616330760 976064124 607380120 8699769 998280938 580008436 958036252 912203574 544195790 396609897 954428754 708902921 801338681 431017191 381717232 344144422 131861617 874277396 830300192 596462835 318671397 244894238 904557382 834593756 283869037 697514761 969250693 509524190 913260759 384371901 692021356 509945770 32685910 505430483 907189201 193340383 693205397 603006308 305262013 925218957 968092842 27052064 47727228 477199307 293774777 98292616 663047137 995897620 288543890 998081856 524487172 892499155 556044593 972323813 578208602 933674462 509188659 985492681 986901126 628028841 519717277 311965185 897395442 829761538 9680527 161715155 343759581 402616197 861303980 911400557 358697993 515548395 553147014 892738525 205604013 762111690 442223169 7841804 517369986 84729818 152655938 700957258 898706126 75157861 271201265 543855670 440588279 204308612 236683234 208667572 404506592 809547310 853106482 518815458 16491026 491832633 360120645 923872102 602086347 641452842 18221609 229080666 428455406 569262655 856993308 230900297 490066099 367669571 96292417 52365382 469261002 374633464 900617667 182287939 49700390 796588976 949085023 222503562 658471212 94278399 66098044 72459139 603916441 257635815 234793049 951525459 549173423 938321308 13662267 288258509 65326301 11071916 364716823 929353581 839483911 199241395 29486252 482468148 829994735 370892643 687560607 531658704 568187724 486108828 475403750 227529481 124500798 228110006 56292488 958873404 963718586 481659835 183136868 593123751 622015148 469053734 211587807 928091671 481375722 612130911 134707706 334981252 784422204 712253942 698883770 390222722 25478322 28778175 349558455 616616543 1 28 432 4784 42229 314064 2036108 11772944 61710789 296841956 322742117 501368237 486564198 208215103 787564548 236938424 301578523 866593178 461034739 153403692 741061604 268366308 41671958 999969805 820629183 540097933 348143198 290585123 709901036 830657214 397773343 205345230 80836479 744283025 767371096 13280133 166091858 688213267 405245759 999129285 957885801 125598090 229197648 232621259 771781842 15692966 623498734 209019752 451480479 405116698 905232949 522429827 160392239 911337480 463779522 870625842 997849245 364479050 834828 300785526 10186705 265101999 566806573 614983712 685595755 48653250 344390997 673637797 896886255 108856368 31386606 486989879 489263782 517653845 976993581 117774221 829510874 294191687 233225993 831800739 448583977 657291524 649603801 456575978 536862581 855051723 994222346 302476269 502749737 322446053 790323255 357338908 887312147 181428924 536100952 55330164 160205355 190454705 365581727 201998030 826748536 400273437 624522779 849319472 800147953 80982274 447705256 168185200 97822479 309878269 678607548 912097410 927785144 334246635 662138658 715198385 260363473 461374975 89468114 651175074 575096135 130470890 71518840 879845193 486812125 128678982 647847215 49005945 59417027 550597313 85275582 589669875 488581288 579391253 238935007 307933774 801626662 991248834 831660242 2289249 939337934 170802252 112167473 712496239 45742853 482400666 341362938 957391891 147812751 376451585 832724562 418101830 38563919 274362964 819817184 400041713 313141267 806456583 999307614 670677205 585839782 845991536 831623045 109161241 554327240 822718306 173814042 363700239 22366070 479904205 190929878 554951008 774006606 279182950 109357938 401823952 575672540 860574847 593910748 547825741 217594637 989467389 184852185 331539318 325720467 383229710 654245987 146654996 209385163 560462909 965812836 65583448 508391947 709539829 955465325 214525022 394005813 531700924 773028650 417539579 326670161 406612199 165245 699092510 550837077 14964582 527720684 440459594 268905155 297293091 881879628 1 29 462 5274 47935 366779 2445008 14530396 78259797 386723841 770080067 561338901 331351593 839635833 167817400 497149119 881282118 352201610 471630724 181160121 88806794 987377178 289689361 946592969 656979867 594487341 196240769 948508749 810784209 709855728 576276359 518417791 87667236 667014934 181628700 79050911 337053925 373883684 560120551 458872893 815731972 827954345 771964062 380463298 190074568 335845313 308369049 297128477 730684746 742600059 263592454 96421517 206168581 306386280 238588046 136275025 509837233 285349782 467079296 44733505 132275281 829959933 391862643 62600608 253168338 426879146 365435454 91732486 471304236 543190875 798110387 894371900 696428631 750022470 726550236 936549828 542410178 939184541 791578453 983635297 823881369 150676558 585328209 653882077 963087655 950795211 936066317 71868369 440124326 965151462 175368387 40663323 699428294 108367130 332044307 970432796 572024201 885659377 539317691 132218646 139253073 467726930 45351751 297376822 508633325 703469419 746467332 503668629 112630766 930570931 962347630 576196343 698904389 167199167 333129737 608922442 222067115 688206452 802821275 954540394 911151138 906746447 902608727 890863920 307268385 54404696 104370759 495676754 441341576 829087999 88911607 975336543 381836343 298727399 758323163 709721214 146811076 322114121 909574264 955852236 803216000 511491931 157225317 671670053 367885171 612666342 842261160 508147005 345029386 809990068 981225972 241279545 458275632 172983843 48836190 961296645 538132589 271432367 877708377 386417805 815731556 463571419 404450924 113136747 549319603 219464194 220054123 907114544 328856175 265047793 589592614 328159953 809008569 510434161 420313068 107873733 868895119 895337042 156863206 48004547 666506430 727609186 85858741 59205240 78940637 545962715 139572749 421355881 858507471 952603331 401020118 942925111 296295597 997986384 115737481 677010850 282276283 274892540 163700485 118592549 846472792 136765224 236032397 179431589 539549211 214067143 923131121 999465547 232088789 610013691 896204760 478686995 218989077 91096939 221616643 243944261 454787573 542927414 355318220 147354818 482630 675619041 634351197 478341164 574509037 738721209 1 30 493 5796 54193 426242 2919073 17814512 98499977 499582398 346636279 286311246 338970899 482987014 740494022 522312682 389124982 438269373 295660905 384589942 269003911 190728878 21841107 394443500 159301748 885681179 869073529 396029106 969827087 16747334 474716791 259235367 753984455 365768194 423375006 957390875 407261764 592999097 928039310 529328158 133251022 533719572 434981329 779487889 212784950 467080112 287628298 91658981 576061624 322787361 682746649 234833733 676878118 220869554 982232103 879428014 742840902 65876039 230084790 68776407 988541480 113769367 288661011 898604342 790158821 811679832 416532461 643426286 357304561 904850873 143689492 643378934 217587561 816799579 741653213 950522177 519192837 195766899 875531753 913462122 931740864 147485151 73473743 881407231 943949423 19375017 95185407 658198820 654223830 78841384 487272636 810454297 156111172 108214345 594083015 721613382 413639222 199581479 219296986 983776208 50034813 434669652 336761553 553659069 443256837 867959007 649693919 829394710 511124003 801382432 809258820 440312724 549557631 57091967 619973166 38255131 989252595 296849831 126449228 992478958 948085171 398912012 308493194 585304989 581850817 704472537 457658359 706849064 974235300 322942033 801441410 806760539 930211369 674605925 140615032 804334982 654022727 747554604 304695097 670935186 973200118 899755340 43016718 33443894 486649937 183173093 28680647 612676891 17478829 208078434 467131016 651933212 464433186 3993644 959280435 310671435 524438940 540166082 143663989 984026973 596317769 299039541 925611762 115137245 238184581 798462400 902062936 499673997 696053154 121959061 376644235 378356623 996412950 115590297 517087995 817795384 731733847 61225249 930096903 292653780 149516053 503527083 233497811 781589564 87992011 514696635 495015483 151617728 478098704 773499685 621536652 787266199 440325002 249898342 747360642 671517137 216648293 686506084 544204132 949750238 249236969 319054830 756596931 233403453 594672369 158463779 809106181 249481644 610711719 262167344 179138909 270160113 278492510 490828032 946977816 803242084 541036271 624688984 204404014 881539240 779609382 561095932 524976628 888316278 139701497 712146362 413036824 810411985 241441787 247390036 695355554 122993697 227371919 399947791 833892197 899399938 781528108 656359733 551706967 845829828 900357325 1 31 525 6351 61037 493071 3466221 21705119 123102861 640304911 83941000 859775332 485271727 929183599 393442380 976105677 287805815 238271867 74391877 765979021 335546599 709265303 808915958 907593582 463983041 147572225 888153362 391439968 221443415 801779213 245226914 866175931 810047153 267980729 805674759 955321032 906824500 367243333 486256638 145115859 530769671 290945081 932311137 51068986 807551107 185085629 261181005 959829857 118218336 295880881 506261294 848742193 936582961 153400705 578662225 341741810 161659811 816049772 839223846 559301757 400427189 216771109 207016492 505237766 795055758 945605740 555992642 907845643 982951177 401043526 597396374 84431994 362552441 746539639 303946121 357484364 893505269 526515449 560103044 121894895 445706213 592793631 713670463 810676671 143889731 392244416 73126772 488568958 542583029 752584772 7383345 155007498 994039957 804821801 379264833 525210782 239847467 126254398 219331239 753237922 434345445 635807399 872366121 133933893 590603804 32230684 70841222 840236255 909722819 689521789 529248821 178846494 980363222 548654005 434479841 697553680 35011089 544881135 260563063 695816358 44173506 726085055 671716390 781464159 450226987 146813053 877951734 991641337 221699230 419417817 794832550 810418558 969705412 219055178 274301546 503413612 695160244 74090275 26176299 695070748 341801549 897892431 470380437 3467372 448525308 439337134 724845391 9187155 585558376 372261444 277930003 34819054 431482585 279947765 492267585 818516372 484582901 390623889 856573701 179325546 611189228 688765384 847931848 534263758 557397045 116495491 85868985 610969731 478650084 585159686 14772190 776211983 474268574 460744792 134988124 912707317 105964987 809266690 785401545 161419686 653370610 499797235 534961655 323936668 802659551 370287438 326963010 342959476 313044094 148582386 976795271 120954501 724957759 860215558 270001726 640931921 833230238 701256342 242231076 286286219 13632467 253663042 129411109 603714672 564008356 523901279 216864213 524434304 182659511 983267072 644616701 707181007 618980658 405751838 571460922 136629759 744395053 539608518 963053644 97893406 866038338 265757870 944699732 964525924 892464175 168006507 562926324 742708490 132927348 526909479 79557205 129052432 157042523 659309142 834183171 802572815 517259737 256356803 353227137 87135975 224995979 596580540 402931204 515099940 793833445 691900231 589149123 114327507 887760880 389703467 830251700 783657579 433484966 412892473 432995349 911076886 112628181 1 32 558 6940 68502 567920 4095058 26291268 152836946 814626856 19929138 508014078 3627542 383619686 178749032 257695016 714018516 472708243 782289684 785010736 673452130 967313791 416615851 594708501 823838568 374885539 520875465 462873691 866641568 110422771 371334024 597629306 954905318 192386746 711820060 202869372 886359460 670157944 884126969 502946720 582271977 402610790 343533084 511648372 517557636 170605372 597697292 829559995 983984749 601678152 265076525 200313780 586898347 936910249 473920775 97417050 844866738 973357211 106398807 531568235 220592830 72245680 709223174 966562898 364453034 204299565 516186616 388239153 70201813 72763421 794896998 14537122 759848271 370782607 723372604 610938893 161728308 212501210 376508968 271352258 323852567 552136716 801650724 615740271 208656790 224034222 747809272 617340476 153891047 285642015 901118362 123777425 16228193 623027527 937436377 60747289 714381298 882770713 15381170 999192137 197256049 480638655 953137460 883599778 148656904 722191509 39402136 582147050 757441169 260428827 253172482 508174417 834955862 157349819 261175551 247577251 264652493 595186522 812752039 875384578 747313263 224431706 462673707 39074204 237357876 896371707 361524710 10299862 761952483 924315000 304463541 831385606 228637562 845205390 599099308 177524018 209006125 256908838 355221513 792061054 713446694 397486564 756107839 527866716 337624854 575430320 456754471 959728018 921786900 102983773 936936381 473475121 131588049 189268154 863126769 700571091 871530822 832046604 609629520 45186676 853387560 464311797 368430192 151536782 691919878 176735598 972465597 804610607 50289062 722819065 20410813 11987321 648373171 889715409 778512390 280809979 767453391 155472064 275305459 296611231 377220752 229158487 259857310 987705391 873889855 448418244 657467052 301028637 400332864 304525446 853531448 201469133 757430782 288842043 292821474 389580374 148645279 450672899 404696472 399758661 549392647 972607841 459482261 344863732 405989209 14412475 913865943 988039851 302203080 293916756 28383491 502818531 791480646 619991127 151573496 311251301 362738947 457688580 884177111 390413172 889218635 530910268 818241216 542232757 765042883 885001834 10229128 574524301 836418812 984923781 235783687 868003012 379478756 832878398 751487743 496700139 587857943 624473538 510088706 778144708 214176553 953029206 646822434 252787767 281229254 401166205 434753895 343430684 941989547 465870277 861407908 387687010 216509894 375279811 453878600 982073623 677731113 95924240 198468867 861679672 204003039 472066136 228890861 880462406 133638984 924365283 274136081 742318625 898640542 85174164 775817726 982947180 716729952 1 33 592 7564 76624 651480 4814916 31671996 188578368 29248753 200002145 508415428 442411092 823607844 339155380 84465338 814093820 347929398 722645092 146033429 312847170 460125097 915837300 530134554 683613860 22911398 950166343 297700883 874171812 779302544 705201416 91735442 764568060 448540109 794383951 50664826 501387621 764478731 392332791 697065547 136584719 904822171 811342153 498086442 66346910 903864157 648069920 294527566 68277872 192952288 465503414 89641650 342876181 975687654 849073744 732768838 299144725 960087859 432060633 521050995 669642411 783220798 964761936 888496451 578822675 774117896 595815330 556187991 328078421 497539038 461150544 593197759 454579240 228665398 675695769 189021504 506127036 683711210 767254008 372876392 950363733 781425867 518441353 618578159 210702480 146366158 211092828 25645664 252569415 768287264 315751220 46304131 875313001 63062094 41563387 521548621 882111752 325592507 674715724 754661696 386558110 154963091 238088464 48050421 639662963 70331570 315682289 290604457 553625701 114470501 286499320 302628334 934963054 90280656 946037777 701374947 21339121 663053978 944685826 452543047 117230904 560747251 199227363 16627409 318622953 147892287 924956445 813803967 785002825 524657750 94619872 228326183 399365341 370689535 675442405 908504726 873312142 624281896 910865167 214431914 356568789 649815619 48684312 203060656 723151845 388405201 798060040 729614446 977682164 533436928 146813819 149571082 895803037 777214043 552248021 204656845 982800841 733286978 63964308 481147156 389291330 76639625 311176854 441157810 671041225 83215916 462900391 792922861 933493638 911064426 640299582 658369868 816565473 95242536 385493380 848295064 737403618 437312030 117969370 718173112 995019578 309321859 756181744 40101942 426476878 702396178 795715493 835764511 743326504 209546865 430615231 826070511 334341237 118979238 371120144 839568659 676120384 72519 845333099 357629799 910834209 593346831 104377605 380654497 634970517 115890735 793059350 887063630 651636452 507749972 783577804 143656503 242083869 911105370 970085702 524972130 465698950 325374351 536364599 196104291 139239152 633851401 256158579 919175466 894613648 315818683 5141779 876022828 934709255 681050535 191918360 662583345 207316521 848780031 272975543 702356884 769886013 961041057 6500208 70262300 494310602 739703998 384177576 343193798 693062586 969762392 66952659 685150241 630304511 413041585 515441116 191001103 912006289 473846745 605301455 795067847 856671001 508821454 735406667 258084054 117733205 780290039 23367661 593944851 692132515 4650353 187487602 151055135 898863554 673507355 215091232 603704193 594167428 682519378 496434131 965159536 430378180 248402836 470772870 307340881 347656961 749714755 122062081 558277910 169666679 941915597 277380477 270070849 652088255 549544085 1 34 627 8224 85440 744480 5635892 37957128 231322416 291965329 678229698 199102832 733159273 432255582 825398987 945721657 530531857 605903605 198451639 405128341 881104650 95712824 87475937 88052462 854657880 671362129 345256719 279913923 405600244 791623773 184158289 548244621 559931899 811302745 822463013 829884052 612803610 114370483 717655175 250670751 158660853 996989593 922821653 403693850 640224917 726696528 558324649 504260316 457498775 235424755 214797729 595578763 703649058 668639597 273743575 830864733 8621856 152359528 351252345 54682531 631863641 533130514 548187372 212107229 690348600 269650465 644636821 588449397 716956418 569059993 571818753 620732748 238441683 628780105 73251606 77232245 265685085 860541096 181038883 995121568 787161997 984175916 994855981 70309595 279951259 412871815 881913054 268261177 575207129 196951994 610045829 705950877 200402175 179100085 912730914 795237101 264189519 756871237 840795855 477498958 568161700 101820158 478938140 546807900 824972458 320572966 375535061 712736750 146215080 296045377 892271196 198915619 973312163 292266224 766955048 774760742 724672108 189810671 590576941 955913056 705860403 956268133 120026477 977289531 897970234 594373646 802624855 16139526 294245189 661099173 505327457 687552139 570417673 288750674 928298666 124243321 103493234 782666425 810561902 479140046 567654010 66398299 87173858 171094018 401077961 201022453 649177770 751032860 458665510 583069945 3741921 644139368 777863779 427938859 574083500 968708036 5259009 14753514 566158894 428971413 29779639 601893398 934948155 463945886 442386091 787098075 294593703 467511028 998601384 749411810 495421040 283658473 287441865 687819162 964614928 353638623 648210867 238886215 893364457 158958124 29345292 800368429 595552294 572640574 913495958 705720935 850127566 83220185 799386246 848828465 335228800 498492912 819731260 972790229 191002130 289923062 997108332 479589354 13686350 377632380 915241611 38445376 115515812 312111610 862313776 36444206 491509332 899038496 494299749 577210085 925017398 377889538 129014425 544007299 134491550 77644047 150186363 549177782 243194000 889811949 476414356 302027816 934223010 116351600 936035078 728736728 99057293 233685532 715949090 484999785 527817757 40017975 403976200 963752121 230480821 165554215 501580240 480519751 374582722 588438105 13652788 835399525 909982574 63720437 165170490 768431894 385829327 268804006 950180874 398363435 512876602 149304949 858796870 305796565 80654592 209088881 365995652 741417209 580938286 849913699 209592153 430983500 292682916 89781822 346251985 899920810 490814818 319818650 865676138 199552930 49606030 396988194 289382805 394082926 680976370 125444750 312554820 11884810 730982055 36906819 144996838 532313029 339360681 509568859 763509787 79118993 930179491 756170211 627420026 161269793 542072728 498021200 392693531 523036960 919765468 367278574 755839168 466305341 613534367 534169086 166110829 107021592 280650539 268761091 590645300 269909358 234042842 1 35 663 8921 94988 847688 6568888 45268120 282195928 611807809 518705216 990050297 271051698 122408000 405189613 94926808 864141322 53735275 24011733 736554738 929218491 904644261 780020466 504939462 734736582 905177688 612557341 964587741 714487014 841745335 939266470 221175663 553510265 427922711 816845808 551876447 104782423 432788437 75343637 98990584 780296494 401590023 184896774 39759619 46187357 134251301 342702573 517720 358976055 583636644 962541900 167548822 161325057 550357824 277594189 165080443 231182951 735855208 908711807 571176463 42569340 237272417 790920442 624258522 720842250 768667158 451444080 122083868 366641147 308868590 806102171 616667978 212552319 508058403 321794596 570313528 460066496 737582233 710064955 691296552 63281621 675218599 955697061 110510427 512018248 153536802 745040214 175960352 594730127 864516601 686994354 671193730 758082482 651219990 268055455 209604272 794711886 922988292 233697499 855180879 757331520 952855529 712373324 501054908 610479660 988305583 359797155 981016202 392046260 222705767 339379031 255395660 760704862 824907580 377018926 100950434 568292199 345612839 702169410 76425882 316244660 633878521 345805531 43908232 498746978 171201976 618174067 828038701 451921110 452033897 911744318 64098066 83924105 595571257 147937863 948006101 514496555 77289879 282007238 421799065 804334778 765393189 193008022 263503242 355816072 278012511 227861525 902054870 618486736 979710805 971590402 61042704 664850817 113175896 488535341 617582794 612947413 45804546 259073867 263038734 265569066 162645795 60875191 359494871 979749311 139358127 29529290 309151363 279422923 345089768 87598058 700337527 479652910 994907927 933976635 324751070 167729179 810904540 230096199 33195878 559883815 674302503 158162721 997344757 974400760 476723636 933671908 372458552 487353300 603836216 903251923 461631785 620155186 664707969 139328434 135802315 547850780 544085832 243757336 714792500 277247444 736724545 7257213 104433298 33077964 133546300 658470668 407613385 15549086 409602732 220607605 154437658 434924060 212726357 432662346 953726155 55947205 221865215 896738564 702917595 219549259 784888336 998968443 737927890 111474776 479544893 204531672 722344756 339644359 296335713 172390948 145219000 740849986 175518952 876047366 775536223 909308844 333180421 96764559 528034987 396799645 413114766 622993858 563074288 710510893 900874806 315196225 993816000 623166550 642968249 328645521 844280596 556521945 272458659 580772239 284457451 186994948 909094031 935768265 319893231 114481887 109302906 586737223 466388545 717893242 342269015 164207650 394855609 330099455 836592042 939058426 541984626 852636994 524042858 358495217 921118657 464191254 284341637 363378706 679058686 917272314 562488937 105215359 614330571 404183151 365378837 280141835 594380252 79371576 739360814 210010442 10232401 449147207 97531383 696215921 900156881 51327507 224992261 946786023 685932368 729503576 741723150 479111191 872812474 454570174 217639787 553029674 745481673 194164134 241094015 672191097 520725696 177728245 485102929 511421076 349030122 157631252 431267952 813510823 604978728 799539100 871169236 265066919 191499414 52282294 1 36 700 9656 105307 961912 7625652 53738944 342470612 999200441 797070294 375863958 9523173 166271514 481765400 879554808 535680694 467340394 413500052 692064693 580959888 369347871 169821810 621921924 137911737 940784828 741570244 905517670 551817302 657369119 721648393 536831850 500879720 726253305 296162041 891225164 880747817 182180719 544050763 654393489 357200480 356889637 635049309 374948412 486169649 407475615 51228607 535369936 325305756 74215114 944988254 919680639 647644667 526651696 763479161 278201627 103508412 387580497 561661113 38190290 310583115 569811056 351262691 985051203 403138813 643132429 289980808 570569544 550559442 934893929 352045239 810200946 61218795 42358563 89293505 506603831 400595820 117891860 469015294 166372283 320554017 155147268 955469333 896730515 826039051 931193995 36098122 893366407 522834450 917130400 759016216 23584371 48884561 844352920 604253909 886656394 548946691 688504947 972899398 721435398 409845929 399680456 284950632 796741351 217452678 611033399 592790059 219084711 504058472 277505825 120276345 694287126 35416589 305976723 447309020 969824889 565684997 62139306 857693940 901163636 262850397 927594387 721909425 958991660 471789360 260033992 544270783 877013007 153311613 85679796 660447085 213261352 954007371 8266647 75417194 28241545 733410215 579803150 41901427 876245480 900022334 813145019 668096269 73987267 175135030 724217744 139403302 77167168 775504145 397863476 816272710 221129133 242347768 885383757 728565085 947647994 605379205 598139075 269419404 178994132 603450690 652850980 19254430 182635911 57268581 239936865 878358438 515315850 141611162 665647032 700517198 807335907 965806030 897617342 773532343 924389029 419741954 420757062 581633294 179995348 34733596 923518220 731757774 573741822 531242380 813544540 336821038 442738016 551572674 470067223 638102335 989538200 956007535 613954394 401563904 103519975 569290006 144046622 689996849 638589501 358099514 725282594 691632053 702244532 284031792 473014945 465414316 116886234 142777936 342518645 138051544 347505254 57716395 939744642 114873890 359397343 671360195 724489266 683013222 345781236 550104449 877003874 63443231 224660360 658626409 133687251 933261032 273131705 48202694 144323990 559827621 779609382 930553156 35267489 493151974 645090534 517431516 368634145 540405134 215255527 144656993 549192120 659960465 217236722 742258783 538378955 211409043 760044403 389330065 692548510 583181570 627949137 829194932 234693932 651493437 707321269 828284674 652751037 873736576 267300299 729754896 429920674 875733754 60888792 225478637 39002446 407176220 761384762 131879783 661443680 51638267 568172852 186052558 637968267 556455031 313451921 238551452 644714578 449541818 640800540 923965193 38909678 41940756 338485997 888949941 526610135 48150535 778944981 480892059 874500608 900322190 973783674 468787609 618167632 913754856 327797543 845404908 752246622 831422464 484541178 501948673 647306990 882577308 771072569 171273117 620085552 385025714 126556571 472404266 664907284 284895728 860747643 285481155 480968189 426457284 579997870 253315436 264967992 325506073 407074927 289125366 710111895 168902913 39893459 264014099 335462311 284068808 624620216 265346008 330183605 301153063 136165951 223572391 416076696 791322793 440956632 812128221 56870528 529001955 157225171 153110824 659760559 934444871 1 37 738 10430 116437 1088001 8818820 63517016 413577336 466132154 602224077 950429493 571044537 948550192 759622519 360792951 40404471 549575252 331339348 353289303 642561133 959520386 811439523 113998222 306747368 686402540 608623079 625536502 102898449 513583096 310389938 861964034 144673299 459932354 368865341 656127608 909171212 807159815 446679967 582385365 827063804 980667706 264330272 600794253 740948802 906942889 945728377 18846332 985664112 7701519 115050801 870345183 606442987 443069595 817056595 621418778 690512206 255049968 161633922 402904753 372549674 317848199 779510849 454579621 366999138 955388684 940196190 710141532 289889641 400266971 473006189 518001144 203532149 277752196 73653399 957077834 580796815 797359407 33679102 974181950 229170666 221016673 753153481 718492334 480056326 134801483 829292600 87160542 624566954 157188714 912350324 248797376 864861712 311625650 564724833 638897879 211767349 670618766 182357348 406247054 335828971 235855014 766599169 873180801 943988159 797515463 949064434 37355164 366387587 992037332 39085136 457008562 710738441 147115812 245127944 221285308 44913339 750687382 166494925 487773254 2533400 294773545 964749926 838352064 354747747 983055334 906311260 773970452 136280712 732037766 304757958 868694356 9717274 686595153 845171773 715645486 457517675 868876321 257821804 398717354 952878758 459394839 735151005 982831573 597714383 483469574 396276440 147004054 275175512 449695021 280047682 322443740 657859781 236891682 338855034 771308208 208042945 611383416 470020781 959351211 871193372 314812327 417008584 157794928 30304137 772193806 92880268 735754383 725090032 678769251 695572650 713627047 220917673 996272940 711499227 615337951 732510553 265860373 10346269 946167168 327969286 691646116 588894836 556718107 891256057 29035235 193826291 413628097 951441661 812044940 432676044 866499015 139084375 351784477 900166473 781089061 914118385 818686834 857340116 329139077 237478891 284468211 215304591 458481845 227432873 865995208 554027168 463893384 221077016 374577314 119759917 360383422 704486222 404678036 137104816 809074680 755219457 826569646 867839827 768754773 89100960 257194726 724398193 973188469 858913715 18463743 680309520 450458743 140048366 764912130 371007014 456635116 735728421 778688084 152973997 434969799 574794869 212648988 728361716 542931287 302379989 751579729 92390154 220181191 407743441 315151252 520426045 407908622 679231575 395003916 794034847 347654216 68808817 829211530 81601558 162714123 30761100 394951130 268715057 283612447 241955302 623210420 275963878 159211117 252162685 595441437 529655660 437222092 841111836 179960886 135660761 917237477 768051317 444580903 506791801 487181239 875489229 680194597 205928376 680445786 683783933 969592088 132367844 396994570 832926454 630581401 505495558 385734337 641541057 95095471 989574773 911275608 518514268 282262989 419271827 469001628 420271862 947083037 407529572 59976989 434008630 863717239 945875935 75676474 215313835 250745830 87811894 264747800 37018493 98597371 710706515 142785594 391940962 336466122 341268838 21508490 413865364 232101532 92701632 8053527 412757119 757312194 403681966 949009531 880975038 37050684 272465075 678404684 193438246 672480427 700064004 142628578 802581416 279140871 973655892 800905741 598005728 935768930 668573394 207197197 649003003 270174246 76144766 315632510 875459369 359185050 528086919 473525359 758981160 249109513 189948776 344668617 795917722 549344159 348920520 486734532 302843834 285724416 810790165 350603652 574459989 873908008 1 38 777 11244 128419 1226846 10161959 74764168 497121432 26344483 38234873 423642505 376339808 863392989 917340710 353019266 355701734 828153534 204362640 374924405 607928554 963790885 940721850 687219775 764705852 876861874 763291630 981930457 551085656 980270580 505906881 983294521 135354674 135665519 630173290 212355830 143623144 227056594 817242891 163435465 418550307 731605596 289566443 285968813 433396374 290335437 260134359 257166798 296375223 99595679 459082068 507135523 972388714 133158519 975205558 982374421 644050428 996778111 162109063 746906113 514292299 926426755 356009260 196659267 409916170 325494529 655002543 558511285 36446396 471095084 174722764 671116976 160891233 868903396 304037581 23612943 337881011 234387037 370561646 356075504 698718914 535181667 514726084 815242029 608023573 448544035 835833664 991058290 399256230 20531824 669361826 539724566 760387110 830813942 547045707 178050500 929198630 6813905 110412371 858816899 809729618 833864785 232951975 485491061 613385270 553071180 627954610 952757220 692906182 748961577 662247263 52513186 149763764 145530822 33882391 453364543 997405166 992558694 759602854 84367345 100239977 854081961 858205595 486024240 91555639 177882871 949083392 519037398 556513157 228484413 492836072 589348909 196163508 266626335 11245627 157404436 270481031 638406640 490889097 527976504 370488458 823400678 322868722 206357234 647142926 768625346 265191551 148038615 363341916 267722164 893118504 738977503 565582757 762106365 849369394 766495732 13155357 515888816 523640060 647203814 437352666 546684558 961386555 7614498 893885274 936701598 428062192 113231261 402917050 409965843 165984892 799921270 659405770 509144023 774701607 842603658 487390464 251731862 581859608 922860080 258383681 201597752 292594441 460903867 638298912 848020590 765105850 965506327 844776867 575276415 85481014 653985938 197424999 197600210 989591463 112466859 918937916 878289962 30252094 561367106 701604983 794157139 205106586 358551581 218730442 820317821 718077344 742273426 343977802 723940137 91227055 889419899 835334285 445942872 874169472 806494972 841559090 34902341 936247116 742348345 932764662 776531786 136341990 609226011 962126351 692609037 492230872 512261831 61424189 202712100 557188069 23267751 10862209 780311892 698216821 610626474 445698906 548927052 791636623 278469086 802570473 843652647 214889050 950325814 545811188 732525066 799299048 547938769 119233118 836166054 515368215 821018309 703809789 385697728 474302192 326687407 701322950 753939342 860741461 608860184 481069405 497217661 107822505 538149776 65872865 267685484 630211463 833714775 127007356 988488267 704390393 326686679 330510067 968474337 860095258 865223840 3530159 602833824 943838253 510792598 862215682 804647558 57277705 379631476 611335785 827032941 500396827 166974973 950996383 97277257 336237474 527425945 836169765 13569792 45600126 103702022 589110361 158793934 917834123 750227633 450511448 228174293 380815071 984828008 35225572 19924799 316530723 169463852 11894443 83625994 27918722 725825514 510537357 901592447 560692763 386943274 409576331 409681305 19743037 901841314 504205848 287987501 95070522 999713439 52172335 458657276 716446234 960325619 967217606 29400294 323715881 571473809 542099425 838958945 826022366 215456133 111542899 27057122 264098733 414451664 367598279 660361161 317432327 788309656 482969647 453723335 307123116 46250346 156036134 550671015 501877998 918162544 672414507 744250791 519150731 449335541 717241257 798831268 772517138 286300330 910111510 66350225 850058429 996528049 454249733 463645138 33673728 195487971 700828817 25012182 447505308 968790402 312778627 684898658 698549052 965513947 825161447 410399245 428579579 669192144 82412074 1 39 817 12099 141295 1379381 11669611 87657665 594899060 695536795 226472285 640458905 794561570 378189352 472728269 218438573 56516519 255055733 845027144 588332091 652544873 575593478 251899261 421780632 446749115 397384403 967249876 562965804 307548860 910064219 267557957 532097834 694036707 378870548 124206593 109699395 5415029 722948552 875697847 694452268 7553293 132421363 106964105 391245927 870340375 243365738 69805673 199865008 75486973 171179760 109991897 220793643 513746719 106419838 540171765 580499245 759007158 982900537 645687882 590392656 601803737 221575615 697448067 153409333 368742411 593478736 779784392 983542304 533669091 167997680 729893362 841704349 760614624 47743042 998724205 972938209 77600320 536850090 695359058 769331095 966134679 528777379 695035445 387545073 911151592 242062595 521446824 889535341 920252167 112865832 806555197 118151259 625842139 701618487 790273468 694977537 572862214 473466414 246109368 48621359 353657541 554932622 499105369 867797665 487345603 842033962 519557065 245850790 335288378 782811146 892240358 338051309 826545456 41171254 334148733 152569170 144665017 941279118 897754414 89241104 416864510 41530804 299074740 73588196 959211062 109470038 500259918 366443802 403320596 183957534 992196343 652194487 652679636 980112362 896443763 694053263 85474084 793481845 36502549 113761902 13660255 295744749 768030597 559676644 267907464 329732897 34721556 481917917 470669881 496023609 35319413 426881953 436183525 539581676 797395436 949513087 636400441 684066319 283217124 456809507 742722246 708837224 1825110 845476655 721485134 509524702 571748192 313097600 164720049 83489702 463694600 122519767 438333196 350973050 742760174 292313656 699166885 733491013 480543050 245749577 741817620 207993307 244579067 622422144 604751887 899189402 151409381 217727618 880477312 214663719 394263729 196688383 548030201 726215545 464673145 261250632 625458514 838784252 982491280 700533618 585918514 160625577 639912412 329107337 639996475 820595096 822718095 278815123 496262265 918547360 8027724 726754416 823448457 260321413 863184482 650858805 276099402 685460415 954079520 733965175 676833996 368637623 143549481 304621819 472579474 749596748 116386311 410243381 633945382 411647917 177570608 616578162 767744928 61290651 523112125 276619822 15151789 253528389 167816966 891846580 541892511 341041750 391023167 293092921 243156326 622723871 473135257 726189187 379573236 555335821 257038714 482079083 723871307 606515981 65251208 632383753 147352575 594192641 924833549 483314326 808069004 770319259 427864560 25642674 464671587 569308215 637300329 923466624 23057035 86870702 983746124 846059215 574808201 554549209 446310553 959681948 778636627 211592095 516682914 291911580 587928798 427680003 894209596 866648165 679666232 460484096 854394115 982195268 822495481 835383529 431162040 830468499 195346596 57036658 866149457 860543178 818146210 279107618 892401239 225036974 868558986 685134666 744469605 156127522 187537334 788919638 909025900 672187019 217419201 384265406 616374282 378322214 141913342 501653295 461070473 25985020 589549638 109433868 888240019 931367280 762349235 234613827 765084315 611038359 758764450 286873014 382512476 382119459 20294058 943700532 211933192 58390954 180966724 929698288 805610393 509211182 866583662 775212548 88368846 726939816 185342247 229877142 705155204 200856219 36832958 610458570 660966337 749737121 592806565 894272325 480779946 649154472 88597955 74084666 744113332 528684751 282107891 100372245 756922141 58776739 981772435 924634098 951039927 397719622 577729727 762973087 736969640 674672356 297937804 986319572 149411109 496025335 118765897 173573997 13186371 696131467 139811703 497652080 238358226 252091863 126575962 416549513 112043953 769546766 210139961 218718185 975953506 930028805 845629302 57030776 852433935 836915594 400219298 622051773 829969111 114603161 10751254 909008878 579282117 214070865 563200757 1 40 858 12996 155108 1546584 13357338 102391268 708914679 491589996 307979410 602522471 317222127 290284759 54099411 989042041 349750818 106531062 706143382 63807262 819412921 144007031 937903432 671633208 144280187 535961584 391683158 665684992 173615217 173957993 353557533 689224661 70346145 249590014 418977958 826283746 394602103 916349862 513826761 491750575 183159109 757685121 418341803 274891227 642914114 790796259 588464975 740365449 551222753 10565934 35820801 515689568 211177017 828019707 68961130 155306993 295844962 698696703 264483577 967049520 615265667 559761896 719262960 509462378 575657367 591920899 676732702 723371825 327050158 311506131 94078284 608080285 992236405 137506625 399044419 458634324 553334522 801149022 685520978 446537546 993927587 293142441 349812890 364132070 129851348 857298051 877404263 877505804 63808796 43779853 597054006 757518688 847719064 814336009 295491019 566317327 427355879 99632937 271930495 211594531 907085661 370381473 40651392 893659649 363630034 486697292 957988008 762036357 927839193 855832860 336383816 307639758 266751066 682795763 757933830 702637096 416587519 241670221 803239702 991067388 753770489 69318095 379601638 829408102 918333643 833524181 647446668 999853061 600717076 736359930 166694847 912637361 883248816 334184966 360770954 907814459 571070899 760625736 543003305 12232839 27415041 235755079 155935992 895456358 299525687 387663753 430722193 845849975 389897647 157165043 232374231 709459451 819494807 873294798 982307907 723241456 529916420 190269000 832006535 157577121 119818595 751958343 818604698 923214476 455357809 664208514 204222119 358021985 507909159 532713722 447934290 550255949 9030523 204809569 704696131 798537153 779574805 146334295 422444856 763243391 968318292 409596303 730176788 661449533 145680243 291092743 406566554 840725280 859336604 385485264 540592314 491573347 430591599 799102625 349645352 953856191 685505744 968883032 548153198 991972402 298640488 335784052 560792641 200482497 534424478 835919822 256133832 789502694 815463653 367192054 711296060 505894941 749371649 586599852 478956964 771301542 936596369 641013477 895880622 275251735 709512313 675062513 900057226 864601515 604121575 213439255 718556713 352300658 293209273 62461535 212741657 925233457 601757735 357273411 900952265 337965737 654516053 138964736 683012438 388413281 151113816 328964247 191920444 84786019 179152386 346561188 643354711 718267295 169193229 252223726 887596939 657097686 142103925 40078284 150004901 459569297 459199105 789641065 6481222 858687076 375816137 147145108 520309635 748217920 667457550 716254093 186260954 725808394 626037945 743543562 764478177 601933842 797462265 777370200 654651513 156072819 707272486 178868661 27986290 925976600 457000898 540704905 843382395 769084631 760118502 476552208 749317409 710185045 964800796 516878606 266237510 913933501 813693982 336046538 762072594 997287607 756174558 615699332 325935068 478725181 294206110 71125626 862744505 369229533 687983312 908265361 496504119 960935105 69879109 315010091 778995602 757128123 249975621 699329744 984761141 255696873 966070938 214893935 551564463 316442626 532269369 314110968 128028415 969165598 561496103 817486578 282697706 480617072 509205119 834540584 277705122 660874354 778117470 366056531 831243822 903068403 672944646 441340373 340680954 617276976 849516577 560088434 230800586 10428026 372559113 922230949 889642650 244184042 533938488 841639506 817920213 336934324 44823033 565545678 701086145 241957483 114182239 850726147 526783422 115816117 835376982 659266467 815849396 168028335 255187925 748491938 622185783 663040863 743392515 163408177 383060357 31556416 794030948 934245344 258437764 379321408 40236316 660469577 655665845 690942361 375378322 568352979 602028119 317437606 657543398 100015852 252684947 481051042 964341166 522946308 280791483 467949044 475945690 972019230 462068105 580258224 819125286 65219413 675919204 938373431 246074242 416112669 990084376 992206586 174382581 694468435 670357482 52707698 430228891 194064984 374269653 873105421 89789806 360326019 422866288 247972613 990139142 766813630 25619403 929658745 91230876 1 41 900 13936 169902 1729478 15241768 119176344 841399673 434809990 446105964 492649140 758977149 206041682 323715565 660084286 595902939 912996958 734408694 639760787 253066665 208103163 518638879 141246298 316067064 932295902 638352197 835906694 518593201 772224592 710767801 155069328 87760296 888628863 85616127 159719113 852745152 116208329 603162784 598162586 214665773 928212607 364268988 422947444 91651894 294508512 306449339 29129368 721764444 23720919 155935808 134434641 906918132 581645037 673925534 656820458 712140580 940311261 639783029 193680127 625191701 485391283 454129733 912047676 531795443 151893083 16212124 506754047 491882623 143293012 25311790 265858487 730580376 281408346 313354998 904477185 246774679 76212745 790588368 952519623 156839403 194467618 872887052 91963369 534129628 238356180 632320800 58443419 722943306 618550091 33518175 519583410 960079192 538023159 305123951 486152058 294482726 518323725 455607677 182021187 748135143 512410493 35362801 719659644 317014598 528329960 583008290 443175574 659178079 174647583 349497845 577399146 818913619 271472027 656817275 494680790 969710982 229444476 267631925 175671131 35511369 58752774 135202754 944159958 464206230 475819996 314325811 754861491 276808552 810159244 91192489 626570800 590621471 514780234 305537247 801654104 149383516 787215362 114530579 859617326 613074050 468568467 919259772 617744284 340905322 985953212 372028816 217079653 938494776 284906842 769978385 515786223 285120775 375534381 675385916 665832700 133450834 3874364 408375526 770616302 276273159 413928636 723794836 198571707 678091222 296508406 529916658 588863591 413257244 498474249 915935032 120501359 836927142 230121084 774509032 870826787 489996192 917057075 196187219 383821852 922336284 22274995 748507616 607632780 183109949 339998525 507933598 698781318 498085612 803731847 473820207 901546035 302928184 865394080 114078163 2199878 779942965 594445523 91527221 272107811 718335802 365412741 52329171 414520032 494974650 300177708 811610962 146810674 337728819 506402762 403329973 694340600 766854981 757139989 188368338 788752320 918847437 928046733 527551285 479184799 517252899 712149490 791491255 238449676 667119615 757940899 445679476 734062646 326185889 40504124 623294475 807102585 697275776 960233124 90479243 277423126 459856976 523164613 283246190 353589088 214300387 783487356 692462518 267488040 851918218 799153667 810257248 109085516 633189413 670646041 913414538 526057886 701571781 823895555 366072317 141394361 832809290 464577360 305577012 512815120 121404516 195457318 321946163 309097012 239601477 94799504 314416433 43085740 639634392 892727867 559091131 668748148 422889784 711508368 676630033 634668710 364293294 844937242 751071408 322260215 891789141 187899827 511558264 521391391 670781806 509672700 51147255 62331255 681097643 668432081 698715101 46454740 726474418 934462337 72103891 408373632 957100449 670661469 786800623 834620545 287400489 490496888 497846381 189806313 912940390 809020495 703284720 835793884 605744360 923348658 214377202 697918809 343995053 445012242 544883273 475774494 73159748 664916820 945806189 388033609 184443581 891139166 132967061 662232592 630310273 296941879 926467100 732662520 755030683 373067237 200501225 132039597 621016442 864116597 199168443 229224627 19895297 392227721 512572983 888183257 954225811 362992884 408318299 664465052 828120392 703374891 61248349 16358204 241119413 30565637 838212406 921697699 543334430 89858526 273185879 355471309 304528048 507574008 476038937 789196651 57644735 932966132 292240565 284284800 198355642 844613937 375170024 881957600 108981244 644631978 730251746 563646094 15703371 891969119 462467018 842418885 184776107 20489508 525173823 93913531 199936707 49296883 500271791 9386940 42793104 102301079 299925062 242848544 157270543 567750735 512260765 540910896 473863432 123756576 867793612 940752336 189701376 338838501 163690216 120916067 790468763 680974009 939542025 299064055 752326705 668302564 775312490 929999123 713601128 593704708 595301628 539445680 220384571 492539730 572951883 264745653 946510661 751486844 372815432 445849920 481560920 887629330 46438187 433046906 550746520 68280122 549536967 98170304 942092421 657076175 85959544 736296914 244774210 196059783 968298850 183375217 810099519 413635020 636120983 396309504 740465895 371532101 1 42 943 14920 185722 1929132 17340642 138243024 994832181 548192008 829424358 702470585 488681655 275370643 835638795 810867407 286977068 950047225 83539435 44629372 288790619 507410843 264046736 483012816 672138691 875194556 651203850 66911617 918075656 674825734 94581776 415282344 303997379 819537616 622429217 698967413 751254549 420414807 687830513 601402264 434289505 724948167 754889253 808542135 995391960 178813332 724416372 177739106 814105099 753597104 45856871 272275296 786414287 511285559 160720229 317562390 790336119 868224061 359611251 78736463 773457035 927802445 421722380 116775238 364696053 502866895 626441652 490807991 713262576 797949369 598695934 260170588 82830001 494545919 272206045 443643728 598266021 33015507 884148700 307476402 959867411 216334812 800291904 985570368 488188448 107147695 538136243 662412600 979298525 134498654 226734918 727004323 749341953 119616289 344235011 179701806 771727176 867138213 462181714 886155872 120844409 637609736 732957723 950929297 917858187 787591285 658307576 752393246 363474545 410621001 994736846 177814531 780475306 862888709 592093607 579502147 557845688 288775481 603183203 577960148 788283409 673824051 683888139 877184660 633236685 114600324 443874806 243845462 737247494 816215602 301818289 678209727 613605938 858234475 818583083 638002191 955539556 166659792 402119583 136117938 121601666 755992562 47984728 295575049 499852111 307179145 332974068 315732357 716712867 640162541 867854182 934376752 313718034 59903781 946384843 119557570 525136020 151571916 798992199 641098837 260839275 993458171 824535499 355644177 761912070 816737774 16159145 269418274 606453921 360745230 8968332 697762673 987763777 660889863 735951723 644168107 694447061 112348183 530007620 3042837 764274326 848173528 194620935 635775962 259196720 713828904 940082694 457694335 838811079 742877821 825043434 999682813 323541591 50872352 337477908 513975090 485543671 991738379 437900643 771900426 686428428 563411325 914169111 935692665 43568184 490175371 749564693 101137943 245839802 603981104 626386341 386920859 413292672 913439917 70347116 434898910 144090153 824132212 891175519 132402569 347193520 969072546 16729602 608672301 618817500 911982521 688615529 732174336 500282116 497352932 456415575 878875953 316115544 915703538 598465482 596140294 730305232 164832432 897815573 166896959 324516472 764718824 566396641 914517008 874306816 779763109 852306547 611269114 292511571 915381300 758955270 257373679 74625589 121789415 230596845 205840454 916544901 23902587 416402779 293269031 510816400 975368660 955188220 72244504 561311434 137072009 127537010 860723336 883260674 394382836 913512596 497775666 206616201 483790701 11643758 543373789 107216374 536706614 345207484 197739695 416959310 802020491 883579389 155472766 707726533 878636875 137339984 387604391 170286771 862464509 93116703 698306089 277231574 157624181 518482505 545923209 301838767 429107456 65466197 400869145 603396151 201146053 29560436 908247428 740900666 645622178 468181946 182006817 585006092 39427009 901513909 575103140 643739693 969005418 413112711 121940507 949419798 274176335 533655948 73448571 447893873 303200166 406062958 327948494 399154885 680966803 676784794 346165530 118434942 634041854 219847494 927409557 731595298 204066166 484721091 397391612 62697528 613046235 363210072 588627148 359818291 176675393 710790103 31891420 193284227 13322649 80677012 364175866 156203486 303397217 540753075 969185318 762928705 479974322 873609278 714679223 243389411 893917661 730412727 540295939 380888528 199480073 111615382 501213077 699982545 83674978 340471893 589623231 135448371 354059110 416125008 490338358 869847423 644581498 153365962 261322947 680966984 400282844 542955010 604680600 412088220 680278649 139286485 860834305 469429775 280658323 253030904 2560916 10309871 297479762 823144855 871982081 47058346 963847165 382927224 356584190 324565827 306141977 910279795 453817674 601981427 979339306 222338413 904561649 382529080 408856660 854658577 411827225 670817056 827144476 223389693 471934610 930635535 587441381 722797748 95690794 663628478 287716698 646651719 701670514 288321331 90367689 303151955 540716833 449495113 614473847 768187147 779428778 859329178 317839203 24311574 208713726 534909824 569617669 779723332 951823587 262620278 508684571 644816282 124674019 369884532 146396384 993989514 828097325 353947367 356630001 483119775 36683277 829372562 480348153 416969202 237164413 917166508 673670902 955993972 550159722 115253791 571208381 883450110 234414978 338605160 465632072 975880238 1 43 987 15949 202614 2146662 19672862 159841410 171958174 857707214 674952199 863564473 694487987 218927913 150857334 64522123 242512102 726888439 233627107 811786714 114239005 343074532 372330107 720689358 467711835 904517093 48140523 445520536 151023837 477389409 167654505 524330326 826025786 750662832 873751815 63739722 191556854 667326112 50500515 441625511 782830742 400734038 564497630 921910383 845548941 368028935 749018447 103585045 796556849 628596101 868979841 539520158 627354569 90231323 417433082 56768496 355579497 422451590 886349503 72956900 803725461 415871073 683643384 621063238 193330057 325926450 277754812 24871409 448472012 886190243 823962291 441987145 894908057 837390023 862747763 91512877 722912649 93349481 545810047 913016979 515556016 298546360 734212089 844284728 136068973 71028614 122223407 751306630 44843394 423748616 386401231 812571458 811253207 883210298 108253088 777750730 94398075 357510258 341016668 444595182 421469474 846006439 697364303 430219357 145159 329923811 555736286 145037472 50858159 758063180 409311835 199515197 849732459 429458586 110831608 601311986 405029768 899721594 362036575 3616348 447767827 718164293 455022502 154627334 632024645 923207902 841801838 418932384 595460287 460605434 188513457 767682601 51793196 194981425 929803954 504733978 22197692 870666331 333136663 819520200 530915500 599537526 53266589 48676597 387019415 413134249 89916173 988538195 741237674 580557472 340811443 13472882 840030352 781975641 296220934 702357371 942050407 935085214 845987731 799577627 872670633 692587304 440284632 702895036 10589510 109084537 901549736 680965380 523560865 14608855 766098800 955736031 229070295 918139336 762087315 15060087 769624318 210516326 269537431 932448778 651446512 367308406 624037144 927670291 415521073 854675140 947034643 395133007 858104556 792426709 918444166 282314711 96653546 423079321 469451942 792999037 308400615 330587501 691818222 53917678 568461122 362577365 775464857 904714011 845440210 795470521 568880508 666239878 183860147 125507811 545400921 401495311 3467092 430876347 332849310 96436924 957680475 836934713 150232592 891109199 995835861 145792868 255284669 853681633 801676454 45857933 127560794 137690320 534209092 436059291 890838261 134212816 302504982 936257832 761720727 269396963 28197218 59083210 947207164 442972791 384169121 488722025 351406087 443097712 82956552 698141640 145942108 188889308 734290094 387705377 912805029 973822420 47485510 507370861 221674431 786661915 91335607 856760661 173031704 864904090 599152735 495185408 938099393 556362344 990758140 995900803 254599934 462199704 5008078 665636661 527028350 642386127 1829553 551952980 424017355 108488740 701380336 806666866 700141562 59441909 362171728 894757457 445400929 773238426 127546419 723395394 338826564 332919619 340737249 850054615 184058121 13063831 278558952 698063140 498777528 72607237 345269132 902279995 183690503 772520236 708689187 233896476 458831695 230994551 41124197 206351350 689101399 262700029 620939252 892377787 428085255 694339277 213848040 916329377 192795757 474268014 561285670 220016093 638297144 193877561 647642810 64716523 5417153 709160560 438820650 471896153 456049785 424945489 102312939 179871925 155527933 66018018 519349428 575834851 366155295 196027859 709388961 444696414 108229719 111474967 169464130 765045351 916818004 674916990 958919968 932259128 849009441 829390390 846317162 253991616 482990034 163822353 775754269 532037321 49173712 212326050 301906174 678424573 534302771 375782334 160287870 855370313 341617592 25457804 708941176 246832732 903916100 546588049 96029971 706821232 940560978 101534792 337492719 856837601 613769045 707646199 812028723 616833643 679800396 535428679 224426630 413895724 784683428 431644219 111092914 661756720 639659700 41894591 68359952 43802473 952730000 823133424 376059765 707785553 822330735 771301262 948220958 908479296 864547297 515908783 27167717 175015260 401476125 721945851 298498970 707819205 838011772 889483594 356594984 693435347 967781679 401435494 355846180 333596320 628919505 303558980 984974994 113643042 89409518 612893129 122412730 114900098 810658251 247580260 945287301 609126629 492005778 772356444 361927818 440145503 858752994 174471327 210890472 769016792 638211867 546015263 377533141 892710683 705066724 412035898 913706912 989583745 102815427 296051463 435828877 627348761 994079761 369313875 909339708 172995194 816793393 474860389 821690532 962160124 246051373 970475428 561698902 165844443 708639335 918973613 861542417 207950600 197794802 563223285 448456804 787570186 926930606 566070711 279041721 162328562 287318056 191225488 14318341 585550504 409974535 697728497 891226405 200433586 381575055 638337683 483277973 755030264 867834356 962849947 821535631 1 44 1032 17024 220625 2383232 22258540 184242832 375813872 392612893 231706087 882424931 687132034 689650073 577977876 303878988 24310937 406963663 625468735 582435950 41660062 421950986 98962940 938709884 758565048 969234571 703952131 900436492 658647225 285611947 399326780 419454732 205387170 983950227 49990302 189001672 62673927 586296391 184361166 506353667 438069708 256171907 825943859 951340167 368115756 522855639 198647246 263328246 450011807 434855284 725807775 648411666 18383140 128787399 387148373 905324825 158891954 656234845 213026076 490012707 365468167 200221292 298615515 290107567 35072337 317672326 60118064 676291945 898619095 494511021 35193707 681989460 255539191 6318676 181981289 309123618 769843578 942743189 29734288 954472400 463236670 747980714 175643037 260101113 77874147 589524374 710018290 567729062 854908844 767838566 521233813 535397022 395450772 519565978 430844324 691804767 750969410 915664434 335442962 327801393 599337662 151524696 372580414 756807473 202845724 578628778 324772867 495203100 594805038 176866440 134364432 797477913 981614510 128692174 938852792 42148884 122641852 370944239 473851910 935488807 532851475 689984371 438315593 696398812 66001022 428174065 54501471 80878480 666016821 47295976 813797397 317765605 714997505 258919731 82884010 661027522 582655484 361252385 24311003 432884688 368733632 23821090 792526029 846601436 536812192 29313630 382435159 426147993 517181759 645690342 270896281 775661220 283600768 240876557 135665693 104458079 616729602 497103691 828815240 86098789 998656307 754065783 488969594 91503702 52278308 883359011 733253122 448869387 985543203 116773170 582006344 860482711 481797421 498040658 240829616 836032529 195942841 508465042 970760583 262117458 515914406 802808161 784332475 374122343 146224696 841597534 586439935 244148601 788204315 767547799 776362337 510076278 624681830 364806405 36907700 539421266 800828005 512242954 899834647 163376162 50294413 18654970 84289561 55576943 421249957 34930346 752291330 162276973 265235612 648593820 174309283 472188614 715911113 367773012 121970433 269868616 883985007 980070897 514347496 412293057 574601560 116830355 45453500 562859501 189078677 827602581 712444490 316586780 733065979 840949184 60074648 135398686 424428452 321968689 410040315 273128858 471407472 574966766 873880166 875045586 51088331 163730111 878321231 726127318 966070068 992549896 363335253 89848987 723352311 66759579 406269326 227087300 150259572 36586234 121181736 671327424 433664784 948164313 657988535 451431758 352880293 341991927 179834471 17796695 709446365 576526708 534876965 620591563 749402589 628280366 213414310 982746106 780180633 458647121 527146575 210950823 363805011 571210392 912463620 153315485 532024632 427468951 230879114 869803861 964025520 480715223 895116735 766188327 419338263 475074013 158183698 899486620 551866464 830407504 385674668 305150124 25769566 438519248 46473036 427624180 723264512 651472006 264633252 457374493 476392005 982968243 594462543 141658727 489344824 433530156 442633667 193279091 506366676 618868695 731227096 902261819 499005142 38842574 647293009 470120821 963932040 826530559 427769181 52186234 243569284 806914289 77294303 605077946 125786816 193185124 669741115 146483601 421911450 244025223 607708016 920909811 503255382 458139691 962827176 614853461 60315827 350564197 429760397 252570002 854719144 336843776 342192419 596659989 924243516 172320579 980212083 387574794 749118912 796421442 338721201 731277700 423355068 842226704 398877706 643899462 276311394 413568057 530987554 558156380 825270018 71652153 764304967 575174245 41877959 189656159 729954858 472722511 759829544 285982254 921037034 543320666 873711613 829723375 146980729 88768980 242470712 9284436 325379730 426922557 253585643 473459335 496125795 212116723 579959160 525505189 681915634 797942363 691505794 454823298 342255990 994255712 284908161 275004161 935102263 472107098 948357256 856671615 528973823 649773881 963952149 308388016 911396221 251193820 721175020 199750213 907595892 491208059 66513541 911357998 28185931 408941602 745821213 601730782 8869191 260152446 11616084 492782894 282010506 115926945 586669273 760307966 135350671 730510115 701832702 230080848 284697593 182609947 968668397 822892958 20031466 582030222 113170973 44631330 117449096 742186715 393019551 475653487 44400405 854169605 417464027 638137059 767027912 156446839 993857936 340495049 620457258 138844665 409760846 178352112 82788960 388732194 649306589 798058368 662337136 564354859 463324080 651997437 151329929 798760314 140393196 82249686 534814725 624568021 130746531 950081340 74895509 582830295 80288213 896322580 930247101 961634195 343840503 151542664 791653321 891526646 512046490 292522561 321986893 483787584 926080170 410378864 504638099 532986681 138953386 701001827 64586773 800287681 592917926 845148767 612516645 103437292 360749745 802262044 905182790 741928176 827192105 608668686 275550867 759837767 768468707 652063776 969103143 1 45 1078 18146 239803 2640055 25119048 211741156 609749448 185787670 784612981 979654374 245960280 15201333 958496287 21110097 315107827 742613444 350112648 551346765 22689059 646342016 52427180 113726997 20972491 531552248 493279562 92962089 319571072 658193556 921146440 975234478 32484025 175484024 620442122 566033382 228886883 301912152 137109958 37427138 531183271 684452057 239066445 806400806 345167706 766401402 659593100 342864185 793254425 754419464 829307575 253460669 788296808 455700810 203460090 299960617 672027544 662169751 130171479 226661975 16040291 641167104 11608362 92735361 828424038 151425031 757058935 838944903 705030989 271605017 832315720 525711262 695893337 524834613 616761109 89325780 498691877 390082387 413410547 86170624 733987779 857386717 121183471 378540433 791481061 602874536 895775257 706223069 9499 916233199 610175789 305910126 402086898 380865911 987929263 784720236 752249361 533065111 750214951 512527924 120069833 497034065 691332267 542878776 324018841 841280375 368737196 213532423 972352910 856518833 695976280 832491001 482258020 288928023 37469870 669147935 728824530 312167670 98462828 664815478 37466991 488559701 805407681 555656112 449333572 115257333 422614443 217564969 709154128 523463461 73425486 892488653 72758100 139084611 245397266 356349189 258341975 374070936 726599734 907199192 145474167 868900328 80767170 435742131 604761267 550372021 238314098 858506407 406280874 734533546 294613351 569709112 578499728 811514468 971780315 806793934 105431100 109183449 48863833 577768093 679710969 415227663 41263734 575857153 381654592 178237376 962188807 96401085 816699360 379978 698529453 815682387 657011537 324418972 693645417 573047105 308103161 882958960 454854080 319280881 638681315 366562235 558670399 767575020 418970310 599121706 533764150 589341596 935247125 342450103 752510984 17885861 270962366 936052758 754048953 578853463 395299411 975776432 660809842 714104917 664542262 888472526 460099640 981638523 92874960 177231620 389704303 815325394 892076514 810821143 435904186 382196425 459031152 355917826 128881343 657597142 768648132 489510758 615223177 785945817 514595120 566588750 607013232 187911920 428934627 690400146 385480557 274884476 214574226 202705516 78809920 768678876 104566183 54811645 783466377 78714677 225394661 571378521 194681502 425310485 768219090 304793231 206900396 615627160 652872143 605935098 888495311 608958308 684600222 150382009 670451269 632074742 29926906 676412361 727588975 541140282 152873820 396851079 644404346 44361987 675992732 795525664 898044746 408945421 518637916 428148139 754863856 398182352 901207212 713356422 978366083 314876385 700685480 450639991 507197672 750335365 694787156 659670168 536065922 58255852 874808151 601680063 300562698 308983506 144763409 291800793 77526020 485403753 904665596 240987930 592380858 131116194 318805303 40941643 253699630 655235690 431599614 508389196 766960976 64307752 83604788 642165815 298107337 143184667 782909601 97135064 800759539 594114128 462420032 946857620 578998109 847963761 556321528 57391815 681855904 181815656 486333346 837072759 524567487 328595763 549915998 810586503 921107919 625157836 520890292 832156974 502972509 844559735 189855766 821823028 625190873 310510259 495827691 683011136 462720297 218315456 558392392 789434995 973556645 730884239 996176654 617108310 869866261 672230385 823462275 454316955 569646417 836576125 486906178 189726176 941091111 447563926 715506888 259006307 152570437 178255829 705545293 756368978 655390691 445318929 656847742 582354283 964611397 757172000 601301680 424348696 51484783 19240319 282677827 308226295 848392338 155829926 371112122 224524783 972970693 890401898 186586738 229535528 744395297 436751188 287103606 767393594 221149011 725319915 148703291 142739608 565503173 66967587 579759051 568848401 146971072 400042251 42796974 930117091 516575412 958322295 49672443 25502320 669481138 837449618 7837933 569472200 125364493 253977071 938687542 347213905 923213402 374713215 103889249 423021360 42560340 446498368 893011213 263552847 473020638 594960497 638188472 306243047 631678307 460262893 114330448 196301356 120279822 408786998 213927614 687965452 221650209 761159253 159653422 237951119 705996510 183076481 962207888 939920456 729428244 527536009 933629825 48104537 426892607 222940406 156477133 294062878 856995315 562470362 935041969 210948751 968306167 842365144 520781012 542464204 753086923 742421303 62000597 644679235 71406991 633199433 272647461 452692051 412108892 971466694 51102980 982720545 17172841 800141833 835541670 112517201 389287762 451060806 667438631 372888210 71363616 925222882 974951293 516878304 717488009 957226897 42671831 558776576 623171604 305500795 631070922 102790598 482941055 578335399 805101814 173951677 379242816 368922629 730730546 873191134 654555294 282999571 122452789 92227034 843713012 807240125 801145367 399481174 81195926 292593849 487745170 77737545 120468361 275563695 294725580 329691567 323060707 128192468 940264172 278390124 237020514 693096287 868976326 357620751 777387506 600499325 283061659 552760619 551343042 374674126 67456147 355451755 309520773 188033652 438124708 963234900 524570431 966112342 609641134 592345761 1 46 1125 19316 260197 2918394 28277069 242654144 877454212 274093151 658806941 733787098 12686768 373279778 972151771 700803085 323660829 529034010 15342046 14519348 617205005 151932388 986173050 673700068 544467810 964286681 515278420 556139518 340574896 558301369 203169010 995039572 456888812 641435231 165153057 140522292 660622205 195293121 536816710 963078287 7389104 204944482 754195920 468292992 782743724 983001140 866703245 496885028 44229335 385957410 278539952 468949573 420982388 313452346 869856814 98935497 204399132 112520568 660616311 229799510 228233497 492491671 631417681 54933646 149425728 621332861 339088208 164640489 629238436 824895721 154091091 876001533 408513031 998443240 581987593 639413342 564182232 919538600 946772636 882410774 972663920 656083562 92818 266781815 775781699 746031288 222736672 245153398 853395663 612580130 998160370 644539418 268757618 522753001 961290581 775849265 167666621 207332842 699178165 754169098 895892786 110804927 209717022 224332021 783584762 168756823 846734143 820517435 567375827 214226237 514413130 94334242 56417678 452070622 302779049 643793464 45275321 465081583 721848633 905142006 304646178 594655979 909007937 734286949 886228757 175346016 613908391 543890160 182181133 880150750 840065256 833202286 948664835 99995047 986587901 143761895 873393215 472341142 369663112 813013714 860504625 731747262 545041246 583231233 427381591 37913038 537312918 219404202 592801409 727962123 878247573 121527391 62101177 856133295 688561557 4927109 639161755 216890863 944378755 396352437 878653962 905668778 386987830 935008847 899701147 100650401 955831377 336099358 325599961 655390214 368725260 410912881 868037904 255016544 51552711 320078126 868474642 332377928 241406268 35418479 170587950 775390874 598922434 616742075 563583865 362204509 606438997 894815935 49721736 43588534 841088924 703571407 258771291 525460849 233015242 491199815 325653075 858892862 519655123 115437087 727491564 149427446 582972761 204458210 871579136 737982490 129452738 424878982 856725917 336920826 730532856 841738688 738232572 913319995 816486040 235770118 427698004 930569686 569011751 212446463 508105319 803897811 496189040 948372030 432798655 784691260 809769369 691850475 577558004 62715847 947764060 196109904 506172286 447735266 980867772 417186123 46557919 986790130 277584037 822619391 621076591 388367593 68342324 236699370 119970164 657351210 878868802 794459312 436412351 290870119 503296346 564802634 58773734 218770767 842309450 694735121 712067611 605426442 634737321 598847809 189964014 104895974 463967300 12836011 374171101 422839429 769990513 562838372 23465799 935303296 758855803 832260567 373886738 362866660 831747060 745193763 842521525 971131364 323409153 328965945 810807795 987986960 514599613 697337301 518676386 255182547 320862033 438306682 656059329 246817307 296427451 518314128 212813255 401599307 322632262 651271379 102975853 978392574 171788197 425477753 865141598 200230496 352371432 128877128 483645145 487174027 207964600 565016864 366179929 769999162 980709292 279413092 778963675 322935221 775556840 152203885 621120920 754303914 144652778 603456104 397495432 911648885 161631342 183072379 436197254 410415743 654211646 998944149 660332881 659092994 407158213 993390015 62237745 342306369 807083806 460112259 598009122 34231667 354435262 237881432 155417941 495370397 996923439 566380833 854227389 702509945 42544433 284265702 294553519 149363293 27077251 84953964 442875086 52560456 900402134 145229989 73758817 191009440 854994962 638721915 122661714 185868970 77283521 869275152 18655948 313026284 709600476 473812539 310414874 881320952 952459523 248120422 525865505 878780555 987277088 840681160 676792790 412115993 140030918 974129475 721196483 656805079 905290349 47935904 451920705 209356056 551066765 377150442 379611973 957219941 151470005 815021467 645207971 427463516 863082600 325313522 124436219 624577057 614877838 455973640 851822937 25478672 694724523 841056623 311625157 733217559 234679922 488590424 672460808 393534712 496209755 929085969 673429468 675205481 477828672 541309112 421475544 478494486 773959869 620756099 817295158 343366608 474968096 138789669 1261477 581929663 193727536 890932863 10823177 566850894 774883564 16714666 326523886 969386350 297903394 330603328 602435368 640131734 422205271 722651837 536164302 931111157 119137488 728875089 985577117 985476890 17918009 917723365 472997173 89115107 916366434 502538821 230961609 303908854 617061492 736625515 131713887 339453221 738950163 633262610 426758031 238112917 779917917 838020550 66019448 650675847 778117049 610691432 213274580 385410347 146924004 364868172 467790003 719723336 134820272 752419541 477278067 249134595 704095466 475445405 736299900 879265925 152926089 845846141 495967193 279498385 571884448 188818617 160584873 477296264 718325160 376134972 29944771 994040918 900529668 502667072 63109761 493032874 781301515 461834757 82343644 481132313 514447042 33858163 779555233 748165656 15592733 72424287 572256728 868353288 210902382 873738113 462082508 116372507 317994063 320661573 43412947 698165915 782179405 544478699 376533191 591100852 669522818 718785967 689856669 868867194 692259782 326169003 372530014 278822874 245059471 536750832 337386716 351509954 600150419 771930319 812137400 268506281 52663290 576040882 250206016 182636529 238498760 83748189 556944302 408365242 877381661 687598532 206936328 93325077 375585930 311118119 840250578 1 47 1173 20535 281857 3219563 31756649 277324867 182983217 698763572 224340727 130185913 938338213 457596872 500667258 726272186 242531386 490324006 697265581 186365736 123707347 149163288 89978475 985283339 584841356 785509005 693590689 256394211 919078587 671307265 271140497 146527772 508423202 678732983 767147115 418422439 470469749 411147184 246424306 580998273 228726677 964726100 955513349 444565758 668191949 622619432 792082487 929348032 601983375 875985614 424117930 730694027 740975250 920167707 500437835 690210005 493329701 913508192 695611331 515433292 682059417 760833644 299135864 144219873 937695856 872711671 176916492 348891212 334587033 49595521 749704350 806067034 773327860 183297942 590517602 642228939 275941227 305722242 165986509 644370063 71211109 994092320 193064301 728492690 76982066 397536959 240992716 459846893 745186728 715105963 864528752 8495685 753272988 61740216 691254120 133693721 536597663 806042634 964981978 37162518 164112239 637759779 841824460 829311498 573961610 622092127 856298148 23010232 90428839 608194623 46765621 381935126 362962166 452925715 585602790 768818647 88708532 942042803 418311021 521378251 499003594 126819649 281499536 951375086 146412815 883657287 598780576 163659546 959278876 560517421 665346319 929162776 164983787 77699826 451232846 342897676 483260356 399557298 954841649 593150358 617703430 292815034 3827776 631211917 629217856 387782790 117795063 964508694 824603912 347867132 217932218 808071571 466159291 919428338 306867765 310085680 347929669 103137973 445637697 645585557 573817817 596387955 672995733 578127218 402908135 115353766 244018895 365778204 555835033 188328988 247770780 214263457 844226086 575129810 998900133 642186262 886066131 9933705 609621463 398319031 223920768 209742125 519163806 74615456 814536291 217678251 205417278 306418059 464475526 330591049 614947407 841330174 17421893 462387593 572435987 550253368 393354277 125715312 124567536 533400012 599797708 528236566 670562226 867851657 488086533 312725786 238592338 37063455 385067665 487783197 118051898 700641656 71282753 435781034 103306472 894876554 845215295 848516 105817111 455104275 971250603 659938256 173306291 702024160 716038595 487118454 170680030 880373959 881689085 153725278 74926408 143593976 537712434 635112688 530810156 750175992 211491335 495469862 938874667 906814766 530322450 654580872 345961757 642596517 63791230 944154048 670877958 937127089 186748489 915912734 209561832 276486399 229476817 558761321 226557040 227364465 312169979 745218623 741668605 732242764 141121784 862165956 612899824 26577011 945385273 251793938 946782241 731260038 244678083 406380914 904932224 539791264 681567161 903979395 522313639 307479666 592336384 274405785 808155145 116439879 610551965 466693001 783212908 356926408 441684284 460337698 929744044 6376955 718008169 946348344 771828366 973818233 895371075 977137826 380169268 772257849 31334848 472603919 411133545 814229722 268412684 269984826 925865608 465876593 90547760 192297128 107314233 564985934 624177562 939350415 164843750 127698384 375467125 733175906 272735725 449176665 148653187 981408173 518395662 539465581 376426572 523018009 244326749 117372211 788925566 998562683 66998700 958836224 912519308 243826028 372775429 817271079 249393258 980817911 290157076 803249202 54296904 967950499 259586185 891527285 197070576 229312354 227197980 799697366 938796541 780082061 90937344 484280959 41280132 365255061 357940368 463355056 931322797 484716584 549219150 927360223 836260928 974511964 168938341 138740543 617041490 552137623 940491117 311751083 797191757 581186247 747525174 464341615 45074367 877273095 118604361 820377975 651223472 330450797 299712101 798402816 155978336 76119913 279749437 94544299 576902970 337821847 762491092 205421212 628488971 912880168 293200919 74345429 106904237 117214135 997309646 440117215 601730010 44099662 275878624 579837056 734358196 740396992 105320711 497734455 593389397 892951024 375888233 469355971 904918031 759963217 159920933 656339936 82028185 635763012 494109863 887577439 747214684 51704021 870514178 310168296 344440919 671389360 63636271 867520663 253359253 809561479 515218518 735486509 595414813 855063768 809133514 296905455 403829884 13706060 521945271 406722813 508410711 177195219 735377028 927006199 631467156 561281245 747357347 2938426 465345595 461810717 851331500 936133185 709629669 764183492 336958888 999734612 886346709 929391292 283117585 489898780 493902211 377860665 233672406 313970515 130449778 925311516 829665465 27964512 47478431 502231137 77997958 450616449 231073347 922519036 577962078 74763491 840109600 825429573 325716083 462423227 684091307 610980133 146344297 230702558 840583842 568780809 837872774 467777629 918753619 868791683 692922864 937076083 487643358 553595896 717484731 882361644 739294901 547711612 781629368 821302751 368923697 499416921 374122329 146178192 867117817 743635071 435195107 43377741 23687167 878990481 99110158 262344925 137035868 292609610 625408058 171070693 281506530 350758492 515834894 237732608 828774443 840832942 431386878 857791323 291378943 894741249 559570546 881728336 216217018 497590589 210577047 706853900 528807154 595327246 243687205 679896105 276389715 520651743 981854062 782051052 628779694 482906971 308000266 98460224 329039027 663453182 866909422 358447817 756042580 103701857 530184673 82157052 864831037 833622836 129557279 680891914 903510655 223117879 584910098 872789802 683398377 818673921 424793316 162530200 461191009 233747923 764377859 866276050 20068038 599500015 419525268 504837656 702339633 161478719 731429464 9977417 955013204 944736389 868359658 303235910 570685307 762022093 973456873 491776893 191155949 1 48 1222 21804 304834 3544928 35583250 316123172 530785426 505824986 901343166 615485588 789348648 698747334 657848248 964586458 476943547 698458295 801769019 257736525 542576587 933572174 9542546 488292838 779820677 404677231 568188493 931045218 340825658 205993974 185959269 78058729 445883053 431770274 625502333 180277174 804167964 894493650 995189957 934651928 779076648 286076285 196236261 433504295 796345349 46608071 262327913 615865530 569486410 232121371 86175778 154003167 455565337 592635041 449778081 946011559 315342730 523152035 660192808 984322053 918448908 362530845 976500024 826353996 979299043 20455239 106430716 169990095 856925551 339927417 872925000 454748405 844111855 778706572 953334777 367875579 54603227 952723870 746089521 114899675 378338080 515017450 901556480 75514717 118586517 750778341 164215503 398032943 932771419 175973529 371281707 414155738 136305212 176477492 529591042 473449712 104580388 917944592 711611694 275529831 657391663 618370464 182199238 863262145 671572410 926093081 964697471 20599847 886336884 976845790 332330830 936899217 469444206 333826539 382006323 404644652 86283892 711449573 711524895 240243757 137744674 52585102 502954368 568353873 424768720 673699213 453807002 277591996 614231800 858886730 933633627 855960053 795294602 320736325 160050137 741837408 875372187 933116510 439299086 339530899 998809886 988163112 414204450 626581582 425958595 547450689 257877182 25212376 487090639 693248108 736165691 261048117 530252319 667332870 224234420 283256778 493030047 381167115 959191937 567700201 408470930 456733167 877572444 640070139 177231251 53889209 630925282 764167042 903138510 822950867 161878067 741376139 620673064 828400388 989198090 398235498 335164252 650259410 895482301 288920533 986020511 960531109 692510577 743863232 159848129 639142915 658806616 286815941 569150064 996156909 474086872 377428234 108191201 968576455 934066962 520785392 648351310 322768543 500047228 717012630 366640002 617370336 747113890 647615517 420668064 485924194 28548015 242698362 20265134 481161073 780894508 716872330 925052871 809234518 209608950 454869307 42621234 266915957 548835092 11648368 200676498 803279760 609790836 522043768 787672824 264643232 571421826 762085826 854807719 119023111 660310435 945098645 838260736 592383406 728604232 586121308 18945549 62079587 8000021 137221342 936745518 867913927 937623778 183088542 624248829 606106136 815005922 728188591 164502140 885086995 646575964 60630781 250914884 619961376 835493684 1794097 350786557 222634027 605402916 871984975 140157610 784428245 701028584 784157139 199990301 49282014 806191394 544636448 696393844 625422532 306981977 200109353 819880255 622554727 966234587 1715755 884432882 186517679 414057470 559202957 356291776 440462056 76496043 54502936 82793754 693820485 333532789 139408482 538301356 908601203 663844984 277481039 494620179 126148065 101563902 543304970 40138848 255494176 250466774 181548534 183041503 553027506 468172977 571880068 685135214 70030015 431414252 965377675 285528459 577690235 3039911 424468115 149219671 315258608 442938842 340124780 620577523 697442435 606981307 195766252 513624332 160814831 144529981 626344971 929525101 167384034 985564306 757660450 674490248 404160553 218780132 253152109 588527766 276135385 293545669 229980166 406532593 544661736 944987368 74067610 979465423 367319108 691015763 308068787 270297211 892899529 571121326 682341094 508186314 992592910 570463576 551864557 443417375 102996223 180706669 66278518 547390018 97982020 377733797 642211092 809569594 442856622 912786312 563198351 549331531 576357131 891027263 77805689 816522985 731749256 313952972 411776160 795006290 22615421 348238413 716260746 223962550 78670864 47765882 267128253 587371111 927656165 192469863 806624234 136996971 759497678 646978177 833527505 472805550 754214240 960030895 232746388 490616131 420542303 904038549 210637836 74285318 144447351 742135765 244372617 87595635 852731251 594678505 794681848 228154101 363702627 673985808 239196945 836249623 602064792 462168907 430511049 331217937 84426505 529390112 953694258 768941491 296949641 617567965 759210871 554347066 314959464 855978152 459336095 416019714 554419893 643616814 307318600 193723511 342506504 737708842 961578294 644413804 283651295 449519877 262823100 438065978 195660179 15479674 929627357 712657286 867475048 618979059 615899609 290553872 46585860 675146342 899293157 138576244 932939832 413352510 228638502 577046541 52412367 271101119 704058715 716195674 113738084 976781966 417637854 201849275 137988263 703452509 833173534 774723430 98520292 647910333 702073064 101667724 93613248 4773372 993672667 598539625 298728331 547262186 609550837 42278975 203431476 764589375 791435299 273439277 15186943 247517820 332116413 672582410 88991345 573172714 370502342 495515460 486357723 529038430 112617630 9655079 54905538 630913486 94540925 694069860 101033114 601510215 405093272 877399916 606786230 712700446 365826653 440611748 222502187 628732942 260127071 415183336 331627148 603111841 484627861 252203062 603610758 918118836 775502591 558836403 458735214 903545723 229008632 239177179 70767308 751925156 652119146 980361868 450630793 63075950 714904102 795480239 196855664 446357279 343343138 751184330 353543327 265335039 291055365 141693974 952501609 772988967 982806649 295006336 142133453 389243658 551050114 837354729 288032982 926886748 940810321 996269340 544323652 123254721 449847916 164321665 408440169 540527971 235735087 384560805 888470688 711171300 414716347 219479361 559050803 610845133 321258507 296543705 253557800 771631909 466270561 966519146 100544233 474799959 147649345 956135303 808272257 279282920 472357219 422709994 530025514 999788009 64593897 709199531 479060735 311654131 943520011 427742758 799287390 782392773 191335024 830990096 336010037 237942831 237453992 695887098 398366572 529644737 344086296 862051533 684436865 317549101 968659087 366641438 1 49 1272 23124 329180 3895908 39783804 359447204 925733384 746545659 165655001 158091124 719304162 111160209 171158550 935012406 874008903 988755604 608336289 351327718 211049418 970686245 441380023 920727544 396494781 218114186 934368772 753990221 203263446 488226646 946324350 642441651 816607227 122420091 629716118 498106515 488881569 100763230 814241373 430998026 986590664 188596813 238499794 887765759 719310391 819612870 840885905 584773429 811468143 396065785 368868801 299761844 617462619 308704442 206242421 833439007 106715469 970135543 972244832 66232618 207050932 577078708 955731123 103929249 632790957 297717977 280927805 856143814 140717794 889342899 570959166 553036683 311778062 833874032 321035571 629235909 60666525 19636232 889773198 837811568 283828621 499062871 459250525 468391935 389843786 80632526 462481073 859711240 66143264 831825780 518914304 998480225 496960804 480385724 483317701 923742113 771054094 630267330 478946945 527928962 674723787 882998613 123711144 324674723 964132061 961988031 65215295 858250635 924300325 577545014 241841560 172586320 726876085 210684082 897202470 742850020 161301259 120853804 344539574 836860211 667275920 72688787 930704832 179668299 861726583 168665810 834696469 672920894 419563732 302874180 454615268 934181182 119694911 779976833 216225187 244379028 586838513 942544272 397970796 155525782 435250288 609294947 697035870 790138207 313089121 451259481 904475234 15500998 428233316 352796372 805867626 355791012 191743365 390372515 86113794 224579645 34292553 472538607 244805809 799547326 350596592 550928379 248605526 858957317 809083222 418025439 717379009 843111164 748566980 795763411 344249103 246799165 468081584 533360568 97839725 814208152 370784820 149643652 648814350 586462723 179226570 323415874 413399345 830824722 901264775 785155020 673315179 883230707 320461657 209574161 896187167 641537195 580708044 615201169 907420567 226969633 44823693 653925850 618905940 556249274 683808190 595045606 406684866 817926872 498013040 741888764 255307898 750076370 226664326 45791371 138249186 182084615 925519009 32002450 507648904 36302093 164244320 134446595 176304234 443232913 204696272 377207389 330407781 317016375 255990328 346121343 776903928 865285835 180645765 94169320 523805568 66571932 958229276 706032441 157122799 174128102 265560802 960871567 814597354 840895548 702037 848074074 17426708 276377856 55696613 206160180 32721003 453495162 587538197 204676036 610254246 936113705 842825687 202272844 145230437 624393323 739106533 700708897 523328161 691038973 656087189 213848962 927815456 921255504 609475698 113463094 529085932 807792149 579407091 163833313 694176222 471399591 346973697 718259544 297359882 892552532 451373341 120883534 8029910 624607649 606649877 815313728 231664869 673443919 615486405 94571095 110823650 950289120 646876432 928906934 684469503 297251947 919054473 285157267 967739040 274416446 465229888 656873003 825576691 53305194 539107135 609069516 669008004 585520763 526072937 91836656 101778461 538228891 424599066 719851020 234795290 701214554 914481398 497763115 504286064 212679726 409710596 134500525 154608785 554889670 267547678 851784437 749366191 681515762 587313005 604179607 297539881 51380469 30897443 988568867 430543091 168358864 325894509 131217074 122226126 289735266 2541560 697428098 339809826 339814711 568813016 256466301 865405619 710940331 7424767 660900037 729644940 444 450105203 690939247 459755659 92556107 42398758 782901298 483436309 73995240 784415989 602791285 655683750 744368335 684929720 939318197 1937536 94209990 544006669 195169186 297173575 151918090 559870646 425964491 818978660 571568643 60393204 415731654 547756555 991386612 383053326 997830526 963081859 107336308 898219937 906988404 550036125 981857264 691293427 481189647 501756531 316529056 476096058 168221459 165690115 553028411 960794528 453386272 963889156 71983103 494867184 462967097 635240847 989817132 23786457 968645733 163475174 884798755 971346358 8231228 947835970 751371876 21594745 702982989 997528759 30899466 874470660 839706683 64336797 183002010 415355406 851375333 802315034 662347966 459017349 83113197 807783874 686211775 665742332 548408223 38712773 947065654 224142524 544199777 554457822 161813447 59932464 324817969 826816639 159675767 610260222 802832692 962264291 230527850 654881259 493134625 56109407 491401533 163680598 892934948 889185132 78662275 741528574 616484511 204394884 120980232 4959172 884202370 468625389 987185268 797914336 292935354 542176515 965256954 25044127 701524209 669825969 264620823 983915826 463815578 325409981 142164710 946513145 626025918 890502327 456729879 921471703 889764153 10834930 550258959 888111963 456661896 560525119 254574198 379302005 359197537 748972811 432885247 174603143 495215302 304225805 499574 89067439 956588800 479903186 900293862 918419160 874312513 779518268 750190343 34999197 204187488 29703716 310295240 212734818 705461990 880565621 542764103 578132976 871657196 920555643 635330221 603836039 905337022 446003049 531829391 914627500 109964459 793773872 883594493 588890899 761763418 850946563 47045637 406265955 398330580 175033998 98562597 74022406 109783010 888406279 62923507 851720727 920064661 659715101 731241623 740764931 68490942 26861674 832409630 156628069 65837301 277330611 504531610 621094682 513712789 824543274 863846088 522929299 50674845 205053841 391074024 703020653 598865065 977680558 126857946 571772915 596794646 195429545 328266420 36051456 451216030 522276964 948367998 561406981 389510759 585943971 108053297 459413669 288907310 136029766 802792879 520247265 414339912 337619243 597859489 40005835 350918 321070418 199829979 141119131 515535428 350920730 314377413 808898947 900198037 799762368 570476717 244997759 402733111 626061442 103647198 938528989 898060580 652361018 641847472 149112119 134262079 887185896 606038263 859408453 950373236 692335861 405660442 565431386 959094106 393940636 423632434 612413824 143336067 663257107 9730523 471491852 112828340 936303905 998673093 55233966 416039620 144081002 565258672 539355694 202448366 14002378 539019751 307827209 288622328 788194350 570120788 965430343 472467292 
""".split()
X=[]
N=10775
for i in range(N):
    num=int(ans[i])
    index=i+1
    if index!=3 and num==1:
        X.append([num])
    else:
        X[-1].append(num)
n,k=map(int,input().split())
if k%2==1:
    print(0)
else:
    print(X[n-1][k//2])