A Digit Problem

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

Ninjaclasher

Problem type

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

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

Input Specification

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

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

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

Output Specification

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

Sample Input 1

1
1
11

Sample Output 1

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

Comments

7

ross_cleary commented on June 15, 2020, 6:58 p.m.

Remember that leading zeros do not count.