#P17880. Grid Problem
Grid Problem
Yotsugi 有一个高为 、宽为 的整数网格 ,最初所有元素均为 。她可以按任意顺序进行任意多次以下两种操作,也可以不进行操作。
网格是环形的:所有行下标对 取模,所有列下标对 取模。以下使用从 开始的下标。
每次操作选择位置 (,),并选择符号 。
-
将以 为左上角的 区域,分别加上矩阵
-
将以 为左上角的 区域,分别加上矩阵
一次操作中的所有格子必须使用同一个符号。区域跨越边界时按上述取模规则处理。
她想知道:经过这些操作后,能得到多少种不同的网格,使最终每个元素都在 内?
操作过程中,元素可以为负数,也可以大于 ;只有最终网格受到 的限制。 两个最终网格只要有一个位置的值不同,就视为不同。
输出答案对 取模的结果。
输入格式
一行三个整数 。
输出格式
输出一个整数,表示答案对 取模的结果。
数据范围
,。
样例
3 3 1
2
样例说明
满足要求的最终网格是全零网格和全一网格。