Problem:


Score : 600 points

Problem Statement

There are N slimes standing on a number line.
The i-th slime from the left is at position x_i.

It is guaruanteed that 1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}.

Niwango will perform N-1 operations. The i-th operation consists of the following procedures:

Choose an integer k between 1 and N-i (inclusive) with equal probability.

Move the k-th slime from the left, to the position of the neighboring slime to the right.

Fuse the two slimes at the same position into one slime.

Find the total distance traveled by the slimes multiplied by (N-1)! (we can show that this value is an integer), modulo (10^{9}+7). If a slime is born by a fuse and that slime moves, we count it as just one slime.

Constraints

2 \leq N \leq 10^{5}

1 \leq x_1 < x_2 < \ldots < x_N \leq 10^{9}

x_i is an integer.

Subtasks

400 points will be awarded for passing the test cases satisfying N \leq 2000.

Input

Input is given from Standard Input in the following format:

N
x_1 x_2 \ldots x_N

Output

Print the answer.

Sample Input 1

3
1 2 3

Sample Output 1

5

With probability \frac{1}{2}, the leftmost slime is chosen in the first operation, in which case the total distance traveled is 2.

With probability \frac{1}{2}, the middle slime is chosen in the first operation, in which case the total distance traveled is 3.

The answer is the expected total distance traveled, 2.5, multiplied by 2!, which is 5.

Sample Input 2

12
161735902 211047202 430302156 450968417 628894325 707723857 731963982 822804784 880895728 923078537 971407775 982631932

Sample Output 2

750927044

Find the expected value multiplied by (N-1)!, modulo (10^9+7).



Sample input:
3
1 2 3


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
x = list(map(int,input().split()))
dp = [[0]*(N+2) for _ in range(3)]
dp[1][0] = -1
dp[1][1] = -1
dp[1][2] = 1
u=[-1, 10346805, 505173406, 3448935, 252586703, 2069361, 501724471, 1478115, 626293355, 1149645, 501034684, 728213351, 750862239, 154642063, 500739061, 689787, 813146681, 530020404, 500574826, 53176148, 250517342, 492705, 864106679, 478710734, 875431123, 400413875, 577321035, 383215, 750369534, 345184375, 500344897, 613236998, 906573344, 909404455, 265010202, 295623, 250287413, 702982351, 26588074, 384880690, 125258671, 634398707, 500246356, 325822021, 932053343, 229929, 239355367, 957666960, 937715565, 285925447, 700206941, 176673468, 788660521, 207742394, 500191611, 545642673, 375184767, 684392054, 672592191, 728988934, 750172452, 672300772, 306618499, 164235, 453286672, 230928414, 954702231, 567318613, 132505101, 826236916, 500147815, 535357001, 625143710, 643977358, 851491179, 800137963, 13294037, 818316198, 192440345, 443168950, 562629339, 333461074, 817199357, 108558396, 250123178, 706004085, 662911014, 448394794, 966026675, 730453340, 500114968, 307806011, 619677687, 871079004, 478833480, 210635231, 968857786, 412477805, 642962727, 636468154, 850103474, 316934129, 88336734, 631168420, 894330264, 98541, 103871197, 691685489, 750095809, 816608692, 772821340, 567660786, 687592387, 247879177, 342196027, 695742151, 836296099, 461626899, 364494467, 647145776, 375086226, 611655763, 336150386, 878132907, 653309253, 80082775, 500082121, 236301945, 226643336, 441940676, 115464207, 106949213, 977351119, 579025168, 783659310, 76643, 566252554, 992776261, 413118458, 467700340, 750073911, 319222320, 767678504, 286785644, 312571855, 69036875, 321988679, 428641818, 925745593, 899398307, 900068985, 781525481, 506647022, 58891156, 409158099, 322647401, 596220176, 694333424, 221584475, 735914136, 781314673, 782672967, 166730537, 294542007, 908599682, 181880891, 54279198, 916229628, 125061589, 627280163, 853002046, 894797356, 331455507, 630117616, 224197397, 200059126, 983013341, 576329647, 365226670, 631342724, 250057484, 977957724, 653903009, 557433593, 809838847, 540596473, 435539502, 866365497, 239416740, 54745, 605317619, 329897106, 484428893, 72592471, 706238906, 76976138, 821481367, 883301259, 318234077, 492514309, 425051737, 522439540, 658467068, 620740629, 44168367, 926879747, 315584210, 608745641, 447165132, 459379653, 500049274, 819954256, 551935602, 845119005, 845842748, 465164407, 875047908, 516176717, 408304346, 547992455, 386410670, 656155420, 283830393, 403633845, 843796197, 600045990, 623939592, 110177740, 671098017, 397425098, 847871079, 272772066, 918148053, 656696772, 730813453, 191533392, 682247237, 481056319, 323572888, 765733674, 187543113, 481370737, 805827885, 444487027, 168075193, 857185095, 939066457, 850244325, 826654630, 36186132, 540041391, 725140829, 750041064, 770791890, 618150976, 235334695, 113321668, 949456609, 220970338, 243283194, 557732107, 482798267, 553474610, 53271281, 988675563, 641548483, 289512584, 910151118, 391829655, 821599808, 500038325, 254650728, 283126277, 769268675, 996388134, 309128536, 206559229, 65019303, 233850170, 290359668, 875036959, 761602663, 159611160, 307457058, 383839252, 736878415, 143392822, 804914106, 656285931, 972354148, 534518441, 804159273, 660994343, 129728147, 214320909, 745797791, 962872800, 545489387, 949699157, 267593135, 950034496, 46546003, 890762744, 772311381, 253323511, 934460160, 29445578, 13063019, 704579053, 543722809, 661323704, 16110440, 298110088, 287572995, 347166712, 32847, 610792241, 25269233, 367957068, 576834947, 890657340, 897228501, 891336487, 238422128, 583365272, 646185687, 647271007, 605536233, 454299841, 851095285, 590940449, 987946674, 27139599, 189220262, 458114814, 313463724, 562530798, 596469876, 813640085, 415959728, 426501023, 55748818, 447398678, 469417924, 665727757, 565247386, 315058808, 590807920, 612098702, 43009590, 100029563, 153875633, 991506674, 864051980, 788164827, 507071403, 182613335, 882381930, 315671362, 64095674, 125028742, 897535593, 488978862, 537218590, 826951508, 328795473, 778716800, 223461437, 904919427, 292710969, 770298240, 886820348, 217769751, 541582703, 933182752, 360027594, 119708370, 488091109, 500027376, 501346565, 802658813, 78767315, 164948553, 339452605, 742214450, 363663241, 536296239, 813980230, 353119453, 61723257, 38488069, 675218283, 910740687, 702316409, 941650633, 88633790, 659117042, 294736392, 746257158, 526341725, 712525872, 638429797, 261219770, 585633619, 329233534, 666692219, 810370318, 154816578, 522084187, 503692783, 963439877, 664258756, 157792105, 389855564, 804372824, 421711682, 223582566, 489233449, 729689830, 52530661, 250024637, 724490140, 409977128, 106407440, 275967801, 141200817, 922559506, 524614399, 422921374, 762261886, 732582207, 663597097, 437523954, 866074710, 758088362, 689678963, 204152173, 393616357, 773996231, 993189863, 193205335, 142880606, 328077710, 539526746, 641915200, 146090668, 701816926, 966466107, 921898102, 968842650, 300022995, 603127159, 311969796, 927175165, 55088870, 461561205, 835549012, 181641898, 198712549, 352963721, 923935543, 846009435, 136386033, 185767489, 959074030, 774215805, 328348386, 567473980, 865406730, 223902660, 95766696, 898111146, 841123622, 575074733, 740528163, 442127049, 161786444, 245304712, 382866837, 705658349, 593771560, 977152495, 740685372, 260890989, 902913946, 82495561, 722243517, 823429876, 584037600, 98180669, 928592551, 621202340, 969533232, 432069672, 925122166, 727293635, 413327315, 647908147, 18093066, 661343385, 770020699, 305409876, 862570418, 819106063, 375020532, 663386830, 385395945, 875760059, 309075488, 799627406, 617667351, 520568197, 56660834, 631599121, 974728308, 126233684, 110485169, 632515182, 121641597, 543372541, 778866057, 55682048, 741399137, 795430879, 276737305, 400019711, 526635644, 565484533, 994337785, 977335256, 820774245, 525443218, 144756292, 125722978, 455075559, 738337102, 695914831, 877114246, 410799904, 116902314, 750019166, 979686415, 127325364, 325985908, 641563142, 963321744, 884634341, 340055481, 498194067, 852477869, 154564268, 70799178, 603279618, 63309850, 532509655, 513532160, 116925085, 639156821, 145179834, 794294007, 937518483, 288788499, 880801335, 99485519, 79805580, 849575841, 153728529, 333351584, 191919626, 882267751, 868439211, 332767685, 71696411, 109965702, 402457053, 539148433, 828142969, 620468543, 486177074, 357530826, 767259224, 301222630, 902079640, 655249313, 830497175, 692325384, 564864077, 339029554, 607160458, 453328266, 872898899, 294433753, 481436400, 588550336, 772744697, 529429158, 974849582, 497504772, 633796571, 170301081, 475017248, 742113727, 523273005, 507479849, 445381372, 322331154, 886155694, 611219686, 626661759, 206913543, 467230080, 535205154, 14722789, 675383931, 506531513, 975626587, 852289530, 834700730, 771861408, 693070032, 330661852, 869581885, 8055220, 247207621, 149055044, 16016555, 643786501, 153126551, 173583356, 41351903, 500016427, 817766007, 805396124, 606651421, 512634620, 47260389, 183978534, 329686575, 788417477, 281706335, 445328670, 597520046, 948614254, 715412675, 945668247, 488388138, 119211064, 738810433, 291682636, 520817179, 823092847, 838725577, 823635507, 581945405, 802768120, 221389844, 727149924, 849330823, 925547646, 503809331, 795470228, 210303098, 493973337, 552051809, 513569803, 315805035, 94610131, 188921061, 229057407, 134544615, 156731862, 61118252, 281265399, 811308099, 298234938, 200015330, 906820046, 593811447, 207979864, 773211120, 713250515, 370059249, 27874409, 140571519, 223699339, 598555255, 234708962, 799141704, 832863882, 323672494, 282623693, 259059838, 157529404, 90924022, 295403960, 93540068, 306049351, 37317571, 21504795, 218898924, 550014785, 18559696, 576937820, 352788547, 495753337, 63844464, 432025990, 188133448, 894082417, 698181030, 753535705, 493685442, 591306671, 983184224, 441190965, 657357133, 157835681, 255244558, 32047837, 806690335, 62514371, 233024061, 948767800, 493790248, 244489431, 13807375, 268609295, 137565815, 413475754, 481495678, 664397740, 430930710, 389358400, 92783557, 611730722, 285728365, 952459717, 324301694, 646355488, 545345534, 385149120, 283414775, 443410174, 149408274, 608884879, 979879667, 770791355, 12062044, 466591376, 813097932, 180013797, 968056394, 59854185, 908380281, 744045558, 556305099, 250013688, 865271270, 750673286, 256930630, 901329410, 950079306, 539383661, 688086960, 582474280, 411778234, 669726306, 748383769, 371107225, 990910731, 681831624, 649818872, 768148123, 624851682, 406990115, 464529483, 676559730, 81094398, 530861632, 928126254, 519244038, 503214276, 837609145, 827599427, 955370347, 738866689, 851158208, 640419759, 970825320, 684423765, 44316895, 35411311, 329558521, 51715444, 147368196, 547182830, 373128579, 432886260, 763170866, 585745119, 356262936, 303383706, 819214902, 694907037, 130609885, 956534599, 792816813, 940533274, 164616767, 708294624, 833346113, 642429532, 405185159, 84883576, 77408289, 858908407, 761042097, 280306424, 751846395, 923089563, 981719942, 360548537, 332129378, 560158384, 578896056, 436376181, 194927782, 522382527, 402186412, 922811040, 210855841, 21673101, 111791283, 663877972, 744616728, 383245927, 364844915, 96786556, 526265334, 889166093, 625012322, 632592569, 362245070, 587200890, 204988564, 325456034, 53203720, 801665114, 637983904, 102485686, 570600412, 769694890, 461279753, 307163363, 762307203, 578959474, 211460687, 320898890, 381130943, 128067925, 866291107, 268304702, 831798552, 90394377, 218761977, 526023526, 433037355, 657451385, 379044181, 313015361, 844839485, 659024513, 602076090, 268053091, 696808182, 440011828, 886998119, 441288882, 996594935, 709909387, 596602671, 943258062, 71440303, 202729726, 164038855, 915265935, 269763373, 40597911, 320957600, 748043140, 73045334, 848496467, 350908463, 681982476, 983233057, 726268549, 460949051, 755864383, 484421325, 365973692, 650011501, 953396618, 801563583, 348848670, 155984898, 795591549, 963587586, 639482195, 27544435, 257437127, 730780606, 62579964, 417774506, 828050769, 90820949, 311486720, 599356278, 15278459, 676481864, 68564034, 961967775, 671021011, 923004721, 579642850, 568193020, 308119296, 592883748, 514574272, 479537015, 574822767, 887107906, 225575025, 164174193, 672036818, 283736990, 973273105, 432703365, 219861631, 111951330, 95857665, 47883348, 957503032, 449055573, 158017336, 420561811, 10949, 787537370, 507930676, 870264085, 741844417, 721063528, 675089749, 80893222, 172099001, 122652356, 465979424, 691433422, 858944987, 852829178, 284682324, 296885780, 600427004, 988576251, 299076167, 370342686, 414518497, 630445498, 243030350, 451456973, 746140714, 541247784, 530391710, 861121762, 352528622, 411714938, 215395229, 292018800, 165824307, 549090338, 884586673, 964296279, 201845411, 310601170, 851485608, 484766616, 776660256, 216034836, 617031764, 462561083, 57644436, 863646821, 3037686, 706663661, 329315558, 823954077, 698502866, 9046533, 384162838, 830671696, 729740092, 885010353, 755255097, 152704938, 42881702, 431285209, 104487908, 909553035, 642512762, 187510266, 733409665, 331693415, 198823292, 692697976, 616002321, 937880033, 724148130, 154537744, 805319914, 399813703, 185486112, 808833679, 676797602, 760284102, 351916275, 28330417, 985375955, 815799564, 495628384, 487364154, 489805977, 63116842, 428720029, 555242588, 83262679, 316257591, 521749131, 560820802, 451311813, 771686274, 38508515, 889433032, 530269309, 27841024, 557056904, 870699572, 291875932, 897715443, 14336530, 638368656, 912307296, 700009859, 374890913, 263317822, 717958549, 782742270, 563990854, 997168896, 397360785, 488667628, 954683998, 910387126, 913299108, 262721609, 972728461, 72378146, 169023801, 62861489, 492043440, 727537783, 554733724, 369168551, 294127310, 847957419, 955275260, 438557123, 893032887, 205399952, 688031896, 58451157, 700658343, 375009583, 563376828, 989843211, 299178531, 63662682, 903235349, 162992954, 665142918, 320781571, 512406199, 481660872, 473886664, 942317174, 46670034, 670027744, 109598491, 749097037, 923436968, 926238938, 242047633, 77282134, 741153817, 35399589, 927479922, 301639809, 131231084, 31654925, 97570323, 766254831, 776384448, 256766080, 937903109, 558462546, 962273454, 819578414, 80726769, 72589917, 802157881, 897147007, 847194239, 968759245, 933104687, 644394253, 602858728, 940400671, 120009198, 549742763, 968953287, 39902790, 124898448, 924787924, 496030372, 576864268, 511924405, 166675792, 22035548, 95959813, 833782193, 941133879, 739254041, 934219609, 613506005, 666383846, 692922443, 535848209, 279485021, 54982851, 151709109, 701228530, 446484204, 769574220, 846229673, 914071488, 706860670, 810234275, 454554416, 243088537, 979265648, 178765413, 509068465, 383629612, 604660079, 150611315, 288057050, 451039820, 931339360, 827624660, 20574419, 915248591, 988032810, 346162692, 25627965, 782432042, 225072761, 169514777, 838306684, 303580229, 62880499, 226664133, 900772141, 936449453, 640990984, 647216880, 946754315, 240718200, 696211268, 294275168, 751483027, 886372352, 642565477, 264714579, 98245464, 487424791, 622808342, 248752386, 753146739, 816898289, 842113913, 585150544, 437873520, 237508624, 235645586, 871056867, 546143268, 761636506, 896274153, 753739928, 796197476, 222690686, 528544542, 161165577, 375731090, 443077847, 68433922, 305609843, 888897411, 813330883, 729671613, 603456775, 9032278, 233615040, 51605526, 267602577, 24538305, 507361398, 171437019, 837691969, 501230930, 753265760, 541098740, 987813297, 470357718, 426144765, 554752921, 417350365, 170048865, 385930704, 431697939, 346535016, 796618526, 165330926, 390822200, 934790946, 749807203, 4027610, 807237232, 623603814, 287097313, 74527522, 819063534, 508008281, 496411152, 821893254, 804477537, 576563279, 745028170, 86791678, 350843556, 520675955, 599690510, 750008217, 877882914, 908883007, 574830049, 402698062, 154158378, 803325714, 425422534, 256317310, 702135818, 523630198, 697883834, 91989267, 135122033, 664843291, 47066939, 894208742, 144095809, 640853171, 918694570, 222664335, 508204802, 298760023, 639135115, 474307127, 789891326, 857706341, 587420631, 972834127, 896827273, 244194069, 982966968, 59605532, 554532368, 869405220, 648656643, 145841318, 581349539, 760408593, 288691570, 911546427, 544973368, 919362792, 58334879, 911817757, 896559659, 790972706, 592203789, 401384060, 695195075, 110694922, 464538788, 363574962, 793610323, 924665415, 410654259, 462773823, 997729959, 751904669, 118279263, 397735114, 171090347, 105151549, 714293540, 746986672, 328309698, 776025908, 415230106, 756784905, 846508920, 657902521, 328332344, 547305069, 107284582, 594460534, 382030225, 614528707, 47128158, 567272311, 894705269, 78365931, 322155369, 30559126, 614304060, 640632703, 364319963, 905654053, 322947550, 149117469, 817650374, 100007665, 10370353, 453410023, 534375722, 796905727, 250930147, 103989932, 770825611, 386605560, 642391724, 856625261, 509926783, 685029628, 688195417, 513937208, 153853735, 570285763, 161675456, 611849673, 18999523, 799277631, 393880635, 117354481, 456671778, 399570852, 461825710, 416431941, 784321245, 161836247, 269043038, 641311850, 331651231, 129529919, 282003145, 78764702, 213003862, 45462011, 507577759, 147701980, 395255832, 46770034, 207052731, 653024679, 70359187, 518658789, 258071935, 510752401, 21481995, 109449462, 434603539, 775007396, 522491329, 9279848, 942273953, 288468910, 352320534, 676394277, 74634220, 747876672, 672115226, 31922232, 6385788, 216012995, 299370382, 94066724, 261491413, 947041212, 524354518, 349090515, 858358249, 876767856, 802962952, 246842721, 101201931, 795653339, 147375683, 491592112, 27337314, 720595486, 158859586, 828678570, 415101573, 578917844, 114452441, 127622279, 560982824, 516023922, 901886121, 903345171, 346775782, 531257189, 555177205, 616512034, 659050834, 474383900, 394470831, 246895124, 373193055, 622244719, 86963663, 506903691, 455555032, 634304651, 340681590, 568782911, 360831856, 206737877, 353473130, 240747839, 705970085, 332198870, 607809961, 215465355, 779911384, 194679200, 825945635, 546391782, 699393561, 305865361, 19067629, 642864186, 488790178, 976229862, 873734118, 162150847, 549159561, 323177744, 402850610, 272672767, 144023224, 192574560, 87785515, 641707391, 8098683, 221705087, 909097883, 74704137, 882320347, 804442443, 793828311, 989939837, 549302718, 885395681, 277300971, 6031022, 53518627, 233295688, 220447795, 406548966, 767852138, 590006902, 760166792, 484028197, 101803292, 529927096, 209309202, 954190144, 362979662, 372022779, 606368690, 778152553, 630053179, 125006844, 219438433, 432635635, 554462279, 375336643, 17145911, 128465315, 73739531, 450664705, 958586691, 475039653, 661858407, 769691834, 186892032, 344043480, 933209140, 291237140, 587972762, 205889117, 787074040, 334863153, 506856068, 874191888, 602612608, 685553616, 214060084, 995455369, 543866376, 340915812, 111622549, 324909436, 750492777, 884074065, 708744566, 312425841, 665165064, 703495061, 205300419, 732264745, 210838394, 338279865, 544758759, 40547199, 3222088, 265430816, 514457516, 464063127, 731244615, 259622019, 914804841, 251607138, 685227354, 918804576, 57514599, 913799717, 902367809, 977685177, 598476962, 869433348, 970725880, 425579104, 662435063, 820209883, 800006575, 485412660, 374134655, 842211886, 440791863, 522158451, 521828180, 517705659, 137088028, 664779264, 205053848, 25857722, 992445090, 73684098, 158596821, 273591415, 62860055, 686564293, 508481075, 216443130, 915366995, 381585433, 241083500, 792872563, 375240995, 178131468, 986265058, 151691853, 56775014, 409607451, 579445703, 847453522, 525830960, 565304946, 484779585, 978267303, 625704751, 896408410, 223193025, 470266637, 247684427, 582308387, 38967438, 354147312, 247690148, 916673060, 909938530, 321214766, 659895474, 702592583, 929237143, 42441788, 145673232, 538704148, 441995305, 929454207, 665242400, 880521052, 936319876, 140153212, 321107248, 875923201, 364697832, 961544785, 172672574, 490859971, 113351827, 680274272, 200249756, 166064689, 170219057, 280079192, 950825961, 289448028, 788969288, 718188094, 402792460, 97463891, 23599726, 761191267, 797589339, 201093206, 808093154, 461405520, 354436619, 605427924, 71047771, 510836554, 737829438, 555895645, 837844058, 331938986, 748056602, 372308364, 307375884, 691622967, 879718945, 682422461, 966533388, 48393278, 662692749, 263132667, 264764669, 944583050, 636694672, 312506161, 283765824, 816296288, 96262833, 181122535, 519293978, 293600445, 211624392, 102494282, 699828511, 162728017, 933181761, 26601860, 496757444, 400832557, 283191947, 318991952, 312911226, 51242843, 456156770, 285300206, 777783866, 384847445, 85149940, 730639880, 211149765, 653581685, 627422586, 881153605, 753663169, 289479737, 887206521, 605730347, 777589233, 160449445, 693883589, 690565475, 371584363, 564033966, 36655234, 933145557, 816391840, 134152351, 366227714, 415899276, 513049480, 545197192, 335848495, 609380992, 121463475, 263011763, 873489519, 716518681, 641667833, 828725696, 118161584, 689522094, 119176942, 656507684, 674531544, 922419746, 711091531, 829512260, 433740879, 301038045, 8601918, 634026549, 13743759, 348404091, 885083109, 220005914, 743009912, 943499063, 915008761, 220644441, 230775128, 998297471, 103591547, 854954697, 830591448, 798301339, 446343187, 471629031, 154288343, 535720155, 172810396, 101364863, 151109422, 582019431, 333527615, 957632971, 252970271, 634881690, 431477920, 520298959, 301414282, 160478800, 664046345, 374021570, 529516781, 36522667, 460982792, 924248237, 62821283, 675454235, 176476386, 340991238, 910470262, 991616532, 10626242, 863134278, 165834924, 730474529, 844958370, 877932195, 612819139, 742210666, 56767027, 182986846, 564208090, 825005754, 374797530, 476698309, 580704578, 900781795, 379507120, 174424335, 497515414, 77992449, 835826621, 897795778, 174494947, 481793793, 34754742, 819741101, 107443718, 513772221, 714920394, 628718567, 275981501, 365390303, 537073231, 31289982, 821728117, 208887253, 265759096, 914025388, 68971181, 545410478, 281580290, 155743360, 629716196, 299678139, 178401718, 507639233, 844692293, 338240932, 992384518, 34282017, 225127977, 980983891, 7610183, 835510509, 495393572, 961502364, 658542198, 289821425, 14623902, 284096510, 147112141, 154059648, 944900248, 296441874, 518624044, 257287136, 377364071, 739768511, 231023344, 787411387, 329752744, 443553953, 498124854, 612787516, 623193964, 582087100, 308316542, 336018409, 983401371, 141868495, 415735876, 986636556, 157140753, 716351686, 869199337, 609930819, 672005523, 55975665, 280239931, 547928836, 329968255, 23941674, 717708855, 478751516, 260228545, 724527790, 697618226, 79008668, 680450639, 710280909, 917951487, 500005478, 731364546, 393768685, 272588669, 253965338, 100269313, 935132046, 464950107, 870922212, 535550476, 360531764, 801688773, 837544878, 784556152, 40446611, 15753463, 586049504, 248038988, 61326178, 439502542, 232989712, 109895525, 345716711, 921071803, 929472497, 67890521, 426414589, 760568783, 142341162, 911417592, 148442890, 367522307, 300213502, 865840020, 994288129, 472732651, 649538087, 779455297, 185171343, 905137563, 707259252, 233563102, 315222749, 666327137, 121515175, 162796046, 725728490, 376876795, 373070357, 866431335, 270623892, 579603480, 265195855, 467838576, 430560881, 812344657, 176264311, 506939062, 205857469, 513088945, 607697618, 501286701, 146009400, 612908528, 582912157, 335043658, 274545169, 612166763, 942293340, 860648473, 982148143, 843452503, 600922709, 444732732, 155300585, 740463286, 425742804, 537371812, 242383308, 875576617, 388330128, 616443610, 108017418, 489614979, 308515882, 17726758, 731280545, 834603115, 28822218, 554325596, 931823414, 901065300, 1518843, 736767704, 853331834, 858947284, 164657779, 127836109, 911977042, 850683941, 349251433, 816177980, 504523270, 539894809, 192081419, 105268345, 415335848, 91642638, 364870046, 334672512, 942505180, 62973687, 877627552, 509241315, 76352469, 927685965, 21440851, 44848205, 715642608, 543559161, 52243954, 977130960, 954776521, 687039422, 321256381, 717126728, 93755133, 900847972, 866704836, 270436033, 665846711, 92038767, 99411646, 567479167, 346348988, 733338448, 808001164, 222501406, 968940020, 287831617, 362074065, 197937149, 77268872, 299562396, 402659957, 230963317, 699906855, 257737040, 92743056, 269745145, 904416843, 822641038, 338398801, 123353083, 380142051, 300738558, 675958141, 814367542, 514165212, 46857173, 992687981, 447104024, 407899782, 894306069, 247814192, 532851754, 243682077, 624215049, 744902992, 328805416, 31558421, 266380568, 714360018, 965589123, 277621294, 677971117, 541631343, 441224167, 658128799, 361048986, 760874569, 569295198, 280410401, 419686615, 725655910, 884342342, 385843137, 695719960, 519254261, 363641343, 444716516, 200389404, 765134658, 84018410, 13920512, 697846694, 278528452, 715865049, 435349786, 373868048, 145937966, 345772526, 948857725, 752513310, 7168265, 410506135, 319184328, 72966308, 456153648, 79566626, 850004933, 29990646, 687445460, 339519901, 131658911, 144898028, 858979278, 6649429, 391371135, 450929518, 281995427, 563718785, 498584448, 686706274, 698680396, 21281488, 244333814, 470481981, 477341999, 945734007, 455193563, 396044485, 456649554, 915690231, 631360808, 828240169, 986364234, 232727010, 36189073, 10808054, 584511904, 923514951, 531430748, 164561814, 246021720, 704922884, 863768895, 255035260, 277366862, 994394746, 684584279, 626814739, 147063655, 381712717, 923978713, 552452380, 477637630, 434098907, 719278565, 573294721, 946516447, 418414855, 102699976, 926154371, 344015948, 932719425, 529225582, 602230114, 850329175, 484488353, 687504795, 448408308, 281688414, 77674687, 994921609, 173214942, 649589269, 171209206, 31831341, 497930085, 951617678, 378171512, 81496477, 785554698, 332571459, 337935794, 660390789, 430872923, 756203103, 563566019, 240830436, 712521943, 236943332, 316999703, 471158587, 878723277, 23335017, 493831895, 335013872, 862955852, 554799249, 469653288, 874548522, 143643570, 461718484, 398637974, 463119469, 509790785, 621023820, 364261188, 38641067, 726947005, 870576912, 333640650, 517699798, 428576124, 463739961, 758500389, 650819908, 573567386, 65615542, 774767236, 515827466, 629015073, 548785165, 507905352, 883127419, 848448516, 388192224, 432181322, 128383040, 905902909, 968951558, 761138263, 279231273, 229218135, 481136727, 65114660, 409789207, 49802758, 540363388, 365759907, 536294962, 510976424, 901078944, 993293227, 948573507, 275820452, 923597123, 190268133, 984379626, 337354017, 966552347, 640664448, 822197130, 193768530, 301429364, 271032644, 970200339, 740778283, 60004599, 846295140, 774871385, 989352136, 984476647, 720625436, 19951395, 126278400, 62449224, 302793427, 462393962, 34060304, 248015186, 665934758, 288432134, 185435033, 755962206, 847379956, 83337896, 781406064, 11017774, 955090428, 547979910, 539819778, 916891100, 92312241, 970566943, 418976879, 869627024, 911807969, 967109808, 347659076, 806753006, 316693102, 333191923, 236328381, 846461225, 585487694, 767924108, 229362320, 639742514, 498040312, 527491429, 754910754, 575854558, 470592747, 350614265, 983461194, 223242102, 769034519, 384787110, 582794592, 923114840, 835870760, 457035744, 169201887, 353430335, 330303577, 905117141, 843659749, 227277208, 234102272, 621544272, 883272962, 489632824, 637153502, 589382710, 283992383, 754534236, 208283894, 191814806, 74541296, 802330043, 578997140, 575305661, 154843161, 144028525, 894718677, 225519910, 587810372, 465669680, 27031466, 413812330, 918135603, 510287213, 113494796, 957624299, 309375418, 494016405, 598123282, 173081346, 284071060, 512813986, 167738092, 391216021, 44780532, 612536384, 858973311, 584757392, 942533147, 419153342, 422803213, 651790118, 536765982, 531440253, 579622232, 613332070, 843449453, 950386074, 370924270, 968224730, 213473253, 320495492, 262805904, 323608440, 315014948, 973377161, 228141255, 120359100, 723094284, 348105634, 74234647, 147137584, 345137106, 875741517, 688425414, 443186176, 749268136, 821282742, 350571817, 632357293, 598492380, 49122732, 418804177, 743712399, 849060948, 311404171, 865106980, 124376193, 592720953, 876573373, 144295420, 908449148, 403681719, 921056960, 741131674, 292575272, 195248373, 218936760, 916219409, 118754312, 495631135, 117822793, 101127902, 935528437, 195430499, 273071634, 245122705, 380818253, 231635679, 948137080, 163007196, 376869964, 433489579, 398098738, 652178202, 111345343, 622677020, 264272271, 383633879, 580582792, 646844427, 187865545, 994226316, 721538927, 416499115, 34216961, 236098208, 652804925, 512972563, 944448709, 605105042, 906665445, 547476513, 864835810, 564685978, 801728391, 406651766, 4516139, 361627861, 116807520, 869320099, 25802763, 149001371, 633801292, 619636138, 512269156, 997960917, 253680699, 336876420, 585718513, 760102146, 918845988, 218512169, 250615465, 124240468, 376632880, 307696521, 270549370, 956490591, 993906652, 247464588, 235178859, 786849517, 713072386, 886413940, 777376464, 647349152, 708675186, 520052797, 585024436, 266293141, 192965352, 589167148, 715848973, 145458727, 173267508, 207109548, 398309263, 204522126, 82665463, 174127509, 195411100, 948453630, 467395473, 929581635, 874903605, 307603680, 2013805, 847734175, 403618616, 791654099, 311801907, 7224367, 643548660, 132268677, 37263761, 646379799, 409531767, 554625993, 754004144, 748104902, 248205576, 911710093, 410946627, 461081978, 902238772, 600722121, 788281643, 467122501, 372514085, 365595521, 43395839, 866299388, 175421778, 363821214, 760337981, 963055369, 299845255, 308856829, 875004112, 440305575, 438941457, 877530861, 954441507, 132677366, 787415028, 556790802, 201349031, 195733630, 77079189, 796527207, 401662857, 641141081, 212711267, 775152016, 128158655, 412302071, 351067909, 610480645, 261815099, 933888376, 348941917, 81797227, 545994637, 559925484, 567561020, 367495231, 832421649, 582193157, 523533473, 25484260, 447104371, 589898299, 572047908, 904113645, 820426589, 992964554, 459347285, 769054459, 611332171, 452561638, 254102401, 968790622, 649380015, 526319827, 819567561, 751854445, 737153567, 460494494, 394945663, 773632968, 928853174, 971243826, 793710319, 625246741, 986417067, 376022644, 948413640, 658010996, 622097038, 576912188, 491483484, 756101572, 29802766, 926503042, 277266184, 191731871, 434702610, 30131459, 824328325, 931304656, 72920659, 460474491, 790674773, 508674511, 880204300, 269545765, 144345785, 880342579, 955773217, 885817133, 272486684, 525935596, 459681396, 211136411, 529167443, 771005125, 955908882, 532008569, 948279833, 648797533, 395486353, 886341509, 796101898, 759086180, 200692030, 454340984, 847597541, 422684366, 55347461, 90045917, 232269394, 480751184, 181787481, 480003945, 896805165, 122577217, 962332711, 705975793, 705327133, 147096294, 731386915, 669582362, 998864983, 313096908, 875952338, 569969798, 559139635, 355441589, 198867557, 129878966, 585545177, 314419354, 552575778, 595467054, 357146770, 109939686, 373493336, 400909911, 164154849, 861942800, 388012954, 928763801, 207615053, 305088645, 878392456, 843812707, 423254460, 598349138, 828951264, 13532637, 164166172, 24036931, 773652538, 225144597, 53642291, 582681049, 297230267, 570254911, 691015116, 871961948, 807264357, 949498827, 23564079, 947667426, 783636159, 889432336, 947352638, 227327492, 539182969, 334207517, 661077688, 941114560, 15279563, 575422852, 307152030, 195389040, 820316355, 271480235, 682159985, 585288130, 952827030, 709621374, 161473775, 623380467, 574558738, 788657902, 408825187, 920344707, 550003836, 584972365, 505185180, 984465544, 726705015, 195937283, 267187861, 88662855, 898452867, 116282890, 625465077, 731468226, 51994966, 785112555, 885412809, 265197183, 193302780, 804567671, 321195862, 218466477, 928312634, 879827403, 754963395, 151674752, 342514814, 792664353, 844097712, 752479047, 256968604, 587032011, 576926871, 156356774, 785142885, 20859988, 80837728, 468011099, 805924840, 810745474, 509499765, 276016923, 899638819, 318500676, 696940321, 678458024, 558677244, 770495578, 228335889, 233349236, 199785426, 130232939, 230912855, 671759491, 708215974, 2183199, 892160626, 214159837, 580918127, 22854678, 134521519, 894530759, 320655925, 975012809, 665825619, 557007006, 564764963, 12661970, 641001576, 632457665, 39382351, 526547619, 106501931, 487914239, 522731009, 185723170, 753788883, 102706432, 73850990, 682754901, 197627916, 899248062, 23385017, 504858093, 603526369, 70071990, 826512343, 527831367, 535179597, 191607589, 759329398, 172825511, 629035971, 831246995, 755376204, 75191675, 510741001, 958858807, 54724731, 368612926, 717301773, 890678944, 387503698, 474834115, 761245668, 691762526, 4639924, 657757704, 971136980, 805489976, 144234455, 437881935, 176160267, 406620546, 838197142, 910775103, 37317110, 619897108, 373938336, 31952555, 336057613, 102167559, 15961116, 655090521, 3192894, 652501013, 608006501, 569915171, 149685191, 722677878, 47033362, 386005781, 630745710, 47336753, 473520606, 422170969, 262177259, 666670321, 674545261, 579136538, 929179128, 877425278, 438383928, 502643561, 401481476, 254664211, 623421364, 576453553, 550600969, 580614808, 897826673, 22116654, 573687845, 313928570, 245796056, 558363252, 13668657, 66553537, 360297743, 835495402, 79429793, 724033005, 414339285, 830832004, 707550790, 929098975, 289458922, 821993146, 557226224, 163240443, 563811143, 199027658, 280491412, 952981667, 258011961, 742781191, 950943064, 307829688, 951672589, 94894108, 173387891, 120184213, 765628598, 989937649, 777588606, 866809006, 308256017, 324093710, 329525417, 973678686, 237191950, 766358727, 697235419, 55693652, 123447562, 550297393, 686596531, 471506168, 811122363, 919575549, 543481835, 646433377, 753451849, 747676788, 227777516, 903207153, 817152329, 60244526, 170340795, 582046907, 784391459, 123757425, 180415928, 403301393, 603368942, 843463908, 176736565, 331049864, 620373923, 738090628, 852985046, 784176212, 166099435, 358100087, 803904984, 363328893, 607732681, 738465081, 389955692, 808339721, 97339600, 528170146, 912972821, 55274769, 273195891, 150361524, 849696784, 667805915, 652932684, 628195560, 509533818, 973463888, 321432093, 742948100, 244395089, 733948475, 488114931, 490665656, 436867059, 532070023, 581075427, 283828536, 774579784, 546936753, 161588872, 102949661, 201425305, 258886752, 636336387, 135613916, 72011612, 801963624, 96287280, 872343926, 543892761, 624033196, 820853699, 517710070, 504049345, 19214812, 610852547, 832607061, 954548945, 413332331, 537352072, 1012562, 941160177, 305885833, 902221225, 799801936, 896914159, 776438524, 994969922, 659513707, 274651359, 299701761, 942697844, 899500960, 638650489, 90729946, 3015511, 217802058, 526759317, 461387615, 116647844, 405950670, 610223901, 434060219, 203274483, 576580033, 383926069, 908973113, 295003451, 365881491, 380083396, 251751699, 742014102, 948422751, 50901646, 593950901, 264963548, 680960572, 104654601, 537698558, 477095072, 308997794, 181489831, 701495974, 686011393, 380513873, 303184345, 623719894, 889076280, 880837592, 815026593, 651343156, 62503422, 664466235, 609719220, 577803224, 716317821, 665899756, 777231143, 695153534, 687668325, 732941102, 508572959, 522243940, 564232661, 316104825, 536869769, 205334107, 725332356, 175274696, 979293349, 801843695, 737519830, 241382710, 830929207, 551365395, 384845917, 308957151, 93446016, 601773307, 172021740, 849659471, 466604570, 707041035, 145618570, 61828704, 293986381, 199088052, 602944562, 786021027, 393537020, 892265872, 667431580, 535076789, 253428034, 246172270, 437095944, 117305425, 301306304, 165096174, 342776808, 284741410, 107030042, 995125323, 997727688, 704585753, 271933188, 557002390, 170457906, 498542797, 555811278, 494975789, 162454718, 166940146, 875246392, 163268659, 942037036, 326322549, 354372283, 614691155, 656212924, 476240012, 332582532, 938614012, 851747534, 699712742, 602650213, 361087562, 866132376, 505646681, 105419197, 713506401, 669139936, 173916377, 772379383, 674287210, 520273603, 222904584, 1611044, 150437271, 132715408, 755223374, 257228758, 449441527, 732031567, 679502843, 865622311, 962491301, 629811013, 513300339, 957402424, 510089772, 125803569, 3203311, 342613677, 579792248, 459402288, 852352306, 528757303, 332804329, 956899862, 498566983, 951183908, 430625313, 988842592, 469878979, 299238481, 689394827, 434716674, 338112179, 485362940, 995548956, 212789552, 208270382, 831217535, 304102432, 910104945, 969517424, 900003291, 477946797, 242706330, 791630309, 687067331, 963553207, 421105943, 800446742, 720395935, 572652852, 761079229, 131607197, 260914090, 553275485, 758852833, 521330287, 68544014, 328389755, 332389632, 412751769, 102526924, 132453595, 12928861, 48222612, 496222545, 609452082, 36842049, 651561335, 579298414, 815668564, 636795711, 878657770, 531430031, 304433036, 843282150, 65937315, 754240541, 95390759, 108221565, 657576156, 957683501, 650896384, 690792720, 471973178, 120541750, 56341267, 896436285, 672508715, 687620501, 597377418, 89065734, 164014480, 493132529, 412429084, 575845930, 519504012, 28387507, 518244577, 704803729, 233720895, 789722855, 296172642, 423726761, 764709108, 262915480, 143082535, 282652473, 709048916, 742389796, 985091758, 989133655, 148404331, 812852379, 193611651, 448204205, 297677629, 611596516, 835144210, 735133322, 557761028, 623842217, 562677301, 791154197, 691930208, 19483719, 347762088, 177073656, 233552781, 123845074, 83979731, 458336530, 740823932, 454969265, 187792276, 160607383, 704163440, 329947737, 725288070, 851296295, 99726177, 964618575, 589052710, 21220894, 235170720, 72836616, 967745121, 269352074, 705253412, 720997656, 781838099, 964727107, 221714306, 332621200, 594241606, 440260526, 116389081, 468159938, 504135402, 70076606, 509639143, 160553624, 693980545, 937961604, 491295557, 182348916, 644277973, 980772396, 215444111, 86336287, 15556678, 745429989, 121917205, 556675917, 317700382, 340137136, 369866166, 100124878, 191058823, 583032348, 751599381, 585109532, 974478994, 140039596, 749471717, 975412984, 500761869, 144724014, 414015880, 394484644, 184604532, 359094047, 165104620, 201396230, 580384608, 548731949, 242060621, 11799863, 908076918, 880595637, 309159974, 898794673, 367867821, 100546603, 697558214, 404046577, 710410366, 230702760, 538441471, 677218313, 917749433, 302713962, 32523441, 535523889, 75838203, 255418277, 63161007, 368914719, 258794816, 777947826, 597479832, 418922029, 496550693, 165969493, 979301041, 374028301, 437784215, 186154182, 309262917, 153687942, 320757818, 845811487, 611496666, 939859476, 335031515, 841211234, 26908923, 483266694, 263821438, 24196639, 581370666, 831346378, 600719296, 631566337, 672236911, 632382338, 812223656, 472291525, 949064751, 318347336, 176246011, 656253084, 568583862, 141882912, 977701567, 408148144, 762261624, 548131420, 711021789, 590561271, 534286245, 259646989, 921094740, 646800226, 888529608, 105812196, 40003066, 51247141, 637551188, 849914259, 510213187, 581364012, 322984429, 966590884, 676030258, 13300930, 918762295, 248378722, 41632816, 700416282, 133080658, 641595977, 575644459, 159495976, 498676793, 156455613, 154642224, 525621425, 80073697, 228078385, 503974804, 142650103, 296386461, 388891933, 417281915, 692423726, 674011854, 42574970, 814209089, 365319940, 546204271, 605574886, 944594069, 826790846, 954588447, 313711293, 628114308, 940576806, 913084685, 876831588, 696405488, 644739872, 92373677, 943603264, 871168673, 802865177, 119711051, 888794620, 734756453, 580224726, 897640819, 846941798, 396680372, 845282741, 593652887, 685792185, 759828345, 282016983, 517314623, 18327617, 525155673, 966572782, 50569703, 408195920, 935233915, 567076179, 664734503, 183113857, 148828068, 207949638, 265297290, 256524740, 918867102, 272598596, 948743229, 667924251, 251811969, 304690496, 92279534, 560731741, 568953559, 631505885, 605897244, 936744763, 919437011, 858259344, 818184810, 820833920, 581773972, 414362848, 835402239, 59080792, 993088554, 344761047, 599196764, 59588471, 218708015, 328253842, 503022824, 337265772, 806844026, 461209873, 944559141, 855545769, 868220031, 414756130, 407463517, 716870443, 2297203, 650519026, 762685688, 4300959, 167863177, 817013278, 523049058, 506871883, 643779789, 674202049, 524738450, 942541558, 964850063, 110002957, 673524811, 371504956, 943479980, 971749535, 403711942, 957504384, 329344270, 610322224, 779712273, 115387564, 751071024, 999148739, 8542655, 551795777, 870557715, 927477352, 426787136, 415295724, 741690925, 899150673, 974158015, 723171597, 96511595, 735814519, 612768897, 577144175, 163314531, 767860081, 598756124, 86405198, 354293502, 550682435, 30854896, 75554711, 237626691, 791009719, 633590716, 666763811, 745693802, 978816489, 565097532, 626485139, 546996997, 317440845, 139636206, 215738960, 38063250, 760149483, 982251443, 150707141, 331458844, 80239400, 203492922, 832023176, 898737094, 187010785, 448133359, 764758394, 701042530, 518261337, 583827678, 230491396, 685661062, 962124122, 796636849, 531410645, 547521828, 837727121, 630431595, 88238193, 119017180, 170495619, 32748488, 455235131, 331471428, 495808266, 360081173, 5313121, 874269452, 431567139, 213071866, 82917462, 773935352, 865237268, 251048913, 422479185, 812938491, 938966101, 38175076, 806409573, 947371309, 371105333, 716952509, 528383517, 161338067, 91493423, 145957840, 282104045, 28344081, 412502877, 697309182, 187398765, 745215200, 738349158, 446604815, 290352289, 656226882, 950390901, 182047756, 189753560, 595405805, 587212171, 761419974, 248757707, 298758051, 538996228, 932820119, 917913314, 804645031, 448897889, 932065830, 587247477, 937071590, 740896900, 2761475, 17377371, 176181514, 909870554, 754205116, 53721859, 770314064, 756886114, 791910368, 357460197, 27513163, 814359287, 714327843, 637990754, 356144643, 682695155, 89813334, 768536619, 965415968, 15644991, 296299137, 910864062, 293668866, 604443630, 310498864, 132879548, 243223871, 457012694, 520123285, 534485594, 86186142, 272705239, 336344095, 140790145, 882757685, 77871680, 827918702, 314858098, 17201842, 649839073, 818556717, 89200859, 109083815, 753819620, 8179435, 922346150, 169711346, 169120466, 826302850, 496192259, 57145673, 517141012, 455809181, 612563992, 869804395, 990491949, 833743648, 503805095, 490906967, 917755258, 664860343, 247696786, 847032918, 480751182, 795069224, 329271099, 917369377, 644910716, 156785906, 7311951, 709069111, 142048255, 79256248, 573556074, 518250976, 77029824, 273982803, 472450124, 425333610, 148220937, 56682955, 259312022, 690588175, 128643568, 761663620, 688682039, 143899313, 869884259, 328578065, 115511672, 629881659, 893705697, 932206180, 164876372, 302234567, 721776980, 519218049, 249062427, 796940738, 306393758, 995975939, 311596982, 458011902, 291043550, 583269070, 154158271, 446531857, 668009208, 962767311, 991700689, 602412413, 570934251, 224782005, 207867938, 774006517, 493318278, 429032440, 578570380, 888594809, 358175843, 962619592, 934599672, 273021178, 804965413, 708458353, 836002765, 277795349, 527987836, 165470384, 640119969, 793611283, 273964418, 920950325, 664984131, 268159179, 11970837, 746080927, 858854431, 481799192, 239375758, 581676059, 630114276, 806214592, 362263895, 932876193, 348809113, 116947852, 39504334, 588128906, 840225323, 711261024, 855140458, 866563508, 958975747, 817943998, 250002739, 236448123, 365682273, 292627638, 696884346, 173054254, 636294338, 282812346, 126982669, 524943352, 550134660, 141390227, 467566023, 740577476, 732475057, 51386126, 435461106, 273376443, 267775238, 727825840, 180265882, 475140847, 900844390, 99660886, 418772439, 590015864, 392278076, 900711944, 520223309, 471517553, 507876735, 773815368, 293024752, 899294616, 124019494, 137617392, 30663089, 235527994, 219751271, 711707349, 116494856, 956558590, 554947766, 204815682, 672858359, 682355651, 960535905, 621638454, 964736252, 477150786, 533945264, 381365272, 713207298, 46963305, 880284395, 749676758, 71170581, 639564859, 455708796, 549364512, 74221445, 344183899, 683761157, 836068272, 150106751, 598182149, 432920010, 502212207, 997144068, 546378374, 736366329, 664505418, 824769047, 899042401, 889727652, 929963780, 592585675, 295828456, 952568785, 182951633, 353629626, 195806877, 116781551, 141084740, 657611378, 924970342, 833163572, 632275760, 560757591, 578188256, 81398023, 294758552, 362864245, 327655656, 688438401, 292905898, 686535182, 602788332, 933215671, 851510794, 135311946, 843599683, 289801740, 78550180, 632597931, 216218881, 233919288, 635968707, 715280444, 409876667, 906172332, 860449851, 588132159, 670436775, 253469531, 785625255, 602928738, 429563859, 756544476, 377022405, 303848809, 23586349, 750643354, 514991125, 73004700, 500642858, 306454264, 878681948, 791456082, 686111631, 167521829, 528767671, 637272588, 542042004, 806083385, 965519891, 471146670, 555785132, 930324240, 735649494, 991074075, 197401263, 921726255, 262811714, 800461358, 747773342, 222366366, 898398363, 577650296, 389669218, 370231643, 820150183, 212871402, 821512934, 268685906, 728083956, 121191654, 556009744, 937788312, 597870110, 194165064, 14212217, 308221805, 181083021, 54008709, 136884753, 744807493, 533825782, 154257941, 96735971, 8863379, 332576653, 865640276, 145208791, 917301561, 407082265, 14411109, 39426421, 277162798, 343018529, 465911707, 332746871, 450532650, 723696787, 500759425, 610343093, 368383852, 431058825, 426665917, 904764518, 429473642, 445230511, 582328893, 827337118, 563918058, 109436566, 455988521, 253962875, 925341974, 505657291, 674625720, 471743371, 408088990, 268895394, 252261635, 86577252, 769947408, 282169640, 596040713, 753574923, 552634176, 231774080, 207667924, 776110786, 45821319, 717149028, 182435023, 761823960, 167336256, 369094863, 471252590, 294179044, 531486847, 202350825, 438813776, 460676744, 754620661, 98330509, 538176238, 516839701, 963842986, 15709386, 510720429, 902569243, 522424106, 938981413, 357821304, 964901761, 771779584, 173179983, 26121977, 364837194, 488565480, 107385123, 977388264, 791306924, 343519711, 690094454, 660628194, 204768020, 358563364, 498886222, 546877570, 373421859, 450423986, 788106659, 433352418, 838496500, 635218020, 374352651, 832923359, 440982519, 546019387, 232008497, 49705823, 741658929, 783739587, 939216796, 173174494, 247965017, 366669224, 740066741, 404000582, 336790120, 111250703, 928485912, 484470010, 230714901, 643915812, 844791912, 681037036, 455062881, 598968578, 809749045, 38634436, 416976718, 149781198, 328746092, 701329982, 252890232, 615481662, 590275206, 849953431, 200591788, 128868520, 971781687, 46371528, 880797246, 634872576, 968377145, 952208425, 807892764, 411320519, 503308930, 669199404, 656061289, 561676545, 517497030, 690071029, 562731808, 150369279, 238575007, 837979074, 938922642, 407183771, 384617914, 257082606, 263610045, 523428590, 18299670, 996343994, 720558490, 223552012, 685598432, 203949891, 872109713, 947153038, 339666510, 123907096, 477004225, 266425877, 562396099, 621841042, 131293545, 812107528, 712031681, 372451496, 114406206, 164402708, 152223926, 515779214, 309636097, 133190284, 921904044, 357180009, 487275239, 982794565, 837172370, 138810647, 65878021, 838985562, 261440415, 770815675, 807648287, 720612087, 904476511, 829064403, 756347684, 180524493, 856489580, 880437288, 105291077, 284647599, 443883746, 640205204, 184562208, 709843311, 44371919, 362827955, 427334384, 442171171, 512650051, 692921572, 61885468, 347859980, 404334623, 759627134, 605968334, 681820675, 79348485, 222358258, 502525922, 100194702, 781650341, 382567329, 932775600, 42009205, 131751944, 6960256, 136486052, 348923347, 590987860, 139264226, 69017577, 857932528, 876649191, 217674893, 609530851, 186934024, 356786398, 72968983, 979672417, 172886263, 100647944, 974428866, 419357314, 376256655, 914022062, 503584136, 432802664, 705253071, 7160665, 159592164, 881471589, 36483154, 377833220, 228076824, 478201182, 39783313, 402955551, 925002470, 84030076, 14995323, 507497112, 343722730, 726518518, 669759954, 820301966, 565829459, 980757989, 72449014, 895276745, 429489639, 576313877, 503324718, 117440178, 695685571, 135169635, 225464759, 247691480, 640997717, 358211409, 781859396, 112955328, 249292224, 665091211, 343353137, 890705080, 349340198, 109721057, 10640744, 413852602, 122166907, 2128596, 735240994, 760333027, 738671003, 758085997, 972867007, 433123463, 727596785, 751476154, 698022246, 276693461, 228324777, 420497140, 957845119, 741702465, 315680404, 87317098, 914120088, 508118175, 493182117, 566896394, 116363505, 153938978, 518094540, 619452752, 5404027, 515381630, 292255952, 94815853, 961757479, 600987653, 265715374, 261432674, 82280907, 336772992, 123010860, 33733977, 352461442, 241397882, 931884451, 503629853, 127517630, 715791899, 138683431, 219315023, 497197373, 641974846, 842292143, 9112438, 813407373, 44363845, 573531831, 64179778, 690856362, 386286531, 961989360, 350900060, 276226190, 810769138, 238818815, 138367191, 717049457, 25613585, 859639286, 193858588, 786647364, 704817485, 973258227, 515928938, 709207431, 75995898, 51349988, 853660946, 963077189, 434643687, 172007974, 982829050, 966359716, 300628707, 264612791, 268956725, 301115057, 818078881, 925164591, 448925263, 742244180, 547814393, 843752401, 962048224, 224204154, 518392404, 140844207, 505204708, 538837347, 654497427, 997460808, 553016947, 86607471, 713694382, 824794638, 670438580, 85604603, 131490277, 515915674, 997004929, 748965046, 836600685, 475808839, 124397685, 189085756, 379463587, 540748242, 462603075, 392777349, 695654559, 666285733, 983446856, 168967897, 284075007, 830195398, 485185013, 715436465, 331804904, 878101555, 257059985, 781783013, 113560530, 120415218, 463886806, 856260975, 40570788, 118471666, 453610621, 658499855, 117703309, 735579297, 644085687, 939361642, 784491048, 511667512, 482737334, 746915951, 288002367, 167506936, 901990033, 431477926, 406259502, 777399628, 353574608, 234826644, 535936656, 437274261, 888257782, 71821785, 90041110, 230859242, 593303797, 199318987, 438399080, 731559738, 405647703, 754895396, 941981883, 310511910, 410509520, 182130594, 869972806, 519320537, 233131187, 863473506, 720193134, 435288456, 988651618, 166820325, 339689212, 258849899, 365844944, 214288062, 148948164, 731869984, 496263395, 879250198, 440545948, 325409954, 402538003, 286783693, 291244706, 32807771, 104277392, 387383618, 757859003, 257913733, 183053187, 814507540, 34562988, 774392586, 944910900, 253952676, 800950208, 941563713, 235057603, 424224258, 408119585, 194096112, 381341077, 216090661, 655330112, 64191520, 622159506, 952951458, 362595174, 484475779, 149608628, 880569135, 196764190, 639615640, 2699561, 614609071, 830377527, 740568367, 502360288, 32557330, 969699299, 704894607, 320172842, 24901379, 189955226, 270181694, 627440118, 682879957, 649117268, 268147481, 536396498, 255488212, 264609437, 450539472, 629673387, 996646617, 591368903, 974286757, 183100906, 137910226, 745253714, 961798565, 286801509, 595134070, 92433657, 492189813, 906719566, 668677012, 590232069, 983276177, 351172878, 320332224, 656788582, 411098565, 321900280, 96884265, 406815934, 150714682, 86803995, 135516322, 873194744, 985100173, 922617384, 870389145, 45790253, 530002303, 816487530, 423147570, 920055602, 887435696, 390679325, 494676068, 193700988, 992238327, 700601102, 360312718, 199292918, 509975701, 229782928, 63139200, 69769734, 31224612, 829977944, 651396717, 665857572, 231196981, 787659892, 17030152, 220431208, 124007593, 759118314, 332967379, 868789568, 144216067, 676972923, 592717520, 647100059, 377981103, 543351062, 423689978, 127896439, 41668948, 3308430, 390703032, 406479480, 5508887, 987670200, 477545214, 217259598, 273989955, 851487431, 269909889, 274688884, 458445550, 211697154, 546156124, 672381975, 985283475, 989459780, 709488443, 612515997, 434813512, 691246515, 955903988, 710903788, 483554904, 275380477, 173829538, 319528897, 403376503, 765610158, 158346551, 548721341, 666595965, 220619469, 618164194, 940277921, 923230616, 871858818, 292743847, 62297344, 383962054, 369239755, 114681160, 867440571, 319871257, 644403049, 249020156, 947198424, 763745718, 603055696, 377455377, 862657592, 287927279, 912619389, 735296377, 769115742, 675307136, 595691349, 491730597, 613712811, 111621051, 181424919, 884517263, 835618694, 192393555, 806783389, 291397296, 205303140, 461557420, 534204205, 417935380, 544391223, 228517872, 732048247, 584600947, 404686697, 676715171, 643401337, 665151792, 115928570, 952558574, 181288792, 921829878, 480625755, 113638604, 464403887, 117051136, 370540852, 310772136, 461623862, 441636481, 744329019, 244816412, 250164259, 318576751, 65862740, 294691355, 810923888, 641996195, 902914860, 377267118, 68149741, 104141947, 927572834, 95907403, 221721688, 37270648, 393067060, 901165025, 914964559, 289498570, 68433473, 787652834, 452357574, 577421584, 420556947, 572014266, 736946136, 947359342, 45115005, 112759955, 317159192, 293905186, 181586253, 232834840, 414291002, 13515733, 150334624, 206906165, 334407365, 959067805, 928007366, 755143610, 26988723, 56747398, 838152510, 978812153, 728014203, 154687709, 194654621, 747008206, 243748205, 299061641, 522336047, 86540673, 573597600, 142035530, 304934947, 256406993, 443972329, 83869046, 856200208, 695608014, 228409118, 22390266, 868473753, 306268192, 992118129, 929486659, 19171533, 292378696, 865874042, 971266577, 249629784, 209576671, 967455941, 711401610, 170956911, 325895059, 991500612, 268382991, 866158992, 765720130, 297942314, 289811116, 115901157, 306666035, 656908629, 921724730, 431603470, 475193037, 485480255, 185462135, 887478359, 484112365, 971830201, 606736630, 625452121, 160247746, 600002194, 131402952, 492915245, 161804220, 659972588, 157507474, 791378223, 986688584, 993875001, 614070631, 501586138, 60179550, 146930621, 361547142, 799115926, 174052817, 423963375, 537117327, 840609398, 73568792, 948368889, 172568553, 474828389, 937870762, 379029345, 344212707, 87352210, 221593088, 539030163, 374634068, 735017954, 410641371, 7990403, 675285912, 404498920, 816178650, 330815030, 299246190, 987824980, 24561366, 434419803, 709402092, 52865607, 871856203, 406586362, 424530474, 632573961, 655702089, 687620023, 432553490, 693195889, 562188100, 927153104, 796360480, 836160363, 938286690, 591510221, 72147710, 99730368, 454224574, 971789003, 701840863, 905997572, 460528480, 810192185, 370565837, 747027838, 146287636, 993117125, 597624190, 656936469, 109468380, 791747003, 958109708, 448220538, 59377156, 230162540, 747815571, 662088355, 558911400, 720085405, 50563951, 672146946, 967764222, 685591676, 597715253, 782791597, 136535817, 967382169, 622561356, 859815239, 690409130, 272163246, 615817843, 679396217, 474068540, 841943658, 81503598, 760524647, 188434982, 882903705, 716744793, 161593195, 199049369, 999380903, 326089101, 594703036, 555672675, 541901586, 311338510, 48606070, 632136139, 322722836, 691816943, 74397675, 290291396, 77258903, 823422217, 307456196, 593932776, 749228147, 497113158, 219106737, 860769467, 887814060, 708249561, 12989146, 517108484, 774780625, 118049104, 106078342, 826402466, 749230054, 756486285, 401113472, 972224358, 452583905, 302552521, 636646179, 953332726, 870505730, 773738260, 570784953, 432417905, 219965158, 282342989, 576885725, 900864199, 49047886, 203325883, 643079050, 502258073, 903221320, 680813934, 576759657, 58403760, 48557744, 934660053, 471024035, 512901385, 833164867, 574500689, 480665104, 316900646, 275314043, 309818069, 487223546, 256134578, 888414138, 998980462, 376917336, 626840353, 442517942, 168438210, 645439961, 792859260, 883699322, 380051073, 727923796, 459422994, 440369085, 609256088, 145508529, 625307736, 558568011, 62120234, 121565944, 188316440, 998373780, 653848264, 370297123, 135274685, 724224196, 978245299, 523889076, 496953326, 907541227, 123732294, 371117278, 617589433, 555332054, 893424762, 807795895, 356536193, 733416590, 443206970, 694587380, 388688232, 333267861, 323674576, 723406357, 354337593, 82035720, 760026402, 997167520, 292512218, 316941987, 633146574, 729316280, 96482676, 411528890, 294583574, 929656434, 857924490, 884019070, 572729367, 517271332, 86633754, 467597489, 103554774, 400607540, 699154635, 552352303, 102261063, 341199911, 541332735, 600284291, 587063758, 242597291, 97705550, 265863113, 474226815, 493056244, 733697740, 836991422, 964790821, 936031056, 937451806, 24735642, 153801840, 539700576, 501006906, 784812211, 923867091, 718419436, 201809308, 831160485, 895827053, 357015926, 655900957, 276832569, 503612187, 438341761, 321774330, 245943146, 566134342, 283312033, 518631884, 174246015, 823189903, 945948024, 704765887, 897540600, 777313000, 302662604, 377002072, 916018872, 374052451, 528285102, 124102788, 951051025, 955855050, 102458628, 705473317, 490718779, 230540989, 59870355, 451119386, 626572984, 800361064, 808576346, 894140825, 435521300, 733561254, 322177796, 686257046, 391756694, 682797764, 441969015, 521697923, 220897583, 433149694, 380149266, 87710889, 121099692, 181910607, 754921561, 880168994, 543812908, 981527688, 928502558, 649922631, 545564893, 654428418, 772179078, 437502056, 162469818, 720152791, 94588608, 719470732, 146681933, 938765434, 604717727, 977220757, 32087611, 66338683, 518513238, 393707514, 267565873, 278395401, 839764664, 600674519, 697055640, 97866815, 355605922, 538539598, 70541464, 898263607, 116533745, 700831432, 523200467, 820570544, 566609506, 606355637, 297102063, 387576008, 804182681, 564079331, 311060587, 706151039, 144829626, 675533958, 83318958, 805240326, 832252486, 630907553, 159419475, 466944188, 898093720, 674470962, 761063987, 540898617, 121881335, 772997322, 305366547, 279962742, 104303742, 283780510, 925978869, 683747619, 837097228, 916210828, 818718928, 791096582, 913514489, 761766740, 648110247, 12742130, 925927960, 723552189, 935359526, 794949153, 381243462, 286023954, 361716649, 952056826, 516926309, 910213298, 899865124, 496482277, 70383255, 729673646, 61561530, 884527233, 202189950, 805666089, 209140862, 226280819, 421629975, 627051204, 197075191, 484395311, 584554392, 824690011, 365375387, 763159917, 870397657, 909783784, 295735507, 875927226, 699125681, 868576787, 778861276, 230247247, 259196411, 697472835, 290801470, 386816484, 796424339, 464426587, 897961201, 485621913, 599574581, 896855163, 697613201, 812623374, 457194790, 993208537, 434700245, 188011322, 685744010, 474206820, 345551747, 329005498, 474900245, 311048519, 330364340, 288456094, 605463949, 245741742, 616652540, 378050786, 232632157, 14901383, 788742576, 463251521, 238833950, 138633092, 935049368, 595865939, 504349829, 217351305, 836007413, 515065733, 449123453, 912164166, 445282834, 465652328, 445689825, 536460333, 290262364, 730237249, 40487825, 895337390, 285798874, 754337259, 711425616, 440102150, 291163173, 634772886, 7701703, 572172896, 540313713, 940171293, 880555949, 977886612, 164201183, 942908570, 688643162, 136243342, 706053866, 262967798, 981373225, 229840698, 775390742, 605568209, 373058983, 764583725, 818340759, 885502566, 711411385, 477954441, 224843848, 766004288, 294886062, 974139920, 874355560, 824398770, 570363846, 697743180, 858375192, 943170758, 336906516, 398050949, 144580293, 379543090, 25236159, 100346015, 407989750, 227170492, 2867306, 923798774, 226467511, 211342183, 891202592, 527673734, 4581253, 545022962, 544728279, 116134697, 582461462, 240375592, 295027703, 590893744, 68205439, 740001976, 266617855, 948402586, 914336642, 561288612, 274978184, 981166359, 709722346, 852987900, 638336256, 852663570, 372364638, 73548147, 740264179, 865693461, 743591714, 334791181, 495540225, 999432495, 64150759, 156548454, 701197187, 437976169, 10811748, 284984899, 712798175, 779569821, 276863816, 677720798, 997918239, 599433782, 742664339, 64939483, 482114398, 792772592, 79472157, 157209677, 648006501, 276287889, 718096119, 297733527, 88832045, 178573385, 260345807, 54969843, 390936801, 186746668, 976403697, 700454959, 552181613, 582077428, 383703143, 430971400, 47522223, 194006477, 382659823, 964381904, 777842543, 603807530, 973066563, 652544326, 813784669, 439196228, 750990095, 921906357, 594545695, 211627230, 423360986, 299174569, 477159309, 414475632, 193386648, 506766322, 135264015, 82083086, 433804763, 512018469, 278582759, 386826269, 323890103, 612572302, 888015453, 526821149, 333210268, 791340528, 98408688, 648615137, 843172265, 785127459, 92715930, 345507558, 241155281, 435980974, 820327602, 903632182, 710946749, 974749417, 906304541, 511782043, 687607099, 473833713, 475987734, 891818083, 685225177, 444716168, 58825462, 473676319, 165766353, 113663746, 637247690, 769591488, 636823423, 667103762, 859036058, 330538844, 191055052, 470557280, 670208752, 507639785, 106911967, 287711426, 539193887, 153576015, 55278308, 97694520, 978606583, 910158181, 279339847, 635740121, 281652790, 841079996, 190115286, 292644065, 998701539, 476413515, 537606382, 354810687, 374236191, 580736891, 825015843, 811690237, 352255678, 287279369, 772113921, 394328951, 340131670, 704412597, 521402699, 960172357, 645306607, 275001918, 56472940, 792486186, 124932510, 252592590, 312675367, 492232772, 873499238, 863352511, 860234864, 597968645, 89264526, 633593934, 137633540, 544331431, 459835709, 949226437, 647039020, 58141445, 782249562, 812732542, 499171807, 365734113, 857460885, 25997483, 780647074, 892556281, 945275545, 942706408, 569351698, 632598595, 626774143, 96651390, 391498318, 902283839, 333028585, 160597931, 376312371, 609233242, 11584914, 464156317, 357656747, 939913705, 641743592, 877481701, 702481244, 75837376, 157886975, 171257407, 714261401, 896332180, 238306798, 422048856, 989732328, 876239527, 694777337, 128484302, 758660505, 793516009, 351531482, 788463439, 191541907, 78178387, 512357746, 892571446, 609334011, 10429994, 786173473, 40418864, 607242708, 734005553, 3840312, 402962420, 594191553, 405372737, 421919701, 754749886, 267666671, 638008465, 722213976, 949819413, 689657065, 159250338, 128398751, 848470164, 384687395, 339229012, 760526768, 279338622, 241940309, 385247789, 366966010, 614167948, 876572070, 116674618, 248409528, 99892713, 424597119, 565116473, 392800575, 615456431, 246684304, 835879749, 727968449, 354107987, 948230769, 501091603, 402398831, 446080313, 91488537, 607079922, 664128175, 790459067, 105389144, 11427339, 985495990, 567260763, 75042659, 947265383, 759559771, 660327966, 680132290, 987506408, 669203399, 832912813, 626246221, 278503503, 301431221, 782382485, 831797862, 6330985, 574943115, 320500788, 983555103, 816228836, 219514066, 519691179, 719344478, 763273813, 80341280, 553250969, 4874634, 743957123, 151363946, 761365508, 355276891, 92861585, 382370716, 876894445, 310688477, 51353216, 578816496, 36925495, 648300085, 841377454, 787580626, 98813958, 301063588, 449624031, 506208017, 511692512, 91172514, 752429050, 847925648, 801763188, 792454695, 35035995, 638406749, 913256175, 477825528, 763915687, 410341117, 767589802, 696574623, 595803798, 616145358, 379664699, 443250917, 586412759, 347555182, 814517989, 874038771, 915623501, 166041618, 377688102, 560431579, 537595841, 858960154, 755370504, 541064657, 979429407, 576464026, 527362369, 226535018, 184306463, 769438852, 858650890, 416296295, 445339472, 981784316, 193751849, 327800457, 737417061, 127969008, 380622834, 986620943, 345881263, 471911961, 2319962, 386523509, 328878852, 450901865, 485568490, 52380251, 402744988, 320571747, 572117231, 975433574, 718940971, 623066448, 588080137, 956415297, 203310273, 45529139, 419098571, 224001841, 955387555, 469879219, 18658555, 143544209, 309948554, 426746646, 186969168, 2487191, 515976281, 993790663, 668028810, 443322754, 551083783, 23942250, 7980558, 753414355, 827545264, 239236285, 1596447, 224979691, 826250510, 579778709, 804003254, 420076184, 784957589, 639003782, 574842599, 92165284, 361338939, 899206080, 23516681, 894115323, 693002894, 985865062, 315372855, 893483551, 523668380, 386899234, 236760303, 102384881, 711085488, 305983829, 631088633, 569238026, 833335164, 824371430, 837272634, 243788182, 289568269, 204407111, 464589564, 520347079, 438712639, 757529561, 219191964, 645662801, 751321784, 821047049, 200740738, 366756440, 627332109, 693865021, 311710682, 18106934, 788226780, 154983369, 775300488, 217110549, 290307404, 547850811, 948913340, 511850161, 11058327, 889456112, 786843926, 785127237, 156964285, 267229591, 122898028, 122701201, 279181626, 537937685, 506834332, 594852053, 533276772, 791982206, 680148875, 306320735, 417747701, 338584490, 539714900, 462307218, 862016506, 897186638, 707169646, 749346334, 415416002, 718855561, 353775395, 455897007, 964549491, 479834183, 144729461, 799792351, 410996573, 277789279, 278613112, 703298513, 581620225, 630341826, 781905575, 857592885, 99513829, 640357270, 140245706, 113396682, 976490837, 737595399, 629005984, 689296845, 871390599, 908649797, 475471532, 26615124, 153914844, 920189599, 975836298, 890493722, 47447054, 369245936, 586693949, 303805864, 560092110, 810732832, 382814299, 365736914, 994968828, 789174107, 388794303, 141372134, 433404503, 33468068, 654128012, 288613340, 162046855, 775603947, 664762712, 248919168, 486839343, 490910886, 118595975, 524841677, 883179367, 480015637, 848617713, 593151768, 27846826, 780046754, 61723781, 395853131, 775148700, 301712521, 843298269, 360340363, 235753084, 166121629, 905561185, 411187703, 959787778, 101813693, 771740921, 415044051, 823216692, 888775717, 876725928, 59991441, 373838394, 703258724, 113888758, 720932020, 951603580, 199071871, 908576168, 991738748, 30122263, 458958934, 585170401, 167385232, 791023457, 57611410, 892195733, 288810445, 561878716, 816121392, 90207964, 508161891, 701650700, 193201160, 301684471, 186267872, 421731954, 997770789, 588368286, 155946192, 165524932, 380553998, 810186965, 948055955, 369045314, 604114888, 426492523, 459141745, 392088106, 952048362, 583049721, 502313023, 679050047, 69315480, 401952492, 197606562, 681664450, 504362984, 803866344, 587281650, 869232544, 800719600, 194977846, 167095567, 904169864, 5125593, 48669800, 733653812, 264085073, 870969514, 956486414, 646307861, 527637388, 738702094, 636597949, 445014555, 75180762, 104654909, 424848392, 464476123, 833902961, 870722259, 326466342, 698452303, 314097780, 767661341, 254766909, 620216160, 486731944, 675626871, 660716050, 576604382, 371474050, 614484170, 622197548, 612576104, 866974241, 90370367, 744057469, 148244244, 245332828, 418436660, 718433533, 452233220, 766035015, 580154431, 790537717, 994236118, 141914268, 387694586, 387289892, 512457273, 773468380, 315095775, 80794436, 728198201, 551474834, 625192208, 600712656, 685058449, 129443376, 258672028, 818168197, 538814539, 67806958, 189350863, 36005806, 646106198, 400981812, 163204993, 48143640, 526770878, 436171963, 42885421, 771946384, 339242255, 312016598, 114393513, 910426853, 828809307, 258855035, 611534374, 752024676, 296647625, 9607406, 950296611, 805426277, 851441870, 916303534, 841052430, 977274476, 398587841, 706666169, 300355100, 268676036, 928513101, 506281, 383556476, 970580092, 912255906, 652942920, 361789676, 951110616, 359988302, 399900968, 619649097, 948457083, 967099276, 388219262, 700287024, 497484961, 375945372, 829756857, 219857514, 637325683, 924561674, 649850884, 950227985, 471348922, 196517064, 449750480, 472451912, 819325248, 938725998, 45364973, 750629352, 501507759, 592272105, 108901029, 513298272, 763379662, 109515190, 730693811, 453954599, 58323922, 368422784, 202975335, 388844223, 805111954, 815997726, 717030113, 30547546, 601637245, 757385346, 788290020, 87574704, 691963038, 111557504, 954486560, 617271274, 647501729, 403767766, 682940749, 20991229, 190041698, 447129120, 625875853, 53106434, 371007051, 169747105, 974211379, 58893753, 25450823, 875438281, 796975454, 309228655, 132481774, 758186867, 340480286, 706597504, 552327304, 681616073, 268849279, 896066808, 238547536, 379254832, 154498897, 181186387, 590744919, 117599992, 350747987, 34987622, 843005700, 325710320, 690256940, 559239498, 651592176, 848602018, 311859947, 895679812, 444538140, 441484914, 440418796, 456563026, 907513300, 905708914, 325671578, 938814352, 31251711, 89272665, 832233121, 633615993, 304859610, 489015425, 288901612, 75146218, 858158914, 423478680, 332949878, 453541899, 888615575, 188254472, 347576767, 30679589, 843834166, 813686790, 366470551, 119665461, 754286483, 522493058, 261121970, 274421077, 782116334, 192328397, 658052416, 577779485, 768434888, 502223197, 602667057, 187697048, 362666178, 407500471, 87637348, 187573624, 989646678, 345934324, 900921851, 429277208, 368759915, 397439705, 120691355, 258908284, 915464607, 732645721, 775682701, 201806457, 692422962, 94146359, 654478579, 99854132, 46723008, 649731253, 800886657, 592005632, 86010870, 410321108, 924829739, 28493589, 233302285, 997546307, 853520521, 752579018, 72809285, 345658492, 30914352, 4907661, 646993194, 423248384, 99544026, 200688079, 301472281, 75642926, 893010517, 607547015, 196768510, 634287408, 446132936, 967196081, 333715790, 374451030, 767538398, 766108364, 126714017, 98485301, 123086135, 100246186, 218547972, 170443271, 558652716, 920184132, 150653152, 604789183, 82548087, 384504373, 171388404, 108219748, 142370705, 682285729, 53515021, 890390370, 997562665, 716470554, 498863844, 815701346, 852292880, 294071545, 135966594, 236318070, 278501195, 298102023, 85228953, 283884168, 749271402, 712154856, 277905639, 510950587, 747487898, 849036871, 81227359, 435242400, 83470073, 208071683, 437623196, 505104547, 581634333, 34009773, 471018518, 442935141, 663161278, 159898099, 677186145, 457532821, 807345581, 755460194, 328106462, 686339592, 238120006, 340069559, 166291266, 321863041, 469307006, 653207943, 425873767, 827225962, 349856371, 559323708, 801325110, 582380244, 180543781, 515730016, 433066188, 480408058, 752823344, 893440333, 552709602, 78164440, 856753204, 120349662, 334569968, 577228277, 586958192, 169378579, 886189695, 189765066, 337143605, 349961442, 760136805, 433329639, 111452292, 473228874, 805522, 406527948, 575218639, 821149025, 66357704, 961447452, 377611687, 977358341, 128614379, 591589400, 724720767, 565239989, 866015787, 315419599, 839751425, 257419464, 932811159, 121213781, 981245654, 483733029, 814905510, 714470498, 756650173, 66796468, 478701212, 763812711, 255044886, 13127957, 562901788, 694672808, 501601659, 97426068, 671306842, 152088654, 289896124, 899282236, 229701144, 136328968, 426176153, 716569800, 764378655, 238621683, 666402168, 685455912, 478449931, 960895513, 749283495, 791289354, 475591954, 166375874, 715312660, 301707919, 494421296, 781924180, 734939493, 149005634, 649619244, 966386871, 844697417, 250837770, 217358337, 575706157, 669056093, 715265061, 242681470, 470168714, 497774478, 371562011, 106394776, 157260352, 104135191, 690988774, 915608771, 52281956, 152051216, 119938102, 955052476, 693188880, 484758712, 349422188, 950001649, 338836750, 738973402, 9996882, 121353165, 775576587, 895815158, 993342380, 843533669, 446506636, 981776607, 47220781, 710552975, 604943826, 400223371, 714966014, 860197971, 839324107, 286326426, 489161318, 880539618, 335549812, 565803602, 102959094, 130457045, 230831677, 776637746, 483643175, 879426420, 703904310, 760665147, 447956147, 34272007, 854572933, 664194881, 685084511, 166194816, 744675774, 706375888, 562235427, 51263462, 384798985, 566226801, 370488785, 506464434, 340427165, 24111306, 692769872, 748111276, 377068887, 304726041, 156827327, 518421028, 879900895, 825780671, 739576771, 289649207, 315244669, 407834282, 93255284, 818397859, 748154438, 439328885, 465348164, 765715019, 227024408, 152216518, 323859017, 421641075, 305230077, 532968661, 698479105, 877120274, 784247667, 547695383, 609413392, 554110786, 866082858, 328788078, 348018555, 978841754, 77575670, 325448192, 817015570, 345396360, 628819166, 235986589, 670269356, 60270875, 771796898, 528170637, 118292967, 948218146, 307838317, 836254361, 183738914, 843810254, 472723209, 298688709, 54853938, 44532867, 287300478, 82007240, 136656310, 746566268, 901640966, 206214542, 881381362, 287922965, 264005361, 259752006, 418345089, 514193757, 332295394, 759122292, 127827023, 852401868, 664798251, 616860451, 2182637, 894861431, 950009405, 148086321, 542271582, 711863384, 557978268, 382354554, 300608427, 131457740, 460570908, 571541271, 878247611, 641326240, 9794862, 354524458, 517484129, 371194898, 163276426, 492545879, 255165454, 994566831, 811366307, 574202169, 500079213, 906426193, 379365456, 596805829, 524431576, 724102106, 999536423, 648838818, 801427745, 305798258, 472804954, 417572105, 396593395, 367566661, 939911784, 278880514, 975384795, 811921112, 511377553, 781338654, 467895771, 895577102, 310906475, 345965104, 875987380, 509741863, 374248008, 173881044, 534076707, 88536828, 978527791, 616776394, 329731330, 61922537, 828162789, 541989869, 950302576, 229168265, 7407861, 370411966, 149469436, 727484636, 716269912, 93896138, 204718723, 580303695, 359224898, 352081720, 380836599, 664973872, 180965710, 362644035, 57738314, 925648151, 119595252, 549863092, 871828033, 982309291, 390403071, 294526355, 224974682, 10610447, 308994675, 117585360, 165976695, 36418308, 969889444, 983872564, 784673688, 134676037, 792723842, 352626706, 611666980, 360498828, 603653579, 890919053, 261851566, 982363557, 638247259, 110857153, 53504576, 166310600, 779311936, 297120803, 847404686, 220130263, 180121053, 558194544, 810290979, 234079969, 222717030, 252067701, 718440762, 35038303, 854522011, 754819575, 447623546, 80276812, 187740461, 846990276, 570840650, 468980802, 139039015, 745647782, 691157840, 91174458, 772333239, 822138990, 857580581, 490386198, 316955648, 607722059, 292907759, 543168147, 583652642, 7778339, 459980236, 872714998, 831277303, 560958606, 494897207, 778337962, 358722066, 158850191, 954318622, 170068568, 337648099, 184933083, 953281143, 50062439, 156551096, 595529415, 682130856, 291516174, 43334400, 875799694, 47881190, 292554766, 672087886, 487239497, 107247509, 70019798, 799545996, 874735862, 565357579, 487706492, 106391008, 750380938, 836596933, 72362007, 83726733, 207007940, 223655854, 197242322, 121420396, 92302266, 996061584, 679547027, 165431049, 82552310, 575649004, 100698115, 834218075, 290192304, 98079363, 774365978, 111213550, 621030314, 522010342, 505899935, 944807257, 454038459, 142858708, 940297822, 984586730, 154579987, 42908347, 949397340, 252833463, 683933914, 908955215, 550273305, 265661941, 348779107, 857855800, 702023292, 215418669, 355205183, 897000511, 115351380, 591589081, 769220739, 483046024, 838609160, 600574111, 958874720, 209671691, 151356981, 944738803, 516261724, 963120637, 767761948, 169301784, 537919105, 216189312, 627709142, 996993592, 531580507, 282816172, 684457363, 100557696, 129397408, 665666473, 388973913, 810727112, 298739916, 829405374, 709461018, 953612129, 748275350, 635300972, 582984750, 821456922, 989650524, 953353891, 687014154, 587046090, 718892111, 596014147, 93077091, 205006797, 654631462, 76406045, 76843971, 55565426, 160378909, 287170289, 922905747, 688371558, 305748333, 543769321, 469929738, 209425633, 667515761, 349934255, 420605617, 523547671, 513454465, 454791566, 241633347, 121919969, 131910719, 778941058, 512098323, 296701562, 290685333, 836992146, 415673189, 100434316, 300359648, 543191164, 815783172, 664431078, 836118459, 45476420, 316191169, 785066386, 406111828, 758606822, 736145766, 469240335, 974532379, 122860812, 159173668, 63422711, 588123009, 975890816, 328126542, 48655014, 284291931, 112451339, 70941456, 272863994, 988850787, 371489574, 204074072, 213554816, 381130812, 796911363, 274065710, 496214224, 855510898, 64589510, 795280639, 712633276, 767143126, 701292533, 629823498, 757010886, 460547370, 697762180, 323400113, 763530079, 444264804, 580259430, 52906098, 958513912, 20001533, 830100783, 525623574, 282098380, 318775594, 202074072, 924957133, 91610234, 755106597, 663117381, 290682006, 172609134, 661492218, 46134903, 483295442, 906875150, 338015129, 183834839, 6650465, 463290053, 959381151, 42092800, 124189361, 927360164, 20816408, 850186035, 350208141, 434264478, 66540329, 572357335, 820797992, 868310041, 787822233, 678020106, 79747988, 554165125, 749338400, 984972800, 578227810, 888644924, 77321112, 732883284, 762810716, 403652343, 540036852, 728478349, 614039196, 361484532, 251987402, 445802378, 571325055, 615793321, 648193234, 490961395, 694445970, 301985358, 708640961, 260468688, 346211863, 972097282, 337005927, 764646951, 21287485, 318363476, 907104548, 937639089, 182659970, 684613522, 773102139, 179939926, 302787443, 582320829, 972297038, 961308866, 413395423, 30770747, 977294227, 457742840, 656855650, 14352079, 314057154, 806325631, 470288403, 187913121, 956542346, 432335094, 438415794, 970602661, 348202744, 737974906, 322369936, 219852413, 546186842, 782553030, 471801632, 203799906, 935584340, 656493410, 901432592, 438897703, 559855529, 505037275, 444397310, 840655244, 867378230, 78776127, 290112363, 683390751, 948820413, 310396612, 423470899, 861829236, 198340186, 410026281, 922641374, 291334357, 796826447, 743120778, 842896096, 89534190, 879914176, 422065255, 641008495, 499346773, 758657315, 92365142, 509163812, 229025790, 762577840, 251636918, 483286391, 264497945, 525284855, 885371261, 204097960, 156864249, 967616961, 850879975, 783538093, 374801911, 832367255, 327820398, 591556932, 758161959, 74414034, 253808609, 103974819, 923011511, 132648645, 632556947, 128262370, 248226396, 459433551, 194264864, 136299298, 466330249, 974371618, 543652870, 833962129, 945290258, 625905988, 481407954, 152345248, 464633353, 46139767, 56400629, 780365874, 570480031, 784476783, 185577447, 815752946, 443434528, 302948622, 436806351, 968372385, 842600778, 959718509, 614553252, 429129672, 625055618, 409092405, 888473581, 410416960, 744700762, 290886986, 701515556, 207181424, 143291099, 917701123, 961090992, 29540396, 528887822, 496544277, 39753759, 672380527, 879051172, 299598382, 159638744, 529794239, 481509623, 609354011, 761330799, 164126921, 441393696, 251511412, 441410549, 168632886, 736094636, 403422013, 383677305, 730604940, 478955663, 972279574, 691513770, 927772888, 814071843, 934110019, 262668345, 207378065, 859665718, 703731762, 30700093, 858435225, 801234818, 501148605, 51614387, 325259513, 495486652, 381342844, 483451837, 502150483, 298239559, 583931592, 154949213, 408506639, 4296399, 261524529, 862603462, 753435945, 499357615, 821889898, 795166698, 837101028, 675677160, 262369225, 686920712, 471270779, 120338767, 982425035, 306045201, 555001482, 914156605, 836762409, 657434011, 185752478, 704498270, 471739990, 393607873, 985874771, 983594007, 201855971, 436458475, 478752192, 889064650, 164672135, 388454792, 305161112, 532707763, 889856140, 668472771, 57693782, 434697389, 375535512, 428023689, 999574373, 670464111, 504271331, 770885212, 775897892, 389246033, 935278861, 971271568, 463738676, 998437423, 213393568, 14926844, 207647862, 584199286, 870845466, 952835686, 949575340, 286324437, 987079011, 833595114, 861585802, 534423048, 548255801, 980844387, 867907263, 520358969, 806384452, 690683645, 788572091, 474267740, 581657269, 201277159, 883930044, 96501396, 299378062, 178921994, 43202599, 913611442, 177146751, 390487097, 775341221, 859874082, 15427448, 8916138, 537777359, 267366015, 618813349, 947816489, 895504863, 246855699, 316795358, 252298284, 833381909, 456974759, 372846901, 580026893, 989408248, 717979153, 282548766, 71157751, 813242573, 304870905, 773498502, 396925408, 658720426, 87601968, 69818103, 659428907, 107869480, 234880919, 19031625, 771671654, 880074745, 761309058, 991125725, 819271783, 575353574, 76047085, 165729422, 37168851, 40119700, 960592596, 101746461, 241031428, 416011588, 640597887, 449368547, 872311966, 593505396, 358078218, 724066683, 420240389, 382379197, 430800951, 350521265, 115045702, 759130672, 98863973, 291913839, 297207688, 115245698, 229475138, 342830531, 855620933, 481062061, 385890078, 898318428, 583089381, 765705326, 26498016, 273760914, 605467467, 918863564, 450190608, 815215801, 501892474, 544119100, 542502503, 59508590, 199497460, 585247813, 431771920, 16374244, 810971091, 727617569, 472934728, 165735714, 808280015, 247904133, 522439588, 680040590, 283020316, 502656564, 395558246, 437134726, 110491738, 715783573, 621702329, 106535933, 236215323, 41458731, 422890491, 386967676, 197573651, 432618634, 696890833, 625524460, 807280768, 711239596, 381431809, 906469249, 712196569, 969483054, 447402866, 19087538, 134560573, 903204790, 67819294, 973685658, 598358677, 685552670, 580377227, 858476258, 695702015, 764191762, 927946918, 580669037, 65082791, 545746715, 524122115, 72978920, 869355162, 641052026, 972073141, 514172044, 838590136, 706251442, 973755089, 348654591, 498543714, 593699386, 111035441, 372607600, 924796780, 369174579, 700375972, 723302411, 625850836, 645176148, 725635711, 328113441, 731810171, 975195454, 489817150, 91023878, 660619252, 94876780, 415040904, 797702906, 376022479, 793606089, 478894169, 380709987, 77211893, 624378857, 906627527, 649379029, 440466100, 269498114, 54335732, 966410063, 74638611, 458956657, 206716921, 902322519, 477829862, 724448948, 664550529, 466032915, 864146126, 793623742, 217392734, 468535795, 309232836, 370448450, 500346306, 501380741, 874225678, 508688689, 752655506, 88090757, 891111012, 454935277, 794544631, 377102558, 207330260, 526860933, 716844840, 385157032, 215614809, 378443057, 68136318, 395955184, 61099539, 678730102, 331408772, 513756585, 110027555, 907179647, 434072648, 857163925, 472166374, 318995377, 754708037, 678072325, 818108310, 841347581, 745366074, 44906667, 959221529, 884268313, 70694626, 482707984, 504324190, 507822499, 23873007, 648149572, 175011707, 455432031, 868368352, 146834433, 141194017, 302221815, 84282630, 155249432, 182492171, 66439774, 793865277, 621611939, 922635957, 228506347, 521561995, 760061646, 821816120, 267242797, 920373566, 43093071, 802217260, 636352623, 403255896, 668172051, 755982281, 570395076, 453875956, 941378846, 469191197, 38935840, 237264084, 413959351, 623106702, 157429049, 165189127, 8600921, 156682183, 824919540, 716333795, 909278362, 943528904, 544600433, 556935821, 554541911, 539878715, 376909810, 198992825, 504089721, 673935193, 461173075, 332653639, 84855673, 844615333, 84560233, 603813530, 413151425, 112292140, 748096133, 261533591, 528572840, 347437133, 258570506, 253367382, 727904594, 297758037, 306281996, 767841564, 934902201, 739504061, 995245978, 109769101, 416871824, 445743633, 751902551, 374746825, 745453487, 159767932, 458877629, 617588598, 832430175, 102565507, 123848393, 333108689, 423516459, 509831915, 240375591, 318830197, 397534612, 929666675, 664635553, 551010754, 958684692, 82488196, 322455358, 80570122, 78392953, 563017514, 503655979, 595616508, 854534559, 424301227, 571024131, 131882910, 39628124, 628804649, 286778037, 221712905, 259125488, 485337258, 38514912, 882449722, 636991405, 619209831, 236225062, 17557103, 212666805, 506684268, 574110472, 56959151, 528341481, 786804802, 129656011, 422097716, 845294091, 201619738, 64321784, 130782035, 380831810, 529722385, 844341023, 218974580, 571949660, 487135979, 934942133, 381819578, 664289036, 273328445, 57755836, 140800963, 814940833, 69036516, 946852852, 482982695, 466103090, 976464075, 82438186, 68174042, 651117287, 805351578, 360888490, 853246928, 759609028, 58042503, 624531217, 558765665, 398470369, 417619225, 153196879, 316151210, 997987973, 78916971, 155798491, 549981266, 229005951, 309860545, 145521775, 692370978, 291634535, 722618365, 577079139, 102534560, 723265932, 764305291, 334004604, 455460197, 981383659, 615911394, 995850348, 70291920, 801206210, 176818412, 785467129, 930551371, 612391006, 810703731, 103933969, 395213370, 887003262, 335741458, 246659139, 347013817, 214516220, 936390538, 289285190, 44089559, 944297408, 587953837, 679087925, 37256022, 481309796, 215459933, 467299836, 139598339, 136510589, 353570429, 902482710, 184875331, 854229180, 807975782, 918001386, 970805279, 638897678, 916034972, 263993918, 952033364, 82735192, 107101419, 820059988, 637236700, 896805645, 422182182, 136982209, 12779229, 960475166, 820360664, 832492069, 840895356, 634079593, 200426966, 505985422, 200240707, 873040467, 506049498, 929427219, 841861846, 240899596, 489040836, 119687879, 896933244, 790838033, 502325106, 315057138, 788531845, 403107296, 872595938, 681131951, 93937953, 966438100, 955433134, 674404560, 27583921, 58473926, 68144021, 19752167, 121273738, 294064453, 208826071, 920112665, 946616823, 355630512, 654351792, 427570229, 100094049, 433281754, 726010640, 979487877, 436285612, 408971999, 674032330, 625001373, 434070939, 618224065, 146768525, 682841140, 243887688, 146313819, 80482404, 348442173, 292510287, 86527127, 615639992, 318147169, 683350110, 141406173, 710892460, 563491338, 517752458, 262471676, 665788413, 275067330, 185596934, 570695117, 466307579, 733783015, 403429185, 370288738, 398577879, 866237532, 240744546, 25693063, 105916263, 217730553, 265509069, 636688225, 414747909, 133887619, 995657549, 363912920, 880380365, 90132941, 296278169, 737570427, 97857471, 450422195, 591717341, 49830443, 172342626, 709386223, 952163280, 295007932, 804100695, 196139038, 738606382, 450355972, 932371687, 760111658, 536826884, 735758780, 823075258, 753938371, 558458257, 386907684, 644629461, 146512376, 837378412, 449647308, 932871430, 62009747, 360599078, 68808696, 949156126, 515331548, 762873102, 117763997, 186641828, 609875639, 924840958, 855853678, 350439896, 58247428, 455831746, 478279295, 11645996, 277473883, 917594558, 102407841, 860731057, 836429183, 178717526, 841177829, 720952867, 980267956, 341828089, 310819227, 157414808, 482368126, 188717560, 238575393, 529966102, 266972632, 48820043, 190682636, 612816179, 356603649, 301371215, 523481656, 94301598, 940142201, 313601560, 374838379, 997654856, 535585294, 68944396, 819782433, 320522523, 227854398, 589684822, 274682256, 989062430, 537110726, 41532398, 672091953, 484187215, 841880582, 642812021, 418034136, 609992244, 575053379, 656263543, 799091078, 459239419, 216460005, 320292521, 751106107, 508773278, 498572034, 828635883, 273189187, 485908608, 868183168, 583951484, 332252709, 845126625, 912384527, 622324514, 949521204, 820164836, 444863826, 583734645, 464981890, 819869069, 796292841, 257877656, 147914228, 950098561, 976284396, 33045270, 591475820, 323747942, 176814813, 846782851, 597903442, 615176794, 558390779, 541748916, 70542370, 68333163, 328805689, 578083889, 462485171, 458674217, 416581786, 850253510, 316137880, 733033017, 780378799, 886003670, 289094128, 124177588, 540699015, 97146409, 147379276, 858970734, 681432126, 641060088, 163827828, 839939382, 844219204, 585367193, 146452949, 808542174, 343267591, 695216095, 301394166, 642167683, 966607839, 753643211, 425755397, 121795380, 67655973, 730577295, 921799845, 110912064, 144900870, 708951756, 39275090, 676710491, 816298969, 187155407, 608109444, 447562781, 116959644, 643768221, 817984357, 200644419, 357640222, 562557590, 704938337, 153491497, 453086166, 604036805, 930224929, 45999017, 794066083, 502891506, 835218391, 320792393, 626734769, 253692433, 892812631, 423181924, 301464369, 91365373, 714781933, 146248923, 378272238, 626780862, 688511206, 608925552, 651924408, 993848276, 511793178, 961939049, 375321677, 582960971, 757495566, 292431198, 36502350, 508645201, 250321429, 557420353, 153227132, 672470291, 439340974, 737045475, 395728041, 611105332, 843055819, 114593983, 583760918, 590335044, 764383839, 758406032, 318636294, 611502924, 271021002, 844002861, 903041696, 726403166, 982759949, 715363349, 235573335, 549599180, 277892566, 780473566, 465162120, 343882910, 367824747, 962113841, 995537041, 827064200, 598700635, 89380384, 960863131, 919695398, 131405857, 704729245, 400230679, 700345316, 373886671, 818113666, 111183183, 735007053, 949199185, 194145176, 288825148, 807561460, 194834609, 905332790, 685115825, 514694107, 910075095, 696681977, 106435701, 332487014, 410756467, 740563161, 134342953, 826917066, 364041978, 128574559, 60595827, 283247855, 278004872, 160001315, 468894156, 494478910, 298935055, 390279270, 97082532, 374192408, 507106112, 420399641, 654110906, 74826931, 590541514, 568658600, 527004358, 281279042, 568442380, 893170751, 872403750, 49032098, 266912891, 288158374, 577128974, 149045252, 548367989, 889860792, 504431693, 615113325, 666288330, 446414067, 432820138, 104365636, 572604399, 725940355, 958650784, 73335485, 703541136, 856656604, 507205558, 977380311, 519713214, 227417607, 138581399, 785147201, 671509268, 58215728, 732955857, 266634309, 666373439, 709959660, 225266325, 241010771, 861848397, 747320599, 750379716, 438139787, 805171550, 930274921, 184191926, 497669277, 715529416, 198489018, 713332962, 599724125, 452382259, 151027882, 214736821, 36646562, 722615259, 502708092, 791164450, 431719367, 413668559, 133636637, 281959029, 611524768, 54718283, 542448796, 727994264, 953980938, 626981441, 12572011, 462670987, 161871353, 752828649, 976254605, 337312860, 897501620, 735871689, 505589649, 204044495, 101696215, 134447697, 224176021, 626130821, 205798765, 43288626, 614604238, 384973704, 248464864, 141084820, 183073399, 798020360, 866116384, 876787465, 687556133, 276317088, 808296002, 115887040, 4510879, 103833962, 48216700, 388055393, 87643715, 522910663, 341345646, 358574514, 50933594, 591217515, 840987163, 380911980, 75048199, 83668128, 648869624, 684547435, 38131060, 235626295, 527560352, 147089522, 392104257, 765743427, 397253013, 601175416, 523418306, 219406888, 125609983, 230338372, 14980695, 877310334, 957320654, 549165258, 611355007, 269088119, 929526057, 758419854, 316499609, 481921493, 987284678, 7854693, 102082806, 755360218, 315889142, 951284625, 958391728, 261212053, 878815593, 969490710, 629810781, 178910652, 485000669, 982450884, 105166192, 385889792, 742442502, 586589995, 946138873, 513060992, 857357343, 182418597, 778069177, 244282740, 96955917, 553692565, 822543854, 488694132, 647038189, 395653462, 764005762, 671759859, 425805336, 345047227, 525140953, 330314097, 406604241, 102384010, 211193741, 179281682, 65129680, 249443111, 372071235, 273438785, 44638605, 686710933, 757160083, 225211993, 310820469, 894053333, 815265815, 216676209, 528429379, 419248250, 849536891, 317609010, 972763452, 687176329, 236540458, 916461683, 249227863, 720491263, 881233502, 773009697, 207793489, 616004252, 252999921, 524852915, 245272637, 870829468, 596219303, 891869797, 253553733, 469608398, 249538031, 86587247, 306781569, 623982512, 711323668, 183334612, 279843274, 870033374, 528324124, 202000291, 181987706, 168395060, 665845613, 555625355, 661488517, 464242956, 98139607, 242235005, 501295498, 615357454, 731979099, 321957906, 440681332, 422395956, 689741395, 340518518, 29554285, 727531444, 954082285, 299484289, 385847430, 904874526, 372094299, 19317218, 595031416, 208488359, 970853573, 74890599, 243822742, 164373046, 829134652, 350664991, 742166694, 126445116, 261704185, 307740831, 184008151, 295137603, 923862262, 924976719, 88399061, 100295894, 860482, 64434260, 474538026, 985890847, 934855895, 23185764, 679137788, 440398623, 133048480, 317436288, 72822159, 984188576, 304695473, 976104216, 35291061, 403946382, 293275801, 705660263, 587263978, 251654465, 857476478, 334599702, 717224922, 828030648, 757191334, 780838276, 286309845, 258748515, 264221451, 845035518, 233950148, 281365904, 998167307, 575184643, 250826349, 619287507, 426861832, 418989537, 872939572, 469461321, 195677337, 703591889, 34926163, 192308957, 469418920, 128541303, 718785596, 631805026, 634534519, 261714295, 860804001, 9149835, 340286665, 498171997, 228266109, 360279245, 985982007, 111776006, 822670371, 342799216, 389912315, 601974949, 947010647, 936054860, 603581827, 473576519, 263485981, 169833255, 440049954, 61953548, 92005641, 738502116, 155494629, 633212942, 42575155, 781198053, 106166892, 310920521, 834043817, 565646776, 466635514, 406053764, 892819346, 856015844, 251246551, 186225748, 667437190, 57203103, 590165195, 82201354, 849218210, 76111963, 437554360, 257889607, 744449750, 654818052, 328522427, 66595142, 357793859, 460952022, 710077651, 678590008, 934902461, 743637623, 281179295, 991397286, 557253166, 418586185, 80558492, 569405327, 394091119, 532939014, 727733, 419492781, 633459676, 630720211, 798742635, 885407841, 404719948, 903824147, 662998716, 860306047, 4717662, 952238259, 7618226, 914532205, 532093603, 378173842, 759517872, 590262250, 964843591, 428244790, 224907641, 440218644, 563822048, 552645542, 991670941, 642323803, 761618635, 221941873, 427297016, 320102602, 185669002, 92281104, 13871710, 854921659, 532257371, 522185963, 670887328, 681413981, 594794550, 213667192, 1688197, 721085589, 877485893, 756325029, 125979809, 346460786, 414209557, 30942734, 175515873, 173929990, 250211862, 702167315, 719288941, 379813567, 829304751, 302984167, 347565889, 840910341, 154744542, 539674246, 395241059, 111179129, 937628939, 251262961, 234652212, 50097351, 367568813, 890825174, 987751940, 691283668, 982472134, 466387800, 227584967, 521004606, 969040010, 65875972, 949611326, 3480128, 299749354, 68243026, 478116126, 674461677, 104904730, 295493930, 168286031, 69632113, 661475181, 534508792, 742423672, 428966264, 23357330, 938324599, 374686908, 608837450, 215133528, 804765429, 175943789, 93467012, 245783219, 178393199, 516570209, 536484495, 397202532, 989836212, 622983425, 586443135, 393306679, 50323972, 724275175, 487214433, 621819857, 209678657, 86370846, 688128331, 943749003, 457011031, 732538554, 251792068, 777964712, 216401332, 691730563, 852626539, 378357042, 503580336, 377312462, 79796082, 652952938, 940735798, 248838722, 18241577, 720468517, 188916610, 456204311, 114038412, 62553360, 239100591, 927338940, 519891660, 630226317, 701477779, 408383185, 462501235, 459827446, 42015038, 491611374, 507497665, 656753169, 253748556, 176520799, 171861365, 897254180, 363259259, 595293114, 334879977, 396411550, 410150983, 219252568, 782914733, 607343517, 990378998, 319754171, 36224507, 935163330, 947638376, 63161623, 714744823, 303858797, 788156942, 145960645, 251662359, 516313961, 58720089, 940459068, 847842789, 135540182, 567584821, 842324884, 612732383, 886216712, 123845740, 303591701, 820498862, 96672237, 679105708, 372736038, 390929698, 539965705, 56477664, 327454761, 124646112, 685171072, 832545609, 677317523, 671676572, 312552983, 445352540, 586636355, 174670099, 34055853, 554860532, 635537343, 5320372, 458694052, 206926301, 218363507, 561083457, 699351493, 1064298, 255227396, 367620497, 884167009, 880166517, 671704685, 869335505, 902633117, 879043002, 856638395, 986433507, 53675870, 716561735, 925700012, 863798396, 240892626, 375738077, 391843731, 349011123, 462582248, 638346734, 795335265, 614162392, 352457341, 210248570, 581204850, 978922563, 682445589, 870851236, 91231354, 157840202, 349300973, 43658549, 474056992, 457060044, 8470809, 754059091, 329531973, 746591062, 555556776, 283448197, 850594851, 558181756, 272183613, 76969489, 859712184, 259047270, 311289835, 309726376, 17029988, 502702017, 959141764, 257690815, 961381665, 146127976, 456168334, 547407930, 834214525, 980878743, 42229953, 800493830, 774482279, 132857687, 418221406, 130716337, 314149615, 541140457, 429861757, 168386496, 525484520, 61505430, 857445285, 516866992, 928915611, 176230721, 526871605, 120698941, 282220574, 965942229, 750732638, 751814930, 7372218, 63758815, 573869503, 857895953, 577594478, 569341719, 771309528, 609657515, 577441307, 748598690, 383546847, 320987423, 186121084, 921146075, 146362616, 4556219, 297093351, 906703690, 355517848, 522181926, 884908416, 786765919, 84375114, 32089889, 611831803, 345428181, 423656873, 693143269, 738776722, 480994680, 241344335, 175450030, 762677514, 138113095, 328517698, 405384569, 610277337, 619409411, 274316874, 569183599, 485968368, 858524732, 643032994, 512806796, 318474027, 429819643, 785407936, 96929294, 607331051, 393323682, 708387855, 852408746, 573788857, 986629117, 54413481, 257964469, 77299820, 854603719, 163278368, 37997949, 733009224, 25674994, 616100637, 426830473, 187552010, 981538598, 984327227, 717321847, 673245547, 86003987, 781479679, 491414525, 580927066, 483179858, 342072888, 650314357, 948395037, 632306399, 102609896, 634478366, 62711296, 650557532, 20745202, 909039444, 364964705, 962582299, 914746948, 724462635, 67169699, 371122090, 373394740, 773907200, 81029095, 921876204, 135865103, 481024112, 663312552, 112102077, 24292695, 259196202, 599052895, 570422107, 622269671, 252602354, 922437915, 769418677, 458801615, 827248717, 774697908, 498730404, 876401802, 776508477, 204528278, 543303739, 324559562, 356847191, 93848592, 412397319, 328333568, 335219290, 255452909, 542802305, 288961860, 565745142, 629917009, 257957837, 685231222, 998502468, 623632321, 374482523, 170336563, 918300346, 516765800, 737904423, 711209583, 562198846, 693770631, 94542878, 823835394, 689731797, 912974606, 270374121, 144551773, 731301541, 306525183, 696388678, 673876727, 847827283, 734906313, 833142870, 548811128, 491723428, 215658163, 584483952, 821401034, 642037507, 249225596, 415097699, 542218309, 742592510, 114162209, 857718236, 301069051, 165902452, 379406540, 939050781, 385517086, 628529996, 686748180, 890891510, 587015072, 56780265, 885194449, 60207609, 860682307, 231943403, 4701404, 928130491, 201720385, 20285394, 41252475, 59235833, 898156765, 726805314, 200092814, 829249931, 801100469, 558851658, 602748756, 867789652, 861624173, 822042847, 281154636, 469680821, 333715864, 392245524, 402723364, 255833756, 777016626, 241368667, 833201143, 873457979, 677792935, 644001187, 579363545, 83753468, 134812105, 950995020, 948601988, 215738963, 928058742, 203129751, 149789971, 388699814, 356809767, 176787304, 786033367, 117413322, 583001755, 267968328, 312080571, 718637134, 121109631, 444128891, 543496794, 535910896, 461530876, 45020555, 246155027, 115429621, 882193278, 796651902, 994875317, 599659497, 936113245, 219199540, 306616232, 365779869, 820718315, 702823855, 509390051, 377447698, 507795014, 970990945, 320328787, 155255955, 18424923, 205254760, 366118291, 91065297, 799250926, 434986403, 50120508, 759660272, 276447036, 616565597, 199365030, 431736753, 889268643, 360096567, 493926465, 217644228, 536497943, 494325809, 209398520, 583410166, 942812936, 169844606, 230857670, 629424953, 991154634, 182922472, 889444427, 107144031, 336697695, 74474082, 914316038, 365934992, 434562082, 748131701, 982554708, 439625099, 911316163, 220272974, 409694301, 162704977, 63173367, 701269005, 830221890, 643391850, 908227951, 145622353, 479014637, 516403889, 510690010, 52138696, 182857668, 193691809, 66705523, 878929505, 94609512, 628956870, 762912238, 591526597, 432381694, 407253770, 182312251, 17281494, 450594057, 387196293, 532687183, 472455450, 700983225, 126976338, 728361403, 400475104, 354508673, 970781860, 86295584, 617528805, 255217138, 212112129, 775060367, 704059796, 711871310, 97048056, 766709162, 690670542, 860282862, 608045334, 267321208, 327665056, 549274736, 32095760, 767369710, 311079753, 957447980, 476475729, 132809269, 181297587, 682796263, 742237893, 541344401, 74804314, 282084171, 940284571, 517149486, 98382095, 505903359, 319807820, 671126266, 501349784, 337117695, 807304539, 339738273, 915188767, 483209073, 870284187, 892196564, 251180144, 277535687, 16278665, 792907217, 984849653, 590731723, 852447307, 804444115, 160086421, 212564258, 512450693, 148145156, 94977613, 667004192, 135090847, 603857234, 313720059, 266279319, 841439982, 435295280, 324558634, 623390880, 634073744, 902565842, 268198249, 599933981, 127744106, 455167399, 632304722, 982094058, 225269736, 592146177, 814836697, 592013691, 998323312, 512583646, 795684455, 553171238, 987143382, 802125254, 91550453, 785292321, 68955113, 99900587, 372626857, 152274646, 980899286, 559813513, 643400758, 633166989, 297567035, 332590194, 546216832, 386204975, 746094910, 363576651, 453359783, 929265916, 334338506, 168991674, 795116038, 72600686, 991638092, 49839486, 175586439, 467061685, 160166112, 820462543, 328394291, 722563832, 705549286, 879359519, 160950140, 135316890, 548442136, 519876448, 203407967, 712235377, 75357341, 811353411, 543402001, 661846043, 67758161, 284459936, 436597372, 525526680, 992550090, 116313839, 461308692, 112841618, 935194576, 969657709, 522895130, 408046491, 765001155, 143651856, 408243765, 121960497, 211573785, 74959506, 460027801, 74609787, 443717848, 83917233, 695339666, 117413201, 247338034, 786864573, 96850494, 316140917, 996119167, 862483132, 350300551, 104003809, 180156359, 864650305, 99646459, 985261045, 754987854, 75901424, 114891464, 560320193, 31569600, 760882755, 34884867, 578231689, 15612306, 845899524, 414988972, 699503087, 825698362, 711852428, 332928786, 769665936, 615598494, 405929695, 393829946, 73317522, 8515076, 567165327, 110215604, 588151916, 562003800, 829706089, 379559157, 793504629, 666483693, 141832581, 434394784, 834898995, 572108037, 541239967, 838486465, 402694599, 296358760, 772101357, 823550033, 960279202, 688990555, 806950954, 271675531, 524871554, 211844989, 550447721, 563948223, 533459418, 20834474, 693487313, 1654215, 221488745, 195351516, 803019764, 203239740, 225907078, 502754447, 859267746, 493835100, 746120268, 238772607, 742984083, 108629799, 555299921, 636994981, 736055715, 925743719, 191949220, 634954948, 898384516, 137344442, 455196303, 229222775, 774762053, 105848577, 910980372, 273078062, 352929389, 836190991, 703285773, 992641741, 507414649, 494729890, 363567626, 854744225, 566034733, 806258002, 105368275, 217406756, 847581521, 845623261, 964345629, 477951994, 401778038, 355451894, 629346462, 241777452, 151190698, 637690242, 725091570, 86914769, 453151822, 659764452, 751398093, 701688255, 933947903, 382805079, 578032021, 579173279, 831272353, 774360674, 413794239, 833297986, 939149656, 610309738, 104060658, 309082097, 183788465, 970138964, 34234972, 461615308, 56316058, 435929409, 102985717, 646371927, 370314829, 31148672, 130150842, 191981027, 533924438, 684619881, 525943242, 57340580, 195589206, 933720289, 949886495, 659935632, 348434709, 822201528, 242170726, 124510078, 235680345, 473599212, 7091780, 381872859, 879813546, 301527848, 20609568, 688727692, 757768494, 431328796, 368938460, 643963643, 66362684, 956309698, 193922035, 867648192, 425009299, 384557871, 262007009, 337653568, 398476905, 797845678, 76522298, 745865302, 630755293, 806856409, 399087191, 555810529, 966388601, 590712463, 845025601, 942258635, 939981560, 417809347, 685727839, 596196781, 415390759, 903391698, 997393286, 145698648, 201522038, 102651570, 372435144, 230778710, 438159450, 767102106, 521008618, 208967690, 55032058, 772195615, 899078720, 114258936, 207552388, 866024127, 428247139, 792300477, 147056757, 702343352, 462540429, 838357589, 331708441, 821700672, 308335360, 332575896, 717196922, 57964285, 901528589, 476279287, 588325613, 90644396, 802924786, 460914939, 519000799, 740312881, 298842988, 56819302, 547452698, 732201947, 499514268, 58525568, 429422431, 185270426, 167298622, 155386068, 831658601, 230811931, 330235690, 720818244, 622285787, 872164513, 388980051, 122408206, 969105586, 625082133, 380495774, 659288379, 387756222, 32931370, 367700569, 647345681, 703724813, 405461944, 108774183, 820998101, 460244943, 451457430, 359401399, 188633559, 871563723, 534074874, 475472817, 552070977, 351515616, 463786417, 825413342, 547953705, 901628101, 110860844, 225251574, 18635324, 646204673, 196533530, 46625428, 950582516, 630747162, 957482283, 899904252, 144749285, 633596297, 534216740, 665950553, 393826417, 787029192, 226178787, 549415032, 288710792, 607140134, 710278477, 835215565, 286007133, 699624975, 368473068, 685614096, 473679671, 237835467, 522557506, 576630908, 556379981, 126383588, 158579596, 724638797, 146952593, 618333196, 590793130, 369890586, 116417420, 558095739, 207145501, 834710973, 506757870, 861663314, 75167312, 74301528, 603453086, 32694860, 667203686, 872469232, 979533906, 50145757, 464003683, 596680277, 377571805, 494164119, 513494365, 918407796, 28373699, 939408030, 419076255, 18089516, 989406080, 483147178, 864007105, 446668490, 577343858, 506258464, 597327314, 893167619, 373504103, 180691795, 621874106, 231428152, 649530824, 987497105, 761168027, 6732594, 543270340, 615426812, 286798800, 171100113, 71017765, 973839873, 652467477, 180635247, 628203500, 170029924, 721986168, 725537338, 41934523, 556386470, 428100104, 334401106, 347804007, 782874096, 114204559, 762022646, 11195133, 859930754, 934236880, 846105766, 153134096, 456047989, 996059068, 617450771, 964743333, 985303058, 509585770, 23534272, 146189348, 444268112, 432937021, 65993651, 985633292, 583165945, 124814892, 499522330, 604788339, 944900586, 983727974, 318410121, 355700805, 143541771, 585478459, 717551865, 662947533, 138272968, 495750306, 489959662, 634191499, 765856836, 433079496, 52045709, 382860065, 896464947, 148971157, 455463465, 144905558, 900117865, 557950582, 779370731, 653333021, 539523648, 828454318, 301899901, 460862365, 331849652, 215801735, 417348147, 737596522, 512457371, 742740131, 736090132, 592731071, 18863023, 943739183, 721793664, 742056186, 434700813, 985915104, 402521484, 303368315, 983590303, 812726064, 989839146, 80123873, 738915271, 300001097, 549043528, 65701476, 159315599, 746457626, 546272912, 80902110, 1481479, 329986294, 930543441, 78753737, 523730090, 895689115, 147100323, 493344292, 654517738, 996937504, 224676282, 807035319, 390538639, 250793069, 933482252, 30089775, 782646511, 573465314, 220053864, 180773571, 190884284, 399557963, 190316527, 587026412, 771649657, 711981691, 710535737, 768558667, 892990027, 420304699, 615685716, 36784396, 851091833, 974184448, 146771716, 586284280, 735490403, 737414198, 507110098, 468935381, 803728588, 689514676, 538689376, 672106357, 776129923, 43676105, 340840826, 110796544, 360337756, 769515085, 137583923, 187317034, 971606942, 367508977, 801599243, 705320689, 377484534, 503995205, 956911236, 337642956, 839131071, 202249460, 16074204, 408089325, 734272702, 165407515, 502153773, 149623095, 203150694, 493912490, 358560971, 12280683, 391752584, 717209905, 883853783, 354701046, 564985879, 526432807, 249607799, 935928105, 605222857, 203293181, 843276067, 212265237, 98313631, 816286984, 626219259, 827851048, 887900514, 843810015, 111763942, 216276745, 768144350, 846597948, 317035951, 281094050, 869675537, 463576552, 21979105, 398180240, 306268742, 918080185, 210274125, 469143345, 698463591, 795755114, 371328074, 36073855, 384214362, 49865184, 219192052, 227112287, 737382213, 985894505, 123499149, 850920435, 550298797, 452998786, 413578107, 230264240, 208103828, 905096096, 823991064, 685282922, 332638594, 373513919, 574142793, 73143818, 352113758, 996558566, 873579890, 298812095, 288456603, 828468238, 890836243, 54734190, 603357697, 895873505, 982283524, 479054854, 199125806, 224110269, 206480921, 29688578, 715655702, 115081270, 388004829, 873907789, 873504467, 831044181, 965026586, 279455700, 470809697, 860042706, 493810257, 525281979, 635078580, 336073473, 173168004, 483882111, 225331222, 342795838, 104065948, 798857630, 506081528, 891395802, 150058231, 568267912, 494546533, 983691088, 77906965, 311280678, 867069312, 929907623, 74240510, 345204565, 98724214, 136081623, 955891065, 807908925, 306631770, 839698112, 254903036, 237034270, 452132598, 420971829, 555222481, 40751799, 381027514, 880262327, 858298995, 94217491, 318272398, 941451856, 903016310, 858372400, 752720439, 580796601, 846712626, 599524688, 661697255, 999690455, 319185254, 663044554, 995446684, 297351518, 382801446, 777836341, 933265433, 270950793, 333093035, 155669255, 64537217, 24303035, 884190922, 816068073, 51898103, 161361418, 432559212, 845908475, 376150705, 537198841, 117265250, 145145698, 611714739, 538629455, 205412616, 911711112, 75375359, 153728098, 852587014, 296966388, 286924385, 874614077, 267568916, 248556579, 520892436, 609553372, 173286267, 930384737, 300197006, 443907030, 897310074, 854124784, 795692238, 6494573, 912502361, 258554242, 115920696, 887390316, 254868689, 59024552, 501082540, 53039171, 77850927, 413201233, 836611799, 374615027, 493567718, 878243146, 694659915, 200556736, 397984399, 486112179, 84971747, 726291956, 913607982, 651276264, 962468937, 818323093, 690039107, 476666363, 395930761, 435252865, 82520846, 386869130, 216892054, 785392480, 901387818, 716208956, 601007537, 109982579, 597290316, 641171498, 241762690, 788442866, 99149169, 950432103, 102617789, 24523943, 33242059, 601662945, 46980239, 321539525, 438622744, 751129040, 529684239, 451610660, 500257343, 340406967, 640054360, 788379832, 78390240, 29201880, 397911113, 24278872, 997542806, 967330030, 322581707, 735512021, 957920591, 756450696, 112602145, 916582437, 901751142, 787250348, 710223104, 240332552, 267008733, 158450323, 927279371, 637657025, 431640288, 654909038, 641244289, 243611773, 740571440, 128067289, 322433354, 444207069, 156739589, 499490231, 531413871, 188458668, 987234237, 813420180, 919229083, 221258971, 372129696, 84219105, 23885919, 822719984, 994286194, 396429630, 168045134, 441849661, 356320552, 690025540, 368690502, 363961898, 503213050, 229711497, 565909918, 720184546, 604424665, 304628044, 564660184, 572754268, 888946552, 312653868, 406642597, 779284009, 830431857, 31060117, 848896284, 60782972, 243816590, 94158220, 548092660, 499186890, 194363525, 326924132, 427918443, 685148565, 738481375, 567637346, 544290693, 362112098, 907474368, 989122653, 338518895, 261944538, 135583937, 248476663, 989636258, 953770617, 373972404, 61866147, 975115329, 185558639, 381335470, 808794720, 439233463, 277666027, 223734683, 446712381, 201969995, 903897951, 123288722, 678268100, 473877486, 366708295, 699159184, 221603485, 397019610, 347293690, 953159324, 194344116, 697923000, 666633934, 250533127, 161837288, 133347893, 861703182, 131801272, 677168800, 658159667, 41017860, 203545353, 380013201, 429483687, 498583760, 916490577, 146256109, 450765143, 658470997, 482546836, 316573287, 166920623, 364658140, 769192920, 48241338, 760543068, 205764445, 471338629, 147291787, 150006101, 464828217, 510865122, 428962245, 61534844, 442009535, 318720110, 786364687, 871125180, 258635666, 388368209, 43316877, 180213060, 733798748, 599173351, 51777387, 193461536, 200303770, 450308786, 849577321, 854939010, 776176155, 747353545, 551130535, 464254349, 670599959, 360622076, 770666371, 302692306, 800142149, 617052342, 293531879, 771789461, 621298649, 769719996, 48852775, 962333610, 632931560, 761958554, 737113411, 122622607, 246528122, 625567226, 366848870, 357654259, 418495711, 899186076, 982395414, 858667177, 468015528, 660566267, 468725903, 570136791, 12367821, 257566137, 76900920, 439944756, 269850288, 512813826, 250503453, 995178380, 892406109, 163235596, 961933549, 972583149, 359209718, 994177168, 100904654, 728743138, 915580246, 10841147, 947913530, 707978966, 178507963, 577306149, 827950482, 25279401, 638416288, 519106447, 751806097, 980749064, 719170884, 21053669, 160887165, 58134745, 122971573, 667001743, 283067171, 752931610, 641656020, 117901468, 259315942, 218328529, 587123011, 199159944, 911594955, 575333906, 472974012, 130218232, 852382947, 832183569, 448770300, 866934508, 388656500, 845454677, 151331302, 659767016, 431282362, 0]
a = 1
MOD = 10**9+7
start = 2
if N>=10000:
    start = 10000
    dp[1][:10002] = u
for i in range(start,N):
    a = (a*(i-1))%MOD
    i2 = (i+2)%2+1
    i3 = (i+1)%2+1
    for j in range(1,i+2):
        if i+1==j:
            dp[i3][j] = (dp[i2][j-1]*(i-0) + a)%MOD
        elif j==1:
            dp[i3][j] = (dp[i2][j]*(i-1) - a)%MOD
        else:
            dp[i3][j] = (dp[i2][j]*(i-j) + dp[i2][j-1] * (j-1))%MOD
res = 0
n = (N-2)%2+1
for i in range(N):
    res += (dp[n][i+1]*x[i])%MOD
print(res%MOD)