Для определенного числа $\rho \in [0, 1]$ начнем сумму $s$ с $0$ и будем повторно выполнять следующее действие: с вероятностью $\rho$ прибавить $1$ к $s$, в противном случае прибавить $2$ к $s$.

Этот процесс закончится или когда $s$ станет идеальным квадратом, или когда $s$ превысит $10^{18}$ - что произойдет первым. Например, если $s$ пройдет значения $0, 2, 3, 5, 7, 9$, процесс закончится на $s=9$ и окажутся пропущенными два квадрата: $1$ и $4$.

Пусть $f(\rho)$ будет ожидаемым количеством идеальных квадратов, пропущенных к окончанию процесса.

Можно показать, что степенным рядом для $f(\rho)$ является $\sum_{k=0}^\infty a_k \rho^k$ для подходящего (уникального) выбора коэффициентов $a_k$. Среди первых нескольки элементов присутствуют $a_0=1$, $a_1=0$, $a_5=-18$, $a_{10}=45176$.

Пусть $F(n) = \sum_{k=0}^n a_k$. Известно, что $F(10) = 53964$ и $F(50) \equiv 842418857 \pmod{10^9}$.

Найдите $F(1000)$ и приведите в качестве ответа остаток от деления полученного результата на $10^9$.