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.
How to Solve this problem using DP ?
It seems that you can view someone's successful solution.
The DP is quite similar to the first part of CF #157 Div1-B, you can read the editorial here. You need to omit 1 state, though.