#include<stdio.h>
#include<math.h>

int Out[64];

int main() {
    int n, m;
    while(~scanf("%d%d", &n, &m)) {
        int sum = 0;
        int limit = (int)sqrt(n);  // 当i是因子时 n/i通常也是因子 可以将复杂度将为O（logn）。
        for(int i = 1; i <= limit; i++) {
            if(n % i == 0) {
                int t;
                t = i;
                while(t) {
                    sum += (t % m)*(t % m);
                    t /= m;
                }
                if(i * i != n) {  //避免重复计算。
                    t = n/i;
                    while(t) {
                        sum += (t % m) * (t % m);
                        t /= m;
                    }
                }
            }
        }
        int i = 0;
        while(sum) {
            Out[i++] = sum % m;
            sum /= m;
        }
        for(int j = i - 1; j >= 0; j--) {
            if(Out[j] > 9) {
                printf("%c", Out[j] - 10 + ‘A‘);
            } else printf("%d", Out[j]);
        }
        puts("");
    }
    return 0;
}