本题样例格式有误，正确样例如下：

输入样例：

5
1 1 0
4 4 1
2 1
3 3 0
7 10 2
1 2
7 1
4 4 1
3 2

输出样例：

Case #1: 1
Case #2: 2
Case #3: 0
Case #4: 5
Case #5: 1

本题是经典容斥 dp，同时涉及组合数的计算以及 Lucas 定理，因此建议评蓝 $\sim$ 紫（参考 Grid 2），并添加dp、容斥、Lucas 定理的标签。