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: 2019-02-11 08:16:17

what is the code

nadstratosfer: 2018-04-01 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>

Over 100,000 cases per testfile so use fast I/O regardless of the language.

Last edit: 2018-04-01 07:25:05
vish_14: 2017-08-17 03:21:53

TLE in python cost me 4 submission.
Can anyone tell me why am I getting TLE in Python?
Solution Link -
http://www.spoj.com/submit/DIVISION/id=19985254
AC using C++.

Last edit: 2017-08-17 03:22:36
candide: 2017-04-21 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: 2017-04-21 21:23:45
mkfeuhrer: 2016-06-17 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: 2016-06-16 16:58:07

The time limit is unnecessarily strict!

prakash_reddy: 2016-01-17 20:04:40

very easy if u know modular exponentiation......

Thotsaphon Thanatipanonda: 2015-10-03 16:26:40

Finally I can solve this problem using Java with I/O optimization and reduce number of modulo. :D

Rahul yadav: 2015-09-18 15:22:48

nice question

Parul Yadav: 2015-09-05 18:26:08

use scanf/printf


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