#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_MAT = 2;
const long long mod = 1e9 + 7;
struct Mat
{
    ll a[MAX_MAT][MAX_MAT];
    Mat()
    {
        for (int i = 0; i < MAX_MAT; ++i)
        {
            for (int j = 0; j < MAX_MAT; ++j)
            {
                a[i][j] = 0;
            }
        }
        for (int i = 0; i < MAX_MAT; ++i)
        {
            a[i][i] = 1;
        }
    }
};
long long quickpow(long long x, long long y, long long MOD = 9223372036854775807LL)
{
    long long ans = 1;
    while (y)
    {
        if (y & 1)
        {
            ans = (x * ans) % MOD;
        }
        x = (x * x) % MOD;
        y >>= 1;
    }
    return ans;
}
ll get_inv(ll x)
{
    return quickpow(x, mod - 2, mod);
}
ll A[MAX_MAT][MAX_MAT << 1];
void row_minus(int a, int b, ll k)
{
    for (int i = 0; i < 2 * MAX_MAT; ++i)
    {
        A[a][i] = (A[a][i] - A[b][i] * k % mod) % mod;
        if (A[a][i] < 0)A[a][i] += mod;
    }
    return;
}
void row_multiplies(int a, ll k)
{
    for (int i = 0; i < 2 * MAX_MAT; ++i)
    {
        A[a][i] = (A[a][i] * k) % mod;
    }
    return;
}
void row_swap(int a, int b)
{
    for (int i = 0; i < 2 * MAX_MAT; ++i)
    {
        swap(A[a][i], A[b][i]);
    }
}
Mat getinv(Mat x)
{
    memset(A, 0, sizeof(A));
    for (int i = 0; i < MAX_MAT; ++i)
    {
        for (int j = 0; j < MAX_MAT; ++j)
        {
            A[i][j] = x.a[i][j];
            A[i][MAX_MAT + j] = i == j;
        }
    }
    for (int i = 0; i < MAX_MAT; ++i)
    {
        if (!A[i][i])
        {
            for (int j = i + 1; j < MAX_MAT; ++j)
            {
                if (A[j][i])
                {
                    row_swap(i, j);
                    break;
                }
            }
        }
        row_multiplies(i, get_inv(A[i][i]));
        for (int j = i + 1; j < MAX_MAT; ++j)
        {
            row_minus(j, i, A[j][i]);
        }
    }
    for (int i = MAX_MAT - 1; i >= 0; --i)
    {
        for (int j = i - 1; j >= 0; --j)
        {
            row_minus(j, i, A[j][i]);
        }
    }
    Mat ret;
    for (int i = 0; i < MAX_MAT; ++i)
    {
        for (int j = 0; j < MAX_MAT; ++j)
        {
            ret.a[i][j] = A[i][MAX_MAT + j];
        }
    }
    return ret;
}

Mat operator * (Mat x, Mat y)
{
    Mat c;
    for (int i = 0; i < MAX_MAT; ++i) {
        for (int j = 0; j < MAX_MAT; ++j) {
            c.a[i][j] = 0;
        }
    }
    for (int i = 0; i < MAX_MAT; ++i) {
        for (int j = 0; j < MAX_MAT; ++j) {
            for (int k = 0; k < MAX_MAT; ++k) {
                c.a[i][j] = (c.a[i][j] + x.a[i][k] * y.a[k][j] % mod) % mod;
            }
        }
    }
    return c;
}