Description

出发之前,奇奇多年的朋友灰灰觉得他这次的冒险凶(bi)多(si)极(wu)少(yi),但奇奇也不听劝.没有办法的灰灰也不能看着朋友白白送死,只好拿出一个珍藏许久的珍珠手链,这个手链由许多颜色都不一样的珍珠组成,希望能给奇奇带来一丝幸运,能保佑奇奇成功归来.

奇奇回到家后,拿出灰灰送的珍珠手链,觉得的确很神奇,因为这么多珍珠,颜色都不一样,而且每种颜色的排列貌似有种很特别的顺序.正仔细观察着,忽然一不小心把珍珠手链掉到了地上,珍珠手链意外的断开了,五颜六色的珍珠撒了一地,幸亏奇奇眼急手快,一颗不落的都捡了起来,正准备再次串起来的时候,发现了一个大问题,忘记顺序了!这可不好办.所以奇奇想让你们帮助他计算下一共有多少种排列可能?已知这个手链由 n 个颜色各不一的珍珠组成(顺序按照同一种方向计算).

Format

Input

输入数据有多组.每组输入包含一个整数 n(0 < n <= 100),含义如题所示.

Output

对于每组输入,输出一个数字,代表着一共有多少种可能排列, 最后的答案需要对 1,000,000,007 取模.

Samples

2
3

1
2

Hint