#include <stdio.h>
#define MOD 1000000007ULL
unsigned long long a[2], temp[2], b[2][2], temp1[2][2], n;
void solve()
{
a[0] = 2;
a[1] = 1;
b[0][0] = 2;
b[0][1] = 1;
b[1][0] = 1;
b[1][1] = 1;
while(n>0)
{
if(n&1)
{
temp[0] = a[0]*b[0][0] + a[1]*b[1][0];
temp[1] = a[0]*b[0][1] + a[1]*b[1][1];
a[0] = temp[0]%MOD;
a[1] = temp[1]%MOD;
}
temp1[0][0] = b[0][0]*b[0][0] + b[0][1]*b[1][0];
temp1[0][1] = b[0][0]*b[0][1] + b[0][1]*b[1][1];
temp1[1][0] = b[1][0]*b[0][0] + b[1][1]*b[1][0];
temp1[1][1] = b[1][0]*b[0][1] + b[1][1]*b[1][1];
b[0][0] = temp1[0][0]%MOD;
b[0][1] = temp1[0][1]%MOD;
b[1][0] = temp1[1][0]%MOD;
b[1][1] = temp1[1][1]%MOD;
n = n>>1;
}
}
int main()
{
unsigned int t;
while(t--)
{
n = n - 1ULL;
solve();
printf("%llu\n", (a
[0]*a
[1])%MOD
); }
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgTU9EIDEwMDAwMDAwMDdVTEwKCnVuc2lnbmVkIGxvbmcgbG9uZyBhWzJdLCB0ZW1wWzJdLCBiWzJdWzJdLCB0ZW1wMVsyXVsyXSwgbjsKCnZvaWQgc29sdmUoKQp7CglhWzBdID0gMjsKCWFbMV0gPSAxOwoJYlswXVswXSA9IDI7CgliWzBdWzFdID0gMTsKCWJbMV1bMF0gPSAxOwoJYlsxXVsxXSA9IDE7Cgl3aGlsZShuPjApCgl7CgkJaWYobiYxKQoJCXsKCQkJdGVtcFswXSA9IGFbMF0qYlswXVswXSArIGFbMV0qYlsxXVswXTsKCQkJdGVtcFsxXSA9IGFbMF0qYlswXVsxXSArIGFbMV0qYlsxXVsxXTsKCQkJYVswXSA9IHRlbXBbMF0lTU9EOwoJCQlhWzFdID0gdGVtcFsxXSVNT0Q7CgkJfQoJCXRlbXAxWzBdWzBdID0gYlswXVswXSpiWzBdWzBdICsgYlswXVsxXSpiWzFdWzBdOwoJCXRlbXAxWzBdWzFdID0gYlswXVswXSpiWzBdWzFdICsgYlswXVsxXSpiWzFdWzFdOwoJCXRlbXAxWzFdWzBdID0gYlsxXVswXSpiWzBdWzBdICsgYlsxXVsxXSpiWzFdWzBdOwoJCXRlbXAxWzFdWzFdID0gYlsxXVswXSpiWzBdWzFdICsgYlsxXVsxXSpiWzFdWzFdOwoJCWJbMF1bMF0gPSB0ZW1wMVswXVswXSVNT0Q7CgkJYlswXVsxXSA9IHRlbXAxWzBdWzFdJU1PRDsKCQliWzFdWzBdID0gdGVtcDFbMV1bMF0lTU9EOwoJCWJbMV1bMV0gPSB0ZW1wMVsxXVsxXSVNT0Q7CgkJbiA9IG4+PjE7Cgl9Cn0KCmludCBtYWluKCkKewoJdW5zaWduZWQgaW50IHQ7CglzY2FuZigiJXUiLCAmdCk7Cgl3aGlsZSh0LS0pCgl7CgkJc2NhbmYoIiVsbGQiLCAmbik7CgkJbiA9IG4gLSAxVUxMOwoJCXNvbHZlKCk7CgkJcHJpbnRmKCIlbGx1XG4iLCAoYVswXSphWzFdKSVNT0QpOwoJfQp9