题目链接：

题目大意：求0~2ⁿ-1 中有多少个数字能被3整除（包括0 和2ⁿ-1）。 n <= 2e18, 答案对 mod = 1e9 + 7取余。

解题思路：通过分析可以发现个数是 (2ⁿ / 3 + 1) % mod . 那么关键问题就是如何快速计算 2ⁿ / 3 % mod 。

由于n比较大，所以可以使用快速幂取模进行计算。然而，尽管a / b % c 可以通过逆元来计算，但前提是a整除b并且逆元存在。这里3关于mod 的逆元确实存在（互质），2ⁿ 却无法整除3，那么如何解决这个问题呢？

能够发现 2ⁿ % 3 = 1 或 2，并且当且仅当n为奇数为2，n为偶数为1。那么我们就可以将 2ⁿ / 3 % mod 转化成 2ⁿ - (n & 1? 2: 1) / 3 % mod.这样两者就能够整除了，从而也就可以采用快速幂取模计算了。

代码：

1 ll n; 2 ll x; 3  4 ll ext_gcd(ll a, ll b, ll &d, ll &x, ll &y){ 5     if(b!= 0){ 6         ext_gcd(b, a % b, d, y, x); 7         y -= x * (a / b); 8     } 9     else{10         d = a; x = 1; y = 0;11     }12 }13 void dowork(){14     ll d, y;15     ext_gcd(3, mod, d, x, y);16     if(x < 0) x = x + (abs(x) / mod + 1) * mod;17 }18 ll pow_mod(ll a, ll b){19     if(b == 0) return 1;20     ll tmans = pow_mod(a, b / 2);21     ll ans = tmans * tmans % mod;22     if(b & 1) ans = a % mod * ans;23     return ans;24 }25 void solve(){26     ll ans = pow_mod(2, n);27     ans = ans * x % mod;28     ans = (ans - ((n & 1? 2: 1) * x) % mod) % mod; 29     if(ans < 0) ans = (abs(ans) / mod + 1) * mod + ans;30     ans = (ans + 1) % mod;31     printf("%lld\n", ans);32 }33 int main(){34     dowork();35     while(scanf("%lld", &n) != EOF){36         solve();37     }38 }

题目：

DIVISION - Divisiblity by 3

 

 

 

Divisiblity by 3 rule is pretty simple rule:Given a number n sum the 

digits of n and check if sum is divisible by 3.If divisible then n is 

divisible by 3 else not divisible.

Seems pretty simple but what if we want to extend this rule in binary 

representation!! Given a binary representation we can again find if it is 

divisible by 3 or not.

Making it little bit interesting what if only length of binary 

representation of a number is given say n.Can we find how many numbers 

exist in decimal form such that when converted into binary form has n 

length and is divisible by 3 ??

Divisiblity by 3 rule is pretty simple rule: Given a number sum the digits of number and check if sum is divisible by 3.If divisible then it is divisible by 3 else not divisible.Seems pretty simple but what if we want to extend this rule in binary representation!!

Given a binary representation we can again find if it is divisible by 3 or not. Making it little bit interesting what if only length of binary representation of a number is given say n.

Now can we find how many numbers exist in decimal form(base 10) such that when converted into binary(base 2) form has n length and is divisible by 3 ?? (1 <= n < 2*10^18)

 

Input

 Length of binary form: n

output

Print in new line the answer modulo 1000000007.

Example

Input:1

2

Output:1

2

Explanation: For n=2 there are only 2 numbers divisible by 3 viz.0 (00) and 3 (11) and having length 2 in binary form.

NOTE:There are multiple testfiles containing many testcases each so read till EOF.

Warnings: Leading zeros are allowed in binary representation and slower languages might require fast i/o. Take care.