Misinterpretation 2

Problem code: MISINT2

All submissions for this problem are available.

Chef's brother likes to put words in Chef's mouth. Chef hates it about him of course. He has decided to become extremely careful about what he speaks. Fortunately, he knows how his brother transforms the words, that Chef uses. He has decided to use only those words which remain the same even after his brother's transformation!

If Chef speaks an N letter word, his brother moves all the letters which are at even positions (assuming, numbering of positions starts from 1), to the beginning of the word; and the rest of the letters follow as they appeared in the word, e.g. abdef becomes beadf; cdcd becomes ddcc.

Chef wants to know how many words he can use, provided that the length of each word is between L and R inclusive and each word is composed of lowercase letters of the English alphabet. They use an ancient language in Byteland, which allows all possible words within the above definition!

Input

The first line contains a positive integer T, the number of test cases. In the following lines, T test cases follow. Every test case is a single line that contains two space separated positive integers, L and R. L is lower bound and R is upper bound for the length of the word that Chef wants to use.

Output

For each test case, print the number of words with length between L and R inclusive that Chef can use; that is, number of words, which remain the same after brother's transformation. Since the result can be quite large, output the result modulo 1000000007.

Constraints

1 <= T <= 5
1 <= L <= R <= 1010
R - L <= 50000

Sample input

3
1 5
6 7
45 50

Sample output

1430
18252
871229844
Author: anton_lunyov
Date Added: 15-08-2011
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

@admin: plz provide some

jainharshit @ 2 Jan 2012 06:41 PM
@admin: plz provide some explaination of the test cases..!!!

Talking about first test

mr777 @ 2 Jan 2012 06:44 PM
Talking about first test case, how 1 5 results in 1430?

@jainharshit @mr777 please

hiroto_adm @ 2 Jan 2012 08:05 PM
@jainharshit @mr777 please read the problem statement carefully and think about examples by yourself. If the problem statement has ambiguities, please indicate them.

I do have a working source

pvihari @ 9 Jan 2012 02:56 PM
I do have a working source code for this problem, but I am facing trouble getting it right on codechef It takes input from a file and outputs it to a file. I am getting a run time error when uploading the code. I suppose the possible reason might be that codechef is running it in a different way and hence the program is unable to open the files and I think thats the reason why it is throwing run time error which is related to segmentation fault. Please help me thank you.

@pvihari: You should read

anton_adm @ 9 Jan 2012 10:52 PM
@pvihari: You should read from the standard input and write to the standard output.

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions