最近,闲着没事的欧米茄同学迷上了机器人,而且花了£2^2^2^2买了很多机器人。他准备给这些机器人编排一个舞蹈:所有机器人组成四个方阵(四个正方形),然后再变成四个三角阵(四个正三角形)。比如,如果有144个机器人,就可以组成下面的队形:
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * *
*
* *
* * *
* * * *
* * * * *
* * * * * *
* * * * * * *
* * * * * * * *
* * * * * * * * * *
* * * * * * * * * * *
* * * * * * * * * * * *
* * * * * * * * * * * * *
* * * * * * * * * * * * * *
* * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * * *
机器人总数是固定的,可奇怪的是,要想组成这样的舞蹈队形,机器人的数目只能是某些特定的数字。我们把这些数字从小到大排列,第一个就是144,请你编程计算第n个数字是多少。由于结果比较大,你只需输出结果mod 1000000000的值即可。
数据范围:1 <= n <= 2147480000
输入一行,一个数字n
输出一行,一个正整数,即所求第n个数字mod 1000000000的值