当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6470：Count

题目描述
Farmer John有n头奶牛.
某天奶牛想要数一数有多少头奶牛,以一种特殊的方式:
第一头奶牛为1号,第二头奶牛为2号,第三头奶牛之后,假如当前奶牛是第n头,那么他的编号就是2倍的第n-2头奶牛的编号加上第n-1头奶牛的编号再加上自己当前的n的三次方为自己的编号.
现在Farmer John想知道,第n头奶牛的编号是多少,估计答案会很大,你只要输出答案对于123456789取模.
输入解释
第一行输入一个T,表示有T组样例
接下来T行,每行有一个正整数n,表示有n头奶牛 (n>=3)
其中，T=10^4,n<=10^18
输出解释
共T行,每行一个正整数表示所求的答案
输入样例 
5
3
6
9
12
15
输出样例 
31
700
7486
64651
527023
来自杭电HDUOJ的附加信息
Recommend liuyiding
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 “字节跳动-文远知行杯”广东工业大学第十四届程序设计竞赛
源链接： HDU-6470
最后修改于 2020-10-25T23:31:38+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 65536/65536K(Java/Others)