1309.cpp

平时acm训练时ac的源代码

//1309

#include <iostream>

using namespace std;

int main(void)
{
	int mem[1002] = {0, 2592, 6706, 4944, 714, 464, 6707, 3198, 8950, 9345, 5392, 306, 7174, 4396, 4775, 7358, 4541, 5504, 5452, 806, 1890, 8598, 8016, 1375, 8162, 7227, 7999, 1431, 3340, 3420, 84, 2025, 821, 3385, 6114, 1887, 8138, 4412, 2362, 9216, 6520, 5312, 3096, 4598, 963, 202, 3301, 4243, 3266, 3921, 3149, 8815, 4310, 9494, 965, 2364, 1002, 2205, 4208, 9780, 2416, 7663, 2301, 5925, 6194, 8833, 2839, 2010, 6724, 2030, 2835, 3684, 1595, 6975, 136, 665, 2775, 7310, 7989, 8706, 80, 8417, 2468, 8074, 5070, 6808, 7684, 224, 2387, 5900, 8614, 2518, 6927, 5951, 2475, 7112, 8674, 917, 6741, 8169, 742, 8348, 8025, 7350, 8125, 1950, 1286, 7217, 7686, 6310, 7696, 1714, 5134, 7400, 1336, 6133, 5994, 6478, 3307, 5269, 6823, 6940, 9590, 5651, 8390, 792, 2801, 7081, 450, 6717, 9492, 7208, 1710, 8748, 6638, 9220, 5196, 6663, 4979, 4808, 7710, 5227, 3977, 8090, 5146, 9652, 6696, 7454, 9166, 1981, 9444, 2302, 3346, 4560, 594, 3857, 5529, 4974, 852, 850, 510, 8850, 6145, 940, 9731, 4083, 9800, 1574, 2722, 341, 118, 3992, 6221, 986, 2148, 665, 9718, 745, 3155, 3235, 6522, 3189, 719, 3959, 5070, 6630, 4838, 4796, 8670, 837, 3213, 6880, 2630, 9915, 5885, 9054, 9257, 8465, 2124, 7615, 4499, 7471, 9063, 2425, 910, 3172, 1524, 9425, 8367, 7663, 6178, 2461, 7757, 7941, 4597, 3080, 9137, 4452, 7840, 1040, 4565, 9491, 4310, 5112, 3173, 6188, 1395, 9111, 2102, 5149, 763, 743, 4368, 4465, 6561, 1758, 6298, 6939, 6663, 5832, 1071, 8347, 839, 9738, 8184, 956, 6976, 5612, 7681, 7957, 8875, 2203, 34, 952, 7422, 8130, 6875, 3823, 6949, 5585, 2688, 4409, 9393, 9090, 8578, 8935, 4288, 4859, 6799, 8340, 9145, 9787, 4302, 1426, 75, 5778, 6482, 2124, 444, 3148, 1211, 9298, 4033, 1024, 5328, 7821, 692, 656, 2106, 8535, 9480, 9558, 4684, 2555, 3710, 1263, 6944, 6181, 8391, 4778, 4056, 960, 2392, 1313, 5152, 601, 7491, 1584, 2702, 2897, 1817, 7406, 9010, 5569, 3983, 2400, 9407, 7338, 9444, 7298, 8661, 2452, 7461, 6181, 4348, 8907, 1803, 8285, 7089, 2641, 5467, 2562, 9457, 5296, 1497, 8542, 4137, 8556, 3188, 1860, 3358, 7315, 5399, 7301, 8896, 1412, 2470, 3535, 4299, 5425, 2892, 8046, 7876, 8131, 878, 650, 2636, 2964, 6294, 3055, 2205, 7465, 5250, 4756, 8655, 1346, 8436, 1406, 7792, 1468, 8691, 8586, 1657, 703, 7120, 3258, 8250, 7130, 5454, 3529, 1963, 4628, 5053, 4773, 6769, 8720, 367, 5675, 9831, 6121, 2386, 2082, 9040, 6706, 2447, 1098, 9586, 3322, 9685, 8197, 8401, 1272, 6142, 4544, 4546, 3757, 7743, 2532, 5314, 3531, 1047, 7396, 3706, 4800, 5912, 9097, 3413, 7240, 7911, 2743, 3691, 9512, 6193, 842, 2353, 731, 892, 4442, 1018, 765, 6824, 1281, 4389, 8704, 4663, 3113, 8571, 3868, 9608, 5400, 825, 7325, 4939, 4790, 4183, 5665, 4615, 2928, 5484, 5777, 7728, 7423, 2958, 1440, 3639, 8542, 8205, 6763, 7579, 6277, 6797, 4519, 3829, 5933, 1510, 1210, 8345, 5377, 3634, 9146, 1720, 2482, 6514, 9536, 9688, 5693, 7838, 9256, 9723, 369, 8194, 211, 632, 9299, 241, 1924, 8229, 4887, 7415, 3407, 9901, 9433, 9263, 7485, 6834, 9806, 5424, 3282, 4434, 2868, 2823, 9758, 7360, 7503, 6606, 2977, 1846, 2227, 4083, 2555, 1952, 8573, 7011, 2813, 2067, 5950, 9012, 8061, 2376, 5350, 9344, 1672, 2365, 3202, 8491, 2263, 4690, 2349, 3852, 95, 5022, 641, 8211, 6431, 3528, 7788, 3295, 1605, 8902, 6607, 1421, 2282, 9748, 6034, 8409, 9611, 4967, 7829, 1393, 9420, 6116, 4334, 3577, 8459, 6003, 7005, 1411, 2137, 6550, 4711, 4511, 1844, 1986, 5978, 7172, 7657, 8802, 2125, 8589, 3810, 1289, 6459, 760, 1332, 2281, 2038, 4155, 491, 3552, 5711, 2133, 9510, 8083, 4514, 6239, 2678, 6568, 8055, 5765, 889, 7494, 7323, 4619, 3252, 6078, 3861, 2229, 2428, 7071, 8087, 7298, 8901, 4282, 4239, 1157, 7050, 7919, 7367, 2143, 8602, 5012, 1400, 2226, 8837, 506, 889, 2827, 590, 2845, 7154, 9638, 6641, 9101, 9100, 9400, 559, 253, 4696, 8237, 8138, 8753, 5544, 9818, 8779, 3294, 3937, 5329, 1017, 577, 2100, 5968, 4061, 7789, 1611, 8386, 1206, 5344, 4730, 8141, 1194, 4029, 2752, 692, 774, 9494, 6558, 796, 2898, 1145, 5237, 4804, 2854, 1948, 4432, 6012, 5853, 1984, 6815, 8298, 251, 9556, 227, 8366, 71, 7890, 3645, 218, 333, 71, 6082, 924, 4371, 677, 8870, 2058, 5140, 5948, 5296, 4521, 7653, 1497, 8844, 7797, 2094, 1976, 9448, 7575, 4760, 5517, 2136, 5886, 4597, 5170, 3481, 2136, 3311, 8620, 4926, 7018, 423, 6078, 7070, 2785, 6933, 627, 6509, 4865, 9958, 6411, 1511, 2085, 9576, 4799, 4983, 8323, 6062, 2648, 9940, 8883, 1857, 3876, 2075, 5985, 1150, 2288, 9300, 6077, 6369, 9082, 105, 268, 3295, 873, 4290, 3668, 8525, 3727, 9334, 3013, 2568, 2910, 2605, 8446, 5809, 4584, 6993, 6633, 152, 2064, 7762, 8962, 6914, 9149, 6776, 3538, 6608, 914, 6298, 880, 3335, 2970, 1266, 5095, 8203, 805, 517, 919, 5619, 1071, 5871, 1015, 1401, 8706, 7594, 3823, 8899, 1402, 1200, 8242, 7887, 3931, 7225, 8167, 8650, 5088, 1539, 1716, 1011, 6397, 6950, 1103, 9852, 1893, 605, 4090, 4097, 1740, 1883, 979, 5554, 4872, 6189, 8101, 611, 2501, 6844, 6557, 1461, 9328, 1477, 4054, 7115, 5378, 6228, 4166, 8950, 1061, 7692, 1821, 9745, 346, 9288, 6960, 2284, 8251, 9610, 679, 4125, 1578, 5828, 1119, 8551, 2782, 9500, 732, 7482, 7496, 1680, 9905, 2714, 931, 608, 1407, 3997, 7173, 9623, 7940, 2267, 3401, 5701, 4454, 8175, 4694, 9364, 7973, 4371, 1189, 4896, 1870, 9662, 6530, 3567, 8090, 6280, 2137, 7295, 8152, 1325, 18, 9952, 1722, 6663, 8805, 9345, 5831, 8801, 4090, 5151, 9930, 798, 4266, 2500, 5642, 5154, 3433, 451, 9035, 1967, 6131, 2299, 9888, 3012, 9712, 7899, 5133, 9826, 8177, 8141, 2559, 366, 7961, 2626, 7518, 5110, 6953, 2509, 7046, 4998, 3220, 8903, 2891, 6377, 7050, 9962, 6962, 7244, 5877, 2787, 4170, 8014, 885, 1316, 6500, 6702, 443, 6583, 5876, 4321, 5017, 9754, 4461, 6530, 6445, 1478, 7476, 4414, 2807, 8526, 5726, 1516, 7731, 9814, 2099, 3083, 4886, 7142, 954, 5168, 6340, 5769, 3316, 5547, 2766, 6888, 7245, 7404, 4851, 8823, 862, 7846, 2155, 6533, 8142, 541, 7780, 2007, 4541, 2859, 6374, 3511, 93, 4518, 5180, 5836, 1609, 6150, 6326, 7463, 3634, 1010, 2871, 5198, 7424, 13, 7497, 6088, 4044, 5800, 8250, 5152, 9710};
	__int64 n, a, b, c;
	cin>>n;
	a = mem[n/100000];
	c = __int64(n/100000)*100000;
	n = n%100000;
	for (__int64 i=1; i<=n; i++)
	{
		b = ((a-1)*((((i+c)%9973)*((i+c)%9973)*((i+c)%9973))%9973)*((i+c)%9973)*((i+c)%9973))%9973;
		a = (b+((i+c)%9973)*((i+c)%9973)*((i+c)%9973)-a*((i+c)%9973)+3*((i+c)%9973)+7*a)%9973;
		if (a<0)
		{
			a += 9973;
		}
	}
	cout<<a<<endl;;
	return 0;
}