Lucky Number

Problem code: LUCKY2

All submissions for this problem are available.

Chef loves lucky numbers. Everybody knows that lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Let F(X) equals to the number of lucky digits in decimal representation of X. Chef wants to know the number of such integers X, that L ≤ X ≤ R and F(X) is a lucky number. Help him and calculate that number modulo 109+7.

Input

First line contains one integer T, the number of test cases. Each of the following T lines contains two space separated positive integers L and R.

Output

For each of the T test cases print one integer, the number of such X, that L ≤ X ≤ R and F(X) is a lucky number, modulo 1000000007.

Constraints

1 ≤ T ≤ 10

1 ≤ L ≤ R ≤ 101000

Example

Input:
4
1 100
1 10000
1 100000
4444 4447

Output:
0
16
640
2

Notes

First test case: of course, any number of less than 4 digits can't contain lucky number of lucky digits, so the answer is 0.

Second test case: 16 required numbers are 4444 4447 4474 4477 4744 4747 4774 4777 7444 7447 7474 7477 7744 7747 7774 7777.

Third test case: there are 640 required lucky numbers. Some of them are 4474, 14747, 41474, 77277, 44407, 74749.

Fourth test case: the only two required numbers are 4444 and 4447.

Author: witua
Tester: anton_lunyov
Editorial http://discuss.codechef.com/problems/LUCKY2
Date Added: 11-11-2011
Time Limit: 2 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, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, 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

can you plz explain me the

confusedpm @ 17 Mar 2012 01:35 AM
can you plz explain me the 2nd case...how 16 lucky no.s betn 1 to 100.. m not getting it...:-O

@jigyasu, when L = 8910 and R

bodmas @ 19 Mar 2012 02:42 AM
@jigyasu, when L = 8910 and R = 8961, your acCepTed c0de outputs 16 instead of 0. Check that out yoUrself. Regards.

For the first Test case why

Durgesh kumar @ 31 Mar 2012 07:27 AM
For the first Test case why 47 and 74 will not be considered as lucky number?

why not 47 and 74 for the

rahuldubey7474 @ 2 Apr 2012 02:14 AM
why not 47 and 74 for the first test case???? plz explain

Thanks bodmas, It's

jigyasu @ 11 Apr 2012 08:49 PM
Thanks bodmas, It's corrected. There was no such test case to detect the issue. Good catch :)

This can't be an easy

mycontest @ 3 May 2012 10:51 PM
This can't be an easy problem!

I ran other successful

xcode @ 9 Jun 2012 11:32 PM
I ran other successful submissions on my gcc compiler and they are showing same timing as my code does. But when i submitted my code more than 5 times it shows time limit exceeded , admin please tell me how can i check time limit on my compiler so to match your time limiter ??

anyone can explain the

arjunrp @ 16 Jun 2012 01:52 PM
anyone can explain the concept of modulus here???

the third case cannot hav 640

mjnovice @ 18 Jun 2012 10:42 AM
the third case cannot hav 640 as the answer if lucky numbers are only those with digits only 4 or 7.... admins please see to this.........

what is the use of 1000000007

bhavitpant @ 28 Jul 2012 08:07 PM
what is the use of 1000000007 ? why i need to find number modulo 1000000007?

"Third test case: there are

phoxis @ 1 Aug 2012 12:43 AM
"Third test case: there are 640 required lucky numbers. Some of them are 4474, 14747, 41474, 77277, 44407, 74749." How can 14747, 41474, 77277, 44407, 74749 be lucky numbers?

even i dint get how 14747 can

arunkumar93 @ 27 Sep 2012 05:48 PM
even i dint get how 14747 can be a lucky no and 47 cant..

i am getting time limit

deven123dr @ 25 Oct 2012 11:11 AM
i am getting time limit exceeded how can i solve it...im new to code chef pls help deven123dr@gmail.com thanks!

@all who are having doubts:

kuruma @ 16 Nov 2012 04:58 AM
@all who are having doubts: read statement CAREFULLY

i am also not getting how

simac @ 21 Dec 2012 08:46 PM
i am also not getting how 14747, 41474, 77277, 44407, 74749 are lucky number kindly someone give the explaination if it possible to have these as lucky number i had gone through the given so many times. @admins kindly respond

@simac: 14747 is not lucky.

jigsaw004 @ 21 Dec 2012 09:23 PM
@simac: 14747 is not lucky. However, it has 4 lucky digits i.e. '4' & '7'. Moreover, it lies between 1 & 100000 so it is a valid case that has to be counted for.

for 1 to 10000 the lucky no

viking @ 10 Jan 2013 08:24 PM
for 1 to 10000 the lucky no are :4 47 74 77 444 447 474 477 744 747 774 777 4444 4447 4474 4477 4744 4747 4774 4777 7444 7447 7774 7777 and many more ...then how is the answer 16 please see to it admin.......all the combinations are not taken.......:)

@viking: actually all

idebashish @ 28 Jan 2013 02:39 PM
@viking: actually all combinations are not valid. e.g. 74 is invalid because it has 2 lucky digits and 2 is not a lucky number.

is the 1-100000 case correct

bahdur_tyoji @ 21 Feb 2013 12:56 AM
is the 1-100000 case correct ?? how can 74749 be lucky ? now if we consider both digits and length of numbers to come to as lucky , i am getting way more no of cases....

i am not able to optimize my

jony786 @ 3 Mar 2013 11:18 PM
i am not able to optimize my code :-( pls help me ..... http://www.codechef.com/viewsolution/1886564

hmmmmmmmm

mayur1992 @ 6 Mar 2013 09:38 PM
hmmmmmmmm

The question is not "how many

asquirrel @ 10 Mar 2013 10:13 PM
The question is not "how many lucky numbers fall in the range [L..R]" It is "how many numbers in the range [L..R] have a lucky number of lucky digits". I hope this clears up the confusion that half the people seem to be having.

where is the time limit? 1

jerryczz @ 15 Mar 2013 06:25 PM
where is the time limit? 1 second?

@jerryczz : Time limit is

vineetpaliwal @ 15 Mar 2013 09:57 PM
@jerryczz : Time limit is mentioned in this problem like all . Its 2 seconds . Author: witua Tester: anton_lunyov Editorial http://discuss.codechef.com/problems/LUCKY2 Date Added: 11-11-2011 Time Limit: 2 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, FORT, FS, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC

Is time limit for all

cdwijayarathna @ 15 Mar 2013 10:33 PM
Is time limit for all languages are same??

SUCCESSFUL SUBMISSIONS


Fetching successful submissions

HELP




 





Program should read from standard input and write to standard output.  After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:


 


    
    
  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.

    • 
    
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.

    • 
    
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.

    • 
    
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.

    • 
    
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • 
    If you are still having problems, see a sample solution here.