You've got an array a, consisting of n integers. The array elements are indexed from 1 to n. Let's determine a two step operation like that:

  1. First we build by the array a an array s of partial sums, consisting of n elements. Element number i (1 ≤ i ≤ n) of array s equals <image>. The operation x mod y means that we take the remainder of the division of number x by number y. 
  2. Then we write the contents of the array s to the array a. Element number i (1 ≤ i ≤ n) of the array s becomes the i-th element of the array a (ai = si). 



You task is to find array a after exactly k described operations are applied.

Input

The first line contains two space-separated integers n and k (1 ≤ n ≤ 2000, 0 ≤ k ≤ 109). The next line contains n space-separated integers a1, a2, ..., an — elements of the array a (0 ≤ ai ≤ 109).

Output

Print n integers — elements of the array a after the operations are applied to it. Print the elements in the order of increasing of their indexes in the array a. Separate the printed numbers by spaces.

Examples

Input

3 1
1 2 3


Output

1 3 6


Input

5 0
3 14 15 92 6


Output

3 14 15 92 6
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class PrE {

	public static long time;

	public static void main(String[] args) throws Exception {
		time = System.currentTimeMillis();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long[] out = go(br);
		for(int i = 0; i < out.length; i++) {
			System.out.print(out[i]);
			if(i + 1 == out.length) System.out.println();
			else System.out.print(" ");
		}
		br.close();
		System.exit(0);
	}
	
	public static final int P = 1000000007;
//	static long[] inv = {1, 500000004, 333333336, 250000002, 400000003, 166666668, 142857144, 125000001, 111111112, 700000005, 818181824, 83333334, 153846155, 71428572, 466666670, 562500004, 352941179, 55555556, 157894738, 850000006, 47619048, 409090912, 739130440, 41666667, 280000002, 576923081, 370370373, 35714286, 758620695, 233333335, 129032259, 281250002, 939393946, 676470593, 628571433, 27777778, 621621626, 78947369, 717948723, 425000003, 658536590, 23809524, 395348840, 204545456, 822222228, 369565220, 404255322, 520833337, 448979595, 140000001, 784313731, 788461544, 56603774, 685185190, 763636369, 17857143, 385964915, 879310351, 50847458, 616666671, 688524595, 564516133, 15873016, 140625001, 30769231, 469696973, 686567169, 838235300, 579710149, 814285720, 98591550, 13888889, 410958907, 310810813, 93333334, 539473688, 831168837, 858974365, 202531647, 712500005, 123456791, 329268295, 84337350, 11904762, 670588240, 197674420, 252873565, 102272728, 415730340, 411111114, 164835166, 184782610, 43010753, 202127661, 231578949, 760416672, 268041239, 724489801, 646464651, 570000004, 940594066, 892156869, 572815538, 394230772, 209523811, 28301887, 224299067, 342592595, 9174312, 881818188, 873873880, 508928575, 893805316, 692982461, 147826088, 939655179, 239316241, 25423729, 478991600, 808333339, 438016532, 844262301, 886178868, 782258070, 856000006, 7936508, 480314964, 570312504, 798449618, 515384619, 190839696, 734848490, 165413535, 843283588, 274074076, 419117650, 58394161, 789855078, 604316551, 407142860, 134751774, 49295775, 832167838, 506944448, 151724139, 705479457, 149659865, 655405410, 530201346, 46666667, 483443712, 269736844, 594771246, 915584422, 625806456, 929487186, 343949047, 601265827, 685534596, 856250006, 962732926, 561728399, 116564418, 664634151, 587878792, 42168675, 5988024, 5952381, 242603552, 335294120, 795321643, 98837210, 791907520, 626436786, 325714288, 51136364, 683615824, 207865170, 435754193, 205555557, 933701664, 82417583, 562841534, 92391305, 524324328, 521505380, 577540111, 601063834, 338624341, 615789478, 439790579, 380208336, 694300523, 634020623, 343589746, 862244904, 969543154, 823232329, 507537692, 285000002, 228855723, 470297033, 108374385, 946078438, 131707318, 286407769, 526570052, 197115386, 832535891, 604761909, 90047394, 514150947, 32863850, 612149537, 79069768, 671296301, 875576043, 4587156, 470319638, 440909094, 950226251, 436936940, 125560539, 754464291, 364444447, 446902658, 35242291, 846491234, 711790398, 73913044, 277056279, 969827593, 90128756, 619658124, 880851070, 512711868, 67510549, 239495800, 280334730, 904166673, 406639007, 219008266, 707818935, 922131154, 89795919, 443089434, 165991904, 391129035, 28112450, 428000003, 912350604, 3968254, 339920951, 240157482, 556862749, 285156252, 70038911, 399224809, 517374521, 757692313, 417624524, 95419848, 836501907, 367424245, 611320759, 582706771, 138576780, 421641794, 743494429, 137037038, 450184505, 209558825, 388278391, 529197084, 752727278, 394927539, 252707583, 802158279, 681003589, 203571430, 718861215, 67375887, 650176683, 524647891, 77192983, 416083919, 808362375, 253472224, 961937723, 575862073, 756013751, 852739732, 522184304, 574829936, 210169493, 327702705, 215488217, 265100673, 441471575, 523333337, 770764125, 241721856, 646864691, 134868422, 137704919, 297385623, 749185673, 457792211, 857605184, 312903228, 787781356, 464743593, 492012783, 671974527, 403174606, 800632917, 652996850, 342767298, 614420067, 428125003, 741433027, 481366463, 597523224, 780864203, 406153849, 58282209, 3058104, 832317079, 343465048, 293939396, 631419944, 521084341, 624624629, 2994012, 737313438, 502976194, 41543027, 121301776, 631268441, 167647060, 284457480, 897660825, 206997086, 49418605, 715942034, 395953760, 985590785, 313218393, 521489975, 162857144, 413105416, 25568182, 175637395, 341807912, 19718310, 103932585, 826330538, 717877100, 713091927, 602777782, 113573408, 466850832, 812672182, 541208795, 882191787, 281420767, 376021801, 546195656, 295392956, 262162164, 436657685, 260752690, 16085791, 788770059, 618666671, 300531917, 212201593, 669312174, 195250661, 307894739, 160104988, 719895293, 172323761, 190104168, 966233773, 847150265, 932816544, 817010315, 951156819, 171794873, 102301791, 431122452, 63613232, 484771577, 840506335, 911616168, 760705295, 253768846, 55137845, 142500001, 855361602, 614427865, 779156333, 735148520, 424691361, 554187196, 238329240, 473039219, 188264060, 65853659, 352798056, 643203888, 578692498, 263285026, 16867470, 98557693, 534772186, 916267949, 844868741, 802380958, 966745850, 45023697, 44917258, 757075477, 134117648, 16431925, 526932088, 806074772, 610722615, 39534884, 761020887, 835648154, 614318711, 937788025, 50574713, 2293578, 354691078, 235159819, 642369025, 220454547, 716553293, 975113129, 88036118, 218468470, 83146068, 562780273, 176733782, 877232149, 285077953, 682222227, 605321512, 223451329, 161147904, 517621149, 432967036, 423245617, 172866522, 355895199, 198257082, 36956522, 321041217, 638528143, 820734347, 984913800, 208602152, 45064378, 775160605, 309829062, 240938168, 440425535, 447983018, 256355934, 763213536, 533755278, 646315794, 119747900, 228511532, 140167365, 206680586, 952083340, 355509358, 703319507, 654244311, 109504133, 653608252, 853909471, 607802879, 461065577, 38854806, 544897963, 641547866, 221544717, 632860045, 82995952, 529292933, 695564521, 156941651, 14056225, 266533068, 714000005, 1996008, 456175302, 282306165, 1984127, 588118816, 669960479, 747534522, 120078741, 491159139, 778431378, 344422703, 142578126, 598440550, 535019459, 314563109, 699612408, 400386850, 758687264, 597302509, 878846160, 191938581, 208812262, 921606125, 47709924, 441904765, 918250957, 301707782, 683712126, 510396979, 805660383, 561205277, 791353389, 589118203, 69288390, 844859819, 210820897, 811918069, 871747218, 404452693, 68518519, 60998152, 725092256, 311233888, 604779416, 801834868, 694139199, 541133459, 264598542, 854280516, 376363639, 39927405, 697463773, 457504524, 626353795, 174774776, 901079143, 457809698, 840501798, 491949914, 101785715, 525846706, 859430611, 433392543, 533687947, 578761066, 825088345, 446208116, 762323949, 732864680, 538596495, 334500878, 708041963, 813263531, 904181191, 229565219, 126736112, 771230508, 980968865, 898100179, 787931040, 869191056, 878006879, 732418530, 426369866, 447863251, 261092152, 724020448, 287414968, 585738544, 605084750, 656514387, 663851356, 160202362, 607744112, 95798320, 632550340, 835845902, 720735791, 410684477, 761666672, 296173047, 885382066, 76285241, 120860928, 887603312, 823432349, 729818786, 67434211, 36124795, 568852463, 492635028, 648692815, 696574230, 874592840, 377235775, 728896109, 716369535, 428802592, 953150249, 156451614, 842190022, 393890678, 630818624, 732371800, 571200004, 746006395, 944178635, 835987267, 36565978, 201587303, 438985740, 900316462, 30015798, 326498425, 696062997, 171383649, 880690744, 807210037, 677621288, 714062505, 720748835, 870716517, 43545879, 740683235, 359689925, 298761612, 119010820, 890432105, 640986137, 703076928, 291858681, 529141108, 29096478, 1529052, 438167942, 916158543, 823439884, 171732524, 698027319, 146969698, 216338882, 315709972, 983408755, 760542174, 33082707, 812312318, 163418292, 1497006, 41853513, 368656719, 62593145, 251488097, 493313525, 520771517, 454814818, 60650888, 320531760, 815634224, 609720181, 83823530, 345080766, 142228740, 530014645, 948830416, 411678835, 103498543, 237263466, 524709306, 927431066, 357971017, 444283650, 197976880, 92352093, 992795396, 520863313, 656609200, 862266864, 760744991, 696709590, 81428572, 489301002, 206552708, 85348507, 12784091, 626950359, 587818701, 991513444, 170903956, 385049368, 9859155, 355836852, 551966296, 701262277, 413165269, 366433569, 358938550, 93444910, 856545967, 318497916, 301388891, 224687935, 56786704, 802213007, 233425416, 630344832, 406336091, 696011009, 770604401, 235939645, 941095897, 729138172, 640710387, 66848568, 688010904, 29931973, 273097828, 698778838, 147696478, 538565633, 131081082, 721997306, 718328846, 590847918, 130376345, 506040272, 508042899, 676037488, 894385033, 889185587, 809333339, 215712385, 650265962, 304116868, 606100800, 896688748, 334656087, 952443864, 597625334, 779973655, 653947373, 582128782, 80052494, 1310616, 859947650, 518954252, 586161884, 850065195, 95052084, 855656703, 983116890, 690012975, 923575136, 648124196, 466408272, 525161294, 908505161, 839124845, 975578413, 613607193, 585897440, 645326509, 551150899, 805874846, 215561226, 868789815, 31806616, 419313853, 742385792, 278833969, 920253171, 841972193, 455808084, 822194205, 880352651, 537106922, 126884423, 877038902, 527568926, 964956202, 571250004, 46192260, 427680801, 764632633, 807213936, 592546588, 889578170, 581164812, 367574260, 102595798, 712345684, 755856972, 277093598, 816728173, 119164620, 223312885, 736519613, 73439413, 94132030, 462759466, 532926833, 618757617, 176399028, 52247874, 321601944, 917575764, 289346249, 617896014, 131642513, 712907122, 8433735, 84235861, 549278850, 496998803, 267386093, 601197609, 958133978, 560334532, 922434374, 696066751, 401190479, 853745547, 483372925, 239620405, 522511852, 848520716, 22458629, 348288078, 878537742, 216725561, 67058824, 722679206, 508215966, 690504108, 263466044, 359064330, 403037386, 792298722, 805361311, 67520373, 19767442, 269454125, 880510447, 718424107, 417824077, 158381504, 807159359, 987312579, 968894016, 200230151, 525287360, 360505169, 1146789, 918671255, 177345539, 265142859, 617579913, 891676175, 821184516, 840728106, 610227277, 759364364, 858276650, 612684036, 987556568, 736723169, 44018059, 559188279, 109234235, 497187855, 41573034, 738496077, 781390140, 705487127, 88366891, 287150840, 938616078, 813823863, 642538980, 314794218, 841111117, 591564932, 302660756, 256921375, 611725668, 786740337, 80573952, 324145537, 758810578, 882288235, 216483518, 963776077, 711622812, 371303398, 86433261, 712568311, 677947603, 741548533, 99128541, 41349293, 18478261, 916395229, 660520612, 776814740, 819264075, 304864867, 910367177, 952535066, 492456900, 252960174, 104301076, 23630505, 22532189, 595927121, 887580306, 515508025, 154914531, 16008538, 120469084, 164004261, 720212771, 568544106, 223991509, 115588548, 128177967, 467724871, 381606768, 551214365, 266877639, 262381456, 323157897, 884332288, 59873950, 383001052, 114255766, 687958120, 570083686, 204806689, 103340293, 8342023, 476041670, 746097820, 177754679, 580477678, 851659757, 338860106, 827122159, 260599795, 554752070, 199174408, 326804126, 669412981, 926954739, 943473799, 803901443, 468717952, 730532792, 584442174, 19427403, 492339125, 772448985, 1019368, 320773933, 399796544, 610772362, 793908635, 816430026, 447821685, 41497976, 17189080, 764646470, 172552978, 847782264, 877139986, 578470829, 901507544, 507028116, 911735212, 133266534, 874874881, 857000006, 833166839, 998004, 650049855, 228087651, 245771146, 641153086, 2979146, 500992067, 222993064, 294059408, 680514347, 834980243, 896347489, 373767261, 21674877, 560039374, 877089485, 745579573, 676153096, 389215689, 369245840, 672211355, 94819160, 71289063, 226341465, 299220275, 938656287, 767509733, 735665700, 657281558, 747817658, 349806204, 97773476, 200193425, 905314016, 379343632, 628736745, 798651258, 483156885, 439423080, 995196933, 595969294, 504314481, 104406131, 566507181, 960803066, 840496663, 23854962, 551954246, 720952386, 564224552, 959125482, 471035141, 150853891, 618009483, 341856063, 497634819, 755198493, 391879134, 902830195, 762488224, 780602642, 544684858, 895676698, 6572770, 794559105, 297094660, 34644195, 705332091, 922429913, 942110184, 605410452, 642124888, 905959038, 215813955, 435873609, 237697309, 702226350, 929564418, 534259263, 930619803, 30499076, 704524474, 362546128, 375115210, 155616944, 92916284, 302389708, 604224063, 400917434, 621448217, 847069603, 867337609, 770566733, 294063929, 132299271, 394712856, 427140258, 191992722, 688181823, 458673936, 519963706, 977334549, 848731890, 590045253, 228752262, 765130990, 813176901, 686203792, 87387388, 176417643, 950539575, 812219233, 228904849, 625112112, 420250899, 494180845, 245974957, 338695266, 550892861, 2676182, 262923353, 755120219, 929715309, 872888895, 716696275, 280390419, 766843977, 143489815, 289380533, 404067200, 912544176, 415710506, 223104058, 407048461, 881161978, 731750225, 366432340, 393327483, 769298251, 730937779, 167250439, 386701665, 854020985, 342358081, 906631769, 84568440, 952090599, 724107925, 614782613, 508253696, 63368056, 360797921, 385615254, 655411260, 990484436, 878133109, 949050093, 773080247, 393965520, 310938848, 434595528, 893379198, 939003443, 418025754, 366209265, 317052273, 213184933, 855432, 723931629, 264731001, 130546076, 34100597, 362010224, 176170214, 143707484, 474936282, 292869272, 687871082, 302542375, 119390348, 828257197, 320371938, 331925678, 613502114, 80101181, 230834037, 303872056, 91673676, 47899160, 920235103, 316275170, 218776196, 417922951, 56066946, 860367899, 685045953, 705342242, 273561303, 380833336, 353871776, 648086527, 285120534, 442691033, 881327807, 538142624, 652858331, 60430464, 926385449, 443801656, 827415365, 911716178, 128606761, 364909393, 141563787, 533717109, 831553005, 518062401, 89417556, 784426235, 79443080, 246317514, 733442360, 824346411, 617959188, 348287115, 729421358, 437296420, 825061031, 688617891, 965881404, 864448058, 117599352, 858184771, 633198385, 214401296, 687954734, 976575128, 526230835, 78225807, 141821113, 421095011, 626709578, 196945339, 5622490, 315409312, 668805137, 366185900, 177742195, 285600002, 511590731, 873003201, 62250599, 972089321, 782470125, 917993637, 948289585, 18282989, 100873710, 600793655, 712926254, 219492870, 988915288, 450158231, 467984193, 15007899, 133385952, 663249216, 348305755, 848031502, 247049569, 585691828, 509819328, 440345372, 711372554, 903605022, 192638999, 338810644, 570758409, 857031256, 508977365, 860374421, 439594703, 935358262, 414007785, 521772943, 203574205, 870341621, 448409623, 679844966, 853601865, 149380806, 253673629, 59505410, 503474907, 945216056, 513492679, 820493072, 871439575, 351538464, 342813223, 645929344, 201074445, 264570554, 683524909, 14548239, 957153794, 764526, 225362874, 219083971, 451563695, 958079275, 456968777, 411719942, 967300387, 85866262, 547456344, 849013663, 31842305, 73484849, 57532173, 108169441, 905517769, 157854986, 722264156, 991704381, 523737758, 380271087, 696012044, 516541357, 585274234, 406156159, 561140289, 81709146, 27715356, 748503, 634255801, 520926760, 428678121, 684328363, 725577932, 531296576, 776619514, 625744052, 748698890, 746656766, 428359320, 760385762, 847294298, 227407409, 99185789, 30325444, 535107173, 160265880, 90036901, 407817112, 741341199, 804860094, 53715968, 41911765, 903747251, 172540383, 186353633, 71114370, 477655681, 765007326, 713240678, 474415208, 205989775, 705839421, 57622174, 551749275, 801165337, 118631733, 350545457, 262354653, 66085694, 463715533, 995649028, 678985512, 978276618, 222141825, 107013739, 98988440, 250541518, 546176050, 495313630, 496397698, 940244787, 760431660, 786484549, 328304600, 643933960, 431133432, 736200722, 880372499, 589119546, 348354795, 173695498, 40714286, 591720204, 244650501, 290805419, 103276354, 143772243, 542674257, 746979394, 506392049, 296664303, 813475183, 534372789, 793909354, 815994344, 495756722, 330035338, 85451978, 616090336, 192524684, 254404512, 504929581, 15482055, 177918426, 791286021, 275983148, 215438598, 850631142, 604765246, 706582638, 422673201, 683216788, 742837182, 179469275, 31402652, 46722455, 161672475, 928272987, 735560200, 159248958, 314801948, 650694449, 471894521, 612343971, 451836455, 28393352, 392387546, 901106507, 583275747, 116712708, 218081437, 315172416, 820813238, 703168049, 332415694, 848005508, 551202753, 885302204, 45298559, 617969826, 326936260, 970547952, 869267631, 364569086, 833219418, 820355197, 704436865, 33424284, 12951602, 344005452, 222600410, 514965990, 552685252, 136548914, 880515960, 349389419, 242033900, 73848239, 441435345, 769282820, 544286684, 65540541, 193112763, 360998653, 720836148, 359164423, 843097649, 295423959, 810356428, 565188176, 239086637, 253020136, 718980555, 754021453, 943737448, 338018744, 88294315, 947192520, 88844356, 944592797, 76050701, 904666673, 115922719, 607856196, 665336, 325132981, 154152825, 152058434, 823490384, 303050400, 94102055, 448344374, 381204503, 667328047, 318572375, 476221932, 529372941, 298812667, 990771266, 889986831, 982225155, 826973690, 249178174, 291064391, 381483916, 40026247, 627540988, 655308, 163719713, 429973825, 509483326, 259477126, 233834097, 293080942, 781474239, 925032601, 349837136, 47526042, 70917372, 927828355, 532813519, 491558445, 160285530, 845006491, 721970193, 461787568, 771521041, 324062098, 421460895, 233204136, 653970308, 262580647, 466795619, 954252584, 416613010, 919562426, 557556274, 987789210, 532434172, 806803600, 134060296, 292948720, 875080083, 822663258, 63979527, 775575453, 298402558, 402937423, 594767075, 107780613, 973868713, 934394911, 607893066, 15903308, 802924354, 709656930, 480634924, 371192896, 688649339, 639416988, 328689046, 960126589, 767235932, 920986100, 842703733, 227904042, 130599370, 911097106, 503465662, 940176329, 5034613, 268553461, 37712131, 563442215, 853735097, 438519451, 922884019, 263784463, 612398251, 482478101, 529706070, 285625002, 524047474, 23096130, 673112918, 713840404, 948286611, 882316320, 542626015, 403606968, 957737732, 296273294, 603972692, 444789085, 830130198, 290582406, 719504649, 183787130, 468150900, 51297899, 190858556, 356172842, 528686000, 377928486, 353666053, 138546799, 681230774, 908364090, 776889987, 59582310, 437077965, 611656446, 584304112, 868259810, 221677895, 536719710, 600611625, 47066015, 548564451, 231379733, 320927397, 766463420, 847044491, 809378812, 776019482, 88199514, 268693011, 26123937, 284760172, 160800972, 251061251, 458787882, 883101157, 644673128, 13309135, 308948007, 726283993, 565821260, 919130966, 356453561, 152501508, 504216871, 316676703, 542117934, 683102831, 274639425, 724924930, 748499405, 319136175, 633693050, 16776513, 800598808, 819269904, 479066989, 611476394, 280167266, 347462689, 461217187, 830649976, 848033379, 626563435, 700595243, 333135041, 926872777, 508615571, 741686466, 808308611, 619810206, 772377006, 261255926, 144464181, 424260358, 653459496, 511229318, 985823988, 174144039, 526253691, 439268871, 27106659, 608362784, 805179523, 33529412, 815402710, 361339603, 245449209, 254107983, 56891496, 345252054, 910954898, 131733022, 564072561, 179532165, 656925779, 201518693, 778166964, 396149361, 441399420, 902680659, 290623182, 533760190, 937754515, 9883721, 737362004, 634727066, 438769591, 940255227, 743188411, 859212057, 667631736, 708912042, 166570273, 79190752, 257076836, 903579683, 788228511, 993656293, 197118157, 484447008, 632700062, 600115079, 821736636, 262643680, 255025849, 680252588, 289730352, 500573398, 104297995, 959335631, 53234116, 588672773, 244139510, 632571433, 916047979, 808789960, 971477474, 945838091, 482621086, 410592258, 701764376, 420364053, 225696420, 805113642, 574673485, 379682182, 131593875, 429138325, 35127479, 306342018, 528579517, 493778284, 127190504, 868361588, 905702999, 522009033, 218838129, 779594143, 3943662, 554617121, 104108048, 748593931, 386734123, 20786517, 81414936, 869248042, 1121705, 390695070, 365266109, 852743567, 65472860, 544183449, 230855228, 143575420, 945281972, 469308039, 465142223, 906911935, 942618391, 321269490, 803561497, 157397109, 724291278, 920555562, 756246535, 295782466, 98724349, 151330378, 222714683, 628460691, 123408966, 305862834, 692095085, 893370172, 939812265, 40286976, 931053509, 662072772, 962534442, 379405289, 313153552, 941144121, 601429361, 108241759, 909939600, 981888042, 620954475, 355811406, 976438363, 185651699, 345374934, 543216634, 324220888, 856284159, 581649376, 838973805, 164211676, 870774270, 475204363, 549564274, 364180732, 520674650, 232191410, 509239134, 548071704, 958197618, 908844282, 330260306, 459078594, 388407370, 213318897, 909632041, 195240672, 652432437, 238789845, 955183592, 471127904, 476267533, 87331537, 246228450, 984383421, 126480087, 294782143, 52150538, 412681357, 511815256, 614063343, 511266098, 403217161, 797963564, 908409219, 443790153, 876939546, 757754016, 920897922, 577457269, 996796590, 8004269, 523733337, 60234542, 49014385, 582002134, 457158066, 860106389, 981392883, 284272053, 963356353, 611995758, 242440320, 57794274, 345521995, 564088987, 78348333, 733862439, 248016924, 190803384, 146328580, 775607186, 439050135, 633438823, 207169216, 131190728, 10005266, 661578952, 962125204, 442166144, 617446142, 29936975, 232020999, 191500526, 316727847, 57127883, 177579886, 343979060, 626896917, 285041843, 256664926, 602403348, 434464755, 551670150, 892540434, 504171015, 575820744, 238020835, 817282671, 373048910, 906916283, 588877343, 393246756, 290238839, 375713547, 925829882, 14515293, 169430053, 298291043, 913561083, 425245735, 630299901, 786563313, 277376035, 886938571, 99587204, 321815371, 163402063, 373003609, 834706494, 265054042, 963477373, 790231368, 971736903, 880328717, 901950725, 668547978, 234358976, 500768840, 365266396, 97286227, 292221087, 420460361, 509713705, 661727138, 746169566, 9698826, 886224496, 785313621, 509684, 729495675, 660386970, 812722652, 199898272, 388408747, 305386181, 948704933, 896954321, 607813297, 408215013, 443993921, 723910846, 168101267, 20748988, 232675773, 8594540, 636685199, 382323235, 378596671, 86276489, 738779632, 423891132, 152141059, 438569993, 496225469, 789235418, 661136254, 450753772, 175791061, 253514058, 989964884, 455867606, 11027569, 66633267, 819228849, 937437444, 35017509, 428500003, 54472764};

	public static long[] go(BufferedReader br) throws Exception {
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		long[] start = new long[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++) {
			start[i] = Integer.parseInt(st.nextToken());
		}
		if(k == 0) return start;
		long[] choose = new long[n];
		choose[0] = 1;
		for(int i = 1; i < n; i++) 
			choose[i] = (((inv(i) * choose[i - 1]) % P) * (k - 1 + i)) % P;
		long[] out = new long[n];
		for(int i = 0; i < n; i++) {
			for(int j = i; j < n; j++) {
				out[j] += start[i] * choose[j - i] % P;
				out[j] %= P;
			}
		}
		return out;
	}
	
	public static long inv(long i) {
		for(long j = 0;; j++) 
			if((P * j + 1) % i == 0) 
				return (P * j + 1) / i;
	}

	public static void checkTime() {
		System.out.println(System.currentTimeMillis() - time);
		time = System.currentTimeMillis();
	}
}