Задача E. Чокопай ≡

Условие

На дурацкую олимпиаду по программированию пришло n команд, в каждой команде по 3 человека. Как и на всех дурацких олимпиадах, организаторы решили раздать командам чокопай! У них есть m различных видов чокопая, i-го вида чокопая у организаторов a_i штук.

Организаторы хотят раздать чокопай каждой команде таким образом, чтобы никто в команде между собой не поссорился и чтобы каждому участнику команды досталось то же самое множество чокопаев, что и его сокомандникам (более формально, для любого i-го вида у каждого участника команды должно быть одинаковое количество чокопаев i-го вида). Но при этом организаторы не следят за тем, чтобы у каких-либо двух команд был одинаковый набор чокопаек (к примеру, организаторы могут хоть все угощения отдать одной команде и оставить все остальные команды с пустыми руками, могут раздать всем командам чокопай, а могут вообще никому ничего не давать).

Помогите организаторам! Сообщите количество способов раздать чокопай таким образом, чтобы никакие два сокомандника не поссорились между собой.

Формат входных данных

В первой строке вводятся натуральные числа n и m — количество команд и количество видов чокопая (1 ≤ n, m ≤ 10⁵). Во второй строке вводятся последовательность целых чисел a_i (0 ≤ a_i ≤ 10⁵).

Формат выходных данных

Выведите ответ на задачу по модулю 10⁹ + 7.

Примечание

В первом примере раздать чокопай можно следующими способами:

1. Первой команде 3 чокопайки 1-го вида и 3 чокопайки 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
2. Первой команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида;
3. Первой команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида, второй команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида;
4. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 3 чокопайки 1-го вида и 3 чокопайки 2-го вида;
5. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
6. Первой команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
7. Первой команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида;
8. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 3 чокопайки 1-го вида и 0 чокопаек 2-го вида;
9. Первой команде 0 чокопаек 1-го вида и 0 чокопаек 2-го вида, второй команде 0 чокопаек 1-го вида и 3 чокопайки 2-го вида.

Примеры тестов

2 2
3 3

9