import math

import collections

class Solution:

def waysToSplit(self, nums):

# 1 calculate sum[nums[l..r]] 0<=l<r<=n-1,

n = len(nums)

s = nums[::] # deep copy

for i in range(1, n):

s[i] += s[i - 1]

MOD = 10 ** 9 + 7

def summod(y, x):

y = (y + x % MOD) % MOD

return y

# 2 split into 3 parts

cnt = 0

min_r = 1

max_r = 1

for l in range(1, n - 1):

a = s[l - 1] # a 表示第一个子数组之和

if a > (s[n - 1] // 3 + 1): # 第一个子数组之和小于数组之和的三分之一

break

# 2.2 二分法查找中间数组的最小右边界

ll = max(l, min_r) # 最小右边界从l开始，并且相比上次循环中的最小右边界单调不减（因为随着l增大，最小右边界单调不减）

rr = n - 1

while ll < rr:

m = ll + (rr - ll) // 2

b = s[m] - s[l-1]

if (b >= a):

rr = m

else:

ll = m + 1

min_r = ll

# 2.3 顺序查找中间数组的最大右边界。注意：退出循环有两个条件：

# 1. 符合循环中的if条件

# 2. 循环变量达到最大值退出循环

# 循环后要判断是因为哪个情况退出循环，如果是因为第二个条件，则本次查找作废，不计入cnt

max_r = max(max_r, min_r) # 最大右边界随着l增大 单调不减

for ll in range(max_r, n-1):

b = s[ll]-s[l-1]

c = s[n-1]-s[ll]

if (b<=c):

max_r = ll

else:

break

if (s[max_r]-s[l-1] <= s[n-1]-s[max_r]):

cnt = summod(cnt, max_r - min_r + 1)

print(cnt, l, min_r, max_r)

print("L M_min | M_max R")

print(s[l-1], s[min_r]-s[l-1], " | ", s[max_r]-s[l-1], s[n-1]-s[max_r])

print()

return cnt

import time

start = time.process_time()

# Time restriction

# nums = [3351,195,2720,9916,2691,5490,4494,671,1984,2250,8883,8371,5617,961,8089,8754,8873,2836,6150,4147,1429,9451,2801,9514,109,8182,2496,8525,5743,1058,3941,7637,3908,2381,4229,8679,1271,3871,734,7727,7391,6361,9743,9200,4814,2469,5556,4506,4028,6389,1529,7347,1699,1878,1594,4493,4745,5365,5089,764,1442,9211,4256,8727,9145,4613,6927,5275,6973,7887,6584,5326,2607,5292,9271,3112,8159,9735,4272,6006,8046,1963,3673,6491,5898,8194,9133,3542,1864,1873,4246,517,495,9875,4187,4436,7779,5038,2734,3172,6062,7430,9575,4775,3158,4859,3742,3496,3285,7591,9734,9935,2908,6109,4451,9225,3088,6111,7056,3994,2374,1323,7163,8481,4081,5773,3254,8279,2521,123,396,9960,2474,9791,801,3297,798,4423,4375,3441,6815,2994,1611,878,1819,7157,1686,4101,5802,4734,5625,3893,793,7780,4023,2862,7620,6474,9395,2282,6954,8745,7753,5898,6872,6895,3482,8461,2677,6402,9314,7423,4704,1501,2554,6134,4399,8179,8215,6053,3261,9901,3077,9841,5934,6646,4392,522,2334,9262,2381,4104,4731,384,4429,3499,5865,920,8349,78,6830,2281,7897,3979,690,5732,822,6133,5942,8962,541,5144,2992,1220,6638,2578,7934,5330,654,7784,2558,110,8587,8197,6158,7523,722,318,4868,9750,171,197,4980,5203,7470,4005,2134,3911,545,1633,7224,2645,8550,1720,1685,51,488,6313,5520,167,3395,8045,8082,6297,6717,5554,7686,8760,5937,9087,8481,5814,7329,2234,9243,5065,4748,8382,124,3713,7658,2805,7260,9777,7211,4586,4412,8386,7450,422,4208,7105,5921,5155,3554,6804,909,4861,5032,3028,491,8454,8554,768,9929,2087,4584,6206,7796,820,2850,2006,59,6046,567,6180,1259,3899,8344,8571,8401,1691,6723,7872,8867,7618,7682,5104,6750,2716,5537,5014,6456,3978,2662,5092,3965,1273,5354,7133,9924,5427,1914,2021,1532,2202,9916,5931,8362,9193,5153,1013,8954,5766,1364,9277,5455,9910,4544,6524,4564,5203,5161,2487,2205,1130,1799,2368,2962,6026,1374,5511,2030,3599,6608,3521,9933,2482,5139,8280,2569,5187,937,3794,233,3293,3007,74,9346,6408,1897,8689,6518,9840,2993,1845,9800,7456,943,1253,3153,5205,962,7688,8479,2990,2782,2334,3663,8338,9122,5961,2502,1188,6801,1393,613,5509,8311,9456,6026,2557,1616,3411,1180,7720,6186,3579,2167,4738,4350,6528,8981,4622,3752,9250,3269,5804,5722,2733,6289,1427,9841,5432,3010,7896,8264,8134,4955,1302,1202,9207,6884,5510,853,2883,2144,1810,9470,3348,6003,6092,1055,5171,7207,5758,779,5218,4514,4124,4573,5645,5261,1885,1624,2702,1035,7684,9002,3195,75,5966,2798,9339,396,3454,2417,3508,6973,6462,1245,8291,9995,4293,4486,9003,2761,3280,8004,1204,1479,9358,1123,4225,6434,5219,1405,8096,5909,4942,8142,2638,3464,9619,6737,2478,6538,9315,7860,6882,7004,7303,15,2374,5175,8796,1354,444,6501,4034,553,2911,3732,4031,6386,7721,6727,3788,1688,4408,6924,8520,8592,9409,7749,4520,4298,2389,2821,6691,3400,5980,2124,416,5115,1881,3921,7037,1992,4996,8629,2912,8465,9012,6786,2873,4657,4218,5128,8360,3367,7750,8439,5000,5061,4269,2629,6225,4042,1389,2003,2830,8056,2105,2279,9464,1516,8414,5024,6671,4889,1558,9145,6986,8572,208,8933,3638,6197,5361,1484,5168,1050,37,2437,3028,3158,6741,7824,6676,1005,4751,7899,3406,6416,6087,3745,5310,1184,3815,2867,8595,1104,3371,5103,2806,8275,428,7628,3331,1964,1097,2280,6711,1425,4062,5073,9609,4163,9845,4761,6440,5547,8600,4937,5828,1094,2329,2148,5724,932,6006,5840,4152,1518,7282,4390,365,5987,7921,6030,7053,5568,3310,2684,2120,3331,1577,4266,8199,6047,5536,3442,1716,5753,4486,4551,6421,7782,6934,9670,4557,990,9078,9532,5311,3450,9711,2989,9077,575,6258,8675,6693,5757,1372,9356,714,2527,5796,9345,2171,1668,9306,6203,4558,7560,2876,6610,3022,4617,8558,9210,713,2887,9130,1867,838,4281,5377,446,26,5594,9496,4866,7897,6700,556,6355,8531,9870,5697,6963,5077,3875,2693,1682,5941,179,5464,3377,6393,827,7515,6814,4282,1333,9388,5736,7593,8792,4189,5401,9471,237,4056,3233,3169,4161,3842,8432,4022,6,1988,2672,4776,8616,5761,5802,3186,8350,2817,9847,5772,5887,1685,4206,307,930,4681,3553,3712,7811,5701,1842,5342,2654,1247,3745,7963,5406,6852,2578,9460,946,4523,3382,9361,9175,2482,319,8394,2632,3169,2029,8075,7235,5550,4941,6085,9702,1900,5212,3804,5179,8487,8337,6609,3677,5076,7278,5120,4519,1114,5300,2721,2152,1759,9809,4951,1370,9517,1847,5492,4568,7331,8141,4590,4713,9030,547,4469,3117,4309,5436,7101,5811,6329,4643,2349,3712,7953,9373,6193,4237,7434,8695,5242,1544,1201,6101,6240,1238,8383,441,9723,6817,5005,6196,3907,8013,7695,1150,3155,1827,2604,72,9547,1723,4204,8303,9052,2424,5625,5764,6526,9784,4853,1687,8407,4558,9632,5893,4246,1193,4046,4737,7520,5079,6461,6676,8420,8949,1643,9664,9169,3548,2811,4368,1831,5741,3297,6861,1811,1975,6809,4110,6644,1289,6540,1759,3766,1310,7561,9045,9608,6396,8129,9809,1961,3208,2356,9594,9387,8512,8307,9056,4298,2789,3385,8174,6377,7765,847,20,7007,4279,2953,2357,8899,7873,2720,1306,2099,3614,7837,6214,6653,9103,3766,3130,3610,3533,9866,5093,6934,4798,1324,352,9235,793,8773,6573,2851,7640,477,3429,3061,7739,2601,9411,1684,3105,3416,9518,1759,1625,3429,1312,9337,3747,7237,4588,5533,5927,5407,5814,3973,4295,3942,9772,4671,9743,8552,3706,5281,1663,7930,9289,222,1070,7056,6882,3951,1280,1058,8305,7320,9311,3333,3193,9420,4351,7481,6515,673,7942,5522,5945,7706,9033,7238,8075,8310,5061,3179,4714,3737,7010,526,4243,4633,4726,7164,3138,7038,9239,2557,9295,3244,7133,688,4279,4081,9746,347,2234,325,575,6773,8860,234,3435,529,9574,3423,7007,2490,3374,4757,3495,4343,1789,6758,1841,3486,1488,3629,6304,7285,7106,1724,8165,3906,2779,2525,9163,8711,3346,8543,4275,6683,4590,5464,4430,6050,9443,5373,8545,2565,4465,9383,9751,4559,8219,934,3851,6601,8379,7255,933,9879,613,7816,4473,5804,915,4156,1465,5102,74,8536,3478,6964,6619,1954,4283,8903,2962,6988,375,2498,4851,6358,313,2016,825,9578,1040,325,9040,7797,1289,6748,3294,9277,577,3191,1883,1022,8150,8363,698,8459,4579,9744,6747,9148,7002,3011,8764,861,1110,3073,7883,4396,1735,3431,8080,9065,2865,2299,2460,5466,4799,6562,3928,5819,4423,3887,6950,5641,8443,7983,8353,5648,4443,9908,5750,3779,5806,8568,4285,6265,8844,4303,8807,7081,4354,5887,8914,3408,9251,3949,5779,4051,7560,7786,9200,9467,3482,2731,3104,5667,1773,500,3114,4907,1767,9373,5312,2620,3274,3433,8438,1987,9979,3364,6948,4569,9295,4313,5414,2114,4490,4934,5296,7461,9116,689,88,5064,1225,4677,6636,9596,5441,1468,1213,3372,6676,7923,9778,5255,9616,6445,252,3276,2899,1581,8096,9555,7228,2396,8167,7398,1092,5720,3241,7322,2285,3253,8225,5381,2,8065,7162,1058,3647,6925,5684,1524,3930,5351,2229,8592,2236,3650,8731,8325,2017,5580,1930,6896,311,3977,5901,4789,4768,6437,5117,2673,4250,7092,788,9005,5287,8876,6274,8918,219,9858,1564,1396,3768,8342,57,725,653,8159,171,3287,2589,5104,501,8563,8359,1260,2380,2996,3059,2131,5119,732,5478,2830,26,7130,3036,5992,3592,9719,5450,9622,8265,3132,2774,8611,6254,8715,3180,9888,5275,2661,5503,4156,4531,686,8037,9784,4256,4028,8527,9430,3717,9414,5980,6542,132,1326,255,3682,207,4867,3451,6563,4214,8089,7235,747,7205,7678,6263,5316,5360,2310,7238,5563,5155,8197,5053,1003,8456,4,3096,5344,2182,7599,4717,7098,5037,3341,1969,742,6361,8585,8440,1583,8879,6807,4715,9895,6884,8382,699,830,9252,4164,3659,1338,8822,4119,3465,1657,4980,6504,2527,3625,3170,356,2757,3010,5214,3062,8535,8924,1829,1221,5336,6045,4276,3939,7191,6400,601,7753,9548,1677,5170,2456,8108,4020,5233,7729,4748,7702,7458,8107,7149,4853,7059,1141,6860,4196,5023,3991,8847,1323,4428,2719,2211,6315,9958,5878,5592,2345,1862,1543,7752,4446,3123,3580,5093,4733,7361,417,5418,3030,2831,590,511,541,1722,4896,4038,5344,6525,2164,453,742,8160,55,2122,4603,1642,3257,4242,9297,7989,6038,6700,2673,1545,7485,3909,5762,9779,4114,9133,7306,5773,4123,7458,2847,670,5879,935,4233,1633,9069,7417,8645,9687,1922,9637,8376,4864,191,2157,7585,7406,3762,6627,8958,971,979,1094,1181,4394,5534,5536,8936,2064,1356,7708,865,5762,9103,9384,4102,7898,388,7483,7450,3711,9504,7463,1677,5473,26,7179,3384,5578,5895,9176,5989,1129,3480,1166,6535,9694,3313,3399,1325,5639,8996,1573,5842,1471,1742,431,4782,2323,7968,530,3721,1113,1689,154,2293,3625,821,4162,628,9347,8730,408,93,5229,8530,8874,8005,8386,8192,6408,6442,7060,4700,5538,8666,8200,2624,9775,2376,7989,9543,1719,8216,5129,9526,4193,4468,3648,8967,2850,8435,6776,3569,6884,2300,1034,8813,5052,8376,4894,739,109,3100,888,8278,405,3326,8785,7549,2947,6800,3098,3649,9229,7810,3575,5913,3512,949,5646,6582,4790,6325,7455,4976,6867,6176,4737,4366,8074,700,7524,4595,5472,4085,9865,7772,6450,5123,2156,1020,3288,8967,9174,2034,8066,7458,6419,6308,1584,448,15,6922,6766,2953,4162,7870,4518,9692,5849,5349,9080,1073,5513,103,1986,9141,6466,1738,4782,8802,8767,1376,5124,8906,2273,4255,3091,6690,3589,7405,6351,9159,5045,6024,1111,1546,3086,9085,8208,4088,7613,8883,6092,5172,2881,5443,8475,6093,1048,9535,7614,9689,7235,3414,6553,575,8202,736,4908,5277,5449,3902,8958,2935,4145,2272,4300,1068,8859,9970,8237,585,7262,9579,1121,2231,4827,9551,4052,8501,7625,5247,4354,5812,6024,1874,6631,4965,2128,9293,9969,1660,5902,7907,9479,367,3827,1517,5223,539,1121,9463,6243,5961,3012,3360,2753,3621,8795,8360,3084,1908,8581,8236,5081,8320,1995,2442,3179,8306,3398,7570,1083,4407,7248,843,8431,9617,5521,9651,1282,7574,1980,8265,9826,7421,9168,8263,3500,4540,4410,6233,716,7373,7817,9757,305,5616,722,1828,1290,1989,8925,3163,9650,7599,3334,9106,1781,5930,3036,5154,3245,6923,9511,9792,9719,1362,1162,2128,7692,9314,4581,9506,9904,6671,975,4444,8186,7682,9959,2216,2233,5576,6128,7056,3677,7376,1289,9024,3240,5287,1262,5329,4603,4306,5143,2953,9197,1368,8892,6483,6859,9435,1041,8993,1852,597,9767,6189,5051,6855,3377,2066,4710,3024,8734,6547,4473,7025,269,3209,3966,3018,9916,559,3599,309,3667,5273,6357,1404,4073,2525,9875,4473,6176,6955,1473,5398,2703,4710,8086,3667,2108,6254,2863,113,8077,6354,958,2216,8905,9816,9577,3079,3692,1847,8643,2367,6520,7032,6483,4277,1923,3925,1376,4519,4128,5059,4816,2108,5935,6360,9979,7243,4973,3932,383,7169,4765,8657,2029,3941,1326,2228,9808,8053,1410,8297,3554,2366,1025,4145,6533,1930,3018,3742,9237,8182,443,9036,7973,7283,8311,5370,291,4040,6638,9876,6480,2836,87,2014,3694,9810,6445,2956,2092,7005,9841,4808,9816,4164,5268,4153,240,1785,6710,491,4994,8934,5925,4966,4264,8668,4147,3938,9316,7121,6130,5062,8983,8386,8721,2643,7048,5851,8276,3103,570,9754,457,1021,7377,7943,288,5096,9067,3546,8722,9690,9275,6348,5153,2746,5051,3691,7475,3729,9138,4020,7166,5935,2530,6701,482,5279,8149,3920,3816,2050,5754,4701,9060,7572,6371,1637,3905,8854,822,1706,3080,5010,1952,6296,461,3183,4621,194,1128,1986,4794,8557,9275,6511,4417,1885,7836,4777,7591,7696,9537,7305,4236,720,250,4771,4519,8512,6088,3248,8833,5269,17,39,1984,6883,6709,1735,1667,8520,9704,8749,7745,5892,2955,4412,4251,8475,3812,9137,667,5621,1630,8499,8357,9932,3147,6095,1110,2150,4684,1632,4239,9906,1544,6485,931,9006,4273,6286,6625,139,9804,8953,1727,5777,5117,4278,7529,8610,5377,5780,8801,9445,7619,8,1469,9101,1737,9615,5684,9724,2875,7649,1861,8410,2013,6553,9624,3477,4912,7221,1902,8547,6069,3584,3402,757,2913,5005,2393,6990,6245,4740,8083,3606,9307,495,5859,5736,8371,818,165,6035,1783,665,620,296,9461,4137,2274,4807,5875,8406,7855,3213,5117,9500,2921,9106,259,2268,3704,803,5381,9351,4572,4869,348,5263,7880,979,8243,1241,7573,543,2358,3160,7980,4109,7596,6804,7537,9758,5716,706,4936,7115,7376,9190,8650,884,2083,2946,5140,547,1460,8286,9882,3865,6000,6285,2696,6583,142,7590,433,634,2177,9163,991,3675,602,2932,3052,8281,9428,2251,5113,2395,8726,1824,2798,2523,7356,4891,6916,4267,7325,8002,2103,5656,4102,9322,4568,4736,4580,7370,6620,9235,38,6646,6925,1087,911,6727,1595,7365,3759,4576,246,3280,4625,3801,6681,5379,1293,8417,3504,2949,3745,8760,8943,8672,8708,7561,2831,6479,1344,7138,3221,8848,1916,3401,4365,6377,8635,9185,5827,9004,2005,8920,8701,115,943,7519,8121,1424,489,1382,9809,4432,1853,4067,1137,5500,4924,893,974,4640,9097,4444,5683,8264,8422,5860,7280,98,7607,8475,9970,5370,2208,2455,2230,6113,2187,4323,9967,188,5740,1485,1876,1954,7683,9240,8435,3675,9573,7360,7895,8155,2078,8966,4335,5157,2748,8399,2717,4273,2980,340,5577,6466,2905,4829,1379,6672,160,1569,828,5404,6066,7813,7987,7904,2330,5013,8764,6135,6358,2867,3670,2658,3939,3606,4171,7374,2426,5737,5320,5974,1655,2016,536,7282,4516,7964,8400,6088,1263,4152,201,3363,9608,3509,9734,9014,5959,5595,1994,9887,4166,8821,4800,9629,1234,5699,3879,7298,8584,4936,9086,9352,8761,636,8123,5301,9046,247,2203,4687,8901,1644,8925,1963,4150,3657,7326,2829,4143,6990,7442,548,7736,1414,7663,2589,561,3868,582,4298,1143,2276,5248,9791,381,8565,280,4397,7048,1671,1637,8481,6633,9806,7504,227,2501,1827,2087,9882,588,5931,6919,4550,1494,177,5841,2648,3793,5294,663,7258,1456,5044,6221,2282,2593,465,8959,3900,2983,5597,6562,5517,7648,7638,1163,3957,4172,8233,6893,8486,5344,5759,7191,9680,7725,1037,9174,3472,4269,6609,4433,917,3336,8880,2147,9340,1863,2568,1150,5255,5117,4074,9589,5504,1733,6150,5579,2831,6437,650,9625,4716,9520,7119,4649,5048,6572,9143,561,616,6123,9232,6194,7330,4849,3054,2567,5260,9606,5839,2231,9473,7423,4313,7300,6397,4497,3835,2428,9939,6030,4449,2676,22,7284,2448,9006,1009,6534,8194,243,7405,6164,1112,7525,4468,8895,2093,924,1846,7775,4214,6260,8627,4241,6900,1941,7825,7518,4429,6399,5721,4391,338,2665,424,5538,3610,8049,6159,1155,9111,9385,5286,2879,3706,7509,1626,5051,1843,7773,4793,8846,4895,5288,2977,1735,8441,4710,3488,6256,7365,4705,4982,5348,4293,9797,859,8722,2352,1543,3473,8908,6814,2835,743,934,358,6767,5071,1543,8279,2660,4568,3952,5881,3795,7583,3900,8960,6592,9323,2181,8391,2012,5191,2900,2222,4301,1762,999,1038,9990,4213,7818,3644,4934,8627,7141,5945,9484,4258,3914,2570,7899,2213,1068,2898,3889,3390,2972,9751,6433,8052,7230,9770,846,5654,9279,2639,3042,4390,5849,7281,6400,9429,9626,6345,7715,9567,3224,4363,6591,3254,2842,7275,7892,5209,6338,1202,3448,7341,4831,7252,6487,2634,2443,2325,7552,1740,8203,9310,7680,1625,3929,8590,3561,182,9779,6745,4615,3218,5984,9604,2437,3768,9446,610,9033,8347,9246,7566,5785,6757,6160,9162,3432,187,6271,2503,7441,8504,4386,8235,4979,3870,745,1327,6102,3839,8132,2665,3982,6821,2385,2741,4118,7239,9843,3302,7169,2984,3563,4418,9212,6362,2528,2763,2624,4336,1651,2820,7716,1346,7918,8509,5229,3847,7380,2069,1462,2603,4656,1887,3666,3118,5396,3945,2739,353,4913,2490,4290,3654,3839,2519,2583,9016,2037,4508,7210,295,8248,5702,5481,2269,4596,6906,1800,5030,9311,2670,247,731,3029,239,4363,4348,6070,8315,4037,6871,2807,6862,478,8908,2841,9552,4012,4050,5991,6409,8048,3742,1713,8055,3837,7695,7107,8504,5659,9678,6203,1045,1114,5498,1501,8243,6466,9026,3353,2525,517,2543,1964,5053,6688,6943,9359,4920,2764,3439,3590,6179,2803,7648,6757,992,1057,4062,7533,1178,3661,4477,9996,3183,5272,9388,6450,325,7300,3848,3238,5423,3050,410,2073,989,2028,9934,5559,9728,5912,1398,7127,8852,1897,2523,2563,8938,57,2433,299,1326,8785,5486,4112,3426,8963,1456,6516,1526,4009,6200,9335,469,686,8589,1947,1268,8001,2245,6065,2207,4585,5530,9219,9013,7388,8775,654,1639,8957,5238,785,146,7132,242,2711,6092,8704,9382,3957,7928,5965,7109,5191,1128,1684,817,1849,8603,636,2340,4180,7787,5590,340,3677,3191,8490,9215,9445,4065,8415,7105,8639,3645,1587,5375,8291,6221,2834,2068,5129,6962,5984,9590,3385,6821,8466,4634,8730,6202,2092,9629,4760,5421,9874,4536,9449,3907,2266,1619,2605,4245,1417,570,8618,4010,6788,4603,8553,4579,9336,8347,429,5275,4365,2445,3816,5517,8903,5546,141,2386,4233,1095,9007,9768,865,9056,1776,2276,2119,7701,2460,8665,8807,1979,1761,6152,2373,391,4174,3223,3646,3202,7517,7017,2324,1704,2221,5417,2191,3587,4084,6524,5639,7317,6431,5261,4493,3898,9943,7454,2867,8519,4935,5154,2013,1359,9414,8237,8720,5491,1824,7286,9392,8710,1699,7056,4242,3917,178,3232,7067,7582,4234,7641,298,6679,6365,3625,802,4476,919,1388,7143,8582,5862,3911,6967,6206,7514,9552,990,8372,1841,2839,8913,8598,3116,5895,9063,9978,6015,6804,7103,183,8151,2268,4638,8611,1355,6419,3252,3754,800,6882,8951,9168,3761,4706,7838,6241,213,6529,4075,6163,1163,5006,868,3265,9883,344,4480,1020,4835,7411,2854,4162,5761,860,9752,3774,187,219,3249,6044,8425,1167,100,115,1181,8618,7050,2397,1799,7211,5169,7293,915,4134,6944,2655,4904,3584,6336,7337,8975,4018,9581,1441,8409,4692,4276,8196,9439,1237,3197,6938,4089,7982,3421,9089,229,9326,9272,4402,490,6295,2893,712,629,9126,5915,235,8570,4689,9651,6001,9726,5623,2923,5242,1550,7953,2142,1108,9298,8588,725,2530,6601,8501,4423,3369,545,8699,154,1337,6772,1271,2256,8202,4372,56,2703,3266,8138,6134,7498,6286,7601,3585,8343,6837,982,8449,4100,38,1454,102,4187,4673,6994,8195,2910,1964,2767,2283,565,474,7214,5696,9787,4103,6935,26,7843,9108,3977,2714,7027,157,6693,1440,3545,9618,6654,6914,8270,6124,2677,885,9952,8675,6515,7055,2421,4678,5086,4794,7291,4416,978,4010,8808,8818,7424,6734,5610,9867,676,4073,7246,6479,1552,6354,3224,3346,1891,1402,8283,2999,3689,7317,1331,497,5650,3036,6973,1726,7134,5895,8461,726,7208,33,2369,895,8191,961,1171,5280,961,2951,8550,1160,1836,8412,1643,4059,1627,3270,8011,8798,352,1948,53,1197,8621,3392,3542,252,4501,9565,7315,2290,6176,2583,1041,7624,5010,2299,2554,891,1808,549,7463,2112,9760,4643,4956,7461,8894,2222,6520,9343,6460,9588,7390,9656,8300,4594,7390,4167,3647,6653,9544,1527,2560,4105,314,7871,1212,8423,2246,4833,2341,593,5356,2677,930,8106,4706,4307,8453,920,411,3773,7922,1680,9705,6437,1357,9570,3842,4942,6022,2988,606,7135,8436,3323,1991,197,7865,3448,1255,9145,6878,7462,7688,1054,4888,2107,7168,5033,4103,43,7898,355,8465,808,2829,5780,5506,7516,5746,5364,8011,8948,1136,3897,8681,7767,6506,8992,6899,2624,8549,7209,5221,2024,4831,5482,3997,6489,4382,2893,9962,9723,5905,9279,7383,7508,366,3607,1657,9725,5534,9479,9095,1448,6394,2570,4561,8112,7100,2498,5728,848,3537,3389,4970,6419,253,4364,8459,9617,5572,3694,3851,942,3099,8116,2453,4689,9218,7522,7507,8457,6377,4329,7690,1550,2963,9576,5942,5876,3335,6297,8072,9570,8795,7964,1640,8140,20,2918,3750,6367,7141,596,9796,3183,8470,469,3821,1684,8991,972,4926,1442,3151,6711,2205,3332,4858,976,2966,3466,752,9303,7967,2385,1559,9811,1759,9812,8241,2835,2953,334,8504,7414,2806,4791,9014,7168,8382,4334,3921,8461,455,6584,171,5443,8468,8061,7863,2574,8992,9806,5503,1410,1426,3158,2968,3484,1039,2556,9242,2789,1760,8794,5433,3631,6074,2803,157,7475,937,3830,6984,9653,6248,1695,8936,5859,4692,2606,4739,7874,1762,2388,2183,7538,3430,9970,2537,3135,2907,9034,150,7298,4584,5151,102,7572,2540,5810,1559,185,9352,984,3823,2203,9762,2501,6681,8833,1832,4330,3760,8048,3646,880,3050,5772,5255,3628,2345,5003,1747,9269,7658,679,2181,5779,4498,7003,6927,1732,8073,8291,745,5854,4736,2057,2774,3818,6870,3438,3440,9087,8254,3187,1797,388,7040,7981,9757,7234,1613,374,3697,156,4283,352,7223,1688,725,4120,7868,908,4044,9544,1480,2112,4612,2841,5867,1452,5858,667,1261,1757,6796,7524,1871,187,8383,3963,7917,6993,9747,374,6097,7068,4818,3395,1314,8415,739,4924,5844,9738,4049,3839,1816,6041,327,1478,6204,7857,3020,4547,8295,9950,2435,9064,1246,4846,5970,9549,7656,7489,574,4623,6983,9968,7045,9695,5861,9002,3186,8859,3133,5184,2872,7336,921,4984,8257,2896,7709,2811,5972,4570,3919,9951,9268,3486,3806,66,1381,2394,9498,7460,4787,7430,5414,9223,3372,3663,3454,6093,5278,848,1775,6988,9691,5407,3695,6327,5712,8410,1136,8281,6023,1301,8070,2208,7610,6704,7059,2464,2473,9202,92,4080,4910,2693,7733,1083,8758,1048,7777,973,2656,6683,5787,4605,6751,3363,4790,280,698,1391,9541,1696,38,9182,9191,6150,363,9052,1297,979,6997,4723,5052,259,8857,9442,4552,9286,4610,740,336,4404,392,4029,6660,7322,9938,6603,2693,6980,6006,2157,1235,2273,2307,9102,7034,7434,8520,7476,9335,190,4328,5964,7633,9284,3794,5140,6351,1812,8811,6849,210,8381,182,9039,627,4638,3177,3558,9212,6725,2591,2623,3808,1232,7092,2384,9582,8953]

# nums = [824,7618,4767,395,5127,3038,5790,4317,4572,489,4591,9693,6523,8937,9588,2373,7425,6704,7576,8398,2946,1474,9789,693,6705,1170,7497,6861,8084,5508,9061,4706,344,4567,7116,3990,3052,5528,2225,3053,8394,4034,644,6296,1133,3336,2267,9283,5434,9718,2444,1327,2183,2521,7670,5627,8391,542,8340,6898,2766,2939,767,1623,3468,18,3983,953,3292,9990,696,8036,9123,6115,9203,8915,4626,8062,9153,6898,3007,2591,5350,9849,7246,7802,5647,2071,5344,1186,7089,7960,2694,4746,2747,1924,217,5088,8271,1008,3241,3626,3659,2711,9638,2626,9687,4614,4921,4689,4518,6349,6001,5752,6097,4608,5293,6146,2236,3263,8403,48,844,3458,2976,3406,9804,256,5034,3032,1017,3898,2886,8801,3627,3883,9468,500,4633,5493,6570,4228,7730,7814,3517,4024,3796,7012,5634,6,5021,6317,7961,7810,7797,5528,3920,6271,9865,1070,1730,7317,6694,2153,5411,2744,9457,6389,1239,8896,8303,3868,9457,6081,5833,148,3639,5888,5468,7610,1703,6537,7632,9982,4123,2817,2933,229,8830,8519,3896,2278,7332,947,9877,8289,5860,6456,3534,2317,6215,2585,9021,5307,4288,8886,8784,4621,4369,8581,209,8200,7329,133,9598,3056,7908,2033,2049,8866,1531,8044,5031,9655,3841,1743,9549,5155,1636,4302,6618,1798,2913,1593,1516,8502,3060,5702,5020,7179,1573,879,8642,4156,9377,7173,5656,5653,4305,5435,6511,2562,8331,406,9204,7399,1812,4301,4279,5687,555,365,9623,6307,6893,2970,9120,7794,7955,73,7410,4492,4932,6693,3939,8358,3050,2713,888,1991,4924,124,6484,2180,321,5551,3793,8473,7502,6792,6386,6754,1697,3758,3525,8962,9290,7217,1303,3373,2208,1775,2718,2249,9361,9224,8636,9665,2302,922,7648,377,408,5798,1425,9222,7815,4827,7721,8555,4263,1004,1343,7221,8490,7773,8829,831,1690,6088,9335,8327,4727,1535,2094,2052,1033,2084,6327,5031,2329,4468,4188,1398,4650,8813,9709,3387,7861,9848,1567,7160,7950,4636,698,9586,5630,9453,7011,9871,7199,3474,1990,2691,8611,3329,9579,1540,1409,614,3342,6260,5190,5330,8190,1914,1324,8343,1548,345,7413,2781,9301,6257,8143,2539,6200,9299,3230,1583,8721,9410,6080,4699,9203,3383,1208,6085,9414,6323,7449,4790,9155,3576,5232,1105,4961,4409,9698,8064,4779,9562,8680,8880,8091,8245,2570,2236,4104,53,7581,7824,354,3249,5283,9851,2013,1631,6789,425,3171,9265,7453,2915,3764,3016,6556,4414,5197,2979,6297,2831,138,7298,3942,962,9354,5298,2869,3192,5817,8544,7400,1507,7682,2105,5950,9872,4600,4275,959,172,7187,3582,6526,2962,6361,597,8846,830,906,8917,3224,2105,221,1281,6319,8954,5219,6853,8978,6084,1567,3151,1570,8271,9933,5210,4115,9183,7138,1919,5649,1093,8731,595,9459,1987,9545,2791,6347,7704,4971,4395,6166,5282,5408,4075,9039,3909,2603,7867,1779,2389,2181,2785,6506,7026,1857,9956,8441,4064,5257,5547,9629,3323,9477,738,6076,523,3640,2821,5100,7286,9802,2555,8788,2030,3517,2760,3634,2172,9663,4554,6313,3922,2163,8852,3062,4134,9044,3270,2144,2607,5121,3168,9113,7685,4849,1245,6999,817,8538,7970,5799,2382,7792,7591,3500,3094,6841,9424,6339,8451,1263,8294,3491,9625,1307,5746,7439,3751,35,7299,6463,6789,5992,1387,4015,8294,5881,2561,9945,9345,376,5250,9113,5975,112,7075,9755,1572,4389,6174,1478,6459,3616,163,1115,2623,8234,3490,4709,3506,2018,2295,6646,2585,3661,515,4150,9622,75,629,7458,7048,7738,5373,4858,8791,7455,5099,4795,2729,8110,8985,1204,7031,2256,8822,231,5385,6195,3776,8678,7675,1176,369,3092,3807,4084,6794,1056,2138,695,7592,1625,9689,122,2641,3294,192,6634,6405,4700,2890,2924,1567,1029,9662,7734,9661,965,300,5121,2146,2073,6965,4779,5087,7955,5393,5383,9299,2954,3185,968,5148,6670,1806,6722,6147,7710,5199,6951,3180,688,1974,9167,667,5394,2927,8694,2663,3393,7273,3782,9364,1569,6924,4792,831,5180,876,1827,350,6775,2819,490,7986,6984,7545,3887,4134,1466,1867,2197,1379,7030,8391,356,28,8318,3148,344,3074,3412,9641,9602,5568,5286,9139,221,6048,3052,6963,4376,6950,4653,7022,8947,7040,6819,2073,3377,5906,1809,2469,6503,3343,7534,6855,2841,7855,5758,1733,5244,7853,3735,7207,5467,6784,2332,1589,3466,7679,476,7810,7263,8000,4547,8715,6976,744,7963,6476,9248,7559,2454,7558,806,4895,5243,173,845,5571,9650,1950,8726,4439,7295,5401,2431,9802,4137,1445,8026,425,4238,2683,2200,9197,2,9622,4147,735,1530,5381,831,6458,2073,6987,7852,3024,1751,6822,6268,8005,521,2918,5177,5280,2817,4144,6150,3505,6864,8896,1446,5328,8467,6889,7294,6477,7497,2417,2807,6433,2129,3213,1174,7730,5504,620,7164,2512,844,3909,9341,1090,3958,1333,9700,8494,8581,7473,2825,8776,8673,6195,9774,6089,5489,7117,9184,7762,124,3584,3156,3185,880,6002,7034,7691,6420,5007,8141,9674,5424,9362,4544,2219,5915,2814,211,3420,7471,4577,6694,9532,3063,2103,2474,8971,3409,3309,4270,5991,7179,6571,3890,8720,5354,1595,3431,5451,3736,613,7276,3174,909,9015,1624,1784,1327,3812,4761,9408,700,7484,90,7156,203,2729,7556,8426,5443,1068,1773,9643,9220,367,3306,4794,6594,4130,8704,8706,9926,3662,8809,3773,9690,3795,2715,7440,1065,8209,903,4305,3730,2941,9848,646,8803,3288,4760,254,4568,6778,1281,5949,3434,6144,5622,1946,7248,3770,4329,3453,1682,3065,9898,7798,2293,8839,7128,4307,230,9585,2591,8300,5534,44,9405,6344,3243,4994,8316,2409,188,7661,6321,392,5002,4497,7071,8786,3937,9676,2277,4690,3997,79,5917,6475,9732,6557,4879,9171,4337,755,5322,7538,9230,7750,2638,8234,2939,6146,9105,3524,5436,8433,9316,5354,9724,9669,812,3546,1371,2923,647,9376,6495,3132,1004,7710,1854,4444,5675,3241,3191,2282,4646,5092,6224,2868,1437,5163,1817,9921,6897,6458,3064,3170,8375,7412,7085,5943,6821,1458,6122,9186,5426,7768,9166,602,6144,4186,9314,4937,1852,3454,6429,5426,2964,1165,4270,1393,1405,2536,7001,5251,4259,3344,571,2366,9302,4503,2261,3263,7599,1141,9568,495,3902,849,5013,172,7303,3059,3681,7930,2232,288,877,3882,7625,134,7160,5790,901,6026,2494,5101,6641,9768,236,7895,8919,267,114,6257,9303,4347,8039,7415,1270,7273,7838,3145,9301,8052,814,3232,1470,6226,1682,2148,2872,8276,292,1043,6192,299,3420,8486,6059,3799,5535,6983,1183,940,3013,1970,7484,143,5685,7137,1201,305,6294,863,2460,7428,4689,6625,5048,8470,5104,2577,1446,8414,6855,7555,535,776,2556,3428,3849,6106,1907,3754,9648,4824,8911,1808,9338,4921,2658,5656,6282,226,7428,1014,3946,8774,6996,5530,5201,3773,5550,9700,2907,8324,3345,4367,7317,8525,651,9571,6070,5633,7168,8417,6555,9116,1251,1443,730,4799,7314,4528,4793,8863,1245,8855,9905,9902,4963,5588,2444,3240,7279,2221,2787,1436,2033,8204,7747,7831,9004,722,1881,8411,7890,6048,2118,9314,985,2862,3009,751,6403,661,3750,4146,5127,8084,7305,2455,9083,1419,5400,5410,5311,9744,8760,6281,8351,8061,5757,5646,8193,174,7301,9848,2705,6831,1239,1277,8339,1239,4003,2477,2261,3577,7328,1893,9814,3587,3813,1254,3764,7185,1510,5430,7947,2935,5141,9572,2012,197,127,4311,7711,9251,6540,8103,6798,7652,8975,8960,5108,7414,2220,2946,4239,5076,3133,1401,6665,1802,2512,1497,7870,4888,2633,6154,527,867,7417,9625,3762,5664,1702,5107,7983,4183,3520,1440,7582,3138,3482,1158,637,3677,7419,7121,5598,3389,582,6317,9909,6053,1234,9202,7060,4185,1979,8646,6514,5292,695,4898,3406,2227,1506,2072,1188,5635,3466,700,7158,9475,7356,9107,4260,3777,5570,2551,3763,3897,668,8974,4998,3545,967,7733,2853,9734,4747,9241,9370,2584,6997,7900,9072,8084,3020,9003,7406,4198,7754,3252,639,4964,9837,8986,8371,3473,3078,4721,6157,5335,9758,5044,7529,8117,4024,5025,9582,4156,4533,4448,6866,291,557,4422,963,8049,6334,4919,5586,1492,5138,9768,587,3267,9333,3629,5480,8983,7532,7595,2464,3920,8248,3528,7719,2296,2364,6188,5203,5011,3298,6847,1855,8690,8123,6484,8102,1424,8573,2061,5822,531,9391,2853,2972,7605,3584,7026,7523,6186,1405,4174,4390,8799,6325,6829,6873,9478,3449,3902,9082,6246,3369,7916,8092,9134,3872,2133,5134,3786,5478,3334,6609,9698,7883,3527,5335,2250,916,516,8366,5341,8230,9110,351,2799,4745,7209,7369,2407,3393,1988,3161,8736,8788,6412,1954,178,4693,368,8160,5949,7488,4664,3210,430,4368,3370,1056,4928,8565,5482,9831,7057,9100,7000,5966,6941,5308,4089,5105,5024,7782,1364,9953,5182,3433,4357,4309,3400,2494,3858,5871,6005,2574,1494,5520,7674,2424,9226,5936,5777,4891,7989,819,3522,9678,5536,7400,709,7160,7638,7619,3021,6318,7,489,6419,115,495,4766,5030,9443,2872,6118,3281,7419,4890,8324,1900,9591,3738,4033,3901,4453,8324,7783,6431,9558,2167,3556,1198,3118,9289,4122,9841,8854,2809,1366,5026,2492,3615,5070,510,3432,2862,7482,4418,4516,9118,4531,8987,9916,6208,5061,3760,435,3496,1200,7981,6338,8857,1065,1123,8858,3821,7775,7969,4511,5470,3246,8959,4348,3727,1486,1167,9603,50,2674,6028,9140,2230,5067,4183,528,4263,3530,3165,9064,3333,1327,2895,6646,5097,199,5307,9994,7369,8526,5238,9485,9943,6779,1091,1471,10000,8375,8490,6771,8589,1277,2468,9605,6388,6667,9159,2761,7069,5746,4002,942,6532,9234,7648,8609,7435,6478,1964,3169,207,3634,4559,7798,1171,5344,4663,233,3280,3039,9071,513,5354,3839,5859,9832,3155,2560,7021,2694,4400,3977,8041,2034,8761,9944,5101,3553,9540,8151,896,9386,7948,6550,3759,7993,9239,1332,7787,7909,5861,271,8549,77,2608,5709,6329,8035,7836,588,9654,3391,6190,3737,8846,8805,9803,192,3253,1658,6284,7526,6024,1848,4916,6485,7639,5739,8733,5206,124,8932,1222,6602,601,5678,4001,6376,2195,384,629,4373,9545,7375,2284,6719,1229,1352,3473,9755,5392,654,9557,3934,9045,5245,5500,8056,6547,1505,3265,5305,3835,5814,2564,9282,5295,903,9512,6035,5812,1115,6464,7138,5846,3457,9518,1662,6035,7699,7703,9277,2116,9687,8320,5509,2807,9913,22,2312,7876,968,8844,7020,2166,7261,7805,4937,5348,9111,387,3162,5797,336,2533,1649,5899,2991,2361,3145,5533,5598,1450,7632,9569,3970,8848,8139,8131,4939,758,1395,6633,2351,5875,3292,3795,950,681,4996,1543,1568,2510,8288,4821,8143,6208,2925,8635,4874,7220,9043,7429,6365,3075,6740,6944,9228,1617,7096,1390,4811,4191,6691,4225,44,3136,9780,6378,4916,4432,1390,4210,5037,3866,2953,8256,8692,8415,4876,5627,9309,6428,1902,7250,7423,5683,911,2611,6673,78,5216,1898,8387,7562,7930,6027,1913,7993,6893,2253,3014,4640,3644,6097,5312,2434,2007,4632,9495,8222,9287,7320,6962,8555,635,4067,7809,5911,2298,714,8738,3719,4133,266,9224,6311,2041,9287,1399,5720,1627,8118,6719,3378,4038,2916,8635,3086,2317,6133,9317,2315,1135,195,4293,6900,1243,6814,8386,5970,9520,9692,7457,3100,3164,1592,7072,3017,7307,4217,8583,8919,8741,199,6658,9620,8705,1698,1680,7658,9253,9743,984,4474,9784,4940,6513,2780,1029,9881,8905,7097,7976,5036,2271,2456,7967,8807,8611,1219,7718,6988,8271,7982,7785,9230,1422,4736,3612,8832,8513,3854,2136,5663,1754,1529,7804,2366,4407,6732,5765,8610,1918,9752,645,1602,8017,1885,3386,9184,9528,1748,4095,4619,3413,5114,5089,1634,2327,3181,2259,7596,4690,9115,1876,5017,4162,3551,1025,3623,3073,7663,2556,6535,3354,8107,6439,5063,8679,6051,5059,9345,7027,4153,4629,4135,8594,528,3915,3629,2945,7480,4867,1118,560,971,7138,2022,9981,5334,2449,1903,1384,2614,5029,7892,1767,756,635,1653,9492,6769,8886,3563,2558,4442,9465,4,6439,4428,6886,8115,4581,8446,2556,114,5787,8846,7290,2915,7115,6268,9431,296,5301,205,3730,315,8314,5560,6064,7620,6498,9642,5879,4313,1307,390,6992,5123,2709,3472,1088,6922,5394,7634,31,8230,6487,3595,7496,2006,9846,622,6705,4723,6195,5657,8315,3634,2078,4166,252,8135,1751,8351,5947,3076,6237,1055,1396,1844,843,5289,4960,641,7672,662,3237,5413,1715,1436,6749,3794,1389,8825,633,9891,3900,1965,8984,6824,482,9590,6833,6425,8525,9185,4621,9025,3353,518,6849,4210,1604,5440,5249,1341,5573,2375,6906,2522,6596,2775,3533,3154,7418,4337,7145,4598,6353,1002,9551,2032,9296,1039,2715,7277,431,2107,6627,7925,3233,2356,5625,7135,1334,3569,1341,129,5496,8839,8577,859,2366,7692,8812,4567,948,3655,4378,1475,4187,9329,4379,8031,3085,3937,4939,811,9309,24,844,7345,2862,9498,7529,9606,9130,3535,9073,7637,7948,3803,7260,406,9948,2774,6027,5823,9806,1795,3601,9765,1319,9207,3309,6034,9962,7028,7987,9874,4953,8253,5842,258,8081,2276,7651,4533,9164,3625,6961,7184,147,3430,5102,6362,6254,1207,8486,1575,9336,9748,9899,9504,9134,7677,6767,7842,5090,8713,6040,1868,5291,5583,5123,7871,3526,9812,8983,2743,3140,5916,4322,2278,4749,6961,3690,3496,2602,874,298,7098,7684,5555,4093,5437,8036,7749,8417,2364,3091,7184,9913,8577,700,6384,9251,2123,9776,7573,9896,6492,384,5014,2659,5822,3700,2070,617,401,5358,5410,2366,2043,6181,7765,5557,2596,9243,6323,3305,3037,7986,6413,1488,5772,1160,7224,7737,5550,7436,6837,5826,3326,9610,3903,6142,9276,8593,4112,6354,1964,5075,1177,9473,7637,6349,2878,4699,8641,6771,8688,8072,8561,4212,551,5314,1955,3262,6425,5514,4843,7804,8881,1304,7167,7600,6967,6803,7215,7069,7594,2938,4612,7189,1067,5282,3064,4512,6395,926,8813,7957,9772,2623,7263,5752,3712,6215,4829,1145,5457,2272,2114,5306,8465,9587,8647,7976,6960,9784,6975,6142,2814,9364,5927,8493,4530,9880,3663,8685,618,1443,245,7116,8926,9467,3315,408,5860,7625,6445,1018,6163,2463,8708,5434,1293,5839,8476,7040,1630,5607,7724,279,7174,8080,3197,5609,2213,6654,2559,391,1540,7880,4322,1446,262,3521,5357,6608,1372,9133,9153,908,9494,3223,2791,1126,346,6580,7373,4620,1829,4707,2824,6436,3914,5240,6464,8151,160,8514,242,4603,2515,8868,7645,4249,4144,3240,1774,2829,2288,7337,4300,448,6982,8974,2541,1699,5254,3643,3465,9108,8344,2815,2521,7463,4915,3980,1024,2262,18,3530,9001,8116,6375,25,9543,7175,9290,5128,4363,8870,6210,9959,4636,6388,6435,6879,1321,6236,6633,2768,2784,6746,3651,640,3204,3659,6500,219,2546,7904,6913,2473,1945,2662,2709,7867,355,4113,8223,4573,5978,7371,2300,2569,5317,9722,695,7149,6045,9585,6007,170,1627,1046,3179,4136,1462,8838,7502,1304,82,7530,7027,982,2614,1518,1750,6940,49,3689,2727,5387,2383,2995,3757,1179,1926,3304,8190,4892,6913,3151,750,464,4215,1294,6485,7843,430,6509,8164,5140,6493,3934,771,3517,4295,6808,4474,9882,3442,8202,8812,1480,8097,2700,4209,8453,7144,2179,5828,323,6807,9354,9013,9728,7340,7910,9400,3762,262,551,4588,1708,432,8245,2928,2439,5986,4847,5298,6718,698,495,5240,1528,1359,2196,8525,7629,50,5114,8332,4039,9118,9380,7200,8032,8678,4313,5533,5941,1320,5670,9652,5941,314,6381,7733,4427,1433,8646,833,3429,4410,5606,4854,3121,6977,2276,305,3983,5127,4604,8559,7097,3734,7956,4146,2813,4605,7930,8306,4408,5178,8446,256,8464,4560,4436,5109,6704,391,4923,3747,1060,9200,6330,2962,589,5903,9243,3334,7906,4665,3456,7000,2413,8684,8242,7125,4332,6003,9357,4661,9715,8676,7678,727,6810,6658,7166,4335,4178,5544,1878,1254,3402,4987,6318,2940,439,4847,215,6767,9002,9434,5013,8957,1002,2118,2372,687,4241,1844,768,2129,9982,8626,803,8028,6308,6047,1816,934,5508,9760,8108,9428,2046,5101,5136,7060,3843,4688,5783,6555,3225,3432,9313,4165,1644,3767,5474,6743,809,2850,1108,6243,8480,8386,5439,2325,8279,9244,406,9866,1763,9534,8211,1424,2717,793,6657,5548,6442,4383,3080,6421,1071,4792,8764,2128,9107,9515,448,4274,8951,9373,5841,626,5509,743,2573,1514,5237,7219,9624,9761,9356,4298,7408,5974,9348,7073,9697,2297,8190,784,9026,7878,9102,8913,7621,8920,5695,3122,9980,425,5990,3314,1939,1739,6410,3759,8216,3777,8326,1046,2040,1117,4492,5313,6489,9848,3877,8324,4616,6523,8823,482,5940,9485,2708,4196,3519,4975,243,18,3230,4069,7775,9785,8767,8595,9953,3978,2776,2139,3247,4048,5073,5536,3968,6594,7789,3766,1490,8889,2748,9836,5302,9518,4995,7143,1521,386,6254,9678,6104,3044,3694,8480,7866,2048,8000,1098,637,4708,9472,2091,6191,1697,369,3767,8632,2595,5608,4501,3873,9289,4943,3018,6793,2205,9703,2066,6464,8992,8440,1029,6695,5330,9332,5693,9265,3350,5869,2763,7783,1888,1457,9246,2595,9512,8265,5734,477,8812,3197,7077,8943,9424,7560,9251,7,1572,6408,5707,6908,3365,9484,5767,8424,1998,3447,9669,5549,9618,857,9766,8101,2359,1199,3561,4966,415,1639,3773,3287,7947,542,926,4717,6785,8423,8603,608,5842,4742,3684,4730,7568,6726,4795,4475,3878,2955,3839,1746,47,6044,3823,5529,1647,6766,8631,9062,133,1904,1777,2158,5858,3112,2101,2643,4017,8255,6835,6913,7970,939,9539,6468,2992,1820,7536,1596,3634,8936,7372,8349,2414,5055,7724,2634,3135,9612,8664,3032,2350,335,8991,2819,1040,8612,6757,5828,3105,3074,6587,7284,1576,2148,1484,8847,1772,5531,9297,6619,5765,9591,3661,5837,4704,7477,4149,8998,1803,8189,9193,8791,7606,1250,9527,5412,7869,3189,4864,7184,3375,9260,7603,4904,552,4882,5003,1675,1580,7688,7557,562,9880,3514,3750,6347,5389,8952,8657,3517,2736,2663,3730,9470,9885,7464,4335,8238,8220,4492,4908,3073,7616,8406,1667,7702,6107,6606,9295,5498,6086,7337,7728,3558,6967,7043,570,1225,5141,7801,5753,7028,783,3183,4238,8514,3026,695,538,9172,7145,1753,4174,9703,2680,706,8967,5505,271,7396,6040,16,3628,3260,8404,6337,9860,974,5761,8757,1543,1503,2578,4839,2953,8491,6662,739,8378,4012,4685,3277,4935,8549,7028,625,607,619,4419,2082,716,4516,6263,7496,5561,5246,87,2559,9057,2463,2800,9184,5250,5705,5354,5772,7636,6503,1005,5782,3840,9215,5264,6225,3228,4905,227,5370,3302,4001,3388,406,9743,4459,8219,6275,851,818,5645,4857,8669,8156,4696,8395,1222,8102,3432,5795,5152,1383,8068,9571,3328,2687,5262,9993,8150,3278,1081,6693,8576,3846,7733,9910,6141,455,8442,8246,8543,1252,4740,4507,6967,2764,8189,5369,3581,8179,2155,2529,7908,987,1838,5054,7347,9250,8677,6034,2074,8497,9318,5658,7510,1868,3294,4987,5851,6891,7790,3326,4844,2929,9276,9014,802,8002,3756,1155,6131,7703,2919,5801,7737,7183,3124,7752,7118,7299,6099,2882,3814,7100,9992,5010,6009,6715,7625,6733,6768,1575,6484,8889,8023,285,3937,6722,8802,6608,3115,2612,2060,636,5121,190,3478,4813,6350,848,4690,3482,949,9996,6421,3235,2442,2657,4671,6078,8865,6528,2460,4504,4048,7664,7830,2659,282,8413,8953,2873,689,8752,1183,5705,5182,9004,8192,5505,3038,601,2428,5588,1441,8098,5496,3506,8247,7227,7064,6365,4397,3767,8427,7191,1029,4093,6405,9312,4430,6043,5887,6687,34,8034,3190,2914,5874,9825,4224,7310,486,7727,8005,3573,1538,5462,2985,2332,8767,2047,1544,5403,4310,1696,6368,9008,5112,1125,7522,3598,9376,6387,626,3868,2324,5239,5196,9820,3979,5721,5881,4435,3298,6961,9930,2427,1572,6701,8289,4289,5833,7148,3443,8141,229,6684,5005,4985,658,2202,5018,9313,4189,4884,2963,9892,9942,5423,9866,1651,2297,2571,2219,5213,5925,4801,8966,4375,6845,2157,2901,5770,1355,4416,5283,4116,2261,8824,8664,7249,8615,2692,4970,3849,855,5548,3476,7782,8134,4948,7,1685,2101,3827,7499,7971,458,3441,2897,7058,3567,2342,3845,5504,1723,3089,840,6158,5374,618,8467,3359,2011,943,2386,1873,8557,6785,2090,6641,1270,9298,7155,5809,6576,1386,2641,9128,5277,3475,5430,5814,7990,2557,9494,4008,6827,9463,1773,2336,1746,672,2549,1750,6190,6146,8017,1348,8599,5252,3422,9361,3970,192,4960,7044,4004,390,1618,7809,6041,6413,1151,9505,8080,6830,9105,2345,905,8698,5643,4496,3917,7958,9032,1050,4929,5337,7440,9662,3692,9315,2131,6470,8172,9482,4484,2595,4375,7183,1206,1673,2951,7232,1697,4088,1651,1334,8679,3417,2782,1001,2277,1865,2083,8042,2083,7357,9927,4771,5858,814,9767,1872,8072,7062,1413,8175,376,9942,2409,8146,1971,9683,2628,5457,8681,1178,4618,1084,9798,2926,7466,1642,6727,1903,2894,8698,4260,8780,9087,4910,5337,8529,9322,7428,3751,2208,1827,6633,6674,488,5177,2239,3683,9158,7234,5909,6308,249,6564,5793,5918,9312,5145,9178,3753,1749,1206,8128,9500,7018,5487,6917,787,8701,9892,6788,8173,5203,7873,8120,2255,564,2301,3641,8870,5352,2825,8788,9394,7708,4139,9746,5567,3040,8393,8548,5787,4684,514,6865,1194,4630,1336,2180,2984,7229,1891,776,3612,1269,1418,8750,8548,9744,1038,3866,2170,5975,7871,4022,8592,3317,6929,8540,7231,1716,8330,120,3830,5979,7585,3785,8179,9194,7636,9404,6942,908,4772,68,8463,5340,6393,8273,119,5654,4438,2260,9766,91,7300,8671,5813,9157,6428,5875,2211,6376,3811,2790,2005,4860,7348,1812,1258,755,2030,8589,4232,7205,8034,9196,542,6337,2031,1507,4398,3572,6204,9989,7031,4846,5247,8382,7175,9192,873,52,1846,9858,8861,7477,3762,9562,8535,7518,3678,3717,7585,4031,4484,414,9032,3030,769,8365,5074,8251,158,6099,7244,265,5254,2408,6154,2443,6249,3387,2117,9910,526,3416,100,4771,7300,306,4653,5190,8928,6538,9130,9395,2287,3608,6932,4485,5335,736,2670,1357,5510,697,1248,4959,7229,2020,7564,6729,9599,6319,3618,1175,4372,4513,103,8420,6192,6282,3221,4839,3405,2410,9456,4505,9764,1629,347,3656,117,9773,2129,5409,6244,4046,2004,3075,5262,3025,7430,6502,3290,3008,3270,8031,8761,3890,846,6692,2022,6882,2081,385,872,6155,1389,3360,2276,1722,648,5407,2651,1216,3755,2698,451,9094,1066,1135,8941,169,4941,9722,3247,5470,1078,5411,1017,6903,7135,1501,8273,6507,6131,6234,7995,48,241,4707,9575,1879,6114,8155,2340,3071,2493,2009,1413,6162,247,6483,5380,6226,9435,4241,4217,5542,698,5536,9934,5163,6189,3068,6027,9038,6621,2488,9704,8528,7647,1501,7173,8479,7042,4285,525,3322,9455,1965,854,9584,8532,6526,3379,3006,856,2192,444,4501,3569,7984,3076,6702,864,7554,7262,2873,8963,5706,6995,9011,5611,8627,446,4085,6530,570,1300,4438,8494,7470,5280,5954,6969,9939,6947,7604,2213,4501,9344,9181,677,6519,5685,897,3731,596,5270,4399,1147,2403,9195,5961,5863,1099,5879,5938,8290,6829,4078,2412,531,6033,7584,6726,428,2680,7716,9765,2475,7170,6213,3263,7540,7057,6809,68,3147,4101,5144,7294,7966,5601,7057,7979,654,7833,6800,4981,2378,4065,7129,8769,4474,7027,9438,6927,7652,8856,1179,2624,2621,687,2254,3534,9085,4008,8359,6208,4508,254,5165,952,3010,6408,3547,7203,1061,4796,8978,4844,1849,7789,1850,1854,92,2876,3204,8393,6872,7929,5636,379,7422,3041,8931,639,7132,7055,1365,7089,5849,5371,3724,9078,9014,6977,7190,4749,3364,3406,7960,7834,6283,1845,3011,5375,7873,1451,2468,3984,1803,1752,3408,211,7150,4634,7692,4344,3395,5147,8151,3654,9000,6566,8958,8575,5211,4922,3254,2593,463,1316,8158,8762,3659,309,4267,970,1341,576,3258,8377,5496,6412,765,6406,4136,9310,7740,3655,298,1500,7014,8049,2780,7991,1933,7990,3933,772,5533,7118,2532,3256,5797,7712,5185,6158,1891,4066,4503,1698,6564,681,6000,6838,4324,2201,3355,5407,7199,7556,1686,2588,2982,6136,9572,4882,21,8101,38,1420,4028,6425,768,9434,7888,3996,4118,1841,2884,7145,6707,2801,4887,1001,4998,4108,7502,3298,1737,9112,330,6102,1945,8745,1896,6839,3743,9819,9366,170,5927,9118,6060,5989,577,8807,2996,540,2218,6441,1293,4343,710,3986,5320,3165,2739,8157,9077,3624,3980,3882,889,3048,9943,5207,8831,3862,6971,576,551,9895,9413,3094,7079,6712,9167,8518,605,129,6469,4218,9248,6066,2667,1335,6576,1654,8504,4640,1081,8563,2730,6053,9528,2661,9420,5285,7141,9522,8566,7696,5199,7124,8035,5246,62,3420,5208,1251,2187,6821,3303,1487,9337,4070,9522,2579,4850,1497,908,9485,4876,3393,3293,4586,4844,7177,1543,71,4776,6795,5273,3382,9217,6992,592,9027,7123,6248,4716,8277,8830,201,4973,8976,3405,7883,9839,6734,845,3614,5169,9928,861,3449,7626,5303,2091,6238,8282,4847,1447,9851,2700,1751,4878,257,8179,5837,4680,2188,364,5001,1518,3536,9052,5351,7961,4401,2643,277,6336,2221,9729,356,4041,872,6979,7613,8435,7418,4663,7736,1423,7477,5388,8159,7137,9395,353,6382,8406,5301,7353,7765,5031,6424,667,297,119,4004,2406,415,2393,8967,1186,647,1667,4188,1949,2720,1658,591,6967,4815,6181,2984,5556,6472,6127,6081,3161,8751,6962,6022,6181,4892,3103,9515,1508,7553,1082,3540,5876,1472,1915,56,4083,4419,2002,8009,2484,8172,4157,5726,5493,2424,7200,2449,3210,5774,2516,2304,6356,9305,1288,444,3903,6647,3774,7887,707,4535,4628,7492,9237,5440,9598,4219,1453,5857,4546,2636,8032,668,427,3641,4448,6009,2391,724,5074,967,1491,566,5165,7474,7095,9591,5484,5325,7642,4011,8866,5884,6835,1836,9841,8054,3676,7054,9026,8326,108,3979,9707,5888,4260,6855,6590,4305,5925,524,4978,4533,5247,9791,2579,7727,9643,751,2573,4331,5419,6509,884,1182,1467,4662,2599,7346,7153,2511,1713,2664,8033,1419,7423,3847,3222,7602,114,9626,6343,7976,8995,6423,9544,4070,7086,5671,6986,5109,7659,4135,2620,4444,3528,5422,7226,3354,7795,3455,8821,8038,8370,4309,9748,6561,7575,2394,1550,7717,8130,6910,8343,4963,8792,3356,7619,361,397,7315,6449,8926,1385,2243,9363,7822,8997,1798,8327,5766,3928,6214,132,7496,7194,6146,8683,9033,2267,1749,5652,7684,2928,7049,7349,22,9708,8926,9827,8434,5279,6549,7386,4749,2945,8477,7559,3125,5921,5498,4831,5481,8412,9826,7980,8467,6886,3705,8880,4750,7127,2867,4203,841,4933,3269,9034,7601,5014,846,3657,3031,3418,7581,5650,8398,5135,6198,3187,6815,4713,2018,6336,1696,9740,3729,2134,1784,7060,9797,8890,8088,736,5883,5831,775,8170,6550,8142,8619,4811,6721,7329,3758,1430,2784,1863,3702,4554,8191,7739,1971,6495,8423,111,9769,290,7127,8049,3150,9296,5602,6600,3536,4072,3326,148,818,6788,7752,4594,3002,6511,6839,4419,820,667,4975,3564,1142,265,4596,1684,1906,2430,3512,9059,558,1668,8592,452,5030,874,5048,3748,2875,5261,161,2437,3624,5551,9565,1289,1653,6784,4524,6013,5926,4069,5435,6898,1482,2045,2714,6176,6736,5329,9376,2998,8111,6116,618,6569,4227,9532,5643,4121,5769,9897,6377,5410,1050,8393,7974,9122,6304,2982,2083,864,4381,7806,4921,6770,6245,2252,7630,3967,5303,1434,5624,7632,1122,1415,9056,7059,813,2983,9402,2163,2265,2334,2000,5896,8943,2513,9416,9269,1251,8669,8220,4541,6537,3531,9285,7534,3432,5869,9863,422,2927,5616,2490,9551,5358,8064,9382,6499,6235,1695,5160,1377,4521,5829,863,7673,1770,679,5940,6059,4338,7984,1749,8116,448,220,5504,2618,3741,2156,7445,400,422,2468,8354,5949,2563,2226,1572,1728,4394,8312,6158,4184,865,86,6476,8076,879,6675,4142,9505,7542,6005,7300,2433,9992,4896,3439,5908,824,2182,4861,6140,8277,469,2893,276,3056,2612,9758,3830,9027,6516,7946,9944,9340,8063,1130,4357,4105,4237,9624,9280,5619,7814,9593,6186,2171,1823,7888,8294,116,6790,829,3162,7430,1799,2564,7919,4055,6165,8609,7257,2089,8440,936,1860,8461,3481,9958,6771,8002,962,4079,541,3267,1307,6196,1396,3824,4807,8384,8626,6493,6149,5500,7873,19,9697,4107,4088,9315,6759,7195,6718,5458,5296,4756,2637,887,7167,4250,6176,6169,9861,1694,592,4570,6014,9203,6150,4855,9563,4532,101,8649,4026,8652,3047,2496,5871,4239,6796,2906,6350,885,9289,5856,885,5336,9879,9029,8513,5102,3098,6109,6337,5167,5546,7970,8509,2851,1925,1191,2733,2808,8830,8967,2653,1271,3755,1614,2060,3098,1135,9738,5551,7747,1759,1262,9528,8460,7689,2591,8646,7474,7059,8979,185,6724,4060,1025,4115,510,9772,28,6176,9282,9854,9374,4456,9040,5220,3464,8275,5007,4716,6745,6269,8361,7034,1477,5008,9999,7140,5523,5565,7449,6595,9376,6784,2429,2638,2774,8129,6879,2625,270,4674,2633,4631,1899,8587,5819,6992,9363,6236,8018,5658,8182,7568,4685,651,2574,7188,5788,4733,4477,9081,7616,9631,848,2792,1861,1517,720,32,8853,2998,1278,384,6975,5130,7588,7161,8636,8038,2737,7004,1688,645,2508,520,4223,5366,8414,6761,9313,1631,35,5105,6628,8876,9991,7253,3308,2277,4510,3640,6775,8028,3365,3687,1682,4411,8487,4868,5618,2288,8992,714,5668,6571,1273,5101,2435,3111,3290,2752,2465,6197,581,6664,1475,4618,3744,1208,8428,9982,2620,7211,9447,5867,6369,6697,1449,2109,555,2585,449,2724,5937,7639,5675,3782,9073,5772,8524,6184,1964,3493,3413,1320,2083,4415,8776,8997,9988,7742,9642,9909,7504,3944,3185,5144,8676,6523,2107,4440,7632,8463,6311,8325,7778,5209,4713,1565,5032,3383,8677,194,4634,6288,8327,7452,7359,6642,5920,540,8790,5030,2619,6343,8446,2565,6452,3118,4953,4448,2488,1692,6117,644,5045,7416,875,5257,5634,2454,1481,2937,2367,3063,8146,2148,4489,1746,3347,3938,7798,2287,6431,5486,3770,4732,2492,1363,2620,7556,3290,2210,4684,5560,3388,8003,7615,9455,8051,7900,7683,6220,4748,9894,5837,9226,4436,8622,4220,1251,1454,7313,7516,7842,8138,2438,32,3866,3809,5884,1433,9603,1859,7837,3941,5660,6954,9031,4324,1556,1237,4994,4431,2572,3055,5860,3562,7569,2450,2823,185,1122,3404,3995,952,9872,2592,5238,1726,4857,7684,205,6426,3673,4595,9549,2297,7571,7622,6412,7534,2415,5744,6156,1338,423,4801,140,9383,3677,9971,6247,5193,8294,9444,9302,110,2014,4888,2960,6475,3021,7426,5560,6327,3260,3403,7341,4378,3977,238,9224,1306,6101,6564,3525,8406,7023,3682,7982,9681,2199,7633,2667,8831,8030,792,7180,2679,3146,2386,9870,6602,2584,9642,5938,2913,3680,9043,1845,1602,2726,9064,2579,7393,5385,9054,8502,5152,4866,1081,7413,7562,2323,4716,6971,3316,3239,2982,2930,9201,5790,8509,2289,118,5597,172,3433,2770,3624,2974,648,2608,2739,7115,8744,4696,1958,507,8988,999,9702,4688,9075,3367,9475,3320,8556,2189,9486,3762,7395,193,1258,5668,1870,8964,3917,8715,4216,4489,1703,8019,4969,8177,6039,5159,1974,7324,4703,2161,1239,7988,7995,1259,1286,7241,9701,1309,4164,6012,3243,2528,8663,4755,2333,6925,2261,2654,6678,3988,5008,3127,7146,2609,959,8468,7454,6698,1173,6548,6532,4028,8593,4128,3962,3907,5612,5386,3985,7110,3244,725,8653,8497,3607,3258,8610,8399,326,491,6952,9004,1460,112,6646,9904,5381,5680,9241,9100,8323,1347,7754,678,3614,5202,4855,8805,1604,4776,4698,9288,4430,5266,6985,665,9657,9872,4856,1438,7374,3796,8735,8988,4552,9556,4194,5045,5100,5764,2831,36,360,8356,5430,9005,8395,1229,215,8499,6431,6426,8501,8515,7141,1267,4021,1811,5142,8390,5212,208,9096,5010,7893,4566,3076,2024,2062,5161,5492,9703,5945,8219,4936,8016,2871,18,1160,4137,2692,9807,5310,8191,5201,5061,3742,9283,8267,503,6509,3223,9347,3346,3234,4165,9741,3903,2497,2326,701,5012,9668,4908,599,4618,7409,5468,6946,5387,5572,1135,6112,1681,1233,1694,6412,7801,2787,5932,1254,3486,396,273,6646,5718,1711,532,3902,7255,9495,9711,7559,9327,117,348,4157,1312,4981,1648,9127,9336,5712,1786,9458,4851,3932,9137,522,3271,7226,7218,942,8457,9834,1841,4307,7788,2354,4463,4600,1833,2533,4186,7946,1002,9541,982,3692,5433,2760,4162,1888,2408,5854,5921,3920,632,1521,6473,819,8004,330,6563,764,2061,8029,6284,8728,7194,3157,4663,5443,892,5515,7078,852,2250,2922,3067,5701,3898,5588,9582,532,7075,8916,1228,3934,747,1074,5012,2655,1443,8115,4474,7521,2920,8015,1888,7583,5786,5288,1700,7760,5090,2853,5938,620,7276,9496,6001,3188,5144,2199,7396,8673,1841,5393,6304,201,519,7134,7384,9544,6577,3955,5109,2666,8033,4701,1036,4403,4180,4858,965,8260,4456,5203,3254,5146,9382,5647,3933,1868,3321,4524,373,1421,8352,5227,1372,428,2088,9754,1701,827,992,9630,3808,5779,5912,8722,9372,3753,7047,9995,9937,4419,279,4131,8936,1621,7801,7395,9409,4599,4079,6069,5365,5657,1876,8822,7474,4,9356,3240,3151,7786,9414,5592,4413,8993,2161,340,7634,939,9387,4603,3301,4968,1529,7907,9082,809,9790,8196,6306,5225,8904,6898,7604,776,3580,9474,2163,3024,7113,7223,9271,8181,7041,1906,7359,4714,4182,5461,8524,8025,2168,776,2280,5203,3845,2774,8573,7702,4786,323,4397,1768,9032,8492,9345,471,6504,9088,7643,7034,6723,8751,1652,4606,8148,6940,3594,8316,9124,7680,2670,1811,3165,7219,7858,1450,5698,929,3338,528,8162,7998,8996,6737,555,9550,1592,5960,4534,5239,5816,8985,7786,9420,7575,9772,257,1451,1052,5670,2819,1736,3525,3371,6719,3800,4905,9688,5651,2367,9891,7206,9863,4346,3217,3326,750,239,6757,5492,8857,4821,8422,2783,5032,5431,3974,9647,3117,4357,4441,5722,9322,5569,3703,3486,9788,8889,948,1339,1938,3479,2264,1100,6217,5180,9288,3027,6261,3350,9769,5355,9671,4152,4239,6984,3106,3561,8017,5469,6897,6645,2814,8636,1017,4599,7375,5576,8656,1823,3089,7341,4990,5853,3139,7990,5922,8959,5973,4720,1396,497,9557,5751,6467,8946,434,9285,2483,7624,5026,1616,909,6129,5351,1265,9465,6117,5734,5100,2823,4909,1959,9567,2070,5998,3107,9832,4514,6322,853,7843,8178,2656,2757,8025,1011,6673,1294,5910,8541,7890,4797,7824,6648,3481,7946,4823,371,7324,8616,1497,4073,4779,5361,7908,7896,5555,9899,4085,8230,1573,3451,1459,8274,8671,4343,8469,6959,8155,7001,8251,7767,8526,6914,1435,6806,9980,5341,2956,4817,1916,8086,540,7351,1630,6154,3834,6582,2054,4630,4646,9178,438,4123,5107,2843,561,5178,1024,8938,2450,8664,9960,2611,8691,1156,4502,2948,8704,5708,1630,614,4740,6649,6386,1158,7337,3988,7636,755,2232,4348,7665,2599,5959,7807,8901,5409,2225,6611,4934,8112,6574,43,5183,8080,4725,2814,3109,7324,8806,5365,1587,3626,7540,249,8188,6015,1717,9788,8926,6303,3930,3912,4539,558,7800,849,6640,3153,6723,5130,7683,2109,8300,6887,6431,3160,1064,3360,4156,311,5953,6149,9037,8329,8649,9206,8956,1806,1928,1381,1015,5509,1849,2502,4312,4748,9419,2991,324,2694,2833,8660,7717,6316,7909,2387,3586,8488,1141,6193,6411,7793,2408,72,5861,9608,5872,5073,4885,5440,5850,9859,5484,8368,5221,5750,2455,705,1994,2947,1947,4702,7080,7010,6823,5970,3023,1539,4048,8277,2592,7509,4174,4003,7823,9242,5672,5462,4768,410,6245,9381,4644,7105,6780,8044,7632,5086,4791,5968,761,3699,702,3295,268,9159,9284,8359,4869,1688,7067,6927,6795,825,7368,2893,6759,3159,4843,4191,443,8590,9999,1984,6951,5356,6374,9117,9841,6833,9760,4865,4730,8809,7778,7329,2054,7449,5856,5407,6669,7499,3313,1918,950,6657,896,7073,884,8217,579,4364,387,7112,2304,9960,2717,1031,8072,281,1920,3766,4015,3899,9759,2063,4800,1709,9089,5544,1256,5357,2261,9558,4964,710,6165,7151,4819,885,5104,6477,6227,4004,8553,825,755,3811,5980,2071,3901,6934,2301,6047,2460,3458,4988,2527,148,9939,4349,886,3917,3976,6458,176,3284,3658,9657,3032,3590,8178,4565,117,6127,9132,9394,64,3133,3384,4084,9703,2425,1488,5904,2008,641,1559,635,460,4423,3989,2680,5943,4168,6140,7428,8593,4568,1918,5098,6266,312,4095,476,8243,9447,9407,7922,3398,6473,9909,5078,5007,1551,5904,192,5518,7547,6976,1833,5926,5486,2704,8708,3716,6305,9455,4299,8794,7886,310,5043,9344,1124,6140,880,6156,2653,4331,8777,7800,4808,7037,6070,9148,4756,8030,4542,4209,2677,1943,988,1468,1876,6043,1158,3430,1569,225,1536,5603,2137,7892,5456,5692,4739,7158,2865,369,3030,5986,1539,9333,5537,9998,6805,3622,8780,948,5252,8739,2816,4558,8835,2115,2251,86,2594,2710,9276,2423,8979,1458,9906,891,8269,7480,5162,9789,5708,6888,3871,6268,3275,6539,5075,6080,8427,5426,6578,4651,8393,34,7011,718,2669,4469,3597,6189,400,3992,2110,6988,7691,1521,1415,9700,3460,8959,1764,9673,423,1543,8279,6011,5231,9066,9860,5991,3218,3988,5680,9703,5417,5661,3264,9695,1098,1777,793,900,1340,9237,1952,7997,1058,6857,1745,1384,3579,1813,4482,9471,9858,6471,9775,3184,6192,3372,3810,5839,4673,5706,4146,6282,5872,6590,8569,3583,2018,3091,970,6295,7598,6472,674,6365,4083,7647,9677,8237,7950,8348,4495,6140,1246,8797,1229,6594,8069,9750,3530,2919,5893,9315,3450,37,3038,4636,9364,3043,55,6856,4542,4530,4015,5939,1449,4615,8407,770,9906,6419,4779,67,5514,6924,7313,3476,7137,2819,1178,9099,2448,4990,3970,5827,3601,7803,2410,1135,905,7027,189,7845,6054,2481,2233,8064,6527,9990,6054,4608,4768,2906,33,3098,6621,7781,1231,1356,1172,5656,6392,4110,4953,3946,272,6664,8804,6327,4945,234,2507,9040,8363,2606,4101,2988,1680,5513,5343,8554,8885,212,6354,4529,7242,5049,9624,830,4264,8217,7189,6580,6371,1369,1894,3791,1728,3012,1342,7993,4918,2516,3796,4697,6970,186,4158,5633,8124,2170,3748,9551,6450,3019,5492,4814,1266,1783,9067,4392,5612,4838,6524,9132,3928,81,1849,5236,1581,2893,9787,682,1836,3135,7662,5932,3745,9474,4149,8505,6289,7954,3232,5964,2512,5108,831,6992,6925,7748,704,1128,7510,7855,1344,6114,4061,6377,8747,7796,7461,8049,616,5413,3368,5744,8303,8296,9891,206,318,5089,5792,494,2465,242,7759,908,1569,8876,7997,2711,5462,2815,4197,1441,6090,6938,6810,6462,1976,4534,5919,4929,4263,3486,7007,3765,1245,9093,9867,4166,5128,6122,7045,5378,4093,4665,8679,724,4520,5981,9585,1413,2191,7120,3953,4602,7832,5072,6608,8084,8995,1178,9783,2681,6974,7695,6605,8232,6468,1452,7796,4528,2697,9392,8568,1484,9400,9795,5090,5485,9276,3280,4909,7748,8067,1168,5848,8060,787,9424,2926,9671,5840,1981,4883,7864,7412,3710,3839,2011,4732,418,8261,895,899,4111,5376,2686,2697,9149,4944,2541,104,2884,5538,9926,5658,4869,1590,2255,4223,7016,2195,984,2520,5180,1828,3709,3220,9395,6475,6794,2814,6198,4160,1548,7951,9477,9855,2743,90,9119,56,8308,5770,3113,3545,2262,6063,4615,843,4997,6958,7692,2153,7168,9242,3010,7867,4176,6618,7192,9388,9079,212,6278,6249,6629,2276,2202,702,9810,9905,9571,7210,2115,425,8201,3549,3624,6612,2383,5681,9273,2610,8311,2104,8334,4638,9382,5699,6948,6382,7264,6010,2761,1779,1323,5992,2875,8882,247,8165,1825,1837,311,2677,9673,5496,6343,9616,9991,4495,4961,5622,2890,9910,8858,3104,7354,8854,659,3009,1306,192,1522,3862,3566,8242,8553,1062,4843,6687,319,2210,7232,294,1133,8836,6871,5026,3757,9318,9753,9873,5278,3351,9744,5394,4850,7968,395,8196,5790,4504,7836,3230,3079,2526,7724,3004,6419,673,6842,7318,8297,2036,1469,9337,1138,1473,5400,6892,8818,7485,1085,6278,9213,551,1834,2165,3388,4408,4532,9591,9720,7888,1945,6879,8149,5311,3044,5727,7007,7796,8487,1247,9949,5360,2587,548,3185,9839,1994,1140,1108,5075,7072,2799,6347,4085,390,1676,4293,5274,3693,6052,2102,5739,956,1438,3538,654,8916,2986,4421,3856,8422,1770,3159,1055,1264,4747,9938,3156,4379,9178,1044,6765,6446,8206,8706,238,9664,3678,9054,5709,4702,783,6246,3867,5687,3846,534,7602,4870,8764,6301,2707,2949,3409,8161,2480,2157,1307,2793,4672,8133,9633,1598,2764,4385,9994,5508,6345,1020,2212,9744,1843,1514,642,9183,2259,586,6109,7097,4396,6250,9796,2348,3399,4485,2286,709,4027,5371,133,2503,7708,5600,7985,4464,7334,9580,4366,7460,2805,1197,2572,7073,8667,4087,6910,7465,5604,410,1396,374,6968,6735,1381,3047,8960,4626,8364,6008,5172,9782,5518,6197,7323,2153,8145,7530,4572,6300,3273,4021,5412,141,8845,5553]

# Simple case

# nums = [1,1,1]

# ExpectOutput = 1

# nums = [1, 2, 2, 2, 5, 0]

# ExpectOutput = 3

nums = [8975,9106,5349,7891,3795,983,3532,3121,9341,6891,5416,6221,1247,5343,7006]

ExpectOutput = 10

solu = Solution() # 先对类初始化，才能进行调用

# temp = solu.removeSubfolders(s)

temp = solu.waysToSplit(nums)

if (temp == ExpectOutput):

print('right')

else:

print('wrong')

print(temp)

elapsed = (time.process_time() - start)

print("Time used:", elapsed)