湊出總額的有序投幣方式數

題目敘述

販賣機有 n 種代幣，面額分別為 c₁, …, c_n，每種代幣的數量不限。你要依序投入代幣，使投入的面額總和恰好為 x。請問有幾種不同的投幣序列？投入的順序不同就算不同的序列，例如先投 1 再投 2，與先投 2 再投 1 是兩種。

答案可能很大，請輸出除以 10⁹+7 的餘數。

輸入格式

第一行有兩個整數 n 與 x。 第二行有 n 個整數，依序為各種代幣的面額。

輸出格式

輸出一個整數，表示投幣序列數除以 10⁹+7 的餘數。

限制

• 1 ≤ n ≤ 100
• 1 ≤ x ≤ 10⁶
• 1 ≤ c_i ≤ 10⁶

範例

範例 1

輸入

3 9
2 3 5

輸出

8

範例 2

輸入

2 4
1 2

輸出

5

說明

• 範例 1 的八種序列總和都是 9。
• 範例 2 只有面額 1 與 2，序列共五種。