Valentine’s Present
描述
今天是情人节，小杉已经想好了要给喜欢的人送一份特殊的情人节礼物。
礼物是n个颜色各异的箱子，每个箱子里装一个蛋糕，蛋糕是可以上色的。
一个可爱的上色方案应该满足如下条件：
1． 任意一个蛋糕上的颜色应与一个箱子相同（可以是装它的那个箱子的颜色）。
2． 任意开启一个箱子，按里面蛋糕的颜色打开对应的箱子，这两个箱子（也可以是同一个）里的蛋糕颜色相同。
小杉现在想知道总共有多少种可爱的上色方案。
格式
输入格式
一行一个整数n(1<=n<=25)
输出格式
仅有一行，一个整数，为上色方案数对19900801取模的结果
样例1
样例输入1
2
样例输出1
3
限制
每个测试点1s
提示
样例解释：
假设两个箱子一黑一白，可爱的上色方案有如下三种（箱子颜色→蛋糕颜色）：
1．黑→黑，白→白
2．黑→白，白→白
3．黑→黑，白→黑
来源
lolanv
