网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
Valentine’s Cake(cake)
成绩 | 0 | 开启时间 | 2012年10月10日 星期三 16:05 |
折扣 | 0.8 | 折扣时间 | 2012年10月10日 星期三 16:05 |
允许迟交 | 是 | 关闭时间 | 2012年10月10日 星期三 16:05 |
描述
今天是情人节,小杉得到了一个蛋糕(怎么那么多蛋糕……)。
小杉现在很无聊,于是他想给蛋糕上色。小杉的想法是这样的,他先用刀把蛋糕切成若干块,然后再对每个部分上色(怎么又是上色……)。小杉的切法是这样的,一共切n次,每次从蛋糕中某一点(不能在蛋糕边缘)下手,然后用刀痕引出两条射线,一直切到蛋糕的边缘。而且小杉很笨,每次都只能切出固定的一种形状,但是每次的形状都把蛋糕切成了尽可能多块。
一个可爱的上色方案应该满足每个区域只能上粉红或天蓝两种颜色(相邻区域可以同色)。
小杉现在想知道总共有多少种可爱的上色方案。
输入格式
一行一个整数n(0<=n<=1000)
输出格式
仅有一行,一个整数,为上色方案数对19900801取模的结果(@#$%,怎么都一样的……)
样例输入
1
样例输出
4
样例解释
切一次,小杉会把蛋糕切成两个部分,每个部分两种上色可能,一共四种可能(2*2)。