#P18075. Tiling the Floor
Tiling the Floor
Tiling the Floor
题目描述
一块瓷砖由 个方格组成。每个方格的下边和左边各有一条灯带,因此一块瓷砖共有 条灯带。每条灯带可以独立选择 种颜色之一。
把这块瓷砖的图案无限复制,所有瓷砖保持相同朝向,通过平移无缝铺满整个无限平面。
若两个无限图案经过平移和旋转后,所有对应位置的灯带颜色都相同,则认为它们是同一种方案。旋转可改变观察的东、南、西、北方向;不允许镜像反射。颜色的名字固定,不允许把不同颜色统一重命名来判等。
求本质不同的染色方案数,对 取模。比较的是无限平面图案,因此平移不必是整块瓷砖的整数倍,可以是任意整数个方格。
输入格式
第一行整数 。每组数据一行两个整数 。
,。
输出格式
每组输出一行一个整数,表示答案对 取模的结果。
样例 1
输入
3
1 2
2 2
114514 5201314
输出
3
31
377726028
当 时,答案为 。旋转和平移视为相同,镜像不在允许的等价变换中。