Marisa has her favorite digit $d$ and a sequence of $n$ elements $a_1, a_2, \ldots, a_n.$ Marisa wants to select some elements from the sequence such that their product is the largest possible and has a last digit equal to $d$.
### Input
- The first line contains two positive integers $n$ and $d.$
- The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n.$
### Output
- Output a single value representing the maximum product with a last digit equal to $d$ modulo $10^9+7$. If no such sequence exists, print $-1.$
### Constraints
- $1 \leq n \leq 10^5.$
- $1 \le a_1,a_2,...,a_n \le 1000$
- $0 \leq d \leq 9.$
### Example
Input
```
7 3
1 4 11 8 17 5 9
```
Output
```
1683
```
