/ OIer TK / 题库 /

Valentine’s Present

Valentine’s Present

测试数据来自 system/1413

描述

今天是情人节,小杉已经想好了要给喜欢的人送一份特殊的情人节礼物。

礼物是n个颜色各异的箱子,每个箱子里装一个蛋糕,蛋糕是可以上色的。

一个可爱的上色方案应该满足如下条件:
1. 任意一个蛋糕上的颜色应与一个箱子相同(可以是装它的那个箱子的颜色)。

2. 任意开启一个箱子,按里面蛋糕的颜色打开对应的箱子,这两个箱子(也可以是同一个)里的蛋糕颜色相同。

小杉现在想知道总共有多少种可爱的上色方案。

格式

输入格式

一行一个整数n(1<=n<=25)

输出格式

仅有一行,一个整数,为上色方案数对19900801取模的结果

样例1

样例输入1

2

样例输出1

3

限制

每个测试点1s

提示

样例解释:
假设两个箱子一黑一白,可爱的上色方案有如下三种(箱子颜色→蛋糕颜色):
1.黑→黑,白→白
2.黑→白,白→白
3.黑→黑,白→黑

来源

lolanv

信息

ID
1385
难度
(无)
分类
组合数学 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者