...Then Vadim started writing another problem statement, when suddenly...
A certain contest has N sponsors, and each of them wants to see the name of their company in the exactly si 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 si separated by spaces — the wishes of each sponsor (1 ≤ si ≤ 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 109+7. In other words, find the remainder of dividing the number of ways by 1 000 000 007.
1 1 1 1 1
In the first example, there are only four ways to include the names of sponsors:
Both sponsors are included in the first problem, none in the second;
No sponsors are included in the first problem, both in the second;
The first sponsor is included in the first problem, the second in the second;
The second sponsor is included in the first problem, the first in the second.
Problem Author: Vadim Barinov
Problem Source: Ural School Programming Contest 2022