#P9743. LJJ 的生日礼物
LJJ 的生日礼物
题目描述
一条长度为 的纸带由 个方格组成,从左到右编号为 。用编号为 的颜色给每格涂一种颜色,要求相距 或 的两个方格颜色不同。此外有 个预先指定的颜色要求,第 个要求是方格 必须涂成颜色 。
求符合所有要求的涂色方案数,对 取模。方格按固定方向比较,只要某一位置颜色不同,就视为不同方案。
输入格式
第一行一个整数 ,表示测试组数。
对于每组数据,第一行三个整数 。
接下来 行,每行两个整数 。位置按严格递增的顺序给出。
输出格式
输出 行。第 组数据的输出格式为 Case #x: y,其中 是该组答案, 从 开始。
样例
3
0 3 4
1 4 4
1 1
2 5 5
1 1
3 2
Case #1: 6
Case #2: 12
Case #3: 27
数据范围
对于全部数据,,,,,,。至多 组数据满足 。
- 原题测试点 1–3 满足 ,。
- 原题测试点 4–6 满足 ,。