UVa Q10518

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

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

int n,m;
int cur[3][3], uni[3][3] = {{0,1,0},{1,1,0},{0,1,1}};
int ori[3] = {-1,1,1};

void self(){
    int des[3][3];
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            des[i][j] = 0;
            for(int k = 0; k < 3; ++k)des[i][j] += cur[i][k] * cur[k][j];
            des[i][j] %= m;
        }
    }
    memcpy(cur, des, sizeof(des));
}

void mode(){
    int des[3][3];
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j){
            des[i][j] = 0;
            for(int k = 0; k < 3; ++k)des[i][j] += cur[i][k] * uni[k][j];
            des[i][j] %= m;
        }
    }
    memcpy(cur, des, sizeof(des));
}

void mi(int val){
    if(val == 0 || val == 1){
        memcpy(cur, uni, sizeof(uni));
    }else if(val % 2 == 0){
        mi(val/2);
        self();
    }else{
        mi(val/2);
        self();
        mode();
    }
}

int32_t main(){
    int cnt = 0;
    while(cin >> n >> m){
        if(n == 0 && m == 0)break;
        mi(n);
        int ans[3] = {0};
        for(int i = 0; i < 3; ++i){
            for(int j = 0; j < 3; ++j){
                ans[i] += ori[j] * cur[j][i];
                ans[i] %= m;
            }
        }
        cout << "Case " << ++cnt << ": " << n << ' ' << m << ' ' << (ans[1]+m)%m << '\n';
    }
    return 0;
}