今天是情人节，小杉已经想好了要给喜欢的人送一份特殊的情人节礼物。
礼物是n个颜色各异的箱子，每个箱子里装一个蛋糕，蛋糕是可以上色的。
一个可爱的上色方案应该满足如下条件：
1． 任意一个蛋糕上的颜色应与一个箱子相同（可以是装它的那个箱子的颜色）。
2． 任意开启一个箱子，按里面蛋糕的颜色打开对应的箱子，这两个箱子（也可以是同一个）里的蛋糕颜色相同。
小杉现在想知道总共有多少种可爱的上色方案
input:
一行一个整数n(1<=n<=25)
output:
仅有一行，一个整数，为上色方案数对19900801取模的结果
input:
2
output:
3
分析(转dfs35123)：
一些箱子里的蛋糕和箱子的颜色是相同的。其他箱子里的蛋糕颜色必须和这些箱子中某一个箱子的的颜色相同。设有k个箱子里的蛋糕和箱子的颜色相同，则一共有C(n,k)种情况。其他箱子里的蛋糕的颜色选择，根据乘法原理有k^(n-k)种，乘起来就是C(n,k)*k^(n-k)
【参考程序】：
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
long f[26],n;
int main()
{
scanf("%d",&n);
memset(f,0,sizeof(f));
f[0]=1;f[1]=1;
for (int i=2;i<=n;i++)
for (int j=i;j>=1;j--)
f[j]=(f[j]+f[j-1])%19900801;//根据杨辉三角计算组合数
long t,i,j,ans=0;
for (i=1;i<=n;i++)
{
t=f[i];
for (j=1;j<=n-i;j++) t=(t*i)%19900801;
ans=(ans+t)%19900801;
}
printf("%d\n",ans);
system("pause");
return 0;
}