"Joffrey... Cersei... Ilyn Payne... the Houn.." - Arya Stark
Garden of Bones, Game of Thrones S02E04
Arya Stark was one of the crucial member of the Stark family in the HBO's epic fantasy television series Game of Thrones.
Arya had a kill list consisting of a few people who had contributed to making her life stressful. But she is so young that she can not kill a man yet. She decided to go to Braavos to adopt some magical skills.
Arya's tutor gave him a huge task. She had to run a magic code in her computer.
func (L, R){
sum = 0
for (i = L; i <= R; i++){
sum += score (i)
}
return sum
}
Where,
score (N){
A = number of unique non zero digits of N
B = number of unique digits of N which evenly divides N
return power (B, A) //B to the power A
}
She ran the code on her computer smoothly by some magical power. Can you do the same?
Input starts with an integer T, denoting the number of test cases. Each case starts with a line containing two integers L R.
Subtask 1 (20 Points): 1 ≤ T ≤ 10 1 ≤ L ≤ R ≤ 107
Subtask 2 (40 Points): 1 ≤ T ≤ 5 1 ≤ L ≤ R ≤ 1014
Subtask 3 (40 Points): T = 1 1 ≤ L ≤ R ≤ 1018
For each case, print func (L, R) modulo (109 + 7)
Input | Output |
---|---|
3 1 10 12 15 20 100000 | 10 10 2522331 |