Cho ~k~ loại mệnh giá (đồng) như sau: ~c_1,c_2,...,c_k~. Hỏi có bao nhiêu cách để tạo ra số tiền ~S~ từ các mệnh giá đã cho, 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ố cách tạo ra tổng tiền ~S~ lấy modulo cho ~10^9+7~.

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, c_i \leq 10^6~.

Example input 1

3 5
1 2 5

Example output 1

4

Note 1

• Có ~4~ cách để tạo ra tổng ~5~:
  • ~1+1+1+1+1~.
  • ~1+1+1+2~.
  • ~1+2+2~.
  • ~5~.