Суммы двух
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
1024 мебибайта
ввод
стандартный ввод
вывод
стандартный вывод

Фокусница Лина утверждает, что обычный современный компьютер легко может производить сотню миллиардов операций в секунду! Чтобы доказать это, она предлагает проделать следующие вычисления.

Пусть $$$V$$$ — множество целых чисел, изначально пустое. Дано начальное значение числа $$$s$$$. Сделаем $$$n$$$ шагов следующего вида:

- $$$s \leftarrow (s \cdot 618\,023 + 1) \bmod 999\,983$$$;
- найдём число различных пар чисел из $$$V$$$, которые в сумме дают $$$s$$$;
- если это число пар чётно, добавим число $$$s$$$ в множество $$$V$$$.

Сколько элементов будет в множестве $$$V$$$ после $$$n$$$ шагов?

Формально: на каждом шаге мы считаем число пар $$$(a, b)$$$, в которых $$$a \in V$$$, $$$b \in V$$$, $$$a \le b$$$ и $$$a + b = s$$$.

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

В первой строке заданы целые числа $$$n$$$ и $$$s$$$ ($$$1 \le n \le 200\,000$$$; $$$0 \le s < 999\,983$$$; $$$s \ne 742\,681$$$).

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

Выведите одно целое число: размер множества $$$V$$$ после $$$n$$$ шагов.

Пример

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

    4 179629

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

    3

Примечание

В примере значения $$$s$$$ на четырёх шагах равны $$$740\,740$$$, $$$139\,655$$$, $$$469\,353$$$ и $$$880\,395$$$.