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
2015-08-02 12:14:57
Modular exponentiation..came to rescue..:)
2015-07-29 08:02:56 Arun
@admin:Could you please check submission id:14772457. the logic seems to be fine,still i am getting WA

Last edit: 2015-07-29 12:39:37
2015-05-14 16:32:42 The next big thing
nice problem, but very strict Time limit
2015-02-05 16:23:45 Mercury
Got TLE with cin and cout but using bit operations for power functions/divide/etc and scanf/printf got AC.
2015-01-17 19:42:28 Vamsi Krishna Avula
good problem but @bhavik can you tell me why tl is so strict(strict as in strict for slow languages)?

@Vamsi: i know TL is strict for slow languages..i will take care in my next problem(s)..

@admins:i am not sure but i am guessing this is the work of spoj admins/moderators who rejudged the solution and also time limit(from 1s to 0.132 sec)!!Kindly help me with this development..

re(vamsi): thanks @bhavik, looks like some test file(s) are removed.

Last edit: 2015-02-25 17:20:22
2015-01-14 11:00:53 himanshujaju
strict TL. easy problem.
2014-12-30 19:09:48 Malinga
@Bhavik : as you said leading zeros are allowed, can 3 be represented as 11, 011, 0011 , 00011 , 000011..... ??

--bhavik-->yes they are allowed for n=2,3,4,5...respectively.

Last edit: 2014-12-31 15:53:11
2014-12-23 15:53:30 Yashpal
@Francky Awesome speed !! Have you minimized the use of modulo(%) operator ?
--ans(Francky)--> Yes. It's true, I use only 3 % per case. (except IO)
--Re(Yashpal)--> I have actually used modulo exponentiation which uses O(logn) modulo(%) operator. How could i avoid it ??

Last edit: 2014-12-23 18:44:05
2014-12-03 18:20:20 reddappa
can u explain format of the input properly () any line separation btwn two inputs?

--ans(Francky)--> Use scanf, or very defensive fast input method, caused me several issues. Moreover I don't understand why time limit is so strict...

Last edit: 2014-12-04 20:06:44
2014-10-20 19:28:45 Knight
@Bhavik
Could you please help to check submission id:12679204.
I am using scanf/printf and use an algorithm of O(log n) but still it give TLE. Is the time limit very strict ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.