I. Inner subset
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Александра не большой сторонник канцелярии, и дарить она предпочитает конфеты. У Александры есть $$$n$$$ разных коробок, и она знает, что в $$$i$$$-й коробке находится $$$a_i$$$ конфет. Она хочет сделать подарок $$$k$$$ одногруппникам, поэтому суммарное количество подаренных конфет должно делиться на $$$k$$$, но при этом ей нельзя открывать коробки — это за неё сделают голодные до сладкого студенты. Спрашивается, сколько способов накормить своих друзей есть у Александры? Кстати, она не прочь отдать ребятам даже пустые коробки, если такие будут.

Входные данные

В первой строке одно целое число $$$n$$$ (от 1 до 1000) — количество коробок. Во второй строке $$$n$$$ целых чисел $$$a_1$$$, ..., $$$a_n$$$ (от 0 до $$$10^9$$$) разделенных пробелами, где $$$a_i$$$ — количество конфет в $$$i$$$-й коробке. В третьей строке целое положительное число $$$k$$$ (от 1 до 1000) — количество одногруппников.

Выходные данные

Одно целое неотрицательное число — ответ на задачу по модулю $$$10^9 + 7$$$.

Пример
Входные данные
4
1 2 3 4
3
Выходные данные
6
Примечание

В примере подойдут следующие варианты: { }, {1, 2}, {3}, {1, 2, 3}, {2, 4}, {2, 3, 4}.