鸽鸽

题目描述

我说我会鸽结果我真鸽了，也是一种不鸽。

一个字符串是香的当且仅当它同时包含 CXIV 和 DXIV 两种子串，两种子串都只能在该串中出现一次。同时还要满足 CXIV 比 DXIV 更早出现，等价于 CXIV 必须在 DXIV 的左侧。

求长度为 $n$ 的所有只包含大写字母的字符串中，有多少个字符串是香的，结果对 $10^9 + 7$ 取模。

输入

第一行包含一个整数 $T$ ($T \le 200$)，表示数据组数。

对于每组数据，每行为一个正整数 $n$ ($1 \le n \le 10^{9}$)，表示你要求的字符串长度。

输出

对于每组数据，输出一行，格式为 Case #number: result，其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据，而 $\mathrm{result}$ 为答案对 $10^9 + 7$ 取模的结果。

输入样例

5
1
8
9
10
16

输出样例

Case #1: 0
Case #2: 1
Case #3: 78
Case #4: 4056
Case #5: 121875205