#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>

typedef unsigned int uint;

#define C 9901

uint sumdiv(uint n);
uint binexp(uint a, uint b);
int egcd(int a, int b, int *x, int *y);
uint invers_mod(uint x, uint m);

int main(void)
{
	FILE *in =  fopen("C:/Users/arco/Desktop/code/ads.txt", "r");
	FILE *out = fopen("C:/Users/arco/Desktop/code/out.txt", "w");

	if(in != NULL && out != NULL)
	{
		uint a, b;
		fscanf(in, "%u%*c%u%*c", &a, &b);
		printf("%u\n", sumdiv(binexp(a, b)));

		fclose(in);
		fclose(out);
	}
	else
	{
		printf("file error\n");
	}

	return 0;
}

uint invers_mod(uint x, uint m)
{
	int s, f;
	int d = egcd(x, m, &s, &f);
	if(d == 1)
	{
		return (s % m + m) % m;
	}
	else
	{
		printf("No invers moduloar\n\n");
	}
}

int egcd(int a, int b, int *x, int *y)
{
	if(a == 0)
	{
		*x = 0;
		*y = 1;
		return b;
	}
	else
	{
		int x1, y1;
		int d = egcd(b % a, a, &x1, &y1);
		*x = y1 - (b / a) * x1;
		*y = x1;
		return d;
	}
}

uint binexp(uint x, uint n)
{
	if(n == 1)
	{
		return x % C;
	}
	uint res = 1;
	while(n > 0)
	{
		if(n % 2 != 0)
		{
			res = ((res % C) * (x % C)) % C;
		}
		x = ((x % C) * (x % C)) % C;
		n /= 2;
	}
	return res;
}

uint sumdiv(uint n)
{
	uint res = 1, d = 2;
	while(n > 1)
	{
		uint p = 0;
		while(n % d == 0)
		{
			p++;
			n /= d;
		}
		if(p)
		{
			printf("q: %u %u\n", d, p);
			uint iv = invers_mod(d - 1, C);
			uint r = (((binexp(d, p) - 1) % C) * (iv % C)) % C;
			res = ((res % C) * (r % C)) % C;
		}
		d++;
		if(n > 1 && d * d > n)
		{
			d = n;
		}
	}

	return res;
}