Cây của Darth Vader

Xét một cây có gốc vô hạn, trong đó mỗi đỉnh có đúng $n$ đỉnh con. Với mọi đỉnh, cạnh nối đỉnh đó với đỉnh con thứ $i$ (tính từ trái sang) có độ dài $d_i$. Cấu trúc này lặp lại như nhau tại mọi đỉnh: đỉnh con thứ $i$ của bất kỳ đỉnh nào cũng được nối bằng một cạnh độ dài $d_i$.

Khoảng cách giữa hai đỉnh là tổng độ dài các cạnh trên đường đi giữa chúng.

Hãy đếm số đỉnh có khoảng cách tới gốc không vượt quá $x$. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho ${10}^9+7$.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $x$.
• Dòng thứ hai chứa $n$ số nguyên $d_1,d_2,\dots ,d_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất: số đỉnh có khoảng cách tới gốc không vượt quá $x$, lấy phần dư khi chia cho ${10}^9+7$.

Ràng buộc

• $1\le n\le {10}^5$
• $0\le x\le {10}^9$
• $1\le d_i\le 100$

Ví dụ