A certain contest has N sponsors, and each of them wants to see the name of their company in the exactly s_i different problem statements. However, the participants of this contest do not want to see references to more than 2 different sponsors in the same problem statement.

The jury can certainly handle such requirements, but they have a different question. It is already known that there will be M problems in the contest, and how they are arranged in the problem set. Now, it is possible to include the names of no more than two companies in any of the problem statement (for example, “DOUBLETAPP” and “X-tensive”). Now, the question is how many ways there are to do this. Two ways are considered different, if there is at least one problem that has a different set of mentioned sponsors.

However, the jury is currently busy including sponsors in the problem statements, so the task of calculating the number of ways to do this falls to you.

The first line contains two integers N and M — the number of sponsors in the contest and the number of problems in the contest (1 ≤ N ≤ 1000, 1 ≤ M ≤ 2000).

The second line contains N integers s_i separated by spaces — the wishes of each sponsor (1 ≤ s_i ≤ M).

It is guaranteed that the total number of wishes does not exceed 2 · M.

Output the number of ways to include the names of sponsor companies in the problem set modulo 10⁹+7. In other words, find the remainder of dividing the number of ways by 1 000 000 007.

In the first example, there are only four ways to include the names of sponsors: