题目描述

农夫约翰（Farmer John）拥有一个农场。他首先建造一道圆形围栏。接着，他将选取 $n$ 个点，并建造一些直线围栏将这些点连接起来。然后，他会在每个区域中饲养一头奶牛，使得奶牛在不破坏围栏的情况下无法彼此嬉戏。为了饲养更多的奶牛，他还希望划分出尽可能多的区域。然而，他现在正忙于建造围栏，因此需要你帮助他确定：如果恰当地选取这 $n$ 个点，他最多能够饲养多少头奶牛。

:::align{center} :::

输入格式

第一行包含一个整数 $T$（$1 \le T \le 100000$），表示测试数据的组数。对于每组测试数据，有一行包含一个整数 $n$。数据保证 $1 \le T \le 10^5$ 且 $1 \le n \le 10^{18}$。

输出格式

对于每组测试数据，输出一行 Case #i: ans，其中 $i$ 是测试数据的编号（从 $1$ 开始），ans 是农夫约翰最多能饲养的奶牛数量对 $10^9 + 7$ 取模后的结果。

3
1
3
5

Case #1: 1
Case #2: 4
Case #3: 16

提示

翻译由 DeepSeek V4 Pro 完成