// Problem: 阅读理解
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4827/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define endl '\n'
#define Carol MyWife^=^
#define pb push_back
#define pp pop_back
#define debug1(x) cout << #x << " = " << (x) << '\n'
#define debug2(x) cout << #x << " = " << (x) << ' '
//#define x first
//#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6+5, M = 1e6+5;
const int INF = 0x3f3f3f3f;
int n, MOD;
int nmod(int x) {
    if(x < 0) x += MOD;
    if(x >= MOD) x -= MOD;
    return x;
}
template<class T>
T qpow(T a, LL b, LL p) {
    T res = 1;
    while(b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
struct Mint {
    int x;
    Mint(int x = 0) : x(nmod(x)) {}
    Mint(LL x) : x(nmod(x % MOD)) {}
    int val() const {
        return x;
    }
    Mint operator-() const {
        return Mint(nmod(MOD - x));
    }
    Mint inv() const {
        return qpow(*this, MOD - 2, MOD);
    }
    Mint &operator*=(const Mint &rhs) {
        x = LL(x) * rhs.x % MOD;
        return *this;
    }
    Mint &operator+=(const Mint &rhs) {
        x = nmod(x + rhs.x);
        return *this;
    }
    Mint &operator-=(const Mint &rhs) {
        x = nmod(x - rhs.x);
        return *this;
    }
    Mint &operator/=(const Mint &rhs) {
        return *this *= rhs.inv();
    }
    friend Mint operator*(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res *= rhs;
        return res;
    }
    friend Mint operator+(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res += rhs;
        return res;
    }
    friend Mint operator-(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res -= rhs;
        return res;
    }
    friend Mint operator/(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res /= rhs;
        return res;
    }
    friend istream &operator>>(istream &is, Mint &a) {
        LL v;
        is >> v;
        a = Mint(v);
        return is;
    }
    friend ostream &operator<<(ostream &os, const Mint &a) {
        return os << a.val();
    }
} ;
const int MN = 5;
struct Matrix {
    int n, m;
    Mint v[MN][MN];
    Matrix (int t = 0) {
        memset(v, 0, sizeof v);
        if(t == 1) {
            for(int i = 0; i <= n + 1; i ++)
                v[i][i] = 1;
        }
    }
    Matrix operator*(const Matrix& b) const {
        Matrix res;
        res.n = n, res.m = b.m;
        for(int k = 1; k <= m; k ++) 
            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= b.m; j ++)
                    res.v[i][j] += this->v[i][k] * b.v[k][j];
        return res;
    }
    Matrix operator^(LL b) {
        Matrix res = *this, a = *this;
        b --;
        while(b) {
            if(b & 1) res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }
} ;
void solve() {
    while(cin >> n >> MOD) {
        if(n == 1) {
            cout << 1 << endl;
            continue;
        }
        Matrix a, base;
        a.n = 1, a.m = 2;
        a.v[1][1] = 0, a.v[1][2] = 2;
        base.n = 2, base.m = 2;
        base.v[1][1] = 4, base.v[1][2] = 0;
        base.v[2][1] = 1, base.v[2][2] = 1;
        a = a * (base^(n/2));
        if(n % 2 == 0) cout << a.v[1][1] << endl;
        else if(n % 2 == 1) cout << a.v[1][1] * 2 + 1 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --) solve();

    return 0;
}

// Problem: 233矩阵
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/228/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define endl '\n'
#define Carol MyWife^=^
#define pb push_back
#define pp pop_back
#define debug1(x) cout << #x << " = " << (x) << '\n'
#define debug2(x) cout << #x << " = " << (x) << ' '
//#define x first
//#define y second
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6+5, M = 1e6+5;
const int MOD = 10000007, INF = 0x3f3f3f3f;
int nmod(int x) {
    if(x < 0) x += MOD;
    if(x >= MOD) x -= MOD;
    return x;
}
template<class T>
T qpow(T a, LL b, LL p) {
    T res = 1;
    while(b) {
        if(b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
struct Mint {
    int x;
    Mint(int x = 0) : x(nmod(x)) {}
    Mint(LL x) : x(nmod(x % MOD)) {}
    int val() const {
        return x;
    }
    Mint operator-() const {
        return Mint(nmod(MOD - x));
    }
    Mint inv() const {
        return qpow(*this, MOD - 2, MOD);
    }
    Mint &operator*=(const Mint &rhs) {
        x = LL(x) * rhs.x % MOD;
        return *this;
    }
    Mint &operator+=(const Mint &rhs) {
        x = nmod(x + rhs.x);
        return *this;
    }
    Mint &operator-=(const Mint &rhs) {
        x = nmod(x - rhs.x);
        return *this;
    }
    Mint &operator/=(const Mint &rhs) {
        return *this *= rhs.inv();
    }
    friend Mint operator*(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res *= rhs;
        return res;
    }
    friend Mint operator+(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res += rhs;
        return res;
    }
    friend Mint operator-(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res -= rhs;
        return res;
    }
    friend Mint operator/(const Mint &lhs, const Mint &rhs) {
        Mint res = lhs;
        res /= rhs;
        return res;
    }
    friend istream &operator>>(istream &is, Mint &a) {
        LL v;
        is >> v;
        a = Mint(v);
        return is;
    }
    friend ostream &operator<<(ostream &os, const Mint &a) {
        return os << a.val();
    }
} ;
const int MN = 105;
struct Matrix {
    int n, m;
    Mint v[MN][MN];
    Matrix (int t = 0) {
        memset(v, 0, sizeof v);
        if(t == 1) {
            for(int i = 0; i <= n + 1; i ++)
                v[i][i] = 1;
        }
    }
    Matrix operator*(const Matrix& b) const {
        Matrix res;
        res.n = n, res.m = b.m;
        for(int k = 1; k <= m; k ++) 
            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= b.m; j ++)
                    res.v[i][j] += this->v[i][k] * b.v[k][j];
        return res;
    }
    Matrix operator^(LL b) {
        Matrix res = *this, a = *this;
        b --;
        while(b) {
            if(b & 1) res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }
} ;
int n, m;
void solve() {
    while(cin >> n >> m) {
        Matrix a, base;
        a.n = 1, a.m = n + 2;
        for(int i = 2; i <= n + 1; i ++) {
            cin >> a.v[1][i];
        }
        a.v[1][1] = 23, a.v[1][n + 2] = 1;
        base.n = n + 2, base.m = n + 2;
        for(int i = 1; i <= n + 1; i ++) base.v[1][i] = 10;
        for(int i = 2; i <= n + 1; i ++)
            for(int j = 2; j <= n + 1; j ++)
                if(j >= i) base.v[i][j] = 1;
        for(int i = 1; i <= n + 1; i ++) base.v[n + 2][i] = 3;
        base.v[n + 2][n + 2] = 1;
        Matrix b = (base^m);
        cout << (a * b).v[1][n + 1] << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while(t --) solve();

    return 0;
}

#include <iostream>
using namespace std;

const int N = 200010;
const int _l = -1e9, _r = 1e9;
struct Node {
    int l, r;
    int cnt;
} tr[N * 35];
int root[N], idx;
int w[N], n, q, x;
void insert(int p, int &q, int l, int r, int pos, int v) {
    tr[q = ++ idx] = tr[p];
    tr[q].cnt += v;
    if(l == r) return ;
    int mid = l + r >> 1;
    if(pos <= mid) insert(tr[p].l, tr[q].l, l, mid, pos, v);
    else insert(tr[p].r, tr[q].r, mid + 1, r, pos, v);
}
int query(int p, int q, int l, int r, int k) {
    if(l == r) return l;
    int lcnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt;
    int mid = l + r >> 1;
    if(lcnt >= k) return query(tr[p].l, tr[q].l, l, mid, k);
    else return query(tr[p].r, tr[q].r, mid + 1, r, k - lcnt);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) {
        cin >> x;
        insert(root[i - 1], root[i], _l, _r, x, 1);
    }
    while(q --) {
        int l, r, k;
        cin >> l >> r >> k;
        cout << query(root[l - 1], root[r], _l, _r, k) << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int _l = -1e9, _r = 1e9;
const int N = 100010;
struct Node {
    int l, r;
    int mx;
}tr[N * 32];
int idx, root;
int n, a[N], ans[N];
void insert(int& p, int l, int r, int x, int v) {
    if (!p) p = ++idx;
    tr[p].mx = max(tr[p].mx, v);
    if (l == r) return;
    int mid = l + r >> 1;
    if (x <= mid) insert(tr[p].l, l, mid, x, v);
    else insert(tr[p].r, mid + 1, r, x, v);
}

int query(int p, int l, int r, int ql, int qr) {
    if (!p) return 0;
    if (l >= ql && r <= qr) return tr[p].mx;
    int mid = l + r >> 1, res = 0;
    if (ql <= mid) res = max(res, query(tr[p].l, l, mid, ql, qr));
    if (qr > mid) res = max(res, query(tr[p].r, mid + 1, r, ql, qr));
    return res;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    for(int i = n; i; i --) {
        int x = query(root, _l, _r, 1, a[i] - 1);
        if(x > i) ans[i] = x - i - 1;
        else ans[i] = -1;
        insert(root, _l, _r, a[i], i);
    }
    for(int i = 1; i <= n; i ++) {
        cout << ans[i] << " \n"[i == n];
    }

    return 0;
}

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

typedef long long LL;

const int N = 101000;
int n, m, p;
LL a[N];
struct Seg {
    LL val;
    LL add, mul;
    LL siz;
} tr[N<<2];
void pushup(int u) {
    tr[u].val = (tr[u << 1].val + tr[u << 1 | 1].val) % p;
}
void update(Seg &t, LL add, LL mul) {
    t.mul = (t.mul * mul) % p;
    t.add = (t.add * mul + add) % p;
    t.val = (t.val * mul + add * (t.siz)) % p;
}
void pushdown(int u) {
    update(tr[u<<1], tr[u].add, tr[u].mul);
    update(tr[u<<1 | 1], tr[u].add, tr[u].mul);
    tr[u].mul = 1;
    tr[u].add = 0;
}
void build(int u, int l, int r) {
    tr[u] = {a[l], 0, 1, r - l + 1};
    if(l == r) {
        return ;
    } else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
LL query(int u, int l, int r, int ql, int qr) {
    if(l >= ql && r <= qr) return tr[u].val;
    else {
        pushdown(u);
        int mid = l + r >> 1;
        LL sum = 0;
        if(ql <= mid) sum += query(u << 1, l, mid, ql, qr);
        if(qr > mid) sum += query(u << 1 | 1, mid + 1, r, ql, qr);
        return sum % p;
    }
}
LL modify(int u, int l, int r, int ql, int qr, int add, int mul) {
    if(l >= ql && r <= qr) {
        update(tr[u], add, mul);
    } else {
        pushdown(u);
        int mid = l + r >> 1;
        if(ql <= mid) modify(u << 1, l, mid, ql, qr, add, mul);
        if(qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, add, mul);
        pushup(u);
    }
}
signed main() {
    cin >> n >> p;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i];
    }
    build(1, 1, n);
    cin >> m;
    while(m --) {
        int opt, l, r, x;
        cin >> opt >> l >> r;
        if(opt <= 2) {
            cin >> x;
            if(opt == 1) modify(1, 1, n, l, r, 0, x);
            else modify(1, 1, n, l, r, x, 1);
        } else {
            cout << query(1, 1, n, l, r) % p << endl;
        }
    }

    return 0;
}

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

const int N = 1e6+5;

int nxt[N], n;
char s[N];

int main() {
    while(cin >> s + 1) {
        n = strlen(s + 1);
        for(int i = 2; i <= n; i ++) {
            int j = nxt[i - 1];
            while(j && s[i] != s[j + 1]) j = nxt[j];
            if(s[i] == s[j + 1]) j ++;
            nxt[i] = j;
        }
        vector<int> ans;
        for(int i =  n; i; i = nxt[i]) {
            ans.push_back(i);
        }
        for(int i = ans.size() - 1; ~i; i --)
            cout << ans[i] << " \n"[i == 0];
    }
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, nxt[N];
char s[N];
int main() {
    while(cin >> s + 1) {
        n = strlen(s + 1);
        if(n == 1 && s[1] == '.') break;
        for(int i = 2; i <= n; i ++) {
            int j = nxt[i - 1];
            while(j && s[i] != s[j + 1]) j = nxt[j];
            if(s[i] == s[j + 1]) j ++;
            nxt[i] = j;
        }
        for(int i = n; i; i = nxt[i]) {
            if(n % (n - nxt[i]) == 0) {
                cout << n / (n - nxt[i]) << endl;
                break;
            }
        }
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int nxt[N], n;
char s[N];
int main() {
    while(cin >> s + 1) {
        n = strlen(s + 1);
        for(int i = 2; i <= n; i ++) {
            int j = nxt[i - 1];
            while(j && s[i] != s[j + 1]) j = nxt[j];
            if(s[i] == s[j + 1]) j ++;
            nxt[i] = j;
        }
        cout << n  - nxt[n] << endl;
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n, nxt[N], Case;
string s;
vector<int> v;
int main() {
    while(cin >> n && n) {
        cin >> s;
        s = " " + s;
        for(int i = 2; i <= n; i ++) {
            int j = nxt[i - 1];
            while(j && s[i] != s[j + 1]) j = nxt[j];
            if(s[i] == s[j + 1]) j ++;
            nxt[i] = j;
        }
        cout << "Test case #" << ++ Case << endl;
        for(int i = 1; i <= n; i ++) {
            int t = i - nxt[i];
            if(i % t == 0 && i / t > 1) {
                cout << i << ' ' << i / t << endl;
            }
        }
        cout << endl;
    }

    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
string s;
int nxt[N];
int main() {
    int T;
    cin >> T;
    while(T --) {
        cin >> s;
        int n = s.size();
        s =  " " + s;
        nxt[1] = 0;
        for(int i = 2; i <= n; i ++) {
           int j = nxt[i - 1];
           while(j && s[i] != s[j + 1]) j = nxt[j];
           if(s[i] == s[j + 1]) j ++;
           nxt[i] = j;
        }
        int ans = n;
        for(int i = nxt[n]; i; i = nxt[i]) {
            int p = n - i;
            if(n % p == 0) ans = 0;
            ans = min(ans, p - n%p);
        }
        cout << ans << endl;
    }

    return 0;
}