生日礼物的意外

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

我们的大队长xiaoyoulei同学,在过生日的时候收到了rayafjyblue送他的手链,这个手链是什么样子的呢,它有n个珠子,这n个珠子颜色都是不一样的,但是不小心被bobo弄散了,xiaoyoulei很生气,结果把波波揍了一顿,并且要bobo把手链接好,bobo在接手链的时候突然很想了解一个问题,就是他最多可以拼成多少种,因为他人品比较尴尬,所以他想知道他最多要拼多少次,才可以还原,我们认为经过旋转,翻转以后变成一样的是同一种,由于bobo眼神很好,所以他可以保证他每次不会接成一样的方案,现在他很头疼,所以他来问我,但是由于我要出题,所以我就问你们了

Input

每一行有一个整数n,表示有多少个珠子,n<=500 输入以n=-1结束

Output

输出一个整数,表示最多尝试的次数,由于数字会很大,所以最后的值模除一个3000

Sample Input

1
2
3
4
5
-1

Sample Output

1
3
11
70
629

Hint

大数使用long long,切莫使用__int64

Source

watermelon::hdd

提交代码