#define repf(i,a,b) for(int i=(a);i<=(b);i++)using namespace std;typedef long long ll;const int N = 0;const int SIZE = 4;int l, MOD;struct Mat{    ll v[SIZE][SIZE];   // value of matrix    Mat() {        memset(v, 0, sizeof(v));    }    void init(ll _v) {        repf (i, 0, SIZE)            v[i][i] = _v;    }};Mat operator * (Mat a, Mat b) {    Mat c;    repf (i, 0, SIZE - 1) {        repf (j, 0, SIZE - 1) {            c.v[i][j] = 0;            repf (k, 0, SIZE - 1) {                c.v[i][j] += (a.v[i][k] * b.v[k][j]) % MOD;                c.v[i][j] %= MOD;            }        }    }    return c;}Mat operator ^ (Mat a, ll k) {    Mat c;    c.init(1);    while (k) {        if (k&1) c = a * c;        a = a * a;        k >>= 1;    }    return c;}