Keech, Poch and the barn

Kich's and Poch's parents sent them to their grandmother in the village. The boys were very bored and decided to play in the barn, but at some point they accidentally set fire to the barn. Now they need to build the barn again.

That's how they ended up at the plank store. The store has $m$ types of planks with a cost of $a_i$. The boys have $n$ money. Before they buy the planks they need, they decided to answer the question: how many different ways are there to buy planks with a budget of no more than $n$.

It is worth considering that a plank of one type can be bought an unlimited number of times.

Since the answer may be too large, we need to derive it modulo $10^9+7$.

Input

The first line contains two integers $m(1\le m\le 10^6)$ and $n(1\le n\le 10^{18})$ — the number of planks and the amount of money the guys have, respectively.

The second line contains $m$ numbers $a_i(1\le a_i\le 100)$ — the cost of the $i$-type board.

Output

The output contains a single integer — the answer to the problem.

Examples

Note that the order of the boards is important. For example, the option to buy type 1 boards first and then type 2 boards and the option to buy type 2 boards first and then type 1 boards are considered different.