Cod sursa(job #996725)

Utilizator stefan.petreaStefan Petrea stefan.petrea Data 12 septembrie 2013 15:55:26
Problema Suma divizorilor Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 23.73 kb
#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;
#define min(x,y) (((x)<(y))?(x):(y))
#define max(x,y) (((x)>=(y))?(x):(y))
#define mod 9901
#define pL 1000
// first pL primes
long p[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037, 3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209, 3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359, 3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527, 3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659, 3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821, 3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967, 3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129, 4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273, 4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457, 4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637, 4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789, 4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957, 4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101, 5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281, 5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443, 5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623, 5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779, 5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903, 5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101, 6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269, 6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397, 6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599, 6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779, 6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947, 6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103, 7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283, 7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487, 7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607, 7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951, 7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161, 8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311, 8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521, 8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681, 8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831, 8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007, 9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181, 9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343, 9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491, 9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679, 9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973, 10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093, 10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169, 10177, 10181, 10193, 10211, 10223, 10243, 10247, 10253, 10259, 10267, 10271, 10273, 10289, 10301, 10303, 10313, 10321, 10331, 10333, 10337, 10343, 10357, 10369, 10391, 10399, 10427, 10429, 10433, 10453, 10457, 10459, 10463, 10477, 10487, 10499, 10501, 10513, 10529, 10531, 10559, 10567, 10589, 10597, 10601, 10607, 10613, 10627, 10631, 10639, 10651, 10657, 10663, 10667, 10687, 10691, 10709, 10711, 10723, 10729, 10733, 10739, 10753, 10771, 10781, 10789, 10799, 10831, 10837, 10847, 10853, 10859, 10861, 10867, 10883, 10889, 10891, 10903, 10909, 10937, 10939, 10949, 10957, 10973, 10979, 10987, 10993, 11003, 11027, 11047, 11057, 11059, 11069, 11071, 11083, 11087, 11093, 11113, 11117, 11119, 11131, 11149, 11159, 11161, 11171, 11173, 11177, 11197, 11213, 11239, 11243, 11251, 11257, 11261, 11273, 11279, 11287, 11299, 11311, 11317, 11321, 11329, 11351, 11353, 11369, 11383, 11393, 11399, 11411, 11423, 11437, 11443, 11447, 11467, 11471, 11483, 11489, 11491, 11497, 11503, 11519, 11527, 11549, 11551, 11579, 11587, 11593, 11597, 11617, 11621, 11633, 11657, 11677, 11681, 11689, 11699, 11701, 11717, 11719, 11731, 11743, 11777, 11779, 11783, 11789, 11801, 11807, 11813, 11821, 11827, 11831, 11833, 11839, 11863, 11867, 11887, 11897, 11903, 11909, 11923, 11927, 11933, 11939, 11941, 11953, 11959, 11969, 11971, 11981, 11987, 12007, 12011, 12037, 12041, 12043, 12049, 12071, 12073, 12097, 12101, 12107, 12109, 12113, 12119, 12143, 12149, 12157, 12161, 12163, 12197, 12203, 12211, 12227, 12239, 12241, 12251, 12253, 12263, 12269, 12277, 12281, 12289, 12301, 12323, 12329, 12343, 12347, 12373, 12377, 12379, 12391, 12401, 12409, 12413, 12421, 12433, 12437, 12451, 12457, 12473, 12479, 12487, 12491, 12497, 12503, 12511, 12517, 12527, 12539, 12541, 12547, 12553, 12569, 12577, 12583, 12589, 12601, 12611, 12613, 12619, 12637, 12641, 12647, 12653, 12659, 12671, 12689, 12697, 12703, 12713, 12721, 12739, 12743, 12757, 12763, 12781, 12791, 12799, 12809, 12821, 12823, 12829, 12841, 12853, 12889, 12893, 12899, 12907, 12911, 12917, 12919, 12923, 12941, 12953, 12959, 12967, 12973, 12979, 12983, 13001, 13003, 13007, 13009, 13033, 13037, 13043, 13049, 13063, 13093, 13099, 13103, 13109, 13121, 13127, 13147, 13151, 13159, 13163, 13171, 13177, 13183, 13187, 13217, 13219, 13229, 13241, 13249, 13259, 13267, 13291, 13297, 13309, 13313, 13327, 13331, 13337, 13339, 13367, 13381, 13397, 13399, 13411, 13417, 13421, 13441, 13451, 13457, 13463, 13469, 13477, 13487, 13499, 13513, 13523, 13537, 13553, 13567, 13577, 13591, 13597, 13613, 13619, 13627, 13633, 13649, 13669, 13679, 13681, 13687, 13691, 13693, 13697, 13709, 13711, 13721, 13723, 13729, 13751, 13757, 13759, 13763, 13781, 13789, 13799, 13807, 13829, 13831, 13841, 13859, 13873, 13877, 13879, 13883, 13901, 13903, 13907, 13913, 13921, 13931, 13933, 13963, 13967, 13997, 13999, 14009, 14011, 14029, 14033, 14051, 14057, 14071, 14081, 14083, 14087, 14107, 14143, 14149, 14153, 14159, 14173, 14177, 14197, 14207, 14221, 14243, 14249, 14251, 14281, 14293, 14303, 14321, 14323, 14327, 14341, 14347, 14369, 14387, 14389, 14401, 14407, 14411, 14419, 14423, 14431, 14437, 14447, 14449, 14461, 14479, 14489, 14503, 14519, 14533, 14537, 14543, 14549, 14551, 14557, 14561, 14563, 14591, 14593, 14621, 14627, 14629, 14633, 14639, 14653, 14657, 14669, 14683, 14699, 14713, 14717, 14723, 14731, 14737, 14741, 14747, 14753, 14759, 14767, 14771, 14779, 14783, 14797, 14813, 14821, 14827, 14831, 14843, 14851, 14867, 14869, 14879, 14887, 14891, 14897, 14923, 14929, 14939, 14947, 14951, 14957, 14969, 14983, 15013, 15017, 15031, 15053, 15061, 15073, 15077, 15083, 15091, 15101, 15107, 15121, 15131, 15137, 15139, 15149, 15161, 15173, 15187, 15193, 15199, 15217, 15227, 15233, 15241, 15259, 15263, 15269, 15271, 15277, 15287, 15289, 15299, 15307, 15313, 15319, 15329, 15331, 15349, 15359, 15361, 15373, 15377, 15383, 15391, 15401, 15413, 15427, 15439, 15443, 15451, 15461, 15467, 15473, 15493, 15497, 15511, 15527, 15541, 15551, 15559, 15569, 15581, 15583, 15601, 15607, 15619, 15629, 15641, 15643, 15647, 15649, 15661, 15667, 15671, 15679, 15683, 15727, 15731, 15733, 15737, 15739, 15749, 15761, 15767, 15773, 15787, 15791, 15797, 15803, 15809, 15817, 15823, 15859, 15877, 15881, 15887, 15889, 15901, 15907, 15913, 15919, 15923, 15937, 15959, 15971, 15973, 15991, 16001, 16007, 16033, 16057, 16061, 16063, 16067, 16069, 16073, 16087, 16091, 16097, 16103, 16111, 16127, 16139, 16141, 16183, 16187, 16189, 16193, 16217, 16223, 16229, 16231, 16249, 16253, 16267, 16273, 16301, 16319, 16333, 16339, 16349, 16361, 16363, 16369, 16381, 16411, 16417, 16421, 16427, 16433, 16447, 16451, 16453, 16477, 16481, 16487, 16493, 16519, 16529, 16547, 16553, 16561, 16567, 16573, 16603, 16607, 16619, 16631, 16633, 16649, 16651, 16657, 16661, 16673, 16691, 16693, 16699, 16703, 16729, 16741, 16747, 16759, 16763, 16787, 16811, 16823, 16829, 16831, 16843, 16871, 16879, 16883, 16889, 16901, 16903, 16921, 16927, 16931, 16937, 16943, 16963, 16979, 16981, 16987, 16993, 17011, 17021, 17027, 17029, 17033, 17041, 17047, 17053, 17077, 17093, 17099, 17107, 17117, 17123, 17137, 17159, 17167, 17183, 17189, 17191, 17203, 17207, 17209, 17231, 17239, 17257, 17291, 17293, 17299, 17317, 17321, 17327, 17333, 17341, 17351, 17359, 17377, 17383, 17387, 17389};
long invp[] = {1,4951,7426,8251,8911,9076,6807,9351,9451,8133,9571,9626,4703,5422,5381,8949,6999,9736,9751,1273,4813,5966,5192,4838,6085,9802,2815,6445,6509,9459,8408,7540,9537,5094,5285,9835,2983,1039,7217,2245,5173,9846,469,7993,8234,9851,7025,223,8981,2041,4225,9693,2434,5901,8470,3061,5283,6564,2547,7744,6706,4035,7539,1565,6442,94,9871,3153,9529,6117,6160,4508,2083,9555,6103,959,2118,9876,7401,3179,8314,8463,898,9053,2690,9789,4840,5971,9449,1393,8265,6649,6947,7254,5706,8619,994,1885,4078,3282,6510,5182,2625,889,6757,9265,4545,8747,4222,4934,4395,8720,3520,1522,5642,3388,6832,3050,8428,2874,9886,6527,1450,7012,2999,7058,7202,3213,6287,5992,1677,5164,1967,8002,7543,9424,2347,7621,5759,821,2188,8440,3746,9002,849,7857,3893,5124,6843,5364,1345,2464,4030,5174,7464,3906,2513,8482,8748,3992,8509,9849,4971,8768,4494,8923,9891,2853,1051,4295,8588,5232,8834,8625,9777,8191,1405,5595,1501,9113,3820,4896,3255,7760,3495,4602,3185,1156,6627,7740,9583,1031,3038,2341,4483,3879,2467,7148,5952,4594,2443,8927,761,6561,2369,8869,9196,9399,1253,6900,6318,754,2730,6118,3403,4943,3263,3924,993,6834,6450,2755,1540,1121,4645,6566,1127,9481,8333,676,8094,5616,2418,5479,314,1166,4864,3975,2928,518,618,3488,5965,5750,5480,3921,7960,6237,4436,1283,1706,9276,4334,5831,2205,3078,1094,8945,9435,5375,3068,5628,8328,4418,9685,414,2568,5175,4962,8066,7164,3771,5623,1515,6216,5495,6791,2586,4945,2292,6972,4377,3320,1911,3624,4654,4374,4998,6859,5176,1037,7766,9088,2919,7436,9286,3803,7486,4500,683,6377,1880,2225,7176,6645,5476,3113,7084,2638,2427,581,6315,7897,6672,3631,5970,2034,3280,4327,6230,9478,9507,6010,1077,5498,5771,5396,1857,1333,8500,6953,5504,2650,711,3956,9416,9268,7648,9115,1321,1810,8672,9605,4239,743,1046,1519,7871,3577,3072,4633,1646,7900,5707,5220,6006,7626,6980,2799,7019,7946,5758,7193,8753,4549,5331,6602,5552,6361,1718,9546,7194,1395,4073,4598,265,302,3159,2107,2040,9217,5669,7944,7258,5025,5315,1665,4969,1724,7000,4107,5984,4356,6758,5367,6524,2488,1753,1302,3104,1207,4472,5108,5004,4812,1274,6328,6715,8795,6644,6751,8515,3982,7292,3283,3043,2907,2302,6383,9843,5022,2808,5431,8307,7845,5262,4175,1291,3297,5862,2967,5786,2221,5075,4732,4361,3466,1744,6042,1618,8208,3062,3552,181,8565,9178,5201,3243,6185,1865,7101,7508,1611,4182,7866,8422,365,4262,9423,7891,7874,1632,1414,9898,1165,7638,8967,5636,3698,1335,5703,8022,7669,7246,379,5388,640,3239,7090,798,4186,1341,9795,1943,3103,3048,374,4820,7096,4313,5708,351,5958,4516,8068,7381,3063,142,8095,8567,2431,3480,5058,6867,8122,4893,7613,7198,5683,454,9698,9035,8054,4296,6276,3887,6152,3554,3864,3489,1812,6847,998,7385,5074,9825,1658,1072,5013,1086,930,5444,3133,8484,4439,2274,7109,2192,2106,910,8683,8786,8640,9540,4706,9445,1399,5638,1061,5668,9651,8711,304,4183,3541,8273,6490,3549,4398,3542,2147,522,3774,4469,331,8670,4245,9582,4512,2754,9870,4991,2355,2985,7777,3102,6376,6265,185,9688,3874,7700,8278,4518,4739,8948,9704,9353,949,3676,8704,4592,6078,1783,2698,3348,2978,7057,7178,3349,1969,8421,8427,3405,999,1802,3628,484,634,5323,8765,4132,3532,4258,4679,7490,1931,9508,206,7859,4463,1187,1108,7070,425,3200,2391,2733,6705,5127,2368,871,218,19,7869,8011,9836,9723,3036,2395,8538,2321,8306,3869,1874,6882,3092,2788,1141,8915,3665,9655,7243,6099,2858,3145,9444,8935,7225,1707,5824,9899,8101,1597,5092,8059,4323,9066,1876,8363,6285,9069,1852,2908,6959,6468,3592,4773,6040,8330,8827,6987,3884,2299,532,5343,7739,1654,2526,5723,8296,5989,5633,4079,4428,1020,4491,3311,3326,4429,3711,3969,5873,4542,4664,5502,5132,2404,219,9344,6425,9547,8086,3379,8678,8715,764,1244,981,6275,5254,324,2016,3219,6818,7919,5332,9295,6874,6563,1643,3400,8274,8970,4714,5066,637,6162,8198,3946,7266,3260,7884,6683,5775,4954,3988,1922,7706,7137,3646,4680,2451,9630,5449,3071,329,9560,1286,973,169,9033,1586,8062,3404,965,8696,8511,4568,749,5405,9609,6437,2151,5555,8791,2565,6920,8409,9139,1216,8343,6717,2392,2140,2311,6061,3066,7515,2773,4611,2366,4338,5105,9119,323,3154,872,8155,3021,2871,7726,5590,2456,5815,3008,3568,8034,1776,9008,6580,2224,1714,8410,8522,7815,3690,8548,4438,8485,1442,4394,7331,2796,8043,6724,5853,204,5883,661,8501,8819,6192,5144,8604,359,7977,1380,5050,5720,5224,4026,2823,5768,2113,5667,5493,4353,101,6780,7894,6228,8663,619,7045,9434,2636,6735,5618,2082,2774,9183,5948,6944,2117,5135,8579,3493,4414,145,3539,5453,6570,2667,5054,3885,7888,4350,1234,642,9639,1564,1225,679,2463,4798,5117,962,5644,5725,2265,2461,1487,1791,3478,3905,765,7971,551,3548,2686,682,6113,6805,5924,8024,2979,1024,3381,7485,1854,1862,8299,3849,9138,1285,2002,8373,2372,7682,1262,8384,5159,9538,3496,458,3360,7180,7387,992,4010,5949,8520,2430,4066,2133,4444,8658,6894,2043,1777,8317,4185,2373,8673,8374,6114,1972,6044,8051,5151,4114,2726,2445,2537,130,5743,2045,4885,8721,4502,6392,3501,2624,3873,4789,975,7327,3312,1385,2272,4833,2523,6883,3871,2960,3564,1801,4264,7361,6150,1150,8505,9144,596,3355,7272,7199,5191,4289,1691,9239,3216,9130,1105,6431,8523,2380,6556,7779,381,5481,912,8081,746,3028,7982,1794,555,9381,2923,3245,8934,3538,8993,5406,983,5818,2199,2941,2668,3612,1275,654,5855,3695,9108,434,3082,5830,4335,8396,1139,7231,1868,7980,5287,4054,8681,6699,1403,5188,4574,6128,1668,6443,6665,7718,8609,8143,8710,1382,3220,652,175,4411,7356,4844,7907,2212,6508,7320,7928,7297,4758,4925,2344,9752,7615,349,2196,6325,6820,1755,9831,3918,2493,7200,803,3039,5360,5428,6961,8650,3281,1349,7658,8675,6595,8835,1423,5153,5085,8411,4601,991,8825,7908,403,7747,846,6492,2125,6458,9739,1301,4692,6653,4460,4111,1267,8438,6913,6084,2653,5562,7116,989,177,8812,9333,2359,9878,4841,6709,8151,4992,293,8699,8178,9275,103,2925,6816,7655,9273,8570,7182,7630,2014,4391,5672,7473,3315,3375,3535,6002,1600,8769,3295,7820,1424,6929,171,368,7589,7687,5604,6899,7091,3352,4627,2381,1964,9860,5990,8913,9711,2257,9623,1841,8638,1047,6116,2130,2409,5525,2279,1975,6547,7228,2538,6375,8518,1546,5413,7417,7062,6782,5736,6881,2622,9408,44,9679,4230,5844,5735,6783,4101,5892,2304,4724,6674,9231,1882,1808,9455,100,544,6523,3662,9614,2986,4271,220,921,4152,5211,660,9900,7921,943,6234,4097,2031,632,5179,7112,4149,1388,3227,2674,7597,9841,4743,9006,2305,1918,5629,7044,6727,2786,6726,3397,1511,6087,8156,6749,9865,2839,2824,3044,3763,4123,5998,3526,6462,3228,3354,427,3198,6824,3753,7492,5813,3785,827,8854,8060,7812,3265,7937,1016,2810,1503,3002,6990,8010,4515,2312,5579,6076,1078,5091,9188,8843,4738,8394,134,4828,8106,5510,8623,2242,1352,1331,1021,5856,1036,1236,6976,2573,8872,1460,6156,808,431,6136,7547,3502,8135,3030,8182,6115,7130,9308,461,2988,8525,382,5838,5440,1916,9000,4451,8495,8600,1900,9466,6560,2154,2142,3276,2777,3714,7912,4877,8478,8412,2944,2092,9289,9266,1513,4137,4759,480,7605,8845,5238,5269,9191,4487,8146,604,9395,274,3448,8712,833,4976,1661,8276,7642,5762,3387,2477,8973,4163,3314,9785,5946,8350,3639,5807,4442,6145,7895,6515,2589,310,4859,501,9483,2455,5115,3222,398,8524,1563,2828,738,758,7840,6478,3487,9014,6206,8626,5433,6289,4848,1697,2284,4495,6904,9495,9460,2767,2859,6248,8180,9145,9506,1860,1909,7067,7155,4548,8480,9179,8989,2888,3345,7521,3325,2087,8796,39,8890,1044,2713,5131,1346,5508,4710,2702,6204,2629,7995,6397,8805,4072,2255,7981,4213,8100,1612,3571,6941,7016,1268,1952,2169,8516,9358,8926,2216,9365,3509,2614,436,8607,5837,9771,9558,4790,7175,589,3863,3787,2052,9106,7528,1747,9897,1415,9181,3752,6003,5816,4017,888,3687,7753,3290,7471,4987,5052,1545,5891,3799,7051,8856,562,1010,8858,7670,1845,6790,4808,9107,339,9193,7529,84,7372,648,6438,2918,763,5728,8814,5677,2423,1117,6495,7892,7643,3844,9360,9593,4880,9219,4525,2878,1930,7491,4093,4302,5130,7826,4257,8084,4280,2277,4430,2947,6132,8676,4699,5059,6409,5742,9502,1279,6016,7136,6167,4831,6919,5729,9756,1356,4761,6007,5206,2957,6471,5478,2760,8052,7265,7083,8978,8953,1433,8706,3659,9226,9307,2104,5548,6860,5067,2807,1005,5334,526,5875,503,4181,4926,1135,2826,2974,1102,4145,2325,7518,1947,6762,4048,6389,1532,6151,8375,5507,5084,7447,916,7978,160,4860,8888,4458,8170,5280,7501,8370,4575,5150,686,8357,9770,429,6747,7002,7746,6364,9077,6624,2770,5997,7128,2386,2413,4821,1192,3696,4685,6970,5988,4982,2961,4659,5044,1492,2863,6056,7336,1512,1110,6692,5846,7967,1739,7224,3578,868,29,2688,1759,6775,6059,105,9148,6607,154,3429,7450,2623,1856,6474,2017,2991,9850,1561,1012,3965,9023,1462,4405,7399,4617,9202,1982,3083,8349,7885,3852,4074,6215,1223,1271,4331,7723,3476,6909,9682,6401,7530,586,6981,7764,2293,9329,8782,4379,2820,863,6590,4453,5205,2848,3957,342,549,496,9345,8013,9015,7375,9159,6154,4558,7419,4527,258,4223,1571,3861,1915,4329,9457,3707,3433,5930,1158,1883,1145,8049,9009,9149,5972,8542,1842,521,6600,8194,9301,5978,574,6815,890,7022,453,8413,4610,1357,3553,3357,6411,7526,1595,3023,7506,7218,6219,1720,1890,8365,2032,4649,9311,9030,9814,4579,8031,7510,7893,148,4856,8458,2662,1811,2472,8614,6077,1616,2710,5193,1656,6369,5183,7362,5860,9815,4595,1361,7149,2732,2551,8392,6886,8136,7932,4284,2121,2844,9496,1781,8677,1249,960,5309,734,6848,1060,842,7523,6651,1623,3959,6550,9303,8261,1713,8884,4366,3940,4646,1002,4910,8602,796,1793,5389,4660,2742,8582,7754,1608,2569,2351,1629,3907,9089,9019,7586,5718,9597,250,8074,4409,6769,6158,1324,361,1115,1323,373,5258,1097,4795,7709,4510,7060,4457,2536,6018,4888,8829,9641,9079,6374,7574,5780,3105,8311,3168,2830,8461,3749,8241,5605,1570,73,8755,5008,726,8313,2068,7470,7477,1555,6193,2234,14,7688,9050,8733,7878,5868,7066,5894,2363,8543,217,108,1541,5981,7851,9522,5573,511,5914,4629,4265,8005,7511,9699,1128,2010,5639,5488,8362,9291,5263,4650,5986,6995,3064,3789,267,834,2543,9746,8797,1786,7161,4794,802,6813,3593,9592,5540,9576,4517,4389,6422,9318,2211,3826,2780,4547,5100,58,9563,2422,210,1672,3313,6858,7743,9610,5982,9131,9376,3876,9086,4897,3223,6080,3660,3941,3964,2379,4534,4588,6952,2901,2442,8798,3359,3249,684,7564,6842,9524,9737,3210,7010,251,9866,2290,6197,7232,3684,4767,3299,3772,2055,4365,7604,2714,9005,7102,8527};
/* the problem actually asks to compute theta_1(A^B) % 9901. 
 *  http://en.wikipedia.org/wiki/Divisor_function
 *
 *
 * theta_1(A^B) =  
 *
 *
 *     r   p_i^{a_i*B} - 1
 * = Prod  ---------------
 *    i=1  p_i - 1
 *
 * because 9901 is prime now, we can compute p_i^{a_i*B} fast through fermat's little theorem
 *
 * we also need the inverse mod 9901 of p_i - 1  which we can also compute fast through extended
 * euclidean algorithm
 *
 */


// powers of primes in A
long a[pL];
int main() {
    ifstream I("sumdiv.in");
    ofstream O("sumdiv.out");
    long A,B;
    int i,j;
    I >> A >> B;

    long aL = -1;//biggest prime divisor index
    for(i=0;i<pL;i++) {
        while(A % p[i] == 0) {
            A /= p[i] ; 
            a[i]++ ; 
            aL = max(i,aL) ; 
            //cout << p[i] << endl;
        };
        if(A == 1)
            break;
    };
    long S = 1;
    
    // Br = B % (mod-1)
    // it will be used to compute some powers % mod
    long Br = B % (mod-1);
    for(i=0;i<aL+1;i++) {
        if(a[i]) {
            //cout<<"a["<<i<<"]="<<a[i]<<endl;
            //cout<<"p["<<i<<"]="<<p[i]<<endl;
            long u = 1;
            long v = invp[i];
            a[i] %= mod-1;
            long w = ((a[i] * Br) + 1) % mod;
            //cout<<"Br="<<Br<<endl;
            //cout<<"w="<<w<<endl;
            for(j=1;j<=w;j++) {
                u *= p[i];
                u %= mod;
            };
            u = u - 1;
            if(u < 0)
             u += mod;
            //cout<<"u="<<u<<endl;
            //cout<<"v="<<v<<endl;
            S *= (u * v) % mod;
            S %= mod;
        };
    };

    O << S;
    return 0;
};