1221 : hard math

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
256 兆MB
提交次数Submitted
274 次Times
通过次数Solved
84 次Times

题目描述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\).

输入格式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\).

样例Sample