hard math
Description
binarycopycode is terrible at math. He always ask locytus for help but after their retirement, they went to different universities for their graduate studies. So binarycopycode have to seek help from you.
We define $f(x)$ equals to the number of distinct digits in the decimal notation of $x$ . Now please calculate the number of $X$ satisfied that $L \leq X \leq R$ and $f(X)=A $ . Print this count modulo $10^9+7$.
First line is $n(1\leq n \leq200,000)$ which indicate that $L$ and $R$ both have exactly $n$ digits.
Next 2 lines is $L$ and $R$ , it is guaranteed that there are no leading zeros in $L$ and $R$.
The last line contains 1 integers $A$ ($1\leq A \leq 10$).
Print the number of pairs modulo $10^9+7$.
Input
First line is $n(1\leq n \leq200,000)$ which indicate that $L$ and $R$ both have exactly $n$ digits.
Next 2 lines is $L$ and $R$ , it is guaranteed that there are no leading zeros in $L$ and $R$.
The last line contains 1 integers $A$ ($1\leq A \leq 10$).
Output
Print the number of pairs modulo $10^9+7$.
2
40
77
2
34