Неймовірно! Неможливо!
"Дайте мені суми кожного стовпця і кожного рядка прямокутної таблиці 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.