Octagon — RMI contest
Task type: batch | Time limit: 2 s | Memory limit: 256 MB | Difficulty: 24
Algorithms: lagrange interpolation

Romanian Master of Informatics, Day 1
Bucharest, Romania
Thursday 28th November, 2024

# Problem Octagon

| Input file  | stdin  |
|-------------|--------|
| Output file | stdout |

A *nice octagon* is a convex figure with nonzero area with *at most 8* edges, where each edge is either parallel to the coordinate axes, or makes a 45° angle with them. All edges parallel to the coordinate axes must have integer lengths; all other edges must have lengths that are integer multiples of √2. Below we can see a few examples of nice octagons.

![](_page_0_Figure_5.jpeg)

Suppose we walk around the edges of a nice octagon in *counter-clockwise* order. We observe that it is formed out of length 1 and √2 segments that join two grid points that are consecutive in the walk. Consequently, the segments are split into 8 different categories, depending on the direction in which they go: north, north-east, east, south-east, south, south-west, west, and north-west.

Suppose you are given the maximum number of segments of each category that you can use. How many different nice octagons can you form?

## Input data

The first and only line of the input contains 8 space-separated integers — the maximum number of segments going in the north, north-east, east, south-east, south, south-west, west, and northwest directions.

## Output data

Output the required count of nice octagons, modulo 10<sup>9</sup> + 7.

### Restrictions

- Let N be the maximum of the eight values in the input.
- N ≤ 1 000 000 000
- Two nice octagons are considered the same if one can be obtained from the other by a translation *but without using rotations*. In particular, two nice octagons are the same if and only if they use the same number of segments of each of the eight types.

| # | Points | Restrictions                              |
|---|--------|-------------------------------------------|
| 1 | 9      | There are no diagonal segments available. |
| 2 | 17     | N ≤ 100                                 |
| 3 | 29     | N ≤ 2 000                               |
| 4 | 29     | N ≤ 200 000                             |
| 5 | 16     | No further restrictions.                  |

## Examples

| Input file                      | Output file |
|---------------------------------|-------------|
| 1 0 1 0 1 0 1 0                 | 1           |
| 1 1 1 1 1 1 1 1                 | 19          |
| 2 2 2 2 2 2 2 2                 | 228         |
| 1 2 3 4 4 3 2 1                 | 135         |
| 100 100 100 100 100 100 100 100 | 636061137   |

## Explanations

In the first example, the only nice octagon is a 1 × 1 square.

In the second example, there are 19 nice octagons.

Starter code: