DIVISION  Divisiblity 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.
hide comments
klu_70163:
20190211 08:16:17
what is the code 

nadstratosfer:
20180401 07:22:29
AC in Python depends more on luck than anything else. If TLE, resubmit another 10 times, perhaps you'll get lucky. TL carefully set to prevent us passing with a for loop counting numbers up to 2^(10^18). </sarcasm>


vish_14:
20170817 03:21:53
TLE in python cost me 4 submission.


candide:
20170421 19:13:44
Good problem to play with C optimisations. AC in Python. Nevertheless, description could be better, even the title contains a typo. The sentence "numbers in decimal form(base 10) such that when converted into binary(base 2) ..." is misleading and meaningless: does my age change if written in binary vs decimal ? Definition of the lenght of a binary representation is unexpected as it allows for instance 100101 to have length 42 instead of 6. Input format is unclear. Last edit: 20170421 21:23:45 

mkfeuhrer:
20160617 11:57:43
good problem !! had to thnk a lot.... basically see for few starting cases .....ull get the answer!! use modular exponention :) 

Piyush Kumar:
20160616 16:58:07
The time limit is unnecessarily strict! 

prakash_reddy:
20160117 20:04:40
very easy if u know modular exponentiation...... 

Thotsaphon Thanatipanonda:
20151003 16:26:40
Finally I can solve this problem using Java with I/O optimization and reduce number of modulo. :D 

Rahul yadav:
20150918 15:22:48
nice question


Parul Yadav:
20150905 18:26:08
use scanf/printf 
Added by:  Bhavik 
Date:  20140628 
Time limit:  0.132s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own 