Counting Lucky Numbers

A lucky number is defined as a positive integer x whose decimal representation does not contain any of the forbidden substrings given in a set s. In other words, if a string from s appears as a contiguous substring in the decimal representation of x, then x is not lucky. For example, if s = {22, 333, 0233}, then:

• 233 is a lucky number.
• 2333, 20233 and 3223 are not lucky numbers.

Given a positive integer n and a set of forbidden substrings s, compute the number of lucky numbers less than or equal to n. Since the answer can be very large, output it modulo \(10^9+7\).

Note: The decimal representation of a number does not include any leading zeros. Therefore, even if an element of s has a leading zero (for example, 0233), it will only be considered if it appears as is in the representation.

inputFormat

The first line contains two integers n and m, where \(1 \le n \le 10^{?}\) (the upper bound for n) and m is the number of forbidden substrings.

Each of the following m lines contains a non-empty string representing a forbidden substring. The forbidden substrings consist of digits (0-9) and may contain leading zeros.

outputFormat

Output a single integer — the number of lucky numbers not greater than n, taken modulo \(10^9+7\).

sample

100 1
4

81