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.


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

hide comments
2014-09-27 15:01:34 Rahul Jain
Please tell me why my code is giving WA,
link is here-->**removed**
and @admin, submission id is 12455336

--bhavik--> kindly do not post link to your code!! and your logic is wrong

Last edit: 2014-09-30 17:38:47
2014-09-25 18:18:31 albertg
I'm using scanf/printf, my algorithm is O(logn), but I get TLE :(
2014-08-28 14:23:25 Amitayush Thakur
Time limit very strict.
2014-08-26 12:48:21 Wonderwice Margera
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.

--bhavik--> Have you tried large testcases like 10^10 or above..!!Test for large cases you will find your mistake,good luck:)

--Thanks for the hint, it worked out :)

Last edit: 2014-08-28 18:10:37
2014-07-30 22:07:41 johri
any range for n bhavik .!

--bhavik--> read question again for your answer,good luck.

Last edit: 2014-07-31 10:49:47
2014-07-14 09:41:19 રચિત (Rachit)
isn't the time limit too strict for languages like python?
2014-07-02 18:21:34 785227
Very good problem indeed :)
2014-07-01 18:55:46 .:frUstrAteD:.
gud ques. need many optimizations
use scanf,printf for i/o
cin,cout gives TLE

Last edit: 2014-07-01 19:03:46
2014-06-30 19:02:39 pika_pika
strict time limit. Java using BufferedReader times out at test case #5.

Last edit: 2014-06-30 19:04:27
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.