Cho ~k~ loại mệnh giá (đồng) như sau: ~c_1,c_2,...,c_k~. Tìm số lượng đồng xu ít nhất để tạo ra số tiền ~S~, mỗi mệnh giá có thể dùng vô số lần?

Input

• Dòng thứ nhất có hai số tự nhiên ~k,S~ - số lượng mệnh giá và tổng tiền cần đổi.
• Dòng thứ hai gồm ~k~ số nguyên ~c_1,c_2,...,c_k~ , ~c_i~ (~1 \leq c_i \leq 10^5~) các mệnh giá tiền (mỗi mệnh giá đều khác nhau).

Output

Một số nguyên duy nhất - số lượng đồng xu ít nhất tạo ra tổng tiền ~S~ lấy modulo cho ~10^9+7~. Nếu không có cách chia nào thì in ra ~-1~.

Scoring

• Subtask ~1~ ~(10\%)~: ~S \leq 100, k \leq 5, 1 \leq c_i \leq 1000~;
• Subtask ~2~ ~(90\%)~: ~S \leq 10^6,k \leq 100, 1 \leq c_i \leq 10^6~.

Example input 1

3 11
1 5 7

Example output 1

3

Note 1

• Cách tối ưu: ~5 + 5 + 1 = 11~

→ Có ít nhất ~3~ đồng xu để tạo ra ~11~ đồng tiền