#2160. [SCOI2009]游戏

[SCOI2009]游戏

题目描述

windy 学会了一种游戏。对于 11nnnn 个数字,都有唯一且不同的 11nn 的数字与之对应。

最开始 windy 把数字按顺序 1,2,3,,d1,2,3,\cdots,d 写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复,直到序列再次变为 1,2,3,,d1,2,3,\cdots,d。如:1,2,3,4,5,61,2,3,4,5,6 对应的关系为 12,23,31,45,54,661\to2,2\to 3,3\to 1,4\to5,5\to4,6\to 6

windy 的操作如下:

1 2 3 4 5 6

2 3 1 5 4 6

3 1 2 4 5 6

1 2 3 5 4 6

2 3 1 4 5 6

3 1 2 5 4 6

1 2 3 4 5 6

这时,我们就有若干排 11nn 的排列,上例中有 77 排。现在 windy 想知道,对于所有可能的对应关系,有多少种可能的排数。

输入格式

一个整数,nn

输出格式

一个整数,可能的排数。

3
3
10
16

数据规模与约定

对于 30%30\% 的数据,满足 1n101\le n\le 10

对于 100%100\% 的数据,满足 1n1031\le n\le 10^3