#P18748. [正睿NOI2021训练] 纸带
[正睿NOI2021训练] 纸带
纸带
有一条宽为 、长为 的纸带,将其首尾相接拼成一个环。
使用若干边长为正整数、面积不超过 的小矩形,不重不漏地覆盖纸带外侧。每个小矩形染上 种颜色中的一种,要求:
- 外侧任意一点都恰好被一块小矩形覆盖,覆盖在边界处按通常铺砖方式理解。
- 小矩形的任何部分都不能超出纸带外侧。
- 任意四块小矩形没有公共点。
- 任意两块有公共边段的小矩形颜色不同。
- 小矩形不能绕环一周后与自己形成公共边;特别地, 时,不允许一块小矩形沿长度方向覆盖整个圆周。
每块矩形只能横放或竖放。允许矩形跨越纸带首尾接缝。
求本质不同的带颜色覆盖方案数。两种方案当且仅当通过环的旋转可以重合时视为相同;颜色的名称固定,不能交换颜色。对 取模。
输入格式
一行两个正整数 。
输出格式
一个整数,表示本质不同方案数模 的结果。
数据范围
。
样例 1
输入
2 3
输出
9
样例 2
输入
30 3
输出
363308443