D. Exam Room
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Busy Beaver is hosting an upcoming exam for his students in the MITIT exam room. Due to last-minute preparation and bad testing, the students will need to come up to him to complain about things like bad difficulty distributions, server issues, misleading statements, and awful flavortexts without disturbing other students, so he needs to ensure that the seats are well separated.

The room has $$$N$$$ seats at points $$$P_i = (x_i,y_i)$$$, with Busy Beaver's desk located at $$$O = (0,0)$$$. He wants to choose a nonempty subset of the seats satisfying the following condition:

  • Each seat in the subset is strictly closer to Busy Beaver's desk than any other seat in the subset. Formally, for all pairs $$$P_i,P_j$$$ ($$$i \neq j$$$) in the subset, $$$\text{dist}(P_i,P_j) \gt \text{dist}(O,P_i)$$$, where $$$\text{dist}$$$ denotes Euclidean distance.

How many nonempty subsets satisfy this criterion? Since the answer may be enormous, output it modulo $$$998\,244\,353$$$.

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 500$$$).

The $$$i$$$-th of the next $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \le x_i,y_i \le 10^9$$$).

All $$$N$$$ points in the input are distinct and not equal to $$$(0,0)$$$.

Output

Output a single integer — the number of valid nonempty subsets modulo $$$998\,244\,353$$$.

Scoring

There are four subtasks for this problem.

  • ($$$10$$$ points): $$$N$$$ does not exceed $$$15$$$.
  • ($$$10$$$ points): $$$N$$$ does not exceed $$$24$$$.
  • ($$$10$$$ points): $$$N$$$ does not exceed $$$80$$$.
  • ($$$70$$$ points): No additional constraints.
Examples
Input
2
1 2
2 1
Output
2
Input
3
1 2
2 1
1 -3
Output
5
Note

In the first sample, the two desks are $$$\sqrt{2}$$$ apart and $$$\sqrt{5}$$$ away from the origin, so either one or the other can be used.

In the second sample, the third desk is $$$\sqrt{10}$$$ away from the origin and $$$\sqrt{17}$$$ away from the closest other desk, so the third desk can always be used. The valid subsets are: $$$$$$ \{\text{desk }1\}, \{\text{desk }2\}, \{\text{desk }3\}, \{\text{desk }1, \text{desk }3\}, \{\text{desk }2, \text{desk }3\}. $$$$$$