You are given a digit array ~a~ of length ~N~. You must find the number of integers between ~0~ and ~K~ (inclusive) satisfying the following condition, modulo ~10^9 + 7~:

• The digits ~a_i~ for all ~i~ ~(1 \le i \le N)~ show up at least once in the integer.

Input Specification

The first line will contain the integer ~N~ ~(1 \le N \le 10)~.

The next line will contain ~N~ integers, ~a_i~ ~(0 \le a_i \le 9)~. It is guaranteed ~a_i~ is distinct.

The next line will contain the integer ~K~ ~(0 \le K < 10^{1000})~.

Output Specification

Output the number of integers satisfying the condition, modulo ~10^9+7~.

Sample Input 1

1
1
11

Sample Output 1

3

Explanation For Sample 1

The three integers satisfying the constraints are:

• 1
• 10
• 11

Sample Input 2

5
3 9 2 0 1
512309002821093

Sample Output 2

891474356