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:
2015-08-02 12:14:57
Modular exponentiation..came to rescue..:)
|
|
Arun:
2015-07-29 08:02:56
@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 |
|
The next big thing:
2015-05-14 16:32:42
nice problem, but very strict Time limit |
|
Mercury:
2015-02-05 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:
2015-01-17 19:42:28
good problem but @bhavik can you tell me why tl is so strict(strict as in strict for slow languages)?
|
|
himanshujaju:
2015-01-14 11:00:53
strict TL. easy problem. |
|
Malinga:
2014-12-30 19:09:48
@Bhavik : as you said leading zeros are allowed, can 3 be represented as 11, 011, 0011 , 00011 , 000011..... ??
|
|
Yashpal:
2014-12-23 15:53:30
@Francky Awesome speed !! Have you minimized the use of modulo(%) operator ?
|
|
reddappa:
2014-12-03 18:20:20
can u explain format of the input properly () any line separation btwn two inputs?
|
|
Knight:
2014-10-20 19:28:45
@Bhavik
|
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 |