35016번 - Sums of Two 다국어

문제

Lina the Magician claims that a common modern computer can easily perform a hundred billion operations per second! To prove it, she proposes to run the following calculations.

Let $V$ be a set of integers, initially empty. We are given the starting value of the integer $s$. Make $n$ steps described below:

• $s \leftarrow (s \cdot 618,023円 + 1) \bmod 999,983円$;
• find the number of distinct pairs of integers in $V$ that have the sum $s$;
• if this number is even, insert $s$ into the set $V$.

How many elements will there be in $V$ after $n$ steps?

Formally: on each step, we count the number of pairs $(a, b)$ where $a \in V,ドル $b \in V,ドル $a \le b$ and $a + b = s$.

입력

The first line contains integers $n$ and $s$ (1ドル \le n \le 200,000円$; 0ドル \le s < 999,983円$; $s \ne 742,681円$).

출력

Print a single integer: the size of set $V$ after $n$ steps.

제한

노트

In the example, the values of $s$ on the four steps are 740ドル,740円,ドル 139ドル,655円,ドル 469ドル,353円,ドル and 880ドル,395円$.