萌妹子最近在玩一个填数字的游戏：将N种不同的数字填写到正五角星的顶角处，每种数字可以使用多次或者不使用。

一种填写方案经过旋转得到的不同方案算作一种。萌妹子想知道一共有多少种不同的填写方案，你可以帮她解决吗？



有多组测试用例，每组测试用例包含一个整数N，代表萌妹子有N种不同的数字（0<N<=2000）。



输出对于N种不同数字的填写方案数。


样例输入

1
2
3
123


样例输出

1
8
51
5630611467

“只填1种数，每种都用到，有1种方案
 只填2种数，每种都用到，有6种方案
 只填3种数，每种都用到，有30种方案
 只填4种数，每种都用到，有48种方案
 只填5种数，每种都用到，有24种方案”
这个是怎么算出来的？