#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int p = 10000007;

const int bef[1002] = {1,9280440,6430306,9534301,2083265,7638644,4027134,2358556,7687046,2496171,1145863,3513356,5181986,7585983,1138423,7766185,8152228,883520,8943967,4519131,3467465,7536254,451043,2404630,6446932,7895234,4189468,7074117,114398,1146494,1168620,978577,5044126,3585218,1939584,4949154,652258,310518,5219229,6748800,6236230,8692434,643690,4390858,4942166,4712592,6796496,5086106,5186149,9695576,2697936,5391821,2385041,8380200,4504036,9350734,2314558,3911462,494628,7178788,4081699,8647603,2329087,7132184,161773,6685567,3117982,208782,4474240,9631439,896207,2448623,3445245,7804790,2522500,3620564,1793902,4671022,5223428,1331881,4850863,7841536,831338,8079571,6810005,8501437,9734593,5160667,9295615,2086243,2543675,363260,7455607,953827,6650989,3899802,4321525,3132678,4774525,4570043,2651392,533957,3147662,2853751,21368,1098750,9236755,4012065,9324182,1234704,4026884,8337181,3875741,1501344,1098968,5727652,9519460,1337536,1175450,8407138,3142135,4177719,39118,9972133,5739998,8850042,4871923,8151891,9804462,175461,8900123,9837202,3126445,8054908,5956753,523613,1444481,1112414,5859641,3853459,3671435,9207686,6185491,113373,5291332,4211807,7482438,6951762,7663914,6149452,545478,1449806,5149755,616254,6057799,7067664,2667847,7030556,7327488,522958,7959427,1922343,5043545,7453024,1279194,9587049,572372,4565868,4750788,9354077,355113,1385050,5973405,1922829,3056376,963767,5960729,7578959,1610039,1314079,1778438,5869240,1317817,5478548,2710232,7727526,7011455,1572064,2276280,6969344,5181599,71605,7637047,7921885,6539604,437034,5768347,8414120,2827430,7776086,1507381,869125,2099184,9186154,8726238,8003126,9862383,1062838,9900141,7839256,5903197,426648,3535478,3936447,8779666,3747682,9397363,198907,6394934,8038900,9854518,4646666,6526959,3199835,4220530,3014011,3592240,6315940,9456332,3752184,2779760,7339011,2977358,3517522,1637934,1832128,4885970,4467380,1283613,5890551,8268173,9011611,3014433,9919098,5538424,9173534,9817115,5279850,2574217,3529504,4825560,7996963,6678198,6946224,7446582,4017009,325371,1723275,6411408,1341066,6288947,3185421,5136598,9097184,327824,5416294,4990060,5967247,2241470,1353341,6341834,6547623,1459479,4203890,8445423,2246390,1245360,8433288,7560146,531699,8797473,4846744,7568464,5869315,655389,8917005,477919,9946917,1202252,1794897,7782087,949167,6396643,3996089,1784976,5910062,1160066,8862450,6161072,3115572,4633246,6435007,379103,3117318,585606,2350052,3861064,1119093,2605765,4961572,8712315,9941080,9637620,144851,4991430,7569412,937419,3022927,3243772,5872769,3656228,3917331,4937650,6303235,5496427,5941626,5947154,4506513,7397795,57402,6657873,5307693,5701608,203147,5304023,1912707,6105618,2923704,671572,9994086,7055280,8863178,1104375,4964529,2644322,4111574,9007173,8020846,3727750,3846688,2084100,1746800,9674796,4785126,4262974,4436951,2339005,5815917,1441027,7143970,6300873,871732,9140882,2534296,9552526,1984714,1759658,7248966,1807609,1761775,427631,9949239,5602866,3175909,1240302,3298799,2670559,3813230,620572,2340356,130690,7997165,8116720,4644245,1946005,7013912,8933579,9116070,3860822,9541381,2697660,1876466,856655,6515405,4533500,6141415,6602877,8461257,5585139,3105675,2971819,8527586,9858993,6771115,2560057,5948417,6636771,7116720,4745829,4566681,8560460,991308,3511016,3355594,6022843,5659122,2008317,407870,5884119,5801417,3227664,90400,566135,51756,6684221,3738105,3799847,6185084,7428801,328063,7291278,3622867,5543129,4474180,2195015,2814430,1878818,1141246,6875999,8512631,9512490,2694786,215938,6271645,8475372,2929637,8995394,1363650,926188,5921849,5471594,3475650,7508595,9587747,9130460,5687770,1238364,5889902,5409303,1334483,5491664,6207279,2496421,3050945,6950643,4391693,7055770,3299180,1703274,1210720,2044794,8313092,5076207,5028793,2802189,2019933,4226626,1764785,5129408,285762,9425722,5706827,763991,239596,4050818,8850217,1858820,7483694,641524,714668,2793709,5907383,7793666,4335562,6519389,6632412,5329960,3008997,9152703,2707613,3797774,5088865,6678643,9611382,7169662,6239265,434887,7016084,4539827,7804602,9508087,1312171,5034396,698374,9880534,7447138,1228599,4517742,9019783,1067547,2553963,484506,916140,6106744,9035892,684124,1636097,8140316,8348214,9132304,864420,5469846,1959274,4562313,6315913,7040324,7897321,546601,212451,9087541,6246733,8822016,3485708,6869436,8402809,2283403,856666,6327182,5717453,5140108,4536569,8537876,3800193,9173954,6269871,9699330,800739,2364956,1801491,8637485,9795962,5229171,8577279,4742293,1890470,5436455,7926496,6784699,6402455,6448279,1589003,1457078,6877786,4636946,8967455,2324873,4843226,456026,4175030,8350546,9464923,2533093,2581866,1089186,5605417,4575868,6730336,667544,9734786,5922898,247619,1141112,9479230,1482431,6719579,8060543,8950217,7974983,9159877,6746464,3121442,8034246,2410344,3384725,882881,2824358,9681054,9954050,4734205,5153921,5619305,5738219,2376323,5602226,1660013,5109521,3157602,3188703,6251473,784811,9115165,9469949,3519002,3663212,6952690,2661902,8031547,6478189,2844564,7661384,9952465,7057380,2477438,9305853,3786959,7091517,118810,7035052,4725381,6261010,8873045,8084970,9753402,1376108,6962467,2982212,4951977,3012286,4926123,6197869,5053118,8063652,9705891,368918,5519117,8477503,1507546,3448418,2743957,2132604,8167392,7114990,4272031,4915390,6078514,1010103,6968122,3968836,249090,7797729,3506065,9926250,3614194,9553144,9556200,8016300,8244804,1329141,9168043,8484782,8042090,1191681,3515717,9352843,690830,1927788,575488,8726249,6832499,6922874,7567888,9613264,1882183,3067154,8940586,2383541,2279545,4712476,8061770,4444760,5625344,6521282,1163110,4229859,8721782,6178607,87811,3410637,5688434,2887820,1240785,5008597,5078987,9062788,4668940,2012524,5955251,7610707,9227087,3452342,8500165,528246,7383007,7277456,2653128,5979935,7763976,5752637,2360403,4503767,9112888,477223,1366952,1461910,7720320,6800505,2698725,9429186,3987025,8532230,7544432,8899182,4667348,5067728,6449562,5706447,7093675,7470645,1406947,1510339,7870588,9996837,2736429,3177114,7156758,7920486,2839829,1163623,5384056,7709082,2159612,4749866,9791771,5786812,3473130,8906206,7488291,6814834,5108093,5973389,6972572,6576157,8172465,9901928,7169783,8354573,4721138,5123048,4509408,2147041,4363013,7067266,85529,6239708,872673,7002930,8923686,9696499,9130668,1532877,89838,2904815,4752273,541492,865766,3550545,8530199,325650,5484742,5039997,4254559,6865989,6369718,7272880,2681456,3777769,81336,9795827,6555645,2052987,9506585,8108496,2343672,9484152,9053473,1416550,864700,9661950,6612856,9717587,8917642,5899433,8144730,6394236,5305602,6207913,2561081,5053707,2502475,7303940,1389794,7895356,9854160,8581162,7323297,5642381,6027093,602683,9892681,3608017,7678036,3918370,2483451,9274530,1892415,3213168,2137953,8598215,8651066,304032,986059,1037529,1919294,4978300,7457442,6460604,6502035,2183723,7175965,8989955,8064183,872419,1946333,943744,4406465,8593661,5835021,487223,1657405,187634,6356596,1227308,7211960,183174,1214427,7271463,6026062,3019606,305250,6289652,6420626,56895,9372505,5999804,646910,6561541,8432524,6144206,3652067,6366958,3791323,2254700,2036918,669993,394577,2007606,4262819,5950775,4545577,8652149,6799135,5436174,8339781,6889727,4268979,3548410,4494798,6866290,4841557,7275216,3383757,6771198,9776498,9182158,7050698,9479938,2377341,1192388,7783255,1138746,6718419,4430765,4159576,5284554,9034478,4300736,2830536,6373576,3471784,8829548,1474535,6736121,610657,9549491,1745031,3399879,129069,1979898,1789846,211378,7418845,164032,4042048,5735,2714676,1560725,7482486,3284500,302078,228361,8399091,4999195,5525451,3422999,9681762,6159898,3498983,7115763,8855513,5003746,1011455,6742991,6761389,5929616,2250072,2425201,1844496,2739871,1585181,8263277,7787614,5283652,7471906,5562259,9170228,4968915,7240199,4283420,3965817,1997691,823598,2755665,275759,181765,1953550,3312384,2068912,4842387,9484637,4379867,1202687,5101993,1207850,9763470,2981498,6136278,6015511,8004812,641424,23424,6008867,0};

const int now[1002] = {0,9640841,7765684,597480,4702438,1066593,2448304,6932160,2949966,2923491,6864858,1576658,1038459,8910871,859328,2628467,243311,1506518,333708,1817159,4924052,1669685,2642268,1112028,8805171,962703,3601797,2026174,244572,4454100,7332295,8677369,918162,1753829,598875,2087543,3452046,7936131,2160732,428224,3159124,859311,8951293,206759,6599288,8490091,3442823,7242877,9965486,1827974,6691396,9168424,7970710,3072187,2014494,4903482,2477457,7292072,3624274,5336006,3502944,4878339,5614260,8430952,4017106,4906027,3804551,5819884,6124379,1133845,1839421,397336,9331957,3076719,763352,1982599,3950665,2121037,7882224,4381983,7604967,3035124,2726482,7816404,7799686,6668122,6801617,4042723,9516511,6205455,8568485,8005142,4649870,6627167,9276378,4492630,9849999,4704945,3479138,5809233,129680,810014,2713775,1023612,7115164,8511828,3307210,9908331,7528195,6499741,6413448,8035176,6700514,6073302,1958020,9025482,5122744,6887886,8153999,6974752,4104291,1686473,3622762,9969301,4938391,7711903,9604533,2684478,6987324,1362032,2581621,2843439,4644031,2055213,8405199,9163636,6511280,4208832,6201245,4713858,8891213,8140591,6560948,7330001,1867830,6332250,928266,4088467,4012237,5165080,9125622,279740,4784527,838967,1915477,9283160,3142253,1102444,3200318,1066747,7012420,2874554,6147904,9101292,1905291,8491818,2474890,9936609,6068710,6509750,8700833,6459047,5209784,5531885,2958309,1117366,9170450,191481,788295,9902339,5453164,2140962,5277306,5122364,3989579,9984065,4488959,696985,8262921,8870162,578326,8212052,6647485,7880374,6708211,4722692,2213163,7040366,6471520,6690052,1438384,9173410,6906194,849977,524670,5749487,4240740,6846804,6744887,1351627,4122461,2221467,4567848,2470185,4856150,9097789,2637535,5031874,4682439,808727,2571499,5776604,7726950,9765162,3740933,5130069,9634154,7859301,9270919,173322,5994671,513525,2644265,1065601,8418831,5744805,5981292,4380907,4475341,5532400,7568903,5730512,9915130,8471754,5531002,7594133,4654669,7002517,7839072,9687790,1599013,7247174,4519600,1762146,546809,2301485,1874823,5857665,6529365,5282067,9033660,5311594,8162435,8102863,3504631,8381510,7613098,7068538,9399454,6635390,7116247,5342515,4884468,2001703,5130401,4338197,665465,790000,3328997,8095478,8774273,7813768,2067377,729571,1321716,9051424,4293103,9227886,9929254,5802960,4407575,7622845,3024637,1467502,9976077,1821377,57596,3364329,1336753,5398494,3698724,3888300,1305907,5197494,1776548,770445,7949802,300239,2634449,3379332,8883893,3021898,5746710,5619119,9628999,7600262,8783693,8334842,5339692,263217,1860553,9618971,4698600,3915679,4684799,7939897,8534925,7176455,1472369,3504284,9021663,1279371,9719534,2963470,5909920,5339997,4207024,8696653,5650509,8081571,5393354,209438,2514894,9076140,6348240,8923095,3145740,794798,2611363,8409516,5351818,4018010,2323095,7167831,6212542,6373983,8182196,859045,2275685,7670114,1373327,114548,7102473,1630211,6508361,976275,9388094,1401345,3662441,5558674,9880678,3631820,2785099,6342395,6270272,1413086,2954740,3364371,2911065,2110608,3379392,1509804,7987971,296228,5572533,624628,6681363,2703035,8880753,356240,5175695,3840475,3466236,8324063,4519276,3334051,5764365,6342691,994577,7090201,9472340,5811676,892658,8430620,5773888,6047213,8700509,9570378,2589378,5231765,996918,8383774,8772460,7841090,8950988,1706102,9970082,2383731,9573294,5067024,7545934,1319671,9755992,547662,358817,9292927,715105,8285766,6717298,3176638,9166094,1521528,8946832,1755228,6750276,5411286,4447708,6891138,761523,7256584,3365934,7868295,1640251,823174,5591773,829902,2686321,1497365,7719083,1260589,6669068,2150097,6602403,4846173,6592113,6644147,2221506,1912511,1654683,3731523,5231697,2139089,3712314,8267813,8577393,6697598,9370217,3866624,5557935,8619264,2840879,2251168,4578517,6391217,7935714,9112143,6777845,756377,1415195,5856588,3756735,2321930,2447136,6089753,2398804,7696693,4267968,821470,7265114,3817725,2673180,9953308,6079741,9459639,7014448,7531824,3367488,3036808,8628882,9324716,6326366,4661181,7748881,2390886,4966997,3156519,888762,7257670,286260,1744683,8471069,5536081,4035509,3709161,6407324,3607242,4844913,5443685,3272153,5935439,4245737,562038,3526367,8100891,4385814,8103823,914456,6822513,2545888,5991883,1797852,9019680,9012211,3283682,9780731,471094,2472095,4202305,7736312,5666642,7088319,9198509,5756157,914301,7906483,659553,8763880,4968503,8545629,1158117,1111126,2354781,9180801,4763800,5275924,7748390,4740827,9025318,7260934,2502620,4343395,5736391,942330,3410829,9560560,3576096,1504270,9576502,7004124,3051162,2212113,6925573,8579969,5622279,4171716,2746321,231081,4582271,7597829,9091255,9979838,796063,929361,487526,1678543,7748545,9601904,375225,3752942,8750419,8774474,5700779,7526030,4024063,5046606,758854,8760456,2244090,7017436,1430725,2016080,4443139,6713290,4600618,7728620,7782248,5489354,3829609,3466699,5722610,4173980,1297639,3245805,1656712,3650084,6880853,7061704,9705296,1358617,1053851,9714688,7744693,8612515,7372330,9628854,6600369,5107061,2032152,8509440,2727612,264509,1070657,8600150,10291,5107514,3992897,3243687,7758194,6252205,9860651,7467182,6148517,2151534,2967660,8606191,4590597,6587405,3290194,1684127,3245705,1100098,1905712,9409237,9041629,541755,3623846,1758177,8890272,3295382,9807398,5226866,3644438,6505394,4514417,3086302,2484053,7530754,2077532,9288874,7501194,2983506,7414681,5507868,494279,3188641,409312,1557008,4064267,2213031,5074223,8953555,8240103,4194271,9500396,5638121,4602632,7030123,4056057,772584,9109288,8083877,5057680,2338784,2619208,9211907,6618731,5162522,6567308,3128071,7291046,8028172,1107296,2968910,1776997,5562896,9348835,6225011,1205973,4047186,9304869,1743172,6681863,2435121,8289200,9639408,6438585,1060049,8779125,9503701,7675932,1643240,5900603,1409595,1185313,1714590,3776032,4693118,8032316,1555239,7631744,2816473,2517765,3553417,2164212,6731320,3553239,8047840,5905462,7071420,8410116,1912517,4676287,7061942,3914756,2151195,4824694,6701980,2977825,4349041,2066491,7486985,2232697,6308464,4897260,7198261,1407681,1831447,9757669,4288900,6771249,7158118,8640066,3030283,7255593,3211228,5474339,9856229,322076,1278411,4785903,5381232,2482446,5101901,5371579,1144196,8401955,3755765,4126345,5225022,5388367,1181808,772908,9334743,2640854,6241399,7394183,3777573,7835171,8076120,5735132,1267723,9589800,3464008,9184338,3071925,1955137,6522126,7069181,4184331,5760802,2830824,7003474,8691021,872568,3372984,6246180,8995773,6491890,3389286,4760782,8333038,3493528,4662256,7410570,6635245,9858449,6937970,7424143,6050718,4013164,6179898,3192753,119273,8321497,2300805,6943288,1629072,4929811,5455324,2788206,7204704,7077948,7816692,5538184,2867632,5446025,7230381,9503355,1436035,563846,5011944,6850040,6678957,3184399,2607900,3528454,3005554,2496769,444704,6859835,6910024,5679375,176730,984099,5830367,7379126,1172749,9570453,5244729,870967,5895560,1002419,5278602,5665738,5208088,6239859,4207010,2972970,7584400,54344,5668818,1672217,8605094,8619761,6039250,5707512,2315824,908473,1831873,4181609,5967280,3706063,5605054,4741436,6004717,236260,7934699,540312,9675863,7206858,6654807,1742180,3244272,8004146,1079623,7314004,4734116,7842555,8481673,278358,677333,2640377,2687300,9152429,5763167,4886208,2541242,2824136,7245013,9418061,5514237,5126221,7714406,8274953,4722289,5360817,4814863,2567282,5196262,6019226,8265004,7691646,4415519,48955,9869616,1922209,4105388,4005295,8938023,485073,4896701,8270645,4610969,1980992,9969132,492644,8945826,1872645,5907987,2542286,4378473,4973481,999894,6905003,797288,1088236,5773798,5236478,2430534,8530910,2855257,6400224,2382207,3750427,9464773,6878023,432452,5234760,7249117,6789403,7882556,2678437,2231992,8917623,7552700,179791,4518331,870626,9841831,6831066,2769386,9811274,5546941,3170975,4102218,3363539,7948144,9286466,1933951,9064722,9904212,8963203,3423859,9707095,9857030,5652035,2717312,5598950,2545701,3497308,2880346,3916703,5045141,5373873,5903647,3657598,217175,813287,6794503,2994798,1731982,0};

const int sumf[1002] = {0,8562107,1961659,729253,1488133,9771829,8923741,6222868,3586970,8343152,4875571,6666671,7258903,5407710,2857078,3023111,8638849,3896555,9611382,8153448,3315561,875616,5735578,4628685,4057259,9820639,1393054,1126457,603541,54686,5833202,8333307,6880449,7092875,3137333,9124239,7556349,6182772,9540692,7605247,2554470,411048,8546268,4804375,8140734,1692759,3682134,9571852,5117106,3351516,6080720,3728654,8326453,4524566,8533023,9157690,7269471,8495598,7743175,7850792,1087579,8404273,3557599,3994073,8195984,6497613,727076,1848542,6722990,1899121,4575048,3243294,2109144,3958220,4049203,7585761,9695231,8913095,987861,95839,60782,3911776,6284301,3712364,2409362,1837666,3337812,3246105,8328622,4497145,9680637,6373536,6755339,4208153,5203730,2885054,4021508,2542560,1732793,6188501,2910751,2153984,8575211,4900974,4251688,8122398,5851167,3828712,4380557,4234178,6853772,4407518,7276761,3647940,5015007,3778601,9764940,5113300,7483440,2356627,1350709,7550664,7284641,9910720,5616772,4273833,4080974,3520839,3779095,2899524,4063357,5524072,2414499,2165326,2767136,8850877,4467033,9530077,8262123,3281167,1453846,5488853,9307379,4773367,9026991,6876299,9338969,5128688,5688380,6479604,8796714,2009285,4718801,2294187,9888752,5633969,8952352,9235443,3728116,2656451,1984252,7671450,7339345,5655593,5089775,6570670,5522151,4439071,6888200,2373562,7756771,4303136,6392965,2986591,8972993,3198498,4301614,7961920,3186628,1118742,2684758,151156,1872421,5723268,689382,7695641,5989365,2966033,8802114,4709653,6338250,6495701,932002,3682618,9956018,9882417,194665,2494837,5770462,1156175,4384148,9215937,5911564,886100,9775577,9502092,8343855,4756438,3389900,542502,4148111,4869581,2671166,8876816,8491958,1943245,4672425,262647,5759804,9656353,4997508,6199866,1980844,2730144,1702388,3274141,2860533,2034527,7998155,4098827,4769094,8366060,8265887,5648723,8475588,3321730,6848546,3229186,234287,6955343,3405964,472620,2844678,6862591,6600420,4361785,9126445,9284876,8252353,2905069,8023585,2491296,5717390,470508,8540199,8619978,4075016,3438597,9470130,1905192,4356252,3808601,1461453,5302895,7337085,2179299,216241,104308,1040363,4624113,574313,7232645,1228407,8207295,8706217,922776,2576289,13280,4218132,6722647,6346004,474265,1703210,7328456,3298820,7019838,9064124,8402674,1060745,3400809,6597229,6194849,2445909,6931092,1737115,9552815,1275257,5591100,8834577,3912552,2030686,4211599,2990916,3512298,4138701,3890941,9760660,1719570,7874662,1720228,6480086,5984868,1131025,1383081,4249413,2769921,8504797,9692603,3923148,6399202,7377333,3155258,4334842,4134585,4866017,1821405,3016989,8859415,342525,7065969,4701184,7866434,5140661,6130086,7123855,2592693,4519658,316995,1972582,6157213,7841980,9282053,6134162,3116794,5340794,1957749,5298645,9610441,8950475,665705,2787728,9782819,4320978,9120780,6688050,7184909,8703389,7534006,5992396,2484183,9047526,1100827,3345813,5794717,2569233,3937263,535831,51648,9132490,2879115,188972,7212871,1173056,5860691,3780838,6124970,8580038,541964,6442701,6561571,6889473,1016765,4092647,5236700,3091063,8263167,2296290,4522132,1622313,253853,3049042,9557415,7789126,3163516,3572044,2809509,8131599,1146624,7574292,7286069,1916484,150923,1644301,3632340,4107825,8042835,4037774,6257461,9924584,5030203,554288,7758848,1055921,9037766,3924804,9071325,1948466,5175331,5030692,5935457,8319524,2729741,78104,1147079,7401854,2323944,5230056,2756601,863382,6681338,5623451,6665922,3436778,7984635,5695559,3636994,774226,4923514,8399044,3025784,6244350,8431368,3496439,7917992,9658910,4589440,4368028,4358379,6364346,8443026,8809722,7775843,713386,9280085,2314671,8976056,5681375,9714923,8718668,8797528,5955050,485449,9921048,9586563,4105414,7786881,5796189,1032420,2819136,8449240,7726551,2815420,4233233,7811219,8673609,244204,7782308,3277538,7959797,1998930,6939184,350679,5658262,2419094,8848425,4243588,394748,9126633,5171744,8350117,8140068,5813984,9953140,3254825,548270,1696045,2064928,9082612,6410452,1357030,6450498,4411219,2176390,4393146,7103648,2552295,2212410,1531409,5112346,1293960,6450210,2384325,3105406,8116695,2695167,4661614,918417,5405104,5564081,2938417,1045429,1608581,7968873,2308511,7807512,6891762,3465008,1785327,3439982,1116055,4460123,3509191,9983688,1129669,5877360,7982511,2841503,8951210,5685067,420810,423356,7219019,4998014,8698037,4215760,3602508,8384418,6264180,2808696,7456341,6758820,3247430,2161780,8701546,6821711,5196095,282385,415577,6323351,3642717,8482744,6701945,461931,1563943,1011575,2588639,935028,5937688,410688,2550595,6013228,5308216,4037709,5881496,7310879,7817514,5305387,9620567,9370680,6533041,9424584,4125218,4440587,2064237,8962502,72943,5934129,1417993,7240662,3423721,7796559,2542662,4531275,9530556,6812783,9578250,6471114,2463155,3194734,9607913,7153601,6920516,5836916,2585953,6340113,8388846,659747,7613260,1667595,6599133,3967257,8333496,8867932,8915649,8960180,8871219,7281002,2599280,8968706,2892512,8544526,4959320,744017,8407864,6210383,5862632,8245661,542485,9863436,3116600,481475,9198693,9677730,9326434,4001979,5077303,6606183,2551425,7229783,5982297,3807394,381989,4056462,7311427,4174834,2163398,8126779,9592673,8294376,2689271,7253313,1875068,8524350,8452168,6602626,5725187,5023899,1228947,9334720,1747385,8621116,4403858,7282811,3944216,2251110,5978208,2029615,8123899,8826830,2800102,9473076,4755597,4629922,541694,5933474,8834923,1358812,9457674,3594097,8633220,5949185,7671879,1904251,8353620,1967064,1133044,4635726,6838355,8377666,5141435,3735627,9728616,6559750,8305569,7364385,5620995,2604581,7847084,4317904,9026844,1681673,8735873,7100929,7783852,9847566,4876262,2537825,5822582,3782798,1497543,4727128,8372315,9949228,5641173,3947741,4889686,8075348,5168942,8234474,8804198,1786637,2329444,202189,9648081,6082307,3531991,7150204,1817254,5470880,9767247,4745826,5512752,8473785,5790333,1182945,3906975,8794397,1240095,8129857,5352447,1369458,8251748,8791224,2897232,751944,5355827,497620,3426287,105021,5643320,2844543,4462223,5353349,2971626,1553265,735840,6502722,678946,3961848,1251565,6475840,2029983,5852329,297983,9895585,9854876,7200734,7458985,7664914,5545187,7735028,1541041,8376259,645071,9458174,5158468,2232660,3375730,4959444,2923767,6726628,8613081,8755007,1521408,3355463,1791281,6478824,5366826,5282893,3003133,2625283,2084400,1680281,8910160,7009615,7460818,1574436,4464004,3853396,6561593,9916206,872922,3751745,9018015,9427423,6270121,8072874,2779592,3334209,1574543,6172646,5095544,1668176,4305277,2323948,1133433,4740632,4510221,8714284,7743907,1277423,2284931,8383275,3037215,9907211,94474,5819224,4913321,3413115,2880344,5799194,2051237,5487529,9657522,3058553,6534423,487840,9609385,2764743,4735708,7701916,7618442,5841357,5643320,7108214,270068,8149060,3591745,9540473,4023694,4806099,2396271,2272753,6946497,9118168,1218841,8847532,1324614,7665415,731881,9855295,2877256,2503529,2275212,4822633,1073364,4249033,6433162,6826197,296321,7694224,4571741,4422133,7422688,3292919,8686479,657702,4836551,3968995,4652862,8355178,7469020,582598,5482668,2656336,7034060,4301907,7224829,3003778,780659,7100929,5739059,8525461,6678277,2553822,6635606,3731043,1635870,1508908,9208864,8153800,716920,3714373,5194570,5795305,3320818,9577281,2514554,9331575,6111323,4412223,7023632,5205295,5732049,6495268,201557,2007059,6326951,8175771,3177190,3248412,9814049,2990606,5382463,8773695,8145153,1041304,4384158,1347815,9799693,1267929,3277396,9832594,3511467,1683280,4385166,8020713,5725187,3605812,5295949,6175783,110986,6041835,3815733,4309251,3737196,9030074,3757448,5163145,7290173,4109597,7799635,289857,923845,8611293,9915936,4363886,7585275,3353732,8582544,6776559,2099857,1225365,3764847,7355464,2784782,881150,4481122,1268828,1925394,3326378,4906185,8565780,1904201,7374656,1695985,3136472,2856337,7833718,127120,632007,682056,7123476,9595947,1667595,4616446,7503535,6040279,4576031,1374475,6963378,2935391,1298124,511201,4788784,3451466,6449860,9631385,4230422,6013019,9472830,0};

int in() {

	int k = 0, fh = 1; char c = getchar();

	for(; c < '0' || c > '9'; c = getchar())

		if (c == '-') fh = -1;

	for(; c >= '0' && c <= '9'; c = getchar())

		k = (k << 3) + (k << 1) + c - '0';

	return k * fh;

}

void sub(int &x, int y) {x -= y; if (x < 0) x += p;}

void add(int &x, int y) {x += y; if (x > p) x -= p;}

int n, k, a[100003], sum = 0;

int solve(int x, int y) {

	int tot = k % 1000000, a = bef[k / 1000000], b = now[k / 1000000], c, sf = sumf[k / 1000000];

	c = b;

	for(int i = 1; i <= tot; ++i) {

		c = a + b; if (c > p) c -= p;

		sf += c; if (sf > p) sf -= p;

		a = b; b = c;

	}

	c = a + b; if (c > p) c -= p;

	int sff = (sf + c - 1) % p;

	return (int) ((1ll * sff * y % p + 1ll * sf * x % p) % p);

}

int solve2(int x, int y) {

	int times = (-x) / y + 1, ret;

	if (times >= k) return (int) ((1ll * k * ((x + y) + (x + y * k)) / 2 % p + p) % p);

	ret = (int) ((1ll * times * ((x + y) + (x + y * times)) / 2 % p + p) % p);

	k -= times;

	x += y * times;

	if (x > y) swap(x, y);

	return (ret + solve(x, y)) % p;

}

int main() {

	n = in(); k = in();

	for(int i = 1; i <= n; ++i) {

		a[i] = in();

		sum += a[i];

		if (sum > p) sum -= p;

		if (sum < 0) sum += p;

	}

	sort(a + 1, a + n + 1);

	if (a[n] <= 0) {

		sum = (int) ((1ll * (a[n] + a[n - 1]) * k % p + p + sum + p) % p);

		printf("%d\n", sum);

	} else if (a[n - 1] >= 0) {

		sum = (sum + solve(a[n - 1], a[n])) % p;

		printf("%d\n", sum);

	} else {

		sum = (sum + solve2(a[n - 1], a[n])) % p;

		printf("%d\n", sum);

	}

	return 0;

}