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.
Constraints
Subtask 1 [20%]
Subtask 2 [20%]
Subtask 3 [20%]
Subtask 4 [20%]
Subtask 5 [20%]
No additional constraints.
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
Comments