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
Rahul Jain:
20140927 15:01:34
Please tell me why my code is giving WA,


albertg:
20140925 18:18:31
I'm using scanf/printf, my algorithm is O(logn), but I get TLE :( 

Rahul Jain:
20140925 10:56:34
Last edit: 20140928 10:01:49 

Amitayush Thakur:
20140828 14:23:25
Time limit very strict. 

Wonderwice Margera:
20140826 12:48:21
Could admin please take a look at submission id 12237897 and give some idea of what it is doing wrong? The code seemed to work properly in the cases I tried out.


johri:
20140730 22:07:41
any range for n bhavik .!


રચિત (Rachit):
20140714 09:41:19
isn't the time limit too strict for languages like python? 

785227:
20140702 18:21:34
Very good problem indeed :) 

.:frUstrAteD:.:
20140701 18:55:46
gud ques. need many optimizations


pika_pika:
20140630 19:02:39
strict time limit. Java using BufferedReader times out at test case #5. Last edit: 20140630 19:04:27 
Added by:  Bhavik 
Date:  20140628 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own 