Farmer John 喜欢和他的 $N$ 头奶牛玩数学游戏。最近，他们被递推序列吸引了。在每一轮中，奶牛们会排成一排，而 John 会在黑板上写下两个正整数 $a$ 和 $b$。然后，奶牛们会依次报出自己的数。第一头奶牛报 $a$，第二头奶牛报 $b$。此后，第 $i$ 头奶牛报出的数是倒数第二个数的两倍、最后一个数以及 $i^4$ 的和。

现在，你需要编写一个程序来计算第 $N$ 头奶牛报出的数，以检查 John 的奶牛们是否报对了。

输入格式

输入的第一行包含一个整数 $t$，表示测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例仅包含一行，其中有三个数 $N$、$a$ 和 $b$（$N, a, b < 2^{31}$），含义如上所述。

输出格式

对于每个测试用例，输出第 $N$ 头奶牛报出的数。由于这个数可能非常大，你需要将其对 $2147493647$ 取模后输出。

样例

输入格式 1

2
3 1 2
4 1 10

输出格式 1

85
369

说明

在第一个样例中，第三个数为 $85 = 2 * 1 + 2 + 3^4$。

在第二个样例中，第三个数为 $93 = 2 * 1 + 1 * 10 + 3^4$，第四个数为 $369 = 2 * 10 + 93 + 4^4$。