407562: GYM102829 I Luke's Math Problem

Luke likes math problems, so he has asked you to solve this problem.

Given a vector $$$\langle x,y \rangle$$$, what is the total number of nonempty sequences of vectors $$$\{a_i\}_{i=0}^n$$$ such that:

• $$$a_0 = \langle x,y \rangle$$$.
• $$$\forall i > 0, i \in \mathbb{Z}, ||a_i||_2 < ||a_{i-1}||_2$$$.
• $$$\forall i > 0, i \in \mathbb{Z}, ||a_i - a_{i-1}||_2 < \sqrt{2}$$$.
• All vectors in $$$\{a_i\}$$$ have only integer entries.

Moreover, he will give you $$$Q$$$ queries, and you need to output the answer for each of these $$$\mod 10^9 + 7$$$ (a prime).

Note that for vector $$$v$$$ of dimension $$$n$$$, $$$||v||_2 = \sqrt{\sum_{i=1}^n v_i^2}$$$.

An integer $$$Q$$$, $$$1 \leq Q \leq 10^6$$$ which gives the number of queries. $$$Q$$$ lines follow, each with two space separated integers $$$x_i$$$ and $$$y_i$$$, $$$0 \leq |x_i|, |y_i| \leq 10^6$$$, representing the $$$i$$$th query.

On the $$$i$$$th line output the total number of nonempty sequence of vectors that satisfy the above properties for $$$\langle x_i,y_i \rangle$$$.

4
0 2
0 -1
0 -2
-3 -4

3
2
3
125