## DS '19 Day 1 P1 - Arithmetic Square

View as PDF

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 1G

Author:
Problem type

You are given a grid which contains integers.

Some of the 9 elements in the grid will have a value already, and the remaining elements will be unspecified. Every element, including those which are unspecified, must be an integer from to , inclusive.

Your task is to determine the number of ways to fill the grid so that each row, when read from left-to-right is an arithmetic sequence, and that each column, when read from the top-down, is an arithmetic sequence. There is guaranteed to be at least one way. As this number may be large, please output it modulo .

Two ways of filling the grid are distinct if there is some cell which contains a different number in each way of filling the grid.

Recall that an arithmetic sequence of length three is a sequence of integers of the form

for integer values of and . Note that may be any integer, including zero or a negative integer.

#### Input Specification

The input will be 3 lines long. Each line will have three space-separated values. Each given value will either be an integer in the range from to , inclusive, or the symbol X. However, the unspecified values may be integers in the range from to , inclusive.

For 10 of the 100 marks available, there will be 9 X symbols in the input.

For an additional 40 of the 100 marks available, there will be 8 X symbols in the input.

For an additional 40 of the 100 marks available, there will be 7 X symbols in the input.

For the final 10 of the 100 marks available, there will be 4 X symbols in the input.

#### Output Specification

Output a single integer, the number of valid ways to fill the grid taken modulo .

#### Sample Input 1

8 9 10
16 X 20
24 X 30

#### Sample Output 1

1

#### Sample Input 2

X 0 X
0 0 0
X 0 X

#### Sample Output 2

2000001