You are given a digit array of length . You must find the number of integers between and (inclusive) satisfying the following condition, modulo :
- The digits for all show up at least once in the integer.
The first line will contain the integer .
The next line will contain integers, . It is guaranteed is distinct.
The next line will contain the integer .
Output the number of integers satisfying the condition, modulo .
Sample Input 1
1 1 11
Sample Output 1
Explanation For Sample 1
The three integers satisfying the constraints are:
Sample Input 2
5 3 9 2 0 1 512309002821093
Sample Output 2