题目链接
大致看了一下，网上的题解大多数是用的逆元做的，今天受lyd蓝书的启发，发现用分治也可以做这个。
首先，我们设(F(n) = 3^0 + 3^1 + 3^2 + ... + 3^n)。
1.如果n为奇数：
(F(n) = (3^0 + 3^1 + 3^2 ... + 3^{frac{n-1}{2}}) + (3^{frac{n+1}{2}} + ... + 3^n))
进一步可得：
(F(n) = (3^0 + 3^1 + 3^2 ... + 3^{frac{n-1}{2}}) + 3^{frac{n+1}{2}} imes(3^0 + 3^1 + 3^2 + ... + 3^{frac{n-1}{2}}) = (1 + 3^{frac{n+1}{2}}) imes F(frac{n-1}{2}))。
2.如果n为偶数怎么办呢？那么我们发现好像不太好处理的样子，但是！我们可以从多项式里面排除一个数让项数变成奇数！就是这么狠(我们令(F(n) = (3^0 + 3^1 + 3^2 ... + 3^{frac{n}{2}-1}) + (3^{frac{n}{2}} + ... + 3^{n-1}) + 3^n)然后和第1条的方法同理提出来(3^{frac{n}{2}})就可以得到(F(n)= (1 + 3^{frac{n}{2}})
imes F(frac{n}{2}-1) + 3^n)。
3.最后我们来考虑一下递归的终点，设x为函数递归终点前传入的参数，如果x为0的话，显然(F(0) = 1)。如果x大于0，若x为奇数，那么(frac{x-1}{2})最小等于0(x取1)。若x为偶数，那么(frac{x}{2}-1)最小也为0(x取2)所以说我们的函数的递归终点就是(F(0) = 1)。
4.关于时间复杂度。我们可以看到每次我们递归之后计算量就减少了一半，所以时间复杂度是(O(lg(n)))。
//https://www.cnblogs.com/shuitiangong/
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<string>
#include<vector>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define endl '
'
#define rtl rt<<1
#define rtr rt<<1|1
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define maxx(a, b) (a > b ? a : b)
#define minn(a, b) (a < b ? a : b)
#define zero(a) memset(a, 0, sizeof(a))
#define INF(a) memset(a, 0x3f, sizeof(a))
#define IOS ios::sync_with_stdio(false)
#define _test printf("==================================================
")
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> P2;
const double pi = acos(-1.0);
const double eps = 1e-7;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const int _NAN = -0x3f3f3f3f;
const double EULC = 0.5772156649015328;
const int NIL = -1;
template<typename T> void read(T &x){
x = 0;char ch = getchar();ll f = 1;
while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
const int maxn = 1e5+10;
int n;
ll solve2(int y) {
ll ans = 1, res = 3;
while(y) {
if (y&1) ans = ans*res%MOD;
res = res*res%MOD;
y >>= 1;
}
return ans%MOD;
}
ll solve(int n) {
if (!n) return 1;
ll fac = 1;
if (n&1) fac = fac*(1+solve2(n/2+1))%MOD*solve(n>>1)%MOD;
//因为C语言默认除法是向下取整的，所以n为奇数的时候n/2+1和(n+1)/2结果相等，这里只是为了打着方便，n>>1同理
else fac = fac*((solve2(n) + (1+solve2(n>>1))*solve(n/2-1)%MOD)%MOD)%MOD;
return fac;
}
int main(void) {
IOS;
while(cin >> n)
cout << solve(n) << endl;
return 0;
}