Keech, Poch and the barn#11533
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 types of planks with a cost of a_i. The boys have 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 .
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.
The first line contains two integers m~(1 \le m \le 10^6) and n~(1 \le n \le 10^{18}) — the number of plank types and the amount of money the guys have, respectively.
The second line contains numbers a_i~(1 \le a_i \le 100) — the cost of the -type board.
The output contains a single integer — the answer to the problem.
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.
Example 1
Example 2