For a positive integer a, let S(a) be the sum of the digits in base l. Also let L(a) be the minimum k such that S^k(a) is less than or equal to l-1. Find the minimum a such that L(a) = N for a given N, and print a modulo m.



Input

The input contains several test cases, followed by a line containing "0 0 0". Each test case is given by a line with three integers N, m, l (0 \leq N \leq 10^5, 1 \leq m \leq 10^9, 2 \leq l \leq 10^9).

Output

For each test case, print its case number and the minimum a modulo m as described above.

Example

Input

0 1000 10
1 1000 10
0 0 0


Output

Case 1: 1
Case 2: 10
#include <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;

ll gcd(ll a, ll b) {
    if (b==0) return a;
    return gcd(b, a%b);
}

/// x^n % md
ll pow_mod(ll x, ll n, ll md) {
    ll r = 1;
    while (n) {
        if (n & 1) r = (r * x) % md;
        x = (x * x) % md;
        n >>= 1;
    }
    return r;
}

/// x?????????, md????´???°??????x???md????????°??§????????????????????????
ll invp(ll x, ll md) {
    return pow_mod(x, md-2, md);
}

ll totient(ll n) {
    ll m = n;
    for (ll i = 2; i*i <= n; i++) {
        if (n % i != 0) continue;
        m /= i; m *= (i-1);
        while (n % i == 0) {
            n /= i;
        }
    }
    if (n > 1) {
        m /= n; m *= (n-1);
    }
    return m;
}

/**
 * ????????????????????? with Mod
 */
template<int N>
struct Matrix {
    typedef ll D;
    D d[N][N];
    D MD;
    Matrix(ll MD) : MD(MD) {
        memset(d, 0, sizeof(d));
    }

    D* operator[](int p) {
        return d[p];
    }
    
    const D* operator[](int p) const {
        return d[p];
    }
    
    Matrix operator+(const Matrix &right) {
        Matrix res(MD);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res[i][j] = (d[i][j]+right[i][j]) % MD;
            }
        }
        return res;
    }
    
    Matrix operator*(const Matrix &right) {
        Matrix res(MD), r(MD);
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                r[i][j] = right[j][i]; 
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                res[i][j] = 0;
                for (int k = 0; k < N; k++) {
                    res[i][j] += d[i][k]*r[j][k];
                }
                res[i][j] %= MD;
            }
        }
        return res;
    }

    Matrix pow(ll p) {
        Matrix res(MD), buf = *this;
        for (int i = 0; i < N; i++) res[i][i] = D(1);
        while(p != 0) {
            if (p % 2) {
                res = res*buf;
            }
            p /= 2;
            buf = buf*buf;
        }
        return res;
    }
};

ll l;

ll fc = 2;
ll fdp[1000];

void init() {
    fc = 2;
    fdp[2] = 1;
    while (true) {
        bool f = true;
        ll l2 = 2;
        fdp[fc+1] = 0;
        for (int i = 0; i < fdp[fc]; i++) {
            fdp[fc+1] += l2;
            if (fdp[fc+1] >= 1e9+10) {
                f = false;
                break;
            }
            l2 *= l;
        }
        if (!f) break;
        fc++;
    }
}

ll f(ll n, ll m) {
    if (m == 1) return 0;
    if (n <= fc) return fdp[n] % m;
    if (n-1 == fc) {
        Matrix<2> mt(m);
        mt[0][0] = 1; mt[0][1] = 1;
        mt[1][0] = 0; mt[1][1] = l % m;
        mt = mt.pow(fdp[n-1]);
        return 2*mt[0][1] % m;
    }

    ll rep = -1;
    constexpr int B = 1000;
    Matrix<2> mt(m);
    mt[0][0] = 1; mt[0][1] = 1;
    mt[1][0] = 0; mt[1][1] = l % m;
    mt = mt.pow(B);
    auto mt2 = mt.pow(2*1000000000);
    ll sm = 2*mt2[0][1] % m;
    ll l2 = 2*mt2[1][1] % m;
    map<P, ll> mp;
    for (ll i = 0; i < B; i++) {
        if (mp.count(P(sm, l2))) {
            rep = i-mp[P(sm, l2)];
            break;
        }
        mp[P(sm, l2)] = i;
        sm += l2; sm %= m;
        l2 *= l; l2 %= m;
    }
    if (rep == -1) {
        sm = 2*mt2[0][1] % m;
        l2 = 2*mt2[1][1] % m;
        for (ll i = 1;; i++) {
            ll sm2 = (mt[0][0]*sm + mt[0][1]*l2) % m;
            ll l22 = (mt[1][0]*sm + mt[1][1]*l2) % m;
            sm = sm2; l2 = l22;
            if (mp.count(P(sm, l2))) {
                rep = B * i - mp[P(sm, l2)];
                break;
            }
        }
    }
    ll ff;
    if (m == rep) {
        ff = f(fc+1, rep);
        for (ll i = fc+2; i <= n-1; i++) {
            mt[0][0] = 1; mt[0][1] = 1;
            mt[1][0] = 0; mt[1][1] = l % m;
            mt = mt.pow((2*10000*10000)/rep*rep+ff);
            ff = 2*mt[0][1] % m;
        }
    } else {
        ff = f(n-1, rep);
    }
    mt[0][0] = 1; mt[0][1] = 1;
    mt[1][0] = 0; mt[1][1] = l % m;
    mt = mt.pow((2*10000*10000)/rep*rep+ff);
    return 2*mt[0][1] % m;
}

bool solve(int c) {
    ll n, m;
    cin >> n >> m >> l;
    if (!n && !m && !l) return false;
    init();
    printf("Case %d: ", c);
    if (m == 1) {
        cout << 0 << endl;
        return true;
    }
    if (n == 0) {
        cout << 1 % m << endl;
        return true;
    }
    if (n == 1) {
        cout << l % m << endl;
        return true;
    }
    if (n <= fc) {
        printf("%lld\n", (2*pow_mod(l, fdp[n], m)+m-1)%m);
        return true;
    }
    cout << (2 * pow_mod(l, 2*totient(m)+f(n, totient(m)), m) + m-1) % m << endl;
    return true;
}

int main() {
    int c = 1;
    while (true) {
        if (!solve(c)) break;
        c++;
    }
    return 0;
}