The Great Wall of Byteland

Problem code: BWALL

All submissions for this problem are available.

In order to protect the southern border of Bytelandian Empire against intrusions by various nomadic groups, the Emperor of Byteland has decided to build a wall along the southern border. The best architect Johny is recruited for the task.

In order to minimise the cost of raw material, Johny is restricted to use only following two kinds of building blocks:
X     #
XX
The height of the wall is fixed and is 2 units, but the length of the wall varies. As a part of his job Johny needs to find out the number of ways he can construct the wall using above two types of building blocks where the length of the wall is specified. Write a program to help Johny.

Input Format:

The first line contains the number of test cases T followed by T lines. Each of the next lines contains an integer N representing the length of the wall.

Output Format:

Print T lines one for each test case, containing an integer that represents the number of ways of constructing the wall, modulo 1000000007.

Example:

Sample Input:
3
7
2
13


Sample Output:
655
5
272767
Constraints:
1<=T<=1000
1<=N<=10^9
Explanation of 2nd Test Case
N=2
The wall can be constructed in following 5 ways:
##
##


X#
XX


#X
XX


XX
X#


XX
#X


Author: nssprogrammer
Date Added: 16-03-2011
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: C, C99 strict, CPP 4.0.0-8, CPP 4.3.2, CS2, D, JAVA, PAS fpc, PAS gpc


Comments

i m not understaing the case

ab1234 @ 1 May 2011 03:24 PM

i m not understaing the case u have taken for length=2 ,how this case arises

##

##

as we r using the blocks of

x# and xx

and also why use the reverse

ab1234 @ 1 May 2011 03:26 PM

and also

why use the reverse ordering lyk

xx

#x

if it will be there then why not

xx

xx??

@admin: why not cases lyk xx

ashwyn_46 @ 1 May 2011 03:31 PM

@admin: why not cases lyk

xx or x#

##     #x

Number of tilings of a 2xn

havaliza @ 1 May 2011 04:11 PM

Number of tilings of a 2xn board with 1x1 and L-shaped tiles (where the L-shaped tiles cover 3 squares).

I don't understand, what

al13n @ 1 May 2011 04:17 PM

I don't understand, what types of blocks are there and how exactly are we allowed to use them for building the wall.

Now I do.

al13n @ 1 May 2011 04:22 PM

Now I do.

@michael i also dont

raghusinha @ 1 May 2011 05:39 PM

@michael i also dont understand what type of blocks are there can u explain alittle please

Admin: Please make it clear

rajneesh2k10 @ 1 May 2011 05:41 PM

Admin: Please make it clear how the blocks are placed ??

I am not able to figure out why:

XX

XX

is not included as one of the configuration of the wall in the explanation test case!!

@Rajneesh:The blocks are as

snigdha_adm @ 1 May 2011 05:56 PM

@Rajneesh:The blocks are as follows :

 

x

XX                 &                      #.

(L- shaped)                        (A single block).

 

I hope now things will be clear for you.

Are the solutions X     XX   

ashwyn_46 @ 1 May 2011 06:54 PM

Are the solutions X     XX    and       XX     X    considered same for a wall of length 3.

XX     X                 X     XX

 

X     XX                

ashwyn_46 @ 1 May 2011 06:56 PM

X     XX                 XX     X

XX     X                 X     XX

Are the solutions considered same for a wall of length 3?

@Ashwini:Definitely no.The

snigdha_adm @ 1 May 2011 07:26 PM

@Ashwini:Definitely no.The two configuration mentioned by you are altogether different.

@chandan: very clear!! Thanks

rajneesh2k10 @ 1 May 2011 08:05 PM

@chandan: very clear!! Thanks :)

"modulo 1000000007."?what

cxplorer @ 2 May 2011 05:19 PM

"modulo 1000000007."?what does mean MODULO?im new here,plz help me.

Modulo is: C++: N modulo M is

agul @ 2 May 2011 06:53 PM

Modulo is:

C++: N modulo M is N % M

Pascal: N modulo M is N mod M

pls nybdy tell me that wt is

dabbcomputers @ 3 May 2011 11:17 PM

pls nybdy tell me that wt is the output for 0 nd 25 plssss........

GUYS PLEASE HELP;IS LENGTH

ritesh_gupta @ 3 May 2011 11:29 PM

GUYS PLEASE HELP;IS LENGTH AND BRADTH OF WALL SAME

@Ritesh : I wonder how can

manoharsingh23 @ 4 May 2011 12:48 PM

@Ritesh : I wonder how can you  think to solve a problem if you dont even read it carefully. It is clearly mentioned that height of the wall is 2 (constant)and length is variable that is provided in the input and also you must consider the wall in 2D not in 3D , then I dont think you need anything else from problem setter. Do you?

@ manmohar

ritesh_gupta @ 4 May 2011 01:14 PM

@ manmohar singh::yeah,manmohar thats correct..i misread the question ....now i got it...I  even found the algorithm..my answer is working fine for the test cases N=42..but from there its not working bcoz it exceeds the max value of a 64 bit numbers.so what approach should i use...Is there any tutorial in a codechef site to deal wiith Big INT numbers..

Can anyone say(who solved this problem) how many digits are there in answer when N=10^9.

@Ritesh:If u found the

snigdha_adm @ 4 May 2011 01:32 PM

@Ritesh:If u found the algorithm , no need to mention here.It's not a discussion forum and don't expect for any sort of tutorial.Dealing with big integers is a part of solving the problem.

@Amritpal:No more test cases

snigdha_adm @ 4 May 2011 01:35 PM

@Amritpal:No more test cases can be provided.The test cases mentioned in the example are enough for solving the problem.

if i contruct a block of

mendax @ 4 May 2011 02:49 PM

if i contruct a block of lenth with two different methods like1)  # and ##         and  2) ## and # then will it be counted as two different

#        ##                     ##        #

methods or same methods??!! and please clarify how do you take a way of cotruction is different then others..?? like if it looks differents from others or something like that?? please clarify!!

in the previous question ways

mendax @ 4 May 2011 02:52 PM

in the previous question ways of joining the blocks are

1)# and ##

#  and ##

2) ## and #

##        #

in the previous question ways

mendax @ 4 May 2011 02:52 PM

in the previous question ways of joining the blocks are

# and ##

#  and ##

 

 

## and #

##        #

# is a single block.You can

snigdha_adm @ 4 May 2011 03:21 PM

# is a single block.You can use it as many times individually.Don't assume ## as a single block.Go through the problem statement repeatedly.Everything is mentioned.

X  XX         XX X XX X  and 

nishit4091992 @ 5 May 2011 12:23 PM

X  XX         XX X

XX X  and  X XX  are different....

hey pandya !!! both of your

nishit4091992 @ 5 May 2011 12:37 PM

hey pandya !!!

both of your blocks are to be considered identical..

for eg.

## #          # ##          # # #

## #   and # ##  and  # # #   .. are identical as they share same configuration of # block

but,

X XX        XX X

XX X and X XX  are different as there have different configuration of the L shaped blocks.....

I hope this clears you doubt...

hey pandya !!! both of your

nishit4091992 @ 5 May 2011 12:38 PM

hey pandya !!!

both of your blocks are to be considered identical..

for eg.

## #           # ##           # # #

## #   and # ##  and  # # #   .. are identical as they share same configuration of # block

but,

X XX         XX X

XX X and X XX  are different as there have different configuration of the L shaped blocks.....

I hope this clears you doubt...

where can i see the memory

jairamirez @ 6 May 2011 08:42 AM

where can i see the memory limits? what is the memory limit for the ploblems?

Why F# is forbidden for this

wRabbits @ 8 May 2011 07:00 PM

Why F# is forbidden for this prob?

What is the purpose of

jugesh @ 13 May 2011 10:10 AM

What is the purpose of mentioning the modulo? Please explain.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions