Casino Chip Winning Methods

In a casino, new registered players are given exactly one chip drawn from a lottery box. The lottery box contains m chips with distinct positive integer denominations \(a_1, a_2, \ldots, a_m\). After registration, a player picks one chip whose value becomes the starting amount. The only available game is rock-paper-scissors. In each game the player bets a positive number of chips (in units of \(1\) Australian dollar) and if he wins the round he collects all the chips wagered in that round. Importantly, in every game the chips wagered (a positive integer) cannot exceed the total number of chips the player currently holds.

A particular player, xhabc66, after registration went on to win consecutive games (possibly 0 games, meaning he did not need to play any game if his starting chip equals his final amount) without ever drawing or losing. When he left the casino he had exactly \(n\) dollars. However, he cannot recall the number of games played, nor the bet amount in each round, or even which chip he initially obtained. He is curious to know in how many distinct ways he could have ended up with \(n\) dollars.

Two ways are considered different if any of the following holds:

• The number of rounds played is different.
• The bet amount in some round is different.
• The starting chip denomination is different.

Formalization:

Determine the number of sequences \(\{b_k\}\) (with length \(k\) being any positive integer) satisfying:

1. For every \(i\) with \(1 \le i \le k\), \(b_i \in \mathbb{N}^+\) (i.e. a positive integer).
2. For every \(i \ge 2\), \(b_i \in [b_{i-1} + 1, \; 2\,b_{i-1}]\); that is, \(b_i\) can be any integer between \(b_{i-1}+1\) and \(2b_{i-1}\) inclusive.
3. The first term \(b_1\) is chosen from the set \(\{a_1, a_2, \ldots, a_m\}\) (i.e. one of the available chip values).
4. The last term equals \(n\), i.e. \(b_k = n\).

Compute the number of such sequences modulo \(10^9+7\).

inputFormat

The first line contains two positive integers \(m\) and \(n\) --- the number of chip denominations and the final amount \(n\) respectively.

The second line contains \(m\) positive integers \(a_1, a_2, \ldots, a_m\), representing the chip values available.

You may assume that \(1 \le m \le 10^5\) and \(1 \le n \le 10^5\) (the constraints are chosen so that a dynamic programming solution over \(n\) is feasible). Also, each \(a_i\) is a positive integer and may appear in any order.

outputFormat

Output a single integer: the number of winning methods modulo \(10^9+7\).

sample

1 1
1

1