Исследовательская группа
(Время: 1 сек. Память: 32 Мб Сложность: 92%)
Исследовательская группа Кена Оно обнаружила, что простые числа можно находить с помощью диофантовых уравнений – алгебраических задач, сформулированных ещё в III веке древнегреческим математиком Диофантом Александрийским. Эти уравнения требуют целочисленных решений и могут быть крайне сложными, но если решение существует, оно может указывать на простое число.
Удивительно, что связь между диофантовыми уравнениями и простыми числами не была обнаружена ранее, несмотря на многовековую историю изучения обоих направлений.
Как отмечают авторы исследования, эта работа могла быть проведена десятилетия назад, но лишь сейчас математики смогли выявить эту фундаментальную взаимосвязь.
Другими словами, теперь у математиков появился новый инструмент для поиска и анализа простых чисел, который открывает путь к созданию более устойчивых криптографических алгоритмов.
Помогите группе Кена провести оценку числа решений уравнения. Вам дано уравнение вида:
a1×x1 + a2×x2 +...+ aN×xN = S.
Определите число решений данного уравнения в неотрицательных целых числах по модулю 998244353.
Входные данные
Входной файл INPUT.TXT содержит в первой строке два натуральных числа N и S (1 ≤ N ≤ 5000; 1 ≤ S ≤ 1018).
Во второй строке содержится N натуральных чисел ai (1 ≤ ai ≤ 25000; 1 ≤ a1 + a2 +…+ aN ≤ 25000).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 4 20
1 2 3 4 | 108 |
| 2 | 3 10
5 2 3 | 4 |
| 3 | 3 2
5 7 11 | 0 |
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
