
Misinterpretation 2
|
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 |
Tester: | laycurse |
Editorial | http://discuss.codechef.com/problems/MISINT2 |
Tags | anton_lunyov, hard, jan12 |
Date Added: | 15-08-2011 |
Time Limit: | 1.18275 sec |
Source Limit: | 50000 Bytes |
Languages: | C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS |
Comments
- Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. |
