Невероятно! Невозможно!
"Дайте мне суммы каждого столбца и каждого рядка прямоугольной таблицы n×m", — сказал Алекс, — "и я скажу вам, существует ли такая таблица, а если существует, за небольшую плату я могу создать пример такой таблицы". "Невероятно! Невозможно!", — воскликнули его одноклассники, — "Так много чисел! Ты должен быть настоящим гением!".
Однако Василию не нравится, что Алекс становится самым известным человеком в школе.
— "Я заявляю! Я, Василий Великий! Дана прямоугольная таблица n×m и суммы рядков и столбцов, я скажу вам количество возможных таблиц с неотрицательными целыми числами, удовлетворяющих этим условиям".
— "Ты хвастаешься! Спорю на пять долларов, что ты не сможешь сделать это даже для n×3", — говорит Алекс.
— "Спорю на пять, что смогу!", — отвечает Василий.
Завтра конкурс. Алекс создаст несколько таблиц размером n×3 и скажет Василию суммы и размеры. Все мальчики и девочки делают ставки, кто будет победителем!
Ты друг Алекса. Он хочет создать несколько сложных наборов данных для Василия и ему нужен метод для вычисления ответа. Поскольку Алекс не может решить такие задачи, он попросил тебя написать программу, которая сделает это за него.
Алексу нужны только последние семнадцать цифр для проверки ответов. Поэтому ты должен вычислить количество возможных таблиц по модулю 10^17.
Входные данные
Первая строка содержит четыре числа: n, c_1, c_2, c_3, где n — количество рядков, c_i — суммы столбцов. Далее следуют n чисел, каждое из которых является суммой соответствующего рядка. n и все суммы — неотрицательные целые числа. Они не больше 125.
Выходные данные
В первой строке выведите количество возможных таблиц по модулю 10^17.