#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
struct mat {
vector<vector<ll>> m;
ll sz;
mat(ll _sz = 2, ll v = 0) {
sz = _sz;
m = vector<vector<ll>> (sz, vector<ll> (sz, v));
}
mat(vector<vector<ll>> _m) {
m = _m;
}
vector<ll>& operator[](size_t x) {
return m[x];
}
friend mat operator+(mat& a, mat& b) {
mat res(a.m);
for (int i = 0 ; i < a.sz ; i ++) {
for (int j = 0 ; j < a.sz ; j ++) {
res[i][j] += b[i][j];
if (res[i][j] >= mod) res[i][j] -= mod;
}
}
return res;
}
friend mat operator*(mat& a, mat& b) {
mat res(a.sz);
for (int i = 0 ; i < a.sz ; i ++) {
for (int j = 0 ; j < a.sz ; j ++) {
for (int k = 0 ; k < a.sz ; k ++) {
(res.m[i][j] += a.m[i][k] * b.m[k][j] % mod) %= mod;
}
}
}
return res;
}
inline void operator*=(mat& b) {
mat res(sz);
for (int i = 0 ; i < sz ; i ++) {
for (int j = 0 ; j < sz ; j ++) {
for (int k = 0 ; k < sz ; k ++) {
(res.m[i][j] += m[i][k] * b.m[k][j] % mod) %= mod;
}
}
}
m.swap(res.m);
}
};
inline mat pw(mat& a, ll b) {
if (b == 0) return mat();
mat res = a;
for (b -- ; b ; b >>= 1, a *= a) {
if (b & 1) res *= a;
}
return res;
}
int main() {
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnR5cGVkZWYgbG9uZyBsb25nIGxsOwoKY29uc3QgbGwgbW9kID0gMWU5ICsgNzsKCnN0cnVjdCBtYXQgewogIHZlY3Rvcjx2ZWN0b3I8bGw+PiBtOwogIGxsIHN6OwogIAogIG1hdChsbCBfc3ogPSAyLCBsbCB2ID0gMCkgewogICAgc3ogPSBfc3o7CiAgICBtID0gdmVjdG9yPHZlY3RvcjxsbD4+IChzeiwgdmVjdG9yPGxsPiAoc3osIHYpKTsKICB9CgogIG1hdCh2ZWN0b3I8dmVjdG9yPGxsPj4gX20pIHsKICAgIG0gPSBfbTsKICB9CgogIHZlY3RvcjxsbD4mIG9wZXJhdG9yW10oc2l6ZV90IHgpIHsKICAgIHJldHVybiBtW3hdOwogIH0KCiAgZnJpZW5kIG1hdCBvcGVyYXRvcisobWF0JiBhLCBtYXQmIGIpIHsKICAgIG1hdCByZXMoYS5tKTsKICAgIGZvciAoaW50IGkgPSAwIDsgaSA8IGEuc3ogOyBpICsrKSB7CiAgICAgIGZvciAoaW50IGogPSAwIDsgaiA8IGEuc3ogOyBqICsrKSB7CiAgICAgICAgcmVzW2ldW2pdICs9IGJbaV1bal07CiAgICAgICAgaWYgKHJlc1tpXVtqXSA+PSBtb2QpIHJlc1tpXVtqXSAtPSBtb2Q7CiAgICAgIH0KICAgIH0KICAgIHJldHVybiByZXM7CiAgfQoKICBmcmllbmQgbWF0IG9wZXJhdG9yKihtYXQmIGEsIG1hdCYgYikgewogICAgbWF0IHJlcyhhLnN6KTsKICAgIGZvciAoaW50IGkgPSAwIDsgaSA8IGEuc3ogOyBpICsrKSB7CiAgICAgIGZvciAoaW50IGogPSAwIDsgaiA8IGEuc3ogOyBqICsrKSB7CiAgICAgICAgZm9yIChpbnQgayA9IDAgOyBrIDwgYS5zeiA7IGsgICsrKSB7CiAgICAgICAgICAocmVzLm1baV1bal0gKz0gYS5tW2ldW2tdICogYi5tW2tdW2pdICUgbW9kKSAlPSBtb2Q7CiAgICAgICAgfQogICAgICB9CiAgICB9CiAgICByZXR1cm4gcmVzOwogIH0KICBpbmxpbmUgdm9pZCBvcGVyYXRvcio9KG1hdCYgYikgewogICAgbWF0IHJlcyhzeik7CiAgICBmb3IgKGludCBpID0gMCA7IGkgPCBzeiA7IGkgKyspIHsKICAgICAgZm9yIChpbnQgaiA9IDAgOyBqIDwgc3ogOyBqICsrKSB7CiAgICAgICAgZm9yIChpbnQgayA9IDAgOyBrIDwgc3ogOyBrICArKykgewogICAgICAgICAgKHJlcy5tW2ldW2pdICs9IG1baV1ba10gKiBiLm1ba11bal0gJSBtb2QpICU9IG1vZDsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIG0uc3dhcChyZXMubSk7CiAgfQoKfTsKCmlubGluZSBtYXQgcHcobWF0JiBhLCBsbCBiKSB7CiAgaWYgKGIgPT0gMCkgcmV0dXJuIG1hdCgpOwogIG1hdCByZXMgPSBhOwogIGZvciAoYiAtLSA7IGIgOyBiID4+PSAxLCBhICo9IGEpIHsKICAgIGlmIChiICYgMSkgcmVzICo9IGE7CiAgfQogIHJldHVybiByZXM7Cn0KCmludCBtYWluKCkgewoKfQ==