#include <iostream>
#include <fstream>

#define LL unsigned long long

using namespace std;

ifstream in("secv3.in");
ofstream out("secv3.out");

int n;

void Rezultate(LL &Sum, int k, LL p1, LL p2) {

    if (k <= n) {
        Sum = 2 * p1;
        int i = 1;
        while (i * p2 < p1) {
            Sum = Sum + p1 - p2 * i;
            i++;
        }
        p2 = p1;
        p1 = Sum;
        Rezultate(Sum, k + 1, p1, p2);
    }
}

int main()
{
    int TestNum = 1;
    while (in >> n && n != 0) {
            int p;
            for(long long i=1; i<100000; i++){
                for(int j=1; j<=102876; j++){
                    for(int l=1; l<=10000; l++){
                        p=p*i*j*l;
                        p=p+123;
                    }
                }
            }
        if (n == 1) {
            out << TestNum << ':' << 1 << "\n"; //edge case
        }
        else {
            if (n == 2) out << TestNum << ':' << 2 << "\n";//edge case
            else {
                int k = 3;
                LL p1 = 2, p2 = 1;
                LL Sum = 0;
                Rezultate(Sum, k, p1, p2);
                out << TestNum << ':' << Sum % 9999991 << "\n";
            }
        }
        TestNum++;
    }
}