H. It's showtime
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан некий язык, доступный во вкладке «Запуск» под кодовым названием UnknownX. Опознайте этот язык и напишите программу, которая будет решать следующую задачу.

Вам дано число $$$input = 1000 * n + mod$$$ ($$$1 \le n, mod \le 999$$$). Вычислите двойной факториал числа $$$n$$$ по модулю $$$mod$$$.

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

Входные данные содержат одно целое число $$$input$$$ ($$$1001 \le input \le 999999$$$). Гарантируется, что $$$input \mod 1000 \neq 0$$$.

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

Выведите одно число.

Примеры
Входные данные
6100
Выходные данные
48
Входные данные
9900
Выходные данные
45
Входные данные
100002
Выходные данные
0
Входные данные
123456
Выходные данные
171
Примечание

В первом примере вам необходимо вычислить $$$6!! \mod 100$$$; $$$6!! = 6 * 4 * 2 = 48$$$.

Во втором примере вам необходимо вычислить $$$9!! \mod 900$$$; $$$9!! = 9 * 7 * 5 * 3 = 945$$$.

В третьем примере вам необходимо вычислить $$$100!! \mod 2$$$; для простоты можно заметить, что $$$100!!$$$ делится на 100 и, следовательно, делится на 2.