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
adi_tri:
20150802 12:14:57
Modular exponentiation..came to rescue..:)


Arun:
20150729 08:02:56
@admin:Could you please check submission id:14772457. the logic seems to be fine,still i am getting WA Last edit: 20150729 12:39:37 

The next big thing:
20150514 16:32:42
nice problem, but very strict Time limit 

Mercury:
20150205 16:23:45
Got TLE with cin and cout but using bit operations for power functions/divide/etc and scanf/printf got AC. 

Vamsi Krishna Avula:
20150117 19:42:28
good problem but @bhavik can you tell me why tl is so strict(strict as in strict for slow languages)?


himanshujaju:
20150114 11:00:53
strict TL. easy problem. 

Malinga:
20141230 19:09:48
@Bhavik : as you said leading zeros are allowed, can 3 be represented as 11, 011, 0011 , 00011 , 000011..... ??


Yashpal:
20141223 15:53:30
@Francky Awesome speed !! Have you minimized the use of modulo(%) operator ?


reddappa:
20141203 18:20:20
can u explain format of the input properly () any line separation btwn two inputs?


Knight:
20141020 19:28:45
@Bhavik

Added by:  Bhavik 
Date:  20140628 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own 