Một công ty logistics có n kiện hàng. Mỗi kiện hàng thứ i có hệ số giá trị là aᵢ. Để chuẩn bị cho một chương trình khuyến mãi đặc biệt, công ty muốn lựa chọn một số kiện hàng sao cho:

• Mỗi kiện hàng được chọn nhiều nhất một lần.
• Giá trị của lô hàng bằng tích các hệ số giá trị của những kiện hàng đã chọn.
• Chữ số tận cùng của giá trị lô hàng phải đúng bằng d.

Hãy xác định giá trị lớn nhất của lô hàng có thể tạo được. Vì kết quả có thể rất lớn, hãy in ra kết quả theo modulo 10⁹ + 7.

Nếu không tồn tại cách chọn nào thỏa mãn thì in ra -1

Input:

Dòng đầu tiên gồm hai số nguyên n và d (1 ≤ n ≤ 10⁵, 0 ≤ d ≤ 9), lần lượt là số lượng kiện hàng và chữ số tận cùng cần đạt được.

Dòng thứ hai gồm n số nguyên dương a₁, a₂, ..., a_n (1 ≤ a_i ≤ 1000), trong đó aᵢ là hệ số giá trị của kiện hàng thứ i.

Output:

In ra một số nguyên duy nhất là giá trị lớn nhất của lô hàng có chữ số tận cùng bằng d, lấy modulo 10⁹ + 7.

Nếu không có cách chọn phù hợp thì in ra -1.