public class Pow {
long pow(long n, long pow){
    long res = 1;
    while(n != 0){
        if((pow&1) != 0){
            res*=n;
        }
        n*=n;
        pow>>=1;
    }
    return res;
}

long psum(long n, long pow){
    if(pow == 0){
        return 1;
    }
    if(pow == 1){
        return n;
    }
    if(pow % 2 == 0){
        return psum(n, pow / 2) * (1 + pow(n, pow/2));
    }else{
        return n + (psum(n, pow-1) * n);
    }
}

long[][] mpsum(long[][] a, long k) 
    { 
        if (k == 0) { 
            return munit(a.length); 
        } 
        if (k == 1) { 
            return a; 
        } 
        if (k % 2 == 0) 
        { 
            return mmul(mpsum(a, k / 2), madd(munit(a.length), mpow(a, k / 2))); 
        } 
        else 
        { 
            return madd(a, mmul(mpsum(a, k - 1), a)); 
        } 
    } 

long[][] mpow(long[][] a, long k){ 
        if (k == 0){ 
            return munit(a.length);
        }
        else if (k % 2 == 0){ 
            return mpow(mmul(a, a), k / 2); 
        } 
        else{ 
            return mmul(a, mpow(a, k - 1)); 
        } 
    } 

    long[][] mmul(long[][] a, long[][] b){ 
        long[][] c = new long[a.length][b[0].length]; 
        for (int i = 0; i < a.length; ++i){ 
            for (int j = 0; j < b[0].length; ++j){ 
                long z = 0; 
                for (int k = 0; k < a[0].length; ++k){ 
                    z += a[i][k] * b[k][j]; 
                } 
                c[i][j] = z; 
            }
        }
        return c; 

    } 

    private long[][] madd(long[][] a, long[][] b){ 
        long[][] c = new long[a.length][a[0].length]; 
        for (int i = 0; i < a.length; ++i){ 
            for (int j = 0; j < a[0].length; ++j){ 
                c[i][j] = (a[i][j] + b[i][j]); 
            }
        }
        return c; 
    } 

    long[][] munit(int size){ 
        long[][] res = new long[size][size]; 
        for (int i = 0; i < size; ++i) 
            res[i][i] = 1; 
        return res; 
    } 

}