## DMOPC '21 Contest 7 P6 - Rainbow Subgraphs

View as PDF

Points: 30 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

You are given positive integers , , and .

Let be the set of points in the plane such that and are integers, , and . Let be a set of undirected edges between elements of , where if point and point are distance apart.

Calculate the number of subgraphs of the graph , modulo . That is, the number of pairs such that , , and for all . Note that and/or are allowed to be empty or equal to or respectively.

#### Input Specification

The first and only line of input contains three space-separated integers: , , and .

#### Output Specification

Output the number of subgraphs modulo .

#### Sample Input 1

1 1 998244352

#### Sample Output 1

89

#### Explanation for Sample 1

The graph looks like the following:

#### Sample Input 2

2 2 998244352

#### Sample Output 2

41377047

#### Explanation for Sample 2

The graph looks like the following:

#### Sample Input 3

31 4 159265358

#### Sample Output 3

54714600