#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const LL mod = 1000009;

LL brute(LL n) {
    LL X = 0;
    for(LL i = 1; i <= n; i++) {
        X += i * (n/i) % mod;
        X %= mod;
    }
    X -= (n-1);
    X %= mod;
    if(X < 0) X += mod;
    LL sub = n*(n+1)/2;
    sub %= mod;
    X -= sub;
    X %= mod;
    if(X < 0) X += mod;

    if(X == 0) return 0;
    LL res = 0;
    for(LL i = 2; i * i <= X; i++) {
        while(X % i == 0) {
            X /= i;
            res += i;
            res %= mod;
        }
    }
    if(X > 1) res += X;
    res %= mod;
    return res;
}


LL SUM(LL l, LL r) {
    LL n = r-l+1, t = (l+r);
    if(n%2 == 0) n /= 2;
    else t /= 2;
    return ((n%mod)*(t%mod))%mod;
}

int main() {
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);

    int tc = 1000;
//    cin >> tc;
    int caseno = 1;
    while(tc--) {
        LL n = 2000000000000;
//        cin >> n;
        if(n == 0) {
            LL res = 0;
            cout << "Case " << caseno++ << ": " << res << endl;
        }
        else {

            LL l, r;
            LL X = 0;
            for(LL i = 1; i <= n; i = r + 1) {
                l = i, r = n / (n / i);
                LL c = n/i-1;
                c %= mod;
                X += c*SUM(l, r)%mod;
                X %= mod;
            }

            X -= (n-1)%mod;
            X %= mod;
            if(X < 0) X += mod;
            LL res = 0;
//            assert(X < mod && X >= 0);
            if(X > 1) {
                assert(X < mod && X > 1);
                for(LL i = 2; i * i <= X; i++) {
                    while(X % i == 0) {
                        res += i;
                        res %= mod;
                        X /= i;
                    }
                }
                if(X > 1) res += X;
                res %= mod;
            }
            assert(res >= 0);
//            assert(brute(n) == res);
            cout << "Case " << caseno++ << ": " << res << endl;
        }
    }
}