Making Shapes
Contest: Codeforces Round 616 (Div. 1)
Difficulty rating: 3500
Tags: dp

You are given $$$n$$$ pairwise non-collinear two-dimensional vectors. You can make shapes in the two-dimensional plane with these vectors in the following fashion:

1. Start at the origin $$$(0, 0)$$$.
2. Choose a vector and add the segment of the vector to the current point. For example, if your current point is at $$$(x, y)$$$ and you choose the vector $$$(u, v)$$$, draw a segment from your current point to the point at $$$(x + u, y + v)$$$ and set your current point to $$$(x + u, y + v)$$$.
3. Repeat step 2 until you reach the origin again.

You can reuse a vector as many times as you want.

Count the number of different, non-degenerate (with an area greater than $$$0$$$) and convex shapes made from applying the steps, such that the shape can be contained within a $$$m \times m$$$ square, and the vectors building the shape are in counter-clockwise fashion. Since this number can be too large, you should calculate it by modulo $$$998244353$$$.

Two shapes are considered the same if there exists some parallel translation of the first shape to another.

A shape can be contained within a $$$m \times m$$$ square if there exists some parallel translation of this shape so that every point $$$(u, v)$$$ inside or on the border of the shape satisfies $$$0 \leq u, v \leq m$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$  — the number of vectors and the size of the square ($$$1 \leq n \leq 5$$$, $$$1 \leq m \leq 10^9$$$).

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$  — the $$$x$$$-coordinate and $$$y$$$-coordinate of the $$$i$$$-th vector ($$$|x_i|, |y_i| \leq 4$$$, $$$(x_i, y_i) \neq (0, 0)$$$).

It is guaranteed, that no two vectors are parallel, so for any two indices $$$i$$$ and $$$j$$$ such that $$$1 \leq i < j \leq n$$$, there is no real value $$$k$$$ such that $$$x_i \cdot k = x_j$$$ and $$$y_i \cdot k = y_j$$$.

Output format:
Output a single integer  — the number of satisfiable shapes by modulo $$$998244353$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 768.0 MB

Note:
The shapes for the first sample are:

The only shape for the second sample is:

The only shape for the fourth sample is:

Example input:
3 3
-1 0
1 1
0 -1

Example output:
3

Example input:
3 3
-1 0
2 2
0 -1

Example output:
1

Editorial:
Notice that there is a one-to-one correspondent between a non-degenerate convex shape and a non-empty multiset of vectors. That is because, for each shape, we can generate exactly one multiset of vectors by starting at the lowest-leftest point going counter-clockwise (this is possible because no two vectors are parallel); and for each multiset of vectors, we can generate a single convex shape by sorting the vectors by angle then add them in order.
Our problem is now counting the number of multisets of vectors that makes non-degenerate convex shapes that can be contained in a $$$m \times m$$$ square. Rather, we denote $$$c_i$$$ as the number of times the $$$i^{th}$$$ vector appears in our multiset. We need to count the number of arrays $$$c$$$ such that:
1. $$$\displaystyle \sum_{i=1}^{n} c_ix_i = \sum_{i=1}^{n} c_iy_i = 0$$$
2. $$$\displaystyle \sum_{1 \leq i \leq n,\, x_i > 0} c_ix_i \leq m$$$
3. $$$\displaystyle \sum_{1 \leq i \leq n,\, y_i > 0} c_iy_i \leq m$$$
Note that the first conditions are equivalent to $$$\displaystyle \sum_{1 \leq i \leq n,\, x_i < 0} -c_ix_i = \sum_{1 \leq i \leq n,\, x_i > 0} c_ix_i$$$ and $$$\displaystyle \sum_{1 \leq i \leq n,\, y_i < 0} -c_iy_i = \sum_{1 \leq i \leq n,\, y_i > 0} c_iy_i$$$.
For the sake of brevity, let's call $$$\displaystyle \sum_{1 \leq i \leq n,\, x_i < 0} -c_ix_i$$$, $$$\displaystyle \sum_{1 \leq i \leq n,\, x_i > 0} c_ix_i$$$, $$$\displaystyle \sum_{1 \leq i \leq n,\, y_i < 0} -c_iy_i$$$, and $$$\displaystyle \sum_{1 \leq i \leq n,\, y_i > 0} c_iy_i$$$ by $$$nx$$$, $$$px$$$, $$$ny$$$, and $$$py$$$ respectively.
We will now focus on $$$\log_2{m}$$$ layers of the array $$$c$$$, the $$$i^{th}$$$ layer is represented by a bitmask of $$$n$$$ bits, where each bit $$$j$$$ is the $$$i^{th}$$$ bit in the binary representation of $$$c_j$$$. We see that if we iterate over these layers like this, we can slowly construct $$$nx$$$, $$$px$$$, $$$ny$$$, and $$$py$$$ bit by bit, and be able to compare them with each other and with $$$m$$$. So, we do a dynamic programming solution where we maintain these states:
• The current bit.
• The carry-over value for $$$nx$$$.
• The carry-over value for $$$px$$$.
• The carry-over value for $$$ny$$$.
• The carry-over value for $$$py$$$.
• Whether the suffix of $$$px$$$ is larger than the suffix of $$$m$$$.
• Whether the suffix of $$$py$$$ is larger than the suffix of $$$m$$$.
When we iterate over the states, we iterate over the bitmask of the current layer and calculate and update on the next states. note that, for $$$px$$$ for example, the carry-over value has a limit of $$$\displaystyle \sum_{i=1}^{\infty} \lfloor \frac{px}{2^i} \rfloor = px$$$, and $$$px \leq 4n$$$, so each carry-over dimension is at most $$$4n$$$ (practically they cannot all be $$$4n$$$ at the same time, so pre-calculating the bound for each dimension is necessary).
Complexity: $$$O(\log_2{m} \cdot n^4 \cdot 2^n)$$$.