1221 : 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\).

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

2
40
77
2

34

Hint

Source