Cod sursa(job #627)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 11 decembrie 2006 16:48:30
Problema Suma divizorilor Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 49.72 kb
#include <stdio.h>

#define maxn 10010
#define maxx 25
#define mod 9901

int inv[mod]={
1,4951,6601,7426,7921,8251,2829,3713,8801,8911,9001,9076,6093,
6365,9241,6807,6989,9351,4690,9406,943,9451,861,4538,9505,7997,6234,8133,
4097,9571,5749,8354,9601,8445,2546,9626,1338,2345,2031,4703,483,5422,8980,
9676,9681,5381,632,2269,3233,9703,5630,8949,2989,3117,9721,9017,8164,6999,
7216,9736,2597,7825,6915,4177,5179,9751,1330,9173,287,1273,7112,4813,6239,
669,9769,6123,8358,5966,376,7302,2078,5192,4533,2711,3378,4490,4666,4838,
445,9791,9357,7641,8517,316,938,6085,8472,6567,9801,9802,6568,2815,9132,
9425,4149,6445,1388,6509,9356,9811,446,9459,8061,4082,8093,8450,677,3608,
9485,4868,8019,6249,161,8863,1901,8408,3976,7039,9594,7540,6122,9826,670,
665,3227,9537,2674,5094,926,5587,3511,3556,1454,7357,6760,8070,4378,5285,
1329,9835,5180,8012,5177,4179,3130,2983,2964,188,7597,3651,123,1039,4009,
2596,9841,7217,4743,6306,5800,1689,9322,2245,9157,2333,8430,2419,9006,5173,
9016,9846,3118,9629,4166,8771,4228,9209,6936,158,2305,469,1918,7993,9388,
4236,8327,8234,5629,9851,3234,4901,7044,3284,6243,6358,4057,4566,3396,9663,
6727,7025,3097,8173,5671,694,1796,8205,6479,4678,5380,9856,9677,223,222,
9680,9857,8981,7284,2041,4583,8997,2786,4225,6629,5289,6067,1804,6726,9693,
3397,2434,493,8960,3993,8075,4607,5031,1884,9382,1511,5901,7337,4204,7279,
1988,1126,8470,6087,4797,3020,3770,8156,3061,6814,4913,2578,335,6749,5283,
4380,6564,4165,9719,3119,1337,9865,2547,8507,463,2839,7744,5250,6706,2484,
1778,3613,727,69,8629,4488,3380,2824,4035,9090,2189,9364,7593,3267,5615,
8444,9868,8355,2590,8790,4006,6460,7539,9772,7040,3044,1565,1942,6442,1550,
1482,1383,94,8964,8749,5773,6776,3763,5012,6100,5470,3016,6955,6419,1298,
5748,9871,4098,8559,3449,7322,266,3153,3790,2900,2687,5795,4123,4661,7534,
6073,5998,9529,428,6117,8596,4215,3526,6160,2328,4503,7363,7537,6462,4508,
6426,4923,5979,1559,2673,9765,3228,2083,1241,9336,3354,2114,427,9555,5999,
3468,3934,79,2600,6103,3370,5185,7926,959,4343,8947,5632,4694,3198,2118,
8832,9114,7622,4117,5341,7765,7996,9876,4539,1617,6824,7401,3753,3522,8820,
1642,4376,8072,3722,3179,8037,6979,7492,2283,8103,1698,4867,9782,3609,8314,
5813,8463,1317,6499,7771,9037,4636,7786,371,347,3785,898,827,9053,2561,
8190,8854,2339,8383,2690,1263,4928,8060,9789,447,5062,89,111,443,4840,
860,9879,944,9441,5027,3642,7812,5971,4983,7242,5026,9449,945,1393,278,
7063,7644,8265,3265,7595,190,7984,988,902,7117,3363,4148,9797,9133,6649,
3948,1217,3911,5197,41,4480,7635,6947,7441,8988,7937,7254,7945,7466,241,
942,9881,4691,1016,5706,7520,7901,1581,8619,3425,2102,5274,8590,8534,994,
7275,563,6549,4235,9708,7994,7767,7349,5458,1510,9653,1885,4941,4078,4676,
6481,2810,3407,1503,7407,8647,1289,3002,5118,2322,8325,4238,7592,9606,2190,
1194,3282,7046,7033,7640,9810,9792,6510,3240,5619,4689,9883,6990,6224,4297,
9204,8010,5182,4515,6370,2214,3872,2312,2625,510,3353,9533,1242,7369,889,
4907,6757,7196,5314,7240,4985,5579,9265,8717,2244,9730,1690,2062,1412,2972,
6968,6076,4545,2412,6045,2387,4682,8477,8747,8966,6584,1897,7758,1078,4222,
5091,4934,1598,9128,2348,1295,3584,4395,2724,2003,2081,3230,9188,8720,2342,
4886,7953,3520,3755,1522,6606,5733,1132,971,1478,3221,8301,775,8843,741,
4738,5642,4519,47,7633,4482,8716,9325,5580,7837,8491,3388,8897,6832,1663,
2506,3899,3050,5203,2735,656,1508,5460,8428,2335,8160,7165,649,8394,2874,
6806,9886,6366,2049,6526,9230,134,6675,2761,3661,74,133,9237,6527,4134,
1895,6586,1450,117,6294,6868,7848,2428,7012,1986,7281,2515,3767,4828,7987,
4038,2999,6935,9715,4229,214,8106,8009,9347,4298,5510,7058,3983,1763,7887,
3080,8623,1164,6596,7202,4357,8632,2242,8719,9290,3231,2271,2254,7733,3213,
9061,7412,2719,7940,6765,5730,1352,6287,286,9833,1331,1614,8682,5992,4498,
5571,4836,4668,1021,1677,1246,1057,628,5164,2332,9728,2246,7950,3804,1734,
5856,1967,3085,4990,5746,1300,1036,8002,2145,1685,9027,7543,1236,3963,2751,
5430,6976,7122,6648,9424,9798,2816,2029,2347,9299,1599,626,1059,4307,4416,
7842,4557,5147,3811,6019,7009,2573,7621,9511,8833,8872,3998,2566,4938,1723,
7220,7460,5759,4025,3412,1202,8651,5550,6827,8668,1761,3985,4410,1460,821,
6156,2188,9608,4036,7989,1861,2782,6540,7247,8969,4340,8440,808,3746,4752,
6092,9889,9002,431,849,7584,7384,6136,4891,1355,6755,4909,4157,7547,7857,
7411,9182,3214,5609,1750,8200,1160,8836,2560,9469,828,2318,3502,3893,3192,
5136,7805,5124,2611,6843,5060,449,23,5364,4635,9477,7772,6231,1496,4095,
8135,4427,4672,6120,7542,9142,1686,1345,7835,5582,3030,2464,1933,4030,8163,
9845,9722,5174,8182,2531,568,4995,1089,5006,3681,5172,9724,2420,6115,430,
9075,9890,8912,472,2785,9671,4584,7464,7947,1821,2930,3906,4043,7936,9413,
7442,8754,3621,2289,2513,7283,9675,9858,5423,6640,5647,4806,139,4315,8482,
7130,3822,4339,9083,7248,6583,9308,8748,9584,95,3817,3992,9659,494,21,
451,461,8509,1631,6632,4288,2074,2988,9849,5631,9517,4344,8275,8525,1974,
382,5559,1463,6906,7855,7549,5838,4971,1843,2240,8634,8768,622,8424,5790,
8671,7606,4494,8087,8919,5441,3627,5440,8923,8088,3733,3106,5071,1916,471,
9000,9891,8802,7296,1366,508,2627,2853,2870,3760,4450,8901,4451,5741,6831,
9260,3389,6663,8495,1051,3248,2637,7864,4295,6226,4267,5209,497,4196,8588,
5276,5232,737,8225,7975,7068,6752,4854,3837,3997,9112,8834,1162,8625,8147,
2729,8600,755,1900,9777,162,5893,3443,7421,7262,2039,7286,2338,9466,8191,
4068,1405,1008,6654,7776,5702,6560,8654,740,9274,776,5595,3966,1501,3409,
2559,9055,1161,8871,9113,9512,2119,2154,3796,6533,4803,8280,1095,2142,597,
5680,1641,9498,3523,1993,8467,3276,3820,7132,4905,891,4896,2777,3255,2011,
1620,1076,7760,6011,7295,8910,9892,3714,3495,2666,3112,7876,7099,1118,4602,
6312,4005,9598,2591,6743,7208,5985,3185,2801,1107,5300,1936,1422,1156,1490,
6263,7912,255,1432,6627,4227,9717,4167,621,8931,8635,3437,5395,7724,7404,
8232,8329,4816,3598,2642,2657,4877,3620,8986,7443,4748,7740,5772,9583,8965,
9309,8478,1122,8412,4865,1700,845,1066,1031,1277,706,3306,1486,2944,3484,
2092,3038,1226,7223,5841,1206,7154,7973,8227,6144,8381,2341,9289,9189,2243,
9324,9266,4483,4596,3292,8552,5899,1513,3879,7710,539,6620,2111,5575,7496,
5351,2467,6488,799,1251,4564,4059,1174,2748,5598,2940,1792,4137,7148,4473,
1362,4759,5952,480,5991,9170,1615,4541,4594,4485,4360,6862,1171,2679,2443,
7605,8927,5791,1760,9098,6828,2357,761,5939,3303,2701,7817,367,566,2533,
5436,8223,739,8845,6561,5549,9101,1203,5338,1288,9372,7408,5321,5238,2369,
5269,2821,5983,7210,439,4974,3436,8767,8932,2241,9191,4358,4487,9613,70,
2790,8146,8869,1163,9196,3081,1694,3424,9399,1582,3416,7158,5782,4562,1253,
530,6900,2968,1525,3576,7552,604,6318,3481,328,4154,754,8866,2730,7705,
4214,9552,6118,4674,4080,8063,8533,9395,5275,8883,4197,3343,1437,421,3403,
4076,4943,2286,3183,5987,5975,4476,3263,8267,4615,149,67,729,8288,2206,
6331,3330,6781,274,37,7557,5017,3448,9569,4099,8214,876,2067,3587,5898,
8712,3293,4170,725,3615,5009,833,3147,5049,3434,4976,3924,5427,1214,5143,
3506,2604,993,9394,8591,8064,6208,1661,6834,6043,2414,1973,8944,8276,2019,
3633,6450,2581,8418,315,9808,7642,7065,3455,107,3393,4053,1630,8955,462,
9624,2548,2149,5762,2755,3942,3529,7689,6942,8292,5832,1050,8894,6664,1540,
3387,9262,7838,582,6930,3298,2477,3601,6051,7129,8973,4316,7964,1121,8746,
9310,4683,4645,4163,6566,9804,6086,9645,1127,3275,8817,1994,6557,1316,9481,
5814,3706,5057,6310,4604,3970,4858,8333,4386,2865,3314,676,9785,8094,6344,
143,2545,9867,9602,5616,5490,807,9081,4341,961,2996,1818,2249,5946,7736,
6713,2418,9726,2334,9249,5461,3853,5789,8929,623,6681,5479,8350,314,8519,
2582,6594,1166,6958,4864,8744,1123,3639,3975,9775,1902,3669,867,5807,2928,
1823,5934,1062,6493,527,2495,1671,2873,9244,650,4442,518,249,4001,1191,
6023,1758,5793,2689,9464,2340,8722,6145,618,3296,6932,1292,6326,2425,2715,
8185,3488,6176,3561,2183,3324,7895,4712,8297,4899,3236,1408,6515,5965,9824,
6124,2589,9600,9869,5750,3458,313,8420,5480,1970,7104,6329,2208,6518,3921,
362,7229,4275,7524,1647,6856,310,7960,4385,8455,4859,6237,4815,8761,8233,
9706,4237,9367,2323,4436,7675,1999,501,1283,6486,2469,3773,5812,9483,3610,
2455,3730,5327,7830,4301,6963,5115,1706,4966,601,774,9276,3222,2775,4898,
8364,4713,4334,1682,5831,8498,6943,3202,2205,8569,730,1220,5361,398,3078,
7889,1094,8826,4804,5649,2018,8524,8945,4345,5881,5847,1391,947,3270,4614,
8574,3264,9435,7645,2170,1921,4220,1080,404,5526,1873,5110,2376,1563,3046,
2828,9895,7922,4501,2330,5166,4780,5375,2898,3792,8033,3692,1371,3068,643,
7396,2670,5628,9705,8328,8762,7405,1505,7029,6143,8724,7974,8879,738,8656,
5437,4591,5566,1607,4071,7755,758,875,8557,4100,170,580,7840,4418,6819,
1280,6478,9685,1797,414,5035,1159,9057,1751,4279,6897,4785,1596,4936,2568,
4067,8853,9467,2562,5699,6256,3487,8372,2716,2530,9014,5175,8014,4962,793,
2682,5160,7268,5670,9689,3098,3886,6206,8066,6096,748,4046,6998,9844,9018,
4031,7164,9247,2336,7288,3060,9640,3771,2471,4571,4291,843,1702,5623,2728,
8868,8626,2791,3877,1515,4109,1232,804,5917,702,2015,4426,9032,4096,9873,
6235,4861,8112,2587,6126,4091,5433,6216,7416,284,6289,7448,5537,5495,4348,
2503,7233,6791,4848,2586,8130,4862,6960,1210,5765,8008,9206,215,1697,9488,
2284,4945,7702,4456,3833,236,3176,6343,8449,9786,4083,2292,5325,3732,8918,
8924,4495,5861,6904,1465,7653,1953,908,6972,1499,3968,4606,9657,3994,3721,
9495,4377,9755,6761,6363,6095,8169,6207,8532,8592,4081,9788,9460,4929,967,
7662,2651,3320,6229,7774,6656,2403,4552,5020,2880,7108,6026,4241,2202,3565,
7728,1911,814,7120,6978,9492,3180,3624,3691,8242,3793,4654,7054,4374,1644,
4792,2767,4998,2859,6859,6555,1996,6248,9780,4869,247,520,4961,8180,5176,
9749,5181,9346,9205,8107,5766,674,3316,595,2144,9145,1037,125,1494,6233,
9875,9506,7766,9387,9709,1919,2172,1860,9088,4037,9213,4829,987,9431,191,
1909,7730,1639,5682,6266,3453,7067,8878,8226,8725,7155,2919,4548,7436,881,
5872,4600,1120,8480,4317,6873,4384,8335,311,3460,4212,7707,2895,3519,9286,
4887,3803,9155,2247,1820,8994,7465,9410,7255,7671,7379,6764,9179,2720,7253,
9412,8989,4044,750,6817,4420,1553,2798,7486,1375,958,9520,5186,5569,4500,
8250,9896,7427,4401,2122,3648,2888,683,2621,254,8776,6264,5684,6377,1083,
1435,3345,1880,3654,2225,1580,9401,7521,7176,608,7821,4711,8366,3325,4630,
7082,6645,1093,8282,3079,9198,1764,5476,4251,1624,1378,6269,2087,3932,3470,
7098,8796,3113,6643,7084,771,7555,39,5199,4763,2098,6685,4294,8890,2638,
1044,2616,228,5319,7410,9063,7548,8938,6907,3534,662,3376,2713,2427,9221,
6869,7439,6949,5131,4556,9122,4417,8210,581,8490,9263,5581,9024,1346,6315,
5508,4300,8309,5328,5612,950,6914,9839,2598,81,4710,7897,609,6672,366,
8661,2702,3631,2021,5970,9446,3643,6416,1169,6864,4733,5123,9046,5137,2034,
3217,5653,6475,504,4628,3327,6204,3888,2608,2851,2629,3280,1196,4327,6546,
370,9475,4637,6702,388,1070,7748,5499,1983,6254,5701,8848,6655,8053,6230,
9036,9478,6500,5531,7348,9386,7995,9507,5342,4756,6397,6010,8805,1077,9305,
1898,757,8217,4072,7352,1396,4140,5878,5498,7781,1071,6106,5249,9621,2840,
6058,5771,8751,4749,7507,6712,8433,5947,3212,9184,2255,1638,7981,1910,8042,
3566,3751,7403,8764,5396,2540,2448,6696,6339,1533,6578,5637,5956,3744,810,
294,538,8708,3880,2894,7956,4213,8598,2731,4455,8100,4946,5659,1857,6337,
6698,1612,1333,3571,1556,3384,3938,6941,8500,3530,559,6030,2301,7016,3156,
2695,6953,3018,4799,6810,6246,1998,8322,4437,3604,7378,7943,7256,6543,5068,
6351,4049,5504,7179,2650,8057,968,1268,711,1183,578,172,745,1952,8082,
1466,3956,5243,5078,7629,716,2169,8264,9436,7064,8516,9809,9358,7034,6589,
5261,6946,9416,4481,9268,48,6669,715,7648,5079,3862,7503,3702,3009,4116,
9510,9115,2574,2408,412,1799,4957,1321,6719,6279,917,7389,5817,1810,4577,
4493,8926,8672,2444,2374,5112,3870,2216,2886,3650,9742,189,9433,3266,9605,
9365,4239,6028,561,7277,4206,4016,7383,9072,850,6400,5373,4782,533,1577,
5466,3509,5589,3740,353,5399,1653,4736,743,174,1472,653,1742,2614,1046,
436,1519,1180,613,5016,8562,38,7871,772,603,8607,3577,5837,8937,7856,
9064,4158,3072,1235,9141,9028,6121,9771,9595,6461,9545,7364,6072,9558,4662,
1258,4633,5366,7192,7456,2298,4790,1646,8339,4276,7175,7900,9402,5707,6386,
6890,5787,3855,589,5220,5711,3310,4642,6006,6711,7738,4750,3748,3701,7626,
3863,6184,6734,3244,1850,5350,8703,5576,7326,2282,9490,6980,5355,587,3857,
1374,7929,2799,3187,1470,176,896,3787,7019,2795,3574,1527,7187,2052,681,
2890,7330,3580,2976,6503,240,9409,7946,8995,4585,2663,5758,9106,7221,1228,
2297,7528,7193,7360,2180,3206,3431,5716,5536,8121,6290,1589,6172,4747,8753,
8987,9414,6948,7846,6870,880,7969,4549,1200,3414,1584,6129,1747,5331,4400,
7920,9897,6602,1415,6301,7261,8859,3444,5134,3194,283,8124,6217,2528,2718,
9181,9062,7858,5320,8646,9373,1504,8231,8763,7725,3752,9501,6825,5552,1784,
2669,8237,644,6003,4686,3007,3704,5816,7611,918,2619,685,6135,9071,7585,
4017,6361,6763,7942,7672,3605,3035,5170,3683,2487,7184,1718,888,9334,1243,
4466,3687,6071,7536,9546,4504,2179,7454,7194,6759,9757,1455,35,276,1395,
7753,4073,5457,9385,7768,5532,3290,4598,5874,6491,1064,847,433,1712,4203,
9650,5902,791,4964,1708,5835,3579,7471,2891,785,2281,7494,5577,4987,265,
9567,3450,1381,1484,3308,5713,5052,1788,1772,3776,1545,302,1112,3159,3952,
6691,5891,164,61,2077,9821,377,3799,4433,6394,1365,8909,8803,6012,2107,
7051,4776,857,3059,8158,2337,8856,2040,9674,8982,2514,9217,1987,9648,4205,
7588,562,9392,995,7049,2109,6622,5912,5669,8175,5161,4261,6652,1010,2038,
8858,7422,6302,1143,7245,6542,7670,7944,9411,7938,2721,2238,1845,6582,8968,
9084,6541,7258,1144,5025,9443,4984,9328,5315,2439,4144,6405,1103,6790,8116,
2504,1665,4274,8341,363,137,4808,4969,5840,8729,1227,7459,9107,1724,4742,
9735,9842,7000,339,4107,1517,438,8639,5984,8787,6744,2219,2949,3025,4356,
9193,6597,1239,2085,6271,5313,9330,6758,7359,7455,7529,5367,84,6524,2051,
7475,1528,1717,7372,2488,721,1962,2649,7664,5505,607,7899,7522,4277,1753,
1034,1302,2197,5447,4648,4697,648,9246,8161,4032,6438,3104,3735,5781,8616,
3417,2918,7972,8726,1207,4304,5937,763,4472,8689,4138,1398,5960,5728,6767,
3847,3225,667,6241,3286,4209,6800,5108,1875,4904,8814,3821,8972,8483,6052,
6678,1602,5004,1091,6647,9135,6977,8039,815,3362,9428,903,231,5677,4812,
9830,1274,1756,6025,8047,2881,2423,6328,8347,1971,2416,6715,1117,8795,7877,
3471,6403,4146,3365,2916,3419,525,6495,4447,6779,3332,102,770,7873,6644,
7892,4631,1260,3919,6520,291,5867,3465,6854,1649,7,6189,5281,6751,8877,
7976,3454,8515,7643,9437,279,2158,3844,3982,9201,5511,6922,4373,8030,4655,
4775,7292,2108,7273,996,7032,9360,3283,9700,4902,1877,3043,9593,9773,3977,
5514,1448,6588,7639,9359,7047,997,6142,8229,1506,658,3096,9691,6728,2907,
4880,1853,2794,7479,3788,3155,7684,2302,6252,1985,9219,2429,2572,9117,6020,
2193,1946,6383,4525,1657,6110,338,7215,9843,8165,4047,6353,3172,2878,5022,
6283,6223,9350,9884,6808,4801,6535,2808,6483,2745,1930,5354,7491,9491,8038,
7121,9136,5431,4093,1498,8079,909,5996,6075,9317,2973,6423,3868,5114,8307,
4302,1209,8110,4863,8414,1167,6418,9575,3017,7681,2696,6877,5130,7845,7440,
9415,7636,5262,3201,8291,8499,7690,3939,4175,6917,157,9714,9210,3000,1291,
8377,3297,8488,583,2934,3479,6320,2432,3399,4372,7056,5512,3979,6770,156,
6938,4176,9838,7826,951,53,6785,4257,5384,3533,7854,8939,1464,8084,5862,
690,2967,8611,531,4784,8197,4280,5214,2509,6198,2277,5786,7517,6387,3710,
4622,4430,325,2947,2221,5103,259,6132,5075,5129,6951,2697,5546,4383,7962,
4318,879,7438,7847,9222,6295,2525,4732,7808,1170,8676,4361,6554,8023,2860,
309,8337,1648,7074,3466,6001,646,4699,3163,4310,6163,5798,6308,5059,9043,
2612,1744,262,3088,3546,6731,6409,6042,8529,1662,9259,8898,5742,2356,8667,
9099,5551,7400,9502,1618,2013,704,1279,8208,4419,7933,751,4912,9638,3062,
6356,6245,7678,4800,6988,9885,9242,2875,211,1729,6016,5107,7136,4210,3462,
2740,6167,985,4831,3552,4847,8115,7234,1104,2026,3259,4256,6911,54,181,
273,8565,3331,7088,4448,3762,9581,5774,4246,3428,5721,155,6919,3980,3846,
7143,5729,9178,7941,7380,6362,8069,9756,7358,7195,9331,4908,9067,1356,4853,
8876,7069,5282,9634,336,6112,2884,2218,7207,8788,2592,5950,4761,5201,3052,
5592,5487,3243,7500,6185,6408,6837,3547,2906,7024,9692,9664,1805,3559,6178,
408,1865,6278,7614,1322,3915,1116,7101,2417,8432,7737,7508,6007,853,4766,
2483,9619,5251,5206,387,7784,4638,2957,1611,7697,6338,7720,2449,6471,4182,
5890,7307,3953,2167,718,841,4293,7866,2099,4249,5478,8422,624,1601,7127,
6053,2760,9235,135,365,7819,610,714,7631,49,199,5001,1539,8494,8895,
3390,547,4283,4413,3166,2402,8052,7775,8849,1009,7265,4262,3947,9423,9134,
7123,1092,7891,7083,7874,3114,5646,8978,5424,1326,1635,467,2307,297,4287,
8953,1632,5288,9668,4226,8773,1433,1085,6082,5911,7271,2110,8706,540,2856,
202,3659,2763,5693,5887,4368,2555,5304,1188,1350,5732,9282,1523,2970,1414,
7425,9898,4952,3961,1238,7201,9194,1165,8416,2583,4189,2390,5260,7638,7035,
1449,9226,1896,9307,8967,7249,1846,3673,5636,7717,1534,2007,5272,2104,3698,
3569,1335,3121,2814,9800,9803,8473,4164,9631,4381,5548,8653,8846,5703,1315,
8465,1995,8022,6860,4362,4408,3987,4234,9390,564,369,7788,4328,5067,7669,
7257,7246,9085,2783,474,5754,2807,6986,4802,8828,3797,379,4717,5388,4133,
9229,9238,2050,7189,85,5412,290,7078,3920,8344,2209,5964,8360,1409,640,
1005,3239,9355,9793,1389,5849,5334,207,239,7468,2977,5530,7770,9479,1318,
5826,4446,7090,526,8399,1063,7343,5875,798,8700,2468,8318,1284,2744,6984,
2809,9377,4677,9684,8206,1281,503,7800,5654,3128,4181,6694,2450,4186,4851,
1358,4926,1265,1135,4507,9544,7538,9596,4007,1041,2481,4768,5347,4883,1341,
333,2580,8521,3634,1924,2835,1387,9795,4150,1549,9589,1943,5690,3103,7162,
4033,2826,3048,3901,374,5968,2023,2804,3499,4530,4922,9542,4509,3867,6966,
2974,3582,1297,9574,6956,1168,7810,3644,1715,1530,3726,4820,6041,6836,6732,
6186,1102,7236,4145,7096,3472,5372,7582,851,6009,7762,4757,1364,7298,4434,
2325,4313,141,6346,3709,6889,7518,5708,4524,7005,1947,616,6147,402,1082,
7909,5685,351,3742,5958,1400,2213,9343,4516,2993,2048,9240,9887,6094,8068,
6762,7381,4018,4056,9697,6244,6812,3063,3171,6996,4048,7667,5069,3108,5055,
3708,6389,142,8448,8095,3177,3724,1532,7719,6697,7698,1858,2174,6151,6202,
3329,8567,2207,8346,7105,2424,8375,1293,2350,4065,2570,2431,6926,3480,8605,
605,5507,7833,1347,4004,8792,4603,8459,5058,6845,5799,9733,4744,5084,1142,
7260,7423,1416,3851,5463,2228,2524,6867,9223,118,417,1588,7447,8122,285,
9175,1353,4893,6222,6992,5023,1146,916,7613,6720,1866,6211,4459,980,4462,
5312,7198,2086,7881,1379,3452,7978,5683,7911,8777,1491,5927,4873,454,2090,
3486,8187,5700,7778,1984,7014,2303,160,9779,8020,1997,7677,6811,6357,9698,
3285,7139,668,9828,4814,8331,4860,8132,9874,7998,1495,9035,7773,8054,3321,
4266,8888,4296,9349,6991,6284,4894,893,4730,2527,7415,8125,5434,2535,3831,
4458,6276,1867,1660,8531,8065,8170,3887,7796,3328,6333,6152,2397,2276,6893,
2510,4086,1440,4845,3554,3513,3013,5280,7071,8,1101,6407,6733,7501,3864,
6062,5906,1828,407,6723,3560,8370,3489,5082,4746,7445,1590,4575,1812,984,
6796,2741,4121,5797,6847,4311,2327,9549,3527,3944,2187,9092,822,5150,2396,
6201,6334,2175,2499,401,6380,617,8380,8723,8228,7030,998,5452,3124,321,
4890,9070,7385,686,5074,6880,260,1746,7431,1585,4090,8128,2588,8357,9825,
9770,7541,9029,4673,8595,9553,429,9004,2421,2883,6747,337,7002,1658,1869,
5248,7746,1072,3369,9523,2601,5469,9578,5013,1950,747,8168,8067,6364,9888,
9077,4753,782,3883,4796,9644,8471,9805,939,5910,6624,1086,2770,930,5563,
4544,9316,6969,5997,9557,7535,7365,3688,5444,1803,9666,5290,5046,1027,5905,
6182,3865,4511,5770,7742,2841,5920,3133,2759,6677,7128,8484,3602,4439,1475,
4113,2386,9313,2413,8528,6835,6410,4821,2274,2399,3718,3840,5391,3477,2936,
4788,2300,7686,560,7590,4240,8046,7109,1757,8387,1192,2192,7008,9118,3812,
5106,6802,1730,3696,2106,7294,8804,7761,6398,852,6710,7509,4643,4685,7394,
645,6852,3467,9528,9556,6074,6970,910,5859,4497,9169,8683,481,4705,5974,
8578,3184,8786,7209,8640,2822,3382,1558,9540,4924,1360,4475,8577,5988,4706,
4982,9445,7813,2022,6432,375,9823,8359,6516,2210,2961,5727,7145,1399,6373,
3743,7715,5638,3251,479,8685,4760,6741,2593,3211,7735,8434,2250,4659,4125,
5657,4948,3302,8664,762,7151,4305,1061,8401,1824,5296,1444,5044,5292,4872,
6261,1492,127,2863,4388,2981,3132,6056,2842,701,8139,805,5492,3350,5668,
7270,6623,6083,940,243,1827,6181,6063,1028,790,7336,9651,1512,8711,8553,
3588,1110,304,3442,8861,163,7306,6692,4183,4367,6613,5694,2315,2519,3541,
5846,8273,4346,5497,7750,4141,797,6490,7344,4599,7967,882,1739,2738,3464,
7076,292,812,1913,689,6903,8085,4496,5994,911,1966,9152,1735,2904,3549,
2235,4398,5333,6507,1390,8272,5882,3542,205,5336,1205,8728,7224,4970,8936,
7550,3578,7332,1709,1049,8497,8293,1683,2147,2550,4445,6497,1319,4959,522,
5226,1308,1839,114,1809,7610,7390,3705,8462,9482,8315,3774,1774,4469,2927,
8404,868,1767,29,331,1343,1688,9732,6307,6846,6164,4122,9561,2688,8385,
1759,8670,8928,8425,3854,7516,6891,2278,392,4561,8615,7159,3736,4105,341,
5241,3958,4245,6775,9582,8750,7741,6059,4512,3373,673,8007,8108,1211,2754,
8504,2150,4024,9105,7461,2664,3497,2806,6537,475,105,3457,8353,9870,9572,
1299,9148,4991,836,2355,6830,8899,4452,5255,1427,3336,271,183,1131,9281,
6607,1351,9177,6766,7144,5961,2962,2985,64,4723,154,6772,3429,3208,4012,
5535,7450,3432,5051,7317,3309,7512,5221,4523,6385,7519,9403,1017,1314,6559,
8847,7777,6255,8188,2563,252,2623,2314,5886,6614,2764,3102,6440,1944,2195,
1304,350,6376,7910,6265,7979,1640,8822,598,4811,7114,232,3273,1129,185,
693,9688,8174,7269,5913,3351,512,194,1575,535,2310,3874,1856,7700,4947,
5942,4126,3127,6474,7801,3218,4424,2017,8278,4805,8977,6641,3115,2991,4518,
9271,4739,2635,3250,5955,7716,6579,3674,1014,4693,9516,8948,9850,9704,8235,
2671,1561,2378,2727,8149,1703,3005,4688,9353,3241,5489,8443,9603,3268,949,
7828,5329,1749,9059,3215,2036,1012,3676,553,698,4392,2070,1593,2939,8693,
2749,3965,8841,777,5486,6737,3053,3739,7575,3510,9761,927,1420,1938,3029,
9023,7836,9264,9326,4986,7325,7495,8704,2112,3356,4835,9167,4499,7924,5187,
1606,8220,4592,4543,6078,931,819,1462,8941,383,955,1627,4021,4405,1783,
7399,6826,9100,8652,6562,4382,6875,2698,709,1270,5415,1224,3040,3348,5494,
8120,7449,5717,4013,3289,7347,7769,6501,2978,2846,1872,8258,405,1830,147,
4617,269,3338,4354,3027,1940,1567,1447,7037,3978,6921,7057,9202,4299,7832,
6316,606,7178,7665,4050,4569,2473,1982,7780,7749,5879,4347,8119,5538,3349,
5915,806,8442,5617,3242,6736,5593,778,2060,1692,3083,1969,8349,8421,6682,
4250,7885,1765,870,5230,5278,3015,9577,6101,2602,3508,7577,1578,2227,6298,
3852,8427,9250,1509,9384,7350,4074,3405,2812,3123,6140,999,1001,4161,4647,
7169,2198,1802,6069,3689,3626,8922,8920,3628,4590,8222,8657,2534,6215,8126,
4092,6975,9137,2752,1213,8540,3925,1325,6639,8979,9859,484,2267,634,1186,
5306,1223,5542,1271,289,6522,86,5236,5323,2294,976,1815,4041,3908,733,
4331,1978,1652,7572,354,2539,7723,8765,3438,358,3476,6035,3841,4132,6529,
4718,557,3532,6909,4258,631,9855,9682,4679,4192,3517,2897,8245,4781,7581,
6401,3473,4980,4708,83,7191,7530,4634,9039,24,397,8285,1221,5308,4337,
3824,586,7490,6981,1931,2466,8702,7497,1851,4882,6455,4769,2058,780,4755,
7764,9508,4118,1287,8649,1204,5843,206,6506,5850,4399,7429,1748,5611,7829,
8310,3731,8090,2293,5409,5237,8645,7409,7859,229,905,2438,7239,9329,7197,
6272,4463,1680,4336,5359,1222,5417,1187,6610,2556,4028,1935,8782,1108,3590,
1443,5932,1825,245,4871,5929,5045,6066,9667,6630,1633,1328,9753,4379,9633,
6750,7070,6190,3014,5472,5231,8882,8589,9396,2103,6575,2008,2820,8642,2370,
4536,863,425,2116,3200,6945,7637,6590,2391,3896,5217,1426,5739,4453,2733,
5205,6705,9620,7745,6107,1870,2848,5127,5077,7650,3957,5777,342,2368,8644,
5322,5410,87,5064,736,8881,5277,5473,871,3782,1307,5822,523,3421,218,
4522,5710,7513,590,1425,5257,3897,2508,6895,4281,549,19,496,8886,4268,
386,6704,5252,2734,9254,3051,6739,4762,7869,40,9419,3912,3928,4920,4532,
9819,2079,2005,1536,1605,5568,7925,9521,3371,4514,9345,8011,9750,9836,4178,
9748,8013,8181,9015,9723,9007,3682,7375,3036,2094,4779,8247,2331,9159,629,
4260,7267,8176,2683,167,3596,4818,3728,2457,1149,2162,2395,6154,823,3810,
9120,4558,2138,3505,8538,1215,3950,3161,4701,2033,7804,9047,3193,7419,3445,
4555,7844,6950,6878,5076,5245,2849,2610,9045,7806,4734,1655,4527,2321,9369,
3003,1705,8306,6964,3869,7602,2375,8256,1874,7135,6801,6017,3813,258,6882,
2222,3092,2914,3367,1074,1622,4253,925,9763,2675,4933,9302,4223,2788,72,
3663,1571,1141,6304,4745,6174,3490,3861,7628,7649,5244,5128,6879,6133,687,
1915,8915,3107,6350,7668,6544,4329,735,5234,88,9457,448,9042,6844,6309,
8460,3707,6348,3109,1787,7316,5714,3433,8544,3148,1026,6065,5291,5930,1445,
1569,3665,1770,1790,2942,1488,1158,8202,415,120,1883,9655,4608,3973,3641,
9448,9442,7243,1145,6282,6993,2879,8049,4553,3447,8561,7558,614,1949,6099,
9579,3764,832,8547,3616,3680,9009,1090,7125,1603,1538,6666,200,2858,8025,
2768,1088,9011,569,3145,835,5745,9149,3086,264,7324,5578,9327,7241,9444,
5972,4707,5370,3474,360,3923,8542,3435,8637,440,1842,8935,5839,7225,4809,
600,8304,1707,7334,792,8179,8015,521,5824,1320,7616,1800,2200,4243,3960,
6600,9899,2,3301,5941,5658,7701,8101,2285,8581,4077,9380,1886,1722,9109,
2567,8194,1597,9301,5092,2676,4062,966,8059,9461,1264,6466,1359,5978,9541,
6427,4531,5194,3929,457,2660,574,4323,2577,9637,6815,752,4156,9066,6756,
9332,890,8813,7133,1876,7043,9701,3235,8363,8298,2776,8811,892,6221,6285,
1354,9069,6137,322,3802,7952,9287,2343,1340,6454,5348,1852,7022,2908,3619,
8756,2658,459,453,6260,5928,5293,246,8018,9781,9486,1699,8743,8413,6959,
8111,8131,6236,8332,8456,3971,4610,3836,8875,6753,1357,6468,4187,2585,8114,
6792,3553,6194,1441,3592,3057,859,9453,444,9813,4667,9166,5572,3357,2233,
3551,6794,986,7986,9214,3768,3022,4773,4657,2252,2273,6040,6411,3727,5156,
3597,8760,8330,6238,9829,7113,5678,599,4968,7226,138,8976,5648,8279,8827,
6534,6987,6809,7679,3019,9643,6088,3884,3100,2766,8027,1645,7526,2299,6032,
2937,1595,8196,6898,532,7580,5374,8246,5167,2095,856,7291,7052,4656,4825,
3023,2951,2057,5346,6456,2482,6708,854,2097,7868,5200,6740,5951,8686,1363,
6396,7763,5343,781,6091,9078,3747,7506,7739,8752,7444,6173,5083,6305,9734,
7218,1725,2634,5641,9272,742,7570,1654,5122,7807,6865,2526,6219,894,178,
886,1720,1888,153,5723,65,151,1890,556,5387,6530,380,1976,4333,8296,
8365,7896,7822,82,5369,4981,5973,5989,482,9861,2032,5139,3162,6850,647,
7167,4649,3197,9515,5633,1015,9405,9882,9352,5620,3006,7393,6004,4644,8476,
9311,2388,4191,5379,9683,6480,9378,4079,8594,6119,9030,4428,4624,1020,9165,
4837,9814,4491,4579,1257,7533,9559,4124,5944,2251,4824,4774,7053,8031,3794,
2156,281,3196,4696,7168,5448,4162,8475,4684,6005,7510,3311,2264,2956,6701,
7785,9476,9038,5365,7531,1259,7081,7893,3326,7798,505,1312,1019,4670,4429,
6887,3711,2831,3151,268,5522,148,8573,8268,3271,234,3835,4856,3972,5030,
9656,8076,3969,8458,6311,8793,1119,7966,5873,7345,3291,8714,4484,8679,4542,
5565,8221,5438,3629,2704,572,2662,7463,8996,9672,2042,2492,1256,4664,4492,
7608,1811,6170,1591,2072,4290,8153,2472,5502,4051,3395,9695,4058,8697,1252,
8614,5783,393,2137,5146,9121,7843,5132,3446,5019,8050,2404,1199,7435,7970,
2920,2411,9315,6077,5564,4593,8680,1616,9504,9877,862,5267,2371,2710,9818,
5193,4921,6428,3500,2320,5120,1656,7004,6384,5709,5222,219,46,9270,5643,
2992,6369,9344,5183,3372,5769,6060,3866,6425,9543,6463,1136,2178,7362,9547,
2329,8249,7923,5570,9168,5993,5860,8086,8925,7607,4578,4665,9815,3379,9612,
8630,4359,8678,4595,8715,9267,7634,9417,42,922,3262,8576,5976,1361,8688,
7149,764,2926,5809,1775,3686,7367,1244,1679,5311,6273,981,979,6275,6212,
3832,8099,7703,2732,5254,5740,8900,8902,3761,6778,7089,6496,5827,2551,517,
8392,651,1474,6049,3603,7674,8323,2324,6393,7299,3800,324,6886,4623,4671,
9031,8136,2016,5651,3219,1480,1552,7932,6818,8209,7841,9123,4308,3165,6659,
4284,1459,9095,3986,6552,4363,1782,5554,4022,2152,2121,7919,7428,5332,5851,
2236,2723,9295,3585,2069,5602,699,2844,2980,5923,2864,8454,8334,7961,6874,
5547,6563,9632,5284,9754,8071,9496,1643,8029,7055,6923,3400,2132,2554,6612,
5888,4184,2452,1781,4407,6553,6861,8677,4486,8631,9192,7203,3026,5519,3339,
1249,801,3075,2502,8118,5496,5880,8274,8946,9518,960,8439,9082,8970,3823,
5358,5309,1681,8295,4714,1977,5402,734,5066,6545,7789,1197,2406,2576,4915,
575,637,2065,878,6872,7963,8481,8974,140,6391,2326,6162,6848,3164,4415,
9124,1060,5936,7152,1208,6962,8308,7831,5509,9203,9348,6225,8889,7865,6686,
842,8152,4572,2073,8952,6633,298,1458,4412,6660,548,5213,6896,8198,1752,
7174,7523,8340,7230,1666,197,51,953,385,5208,8887,6227,3322,2185,3946,
6651,7266,5162,630,5383,6910,6786,3260,924,5096,1623,7884,5477,6683,2100,
3427,6774,5775,3959,4954,2201,8045,6027,7591,9366,8326,9707,9389,6550,3988,
2632,1727,213,9208,9716,8772,6628,9669,2787,5090,9303,1079,8261,1922,3636,
1991,3525,9551,8597,7706,7957,3461,6799,7137,3287,4015,7587,7278,9649,7338,
1713,3646,2124,1054,3342,8587,8884,498,2382,3516,5378,4680,2389,6592,2584,
4850,6469,2451,4366,5889,6693,6472,3129,9747,5178,9837,6916,6939,3940,2757,
3135,724,8550,3294,620,8770,9718,9630,6565,8474,4646,5449,1002,3071,7546,
9065,4910,753,8602,329,31,1548,6444,9796,9426,3364,7095,6404,7237,2440,
796,5877,7751,1397,7147,8690,1793,1894,9228,6528,5389,3842,2160,1151,319,
3126,5656,5943,4660,9560,5796,6165,2742,1286,5340,9509,7623,3010,2385,6047,
1476,973,1231,8142,1516,7213,340,5779,3737,3055,3594,169,8213,8558,9570,
9872,8134,9033,1497,6974,5432,8127,6127,1586,419,1439,6196,2511,2291,8092,
9787,8062,8593,4675,9379,4942,8582,3404,5456,7351,7754,8218,1608,1404,8852,
8192,2569,6323,2351,965,4931,2677,1173,8696,4565,9696,6359,4019,1629,8511,
3394,4568,5503,7666,6352,6997,8166,749,7935,8990,3907,5405,1816,2998,9212,
7988,9089,9609,2825,6437,7163,8162,9019,1934,5302,2557,3411,9104,5760,2151,
4404,5555,1628,4055,6360,7382,7586,4207,3288,5534,5718,3209,2595,9738,1040,
6459,9597,8791,6313,1348,1190,8389,250,2565,9111,8873,3838,3720,8074,9658,
8961,3818,3278,2631,4233,6551,4409,9096,1762,9200,7059,3845,6769,6920,5513,
7038,9774,8409,3640,5029,4609,4857,8457,4605,8077,1500,8840,5596,2750,9139,
1237,6599,4953,4244,5776,5242,7651,1467,2166,6690,7308,3160,5141,1216,9422,
6650,4263,2186,6158,3528,8502,2756,4174,6940,7691,3385,1542,78,9526,3469,
7879,2088,456,4919,5195,3913,1324,5426,8541,4977,361,8343,6519,7079,1261,
2692,1115,6717,1323,3927,5196,9420,1218,732,5404,4042,8991,2931,3827,345,
373,6434,3049,9256,2507,5216,5258,2392,3191,9049,3503,2140,1097,2607,7795,
6205,8171,3099,4795,6089,783,2893,7709,8709,1514,8144,2792,1855,5661,2311,
9341,2215,7601,5113,6965,6424,4510,6061,6183,7502,7627,5080,3491,3066,1373,
7488,588,7515,5788,8426,5462,6299,1417,2773,3224,7142,6768,3981,7060,2159,
4131,5390,6036,3719,3996,8874,4855,4611,235,8098,4457,6213,2536,2366,344,
3904,2932,585,5357,4338,8971,7131,8815,3277,3991,8962,96,1430,257,5105,
6018,9119,5148,824,13,3537,1834,1733,9154,7951,4888,323,4432,7300,378,
6532,8829,2155,4653,8032,8243,2899,9564,3154,7018,7480,897,9472,348,1306,
5228,872,2360,131,76,1544,7313,1773,5811,8316,2470,8155,9641,3021,4827,
9215,2516,831,5011,9580,6777,4449,8903,2871,1673,1178,1521,9284,3521,9500,
7402,7726,3567,3700,7505,4751,9079,809,7714,5957,6374,352,7574,5590,3054,
4104,5780,7160,3105,8917,8089,5326,8311,2456,5155,4819,6412,1531,6341,3178,
9494,8073,3995,3839,6037,2400,3168,3494,8800,9893,2830,4621,6888,6388,6347,
5056,8461,5815,7391,3008,7625,7504,3749,3568,6573,2105,6014,1731,1836,1370,
8241,8034,3625,5443,6070,7366,4467,1776,2486,7374,5171,9008,5007,3617,2910,
552,5605,1013,5635,6580,1847,2128,866,8406,1903,27,1769,5041,1570,5087,
73,9233,2762,6616,203,3544,3090,2224,7904,1881,122,9741,7598,2887,7917,
2123,4201,1714,6415,7811,9447,5028,3974,8410,1124,1990,4218,1923,6449,8522,
2020,7815,2703,4589,5439,8921,5442,3690,8035,3181,2288,8985,8755,4878,2909,
3679,5008,8548,726,9616,1779,2454,8313,9484,9783,678,3034,7377,7673,4438,
6050,8485,2478,2641,8759,4817,5157,168,4102,3056,4843,1442,5298,1109,5897,
8554,2068,4394,9296,1296,6421,2975,7470,7331,5836,7551,8608,1526,7477,2796,
1555,7694,1334,6572,3699,3750,7727,8043,2203,3204,2182,8369,6177,6724,1806,
1453,9759,3512,6193,4846,6793,4832,2234,5853,2905,6730,6838,3089,3657,204,
5845,5883,2520,3139,1833,3807,14,661,7853,6908,5385,558,7688,8501,3943,
6159,9550,4216,1992,8819,9499,3754,9285,7954,2896,5377,4193,2383,3012,6192,
3555,9760,5588,7576,5467,2603,8537,5144,2139,3892,9050,2319,4529,6429,2805,
5756,2665,8799,3715,3169,3065,3860,5081,6175,8371,8186,6257,2091,8733,2945,
327,8604,6319,6927,2935,6034,5392,359,4979,5371,6402,7097,7878,3933,9527,
6000,6853,7075,5868,2739,6798,4211,7958,312,8352,5751,106,8514,7066,7977,
6267,1380,7321,9568,8560,5018,4554,5133,7420,8860,5894,305,2363,357,5394,
8766,8636,4975,8543,5050,5715,7451,3207,5720,6773,4247,2101,9398,8620,1695,
217,5224,524,7092,2917,7157,8617,1583,7433,1201,9103,4026,2558,8838,1502,
9375,2811,5455,4075,8583,422,2131,4371,6924,2433,9662,9694,4567,4052,8512,
108,546,6662,8896,9261,8492,1541,3937,7692,1557,5981,2823,9611,4489,9816,
2712,7851,663,672,5768,4513,5184,9522,6104,1073,5099,2915,7094,4147,9427,
7118,816,2655,2644,2232,4834,5573,2113,9532,9337,511,5667,5914,5493,5539,
3041,1879,7906,1436,8586,4198,1055,1248,4353,5520,270,5737,1428,98,101,
7087,6780,8566,6332,6203,7797,4629,7894,8367,2184,4265,6228,8055,2652,934,
594,8005,675,8452,2866,2263,4641,7511,5712,7318,1485,8736,707,2700,8663,
5940,4949,3,2476,8487,6931,8378,619,4169,8551,8713,4597,7346,5533,4014,
4208,7138,6242,9699,7045,9361,1195,7791,2630,3990,3819,8816,8468,1128,5675,
233,4613,8269,948,5614,9604,7594,9434,8266,8575,4477,923,4255,6787,2027,
2818,2010,8809,2778,767,478,5954,5639,2636,8892,1052,2126,1849,7499,6735,
5488,5618,9354,6511,1006,1407,8362,4900,9702,9852,2270,9187,9291,2082,9536,
9766,666,7141,3848,2774,8300,9277,1479,4423,5652,7802,2035,5608,9060,9183,
7734,5948,2594,4011,5719,3430,7452,2181,3563,2204,8290,6944,5263,2117,9514,
4695,4650,282,7418,5135,9048,3894,2393,2164,1469,7484,2800,8785,5986,8579,
2287,3623,8036,9493,3723,6342,8096,237,209,2877,6995,6354,3064,3493,3716,
2401,6658,4414,4309,6849,4700,5140,3951,7309,1113,2694,7683,7017,3789,9565,
267,4619,2832,1025,5048,8545,834,4993,570,2706,2543,145,1832,3539,2521,
1960,723,4172,2758,6055,5921,2982,9746,4180,6473,5655,4127,320,6139,5453,
2813,6570,1336,9628,9720,9847,2990,5645,6642,7875,8797,2667,1786,5054,6349,
5070,8916,3734,7161,6439,5691,2765,4794,3885,8172,9690,7026,659,16,2913,
5101,2223,3656,3545,6839,263,4989,9150,1968,5482,1693,8622,9197,7888,8283,
399,2501,4350,802,1234,7545,4159,1003,642,8239,1372,3859,3492,3170,6355,
6813,9639,8157,7289,858,4842,3593,4103,3738,5591,6738,5202,9255,3900,6435,
2827,8253,1564,9592,7041,1878,3347,5540,1225,8731,2093,5169,7376,3606,679,
2054,2463,9022,5583,1939,5518,4355,7204,2950,4772,4826,3769,9642,4798,7680,
6954,9576,5471,5279,6191,3514,2384,4115,7624,3703,7392,4687,5621,1704,5117,
9370,1290,6934,9211,4039,1817,8437,962,2047,6368,4517,5644,3116,9848,8950,
2075,63,5725,2963,9745,3131,5922,4389,2845,5529,6502,7469,3581,6422,6967,
9318,1413,6604,1524,8610,6901,691,187,9744,2984,5726,5962,2211,1402,1610,
6700,4639,2265,486,2461,2056,4771,3024,7205,2220,6884,326,3483,8734,1487,
5038,1791,8692,5599,1594,4787,6033,3478,6928,584,3826,3905,8992,1822,8403,
5808,4470,765,2780,1863,410,2410,4547,7971,7156,3418,7093,3366,5100,3093,
17,551,3678,3618,4879,7023,6729,3548,5854,1736,58,2686,9563,3791,8244,
5376,3518,7955,7708,3881,784,7329,7472,682,7916,3649,7599,2217,6746,6113,
2422,7107,8048,5021,6994,3173,210,6805,9243,8395,1672,3759,8904,2854,542,
2262,3313,8453,4387,5924,128,308,6858,8024,4999,201,6618,541,2869,8905,
2628,7793,2609,5126,5246,1871,5528,2979,4390,700,5919,6057,7743,9622,464,
2258,1386,6447,1925,1024,3150,4620,3712,9894,8252,3047,6436,4034,9610,3381,
5982,8641,5270,2009,3257,2028,9131,9799,6569,3122,5454,3406,9376,6482,6985,
6536,5755,3498,6430,2024,1106,8784,3186,7485,7930,1554,3573,7478,7020,1854,
3876,8145,8627,71,5089,4224,9670,8998,473,6539,9086,1862,2924,766,3254,
8810,4897,8299,3223,3849,1418,929,6080,1087,4997,8026,4793,3101,5692,6615,
3660,9234,6676,6054,3134,4173,3941,8503,5763,1212,5429,9138,3964,5597,8694,
1175,1929,6983,6484,1285,4120,6166,6797,3463,5869,1740,655,9253,5204,5253,
4454,7704,8599,8867,8148,5624,2379,2002,9294,4396,2237,7252,7939,9180,7413,
2529,8184,8373,2426,7850,3377,9817,4534,2372,2446,2542,3143,571,4588,3630,
7816,8662,3304,708,5545,6876,6952,7682,3157,1114,3917,1262,9463,8384,5794,
9562,2901,59,166,5159,8177,794,2442,8674,1172,4061,4932,5093,9764,9538,
1560,5627,8236,7397,1785,3111,8798,3496,5757,7462,4586,573,4917,458,4876,
8757,2643,3360,817,933,3319,8056,7663,7180,1963,490,1957,2231,3359,2656,
8758,3599,2479,1043,7863,8891,3249,5640,4740,1726,4232,3989,3279,7792,2852,
8906,509,9339,2313,5696,253,7914,684,7387,919,227,7861,1045,7564,1743,
6842,9044,5125,2850,7794,3889,1098,992,8536,3507,5468,6102,9524,80,7824,
9840,9737,4010,3210,5949,6742,8789,9599,8356,6125,8129,8113,4849,4188,6593,
8417,8520,6451,334,9636,4914,4324,2407,7620,9116,7010,2430,6322,4066,8193,
4937,9110,3999,251,5698,8189,9468,9054,8837,3410,4027,5303,6611,4369,2133,
516,4444,5828,2148,8506,9625,9866,8446,144,3142,2707,2447,7722,5397,355,
2365,3830,6214,5435,8658,567,9013,8183,2717,7414,6218,4731,6866,6296,2229,
1959,3138,3540,5884,2316,830,3766,9216,7282,8983,2290,4085,6197,6894,5215,
3898,9257,1664,7232,8117,4349,3076,400,6149,2176,1138,1670,8397,528,1255,
4581,2043,839,720,7183,7373,3684,1777,9618,6707,4767,6457,1042,2640,3600,
8486,3299,4,1981,5501,4570,8154,3772,8317,6487,8701,5352,1932,9021,3031,
2055,2953,487,914,1148,5154,3729,8312,3611,1780,4365,4185,6470,6695,7721,
2541,2708,2373,7604,8673,2680,795,4143,7238,5316,906,1955,492,9661,3398,
6925,6321,2571,7011,9220,7849,2714,8374,6327,7106,2882,6114,9005,9725,8431,
6714,7102,1972,8527,6044,9314,4546,2921,411,7619,2575,4325,1198,4551,8051,
6657,3167,3717,6038,2275,6200,6153,5151,2163,3190,3895,5259,6591,4190,4681,
9312,6046,4114,3011,3515,4194,499,2001,2726,5625,1562,8255,5111,7603,2445,
2709,4535,5268,8643,5239,343,3829,2537,356,3440,306,130,3780,873,760,
8666,6829,5743,837,2045,964,4064,6324,1294,9298,9129,2030,9863,1339,4885,
9288,8721,8382,9465,8855,7287,8159,9248,8429,9727,9158,5165,8248,4502,9548,
6161,4312,6392,4435,8324,9368,5119,4528,3501,9051,829,2518,5885,5695,2624,
9340,3873,5662,536,296,6635,468,9712,159,6251,7015,7685,6031,4789,7527,
7457,1229,975,5408,5324,8091,4084,2512,8984,3622,3182,8580,4944,8102,9489,
7493,7327,786,391,5785,6892,6199,2398,6039,4822,2253,9186,3232,9853,633,
5420,485,2955,4640,3312,2867,543,92,1385,2837,465,1637,7732,9185,2272,
4823,4658,5945,8435,1819,7949,9156,9729,9323,8718,9190,8633,8933,1844,7251,
2722,4397,5852,3550,4833,3358,2645,1958,2523,6297,5464,1579,7903,3655,3091,
5102,6883,2948,7206,6745,2885,7600,3871,9342,6371,1401,2960,5963,6517,8345,
6330,8568,8289,3203,3564,8044,4242,4955,1801,5446,7170,1303,5688,1945,7007,
6021,1193,9363,9607,9091,6157,3945,4264,3323,8368,3562,3205,7453,7361,4505,
1137,2498,6150,6335,1859,7991,1920,8263,7646,717,6689,3954,1468,3189,2394,
5152,1150,4130,3843,7061,280,4652,3795,8830,2120,4403,4023,5761,8505,2549,
5829,1684,9144,8003,596,8824,1096,3891,3504,5145,4559,394,1906,515,2553,
4370,3401,423,865,3671,1848,3246,1053,4200,3647,7918,4402,2153,8831,9513,
3199,5264,426,9531,3355,5574,8705,6621,7272,7050,7293,6013,3697,6574,5273,
9397,3426,4248,6684,7867,4764,855,4778,5168,3037,8732,3485,6258,455,3931,
7880,6270,7199,1240,9535,3229,9292,2004,5191,9820,7303,62,2987,8951,4289,
4573,1592,5601,4393,3586,8555,877,4320,638,1411,9320,1691,5484,779,5345,
4770,2952,2462,3032,680,7474,7188,6525,9239,6367,2994,963,2353,838,2491,
4582,9673,7285,8857,7263,1011,5607,3216,7803,5138,4702,9862,2346,9130,2817,
3258,6788,1105,2803,6431,5969,7814,3632,8523,8277,5650,4425,8137,703,6822,
1619,8808,3256,2819,5271,6576,1535,5190,2080,9293,2725,2380,500,8321,7676,
6247,8021,6556,8466,8818,3524,4217,3637,1125,9647,7280,9218,7013,6253,7779,
5500,2474,5,1651,5401,4332,4715,381,8943,8526,2415,7103,8348,5481,3084,
9151,5857,912,489,2648,7181,722,3137,2522,2230,2646,491,2436,907,8081,
7654,746,6098,5014,615,6382,7006,2194,5689,6441,9590,1566,5517,3028,5584,
1421,8781,5301,4029,9020,2465,5353,6982,2746,1176,1675,1023,2834,6448,3635,
4219,8262,2171,7992,9710,470,8914,5072,688,5864,813,8041,7729,7982,192,
514,2135,395,26,3668,8407,9776,8864,756,7757,9306,6585,9227,4135,1794,
696,555,4720,152,4725,1721,4940,9381,9654,5032,121,3653,7905,3346,3042,
7042,4903,7134,5109,8257,5527,2847,5247,6108,1659,6210,6277,6721,409,2923,
2781,9087,7990,2173,6336,7699,5660,3875,2793,7021,4881,5349,7498,3245,2127,
3672,6581,7250,2239,8934,4972,441,113,5820,1309,1369,3694,1732,3806,3538,
3140,146,5524,406,6180,5907,244,5295,5933,8402,2929,8993,7948,2248,8436,
2997,4040,5406,977,983,6169,4576,7609,5818,115,1452,3558,6725,9665,6068,
5445,2199,4956,7617,413,8204,9686,695,1893,4136,8691,2941,5039,1771,7315,
5053,3110,2668,7398,5553,4406,4364,2453,3612,9617,2485,3685,4468,5810,3775,
7314,1789,5040,3666,28,5805,869,5475,7886,9199,3984,9097,8669,5792,8386,
6024,7110,1275,1033,7173,4278,8199,9058,5610,5330,7430,6130,261,6841,2613,
7565,654,2737,5870,883,57,2903,5855,9153,3805,1835,3695,6015,6803,212,
4231,2633,4741,7219,9108,4939,1887,4726,887,7371,7185,1529,6414,3645,4202,
7339,434,1048,5834,7333,4965,8305,5116,3004,5622,8150,844,8742,4866,9487,
8104,216,3423,8621,3082,5483,2061,9321,9731,5801,1344,9026,9143,2146,5830,
8294,4335,5310,4464,1245,9163,1022,1927,1177,3758,2872,8396,2496,1139,1573,
196,4273,7231,2505,9258,6833,8530,6209,1868,6109,7003,4526,5121,4735,7571,
5400,1979,6,7073,6855,8338,7525,4791,8028,4375,9497,8821,5681,7980,7731,
2256,466,6637,1327,5287,6631,8954,8510,4054,4020,5556,956,1377,7883,4252,
5097,1075,8807,2012,6823,9503,4540,8681,9171,1332,7696,6699,2958,1403,4070,
8219,5567,5188,1537,5003,7126,6679,625,9127,9300,4935,8195,4786,2938,5600,
2071,4574,6171,7446,6291,418,4089,6128,7432,3415,8618,9400,7902,2226,5465,
7578,534,5664,195,1668,1140,5086,3664,5042,1446,5516,1941,9591,3045,8254,
2377,5626,2672,9539,5980,3383,7693,3572,2797,7931,4421,1481,9588,6443,4151,
32,301,7312,3777,77,3936,3386,8493,6665,5002,1604,5189,2006,6577,7718,
6340,3725,6413,1716,7186,7476,3575,8609,2969,6605,9283,3756,1179,7561,437,
7212,4108,8143,3878,8710,5900,9652,9383,5459,9251,657,7028,8230,7406,9374,
3408,8839,3967,8078,6973,4094,9034,6232,7999,126,5926,6262,8778,1157,5037,
2943,8735,3307,7319,1382,9587,1551,4422,3220,9278,972,4112,6048,4440,652,
7567,175,7483,3188,2165,3955,7652,8083,6905,8940,5560,820,9094,4411,4285,
299,34,7356,9758,3557,1807,116,9225,6587,7036,5515,1568,5043,5931,5297,
3591,4844,6195,4087,420,8585,3344,7907,1084,6626,8774,256,3815,97,3335,
5738,5256,5218,591,1155,8780,1937,5585,928,2772,3850,6300,7424,6603,2971,
9319,2063,639,6514,8361,3237,1007,8851,4069,1609,2959,2212,6372,5959,7146,
4139,7752,7353,277,9439,946,8271,5848,6508,9794,6446,2836,2259,93,9586,
1483,7320,3451,6268,7882,1625,957,7928,7487,3858,3067,8240,3693,1837,1310,
507,8908,7297,6395,4758,8687,4474,5977,4925,6467,4852,6754,9068,4892,6286,
9176,5731,6608,1189,4003,6314,7834,9025,1687,5802,332,6453,4884,2344,9864,
9627,3120,6571,3570,7695,1613,9172,9834,9752,5286,1634,6638,5425,3926,3914,
6718,7615,4958,5825,6498,9480,8464,6558,5704,1018,4626,506,1368,1838,5821,
5227,3783,349,5687,2196,7171,1035,9147,5747,9573,6420,3583,9297,2349,6325,
8376,6933,3001,9371,8648,5339,4119,2743,6485,8319,502,6477,8207,6820,705,
8738,1032,1755,7111,9831,288,5414,5543,710,7660,969,1134,6465,4927,9462,
2691,3918,7080,4632,7532,4663,4580,2493,529,8613,4563,8698,800,4352,3340,
1056,9162,1678,4465,7368,9335,9534,2084,7200,6598,3962,9140,7544,3073,803,
8141,4110,974,2296,7458,7222,8730,3039,5541,5416,5307,5360,8286,731,3910,
9421,3949,5142,8539,5428,2753,5764,8109,6961,4303,7153,8727,5842,5337,8650,
9102,3413,7434,4550,2405,4326,7790,3281,9362,2191,6022,8388,4002,1349,6609,
5305,5418,635,577,7658,712,612,7560,1520,3757,1674,1928,2747,8695,4060,
2678,8675,6863,7809,6417,6957,8415,6595,9195,8624,8870,8835,9056,8201,5036,
1489,8779,1423,592,936,318,4129,2161,5153,2458,915,6281,5024,7244,7259,
6303,5085,1572,1669,2497,2177,4506,6464,1266,970,9280,5734,184,5674,3274,
8469,9646,1989,3638,8411,8745,8479,7965,4601,8794,7100,6716,3916,2693,3158,
7310,303,5896,3589,5299,8783,2802,2025,6789,7235,6406,6187,9,991,2606,
3890,2141,8825,8281,7890,6646,7124,5005,9010,4996,2769,6081,6625,1434,7908,
6378,403,8260,4221,9304,7759,8806,1621,5098,3368,6105,7747,7782,389,788,
1030,8740,846,7342,6492,8400,5935,4306,9125,627,9161,1247,3341,4199,2125,
3247,8893,8496,5833,1710,435,7563,2615,7862,2639,2480,6458,4008,9739,124,
8001,9146,1301,7172,1754,1276,8739,1067,789,5904,6064,5047,3149,2833,1926,
1676,9164,4669,4625,1313,5705,9404,4692,5634,3675,5606,2037,7264,6653,8850,
1406,3238,6512,641,3070,4160,5450,1000,5451,6141,7031,7048,7274,9393,8535,
2605,1099,10,901,9430,7985,4830,6795,6168,1813,978,4461,6274,4460,982,
1814,5407,2295,1230,4111,1477,9279,1133,1267,7661,8058,4930,4063,2352,2046,
2995,8438,4342,9519,7927,1376,1626,5557,384,4270,52,6913,7827,5613,3269,
8270,1392,9440,9450,9880,9407,242,5909,6084,9806,317,1153,593,3318,2653,
818,5562,6079,2771,1419,5586,9762,5095,4254,3261,4478,43,226,2618,7388,
7612,6280,1147,2459,488,1965,5858,5995,6971,8080,1954,2437,5317,230,7116,
9429,989,11,826,9471,3786,7481,177,4729,6220,4895,8812,4906,9333,7370,
1719,4727,179,56,1738,5871,7968,7437,6871,4319,2066,8556,8215,759,2359,
3781,5229,5474,1766,5806,8405,3670,2129,424,5266,4537,9878,9452,4841,3058,
7290,4777,2096,4765,6709,6008,6399,7583,9073,432,7341,1065,8741,1701,8151,
4292,6687,719,2490,2044,2354,5744,4992,3146,8546,5010,3765,2517,2317,9052,
9470,899,12,3809,5149,6155,9093,1461,5561,932,2654,3361,7119,8040,1912,
5865,293,7713,3745,9080,8441,5491,5916,8140,1233,3074,4351,1250,8699,6489,
5876,4142,2441,2681,8178,4963,7335,5903,1029,1068,390,2280,7328,2892,3882,
6090,4754,5344,2059,5485,5594,8842,9275,8302,602,7554,7872,7085,103,477,
3253,2779,2925,4471,7150,5938,8665,2358,874,8216,7756,1899,8865,8601,4155,
4911,6816,7934,4045,8167,6097,1951,7655,173,7569,4737,9273,8844,8655,8224,
8880,5233,5065,4330,5403,3909,1219,8287,8570,68,9615,3614,8549,4171,3136,
1961,7182,2489,840,6688,2168,7647,7630,6670,611,1182,7659,1269,5544,2699,
3305,8737,1278,6821,2014,8138,5918,2843,4391,5603,554,1892,1795,9687,5672,
186,2966,6902,5863,1914,5073,6134,7386,2620,7915,2889,7473,2053,3033,3607,
9784,8451,3315,8006,5767,3374,664,9768,9827,6240,7140,3226,9767,671,3375,
7852,3535,15,3095,7027,1507,9252,2736,1741,7566,1473,4441,8393,9245,7166,
4698,6851,6002,7395,8238,3069,1004,6513,1410,2064,4321,576,1185,5419,2268,
9854,5382,4259,5163,9160,1058,9126,1600,6680,8423,8930,8769,4168,3295,8379,
6146,6381,1948,5015,7559,1181,713,6671,7820,7898,7177,5506,6317,8606,7553,
773,8303,4967,4810,5679,8823,2143,8004,3317,935,1154,1424,5219,7514,3856,
7489,5356,3825,2933,6929,8489,7839,8211,171,7657,1184,636,4322,4916,2661,
4587,2705,3144,4994,9012,2532,8659,368,6548,9391,7276,7589,6029,7687,3531,
5386,4719,1891,697,5604,3677,2911,18,5212,4282,6661,3391,109,91,2261,
2868,2855,6619,8707,7711,295,2309,5663,1576,7579,4783,6899,8612,1254,2494,
8398,6494,7091,3420,5225,5823,4960,8016,248,8391,4443,2552,2134,1907,193,
5666,3352,9338,2626,8907,1367,1311,4627,7799,6476,1282,8320,2000,2381,4195,
8885,5210,20,8959,9660,2435,1956,2647,1964,913,2460,2954,2266,5421,9860,
4704,5990,8684,5953,3252,768,104,5753,6538,2784,8999,8913,1917,9711,2306,
6636,1636,2257,2838,9623,8508,8956,452,4875,2659,4918,3930,2089,6259,4874,
460,8957,22,9041,5061,9458,9790,9812,4839,9454,112,1841,4973,8638,7211,
1518,7562,1047,1711,7340,848,9074,9003,6116,9554,9530,2115,5265,864,2130,
3402,8584,1438,4088,1587,6292,119,5034,8203,1798,7618,2409,2922,1864,6722,
6179,1829,5525,8259,1081,6379,6148,2500,3077,8284,5362,25,1905,2136,4560,
5784,2279,787,1069,7783,6703,5207,4269,954,5558,8942,1975,4716,6531,3798,
7301,9822,5967,6433,3902,346,9474,7787,6547,565,8660,7818,6673,136,7228,
8342,3922,4978,3475,5393,3439,2364,2538,5398,7573,3741,6375,5686,1305,3784,
9473,372,3903,3828,2367,5240,5778,4106,7214,7001,6111,6748,9635,2579,6452,
1342,5803,30,4153,8603,3482,2946,6885,4431,3801,4889,6138,3125,4128,1152,
937,9807,8518,8419,8351,3459,7959,8336,6857,2861,129,2362,3441,5895,1111,
7311,1546,33,1457,4286,6634,2308,537,7712,811,5866,7077,6521,5413,1272,
9832,9174,6288,8123,7417,3195,4651,2157,7062,9438,1394,7354,36,8564,6782,
182,5736,3337,5521,4618,3152,9566,7323,4988,3087,6840,1745,6131,6881,5104,
3814,1431,8775,7913,2622,5697,2564,4000,8390,519,8017,4870,5294,1826,5908,
941,9408,7467,6504,208,3175,8097,3834,4612,3272,5676,7115,904,5318,7860,
2617,920,44,221,9679,9678,224,45,4521,5223,3422,1696,8105,9207,4230,
1728,6804,2876,3174,238,6505,5335,5844,3543,3658,6617,2857,5000,6667,50,
4272,1667,1574,5665,513,1908,7983,9432,7596,9743,2965,692,5673,1130,5735,
272,6783,55,885,4728,895,7482,1471,7568,744,7656,579,8212,4101,3595,
5158,2684,60,7305,5892,8862,9778,6250,2304,9713,6937,6918,6771,5722,4724,
1889,4721,66,8572,4616,5523,1831,3141,2544,8447,6345,6390,4314,8975,4807,
7227,364,6674,9236,9231,75,3779,2361,307,2862,5925,1493,8000,1038,9740,
3652,1882,5033,416,6293,9224,1451,1808,5819,1840,442,9455,90,545,3392,
8513,3456,5752,476,769,7086,3333,99,100,3334,1429,3816,8963,9585,1384,
2260,544,110,9456,5063,5235,5411,6523,7190,5368,4709,7823,2599,9525,3935,
1543,3778,132,9232,3662,5088,2789,8628,9614,728,8571,150,4722,5724,2986,
2076,7304,165,2685,2902,1737,884,180,6784,6912,952,4271,198,6668,7632,
9269,4520,220,225,921,4479,9418,5198,7870,7556,8563,275,7355,1456,300,
1547,4152,330,5804,1768,3667,1904,396,5363,9040,450,8958,495,5211,550,
2912,3094,660,3536,3808,825,900,990,1100,6188,7072,1650,1980,2475,3300,
4950,9900};
int a[maxn];
int x,n,y,k,l,b,sol;
int c[maxx],p[maxx];

int power(int t)
{
    if (t==1) return b;
    else if (t%2==0)
         {
			 int aux=power(t/2);
             return (aux*aux)%mod;
         }
         else {
				  int aux=power(t-1);
                  return (aux*b)%mod;
              }
}

int main()
{
	freopen("sumdiv.in","r",stdin);
    freopen("sumdiv.out","w",stdout);
    
	int i,j,aux;
	scanf("%d %d",&n,&y);
    
    l=0;
    for (i=1;i*i<=n;i++)
      if (n%i==0)
      {
           l++;
           a[l]=i;
      }
      
	if (a[l]*a[l]==n) aux=l-1;
	else aux=l;
    
	for (i=aux;i>0;i--)
    {
        l++;
        a[l]=n/a[i];
    }
    
    k=0;
	sol=1;

	aux=n;

	for (i=2;i<=n;i++)
	  if (n%a[i]==0)
	  {
		  k++;
		  c[k]=a[i];

		  while (n%a[i]==0)
		  {
				p[k]=p[k]+y;
				n=n/a[i];
		  }
	  }

	for (i=1;i<=k;i++)
	{
		b=c[i]%mod;
		x=power(p[i]+1);
		x--;

		y=((c[i]-1)%mod)-1;
		if (y<0) y=y+mod;

		x=(x*inv[y])%mod;

		sol=(sol*x) % mod;
	}

	printf("%d\n",sol);
    
    return 0;
}