给定正整数 以及 的排列 。
称一个大小为 ，元素均为 中的正整数的矩阵为一幅画。对于一幅画 ，定义 为这个矩阵从上到下第 行，从左到右第 列的位置的值。
定义两幅画 相同，当且仅当对于所有 ，，均有 。以下将两幅画 相同记作 。
定义两幅画 相似，当且仅当 进行若干次如下两种变换之一可以得到 ：
- 将 的第一行移动至最后一行；
- 将 的第一列移动至最后一列。
以下将两幅画 相似记作 。
可以证明，二元关系相同和相似均构成等价关系。
对于一幅画 ，定义 也是一幅画，其中 (, )。
定义一幅画 是优美的，当且仅当 。
你需要回答以下两个问题：
- 最多能选出多少幅优美的画，使得它们互不相同？
- 最多能选出多少幅优美的画，使得它们互不相似？
由于答案可能较大，你只要求求出答案对 取模后的结果。
