atcoder#ABC280G. [ABC280G] Do Use Hexagon Grid 2
[ABC280G] Do Use Hexagon Grid 2
Score : points
Problem Statement
We have an infinite hexagonal grid shown below.
A hexagonal cell is represented as with two integers and . Cell is adjacent to the following six cells:
Let us define the distance between two cells and by the minimum number of moves required to travel from cell to cell by repeatedly moving to an adjacent cell. For example, the distance between cells and is , and the distance between cells and is .
You are given cells . How many ways are there to choose one or more from these cells so that the distance between any two of the chosen cells is at most ? Find the count modulo .
Constraints
- are pairwise distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
Output
Print the answer.
3 1
0 0
0 1
1 0
5
There are five possible sets of the chosen cells: , and .
9 1
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
33
5 10000000000
314159265 358979323
846264338 -327950288
-419716939 937510582
-97494459 -230781640
628620899 862803482
31