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

来源Source