Valentine’s Cake(cake)

Grade 0 Open Time Wednesday, 10 October 2012, 4:05 pm
Discount 0.8 Time Discount Wednesday, 10 October 2012, 4:05 pm
Allow late Yes Close Time Wednesday, 10 October 2012, 4:05 pm

描述

今天是情人节,小杉得到了一个蛋糕(怎么那么多蛋糕……)。

小杉现在很无聊,于是他想给蛋糕上色。小杉的想法是这样的,他先用刀把蛋糕切成若干块,然后再对每个部分上色(怎么又是上色……)。小杉的切法是这样的,一共切n次,每次从蛋糕中某一点(不能在蛋糕边缘)下手,然后用刀痕引出两条射线,一直切到蛋糕的边缘。而且小杉很笨,每次都只能切出固定的一种形状,但是每次的形状都把蛋糕切成了尽可能多块。

一个可爱的上色方案应该满足每个区域只能上粉红或天蓝两种颜色(相邻区域可以同色)。

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

输入格式

一行一个整数n(0<=n<=1000)

输出格式

仅有一行,一个整数,为上色方案数对19900801取模的结果(@#$%,怎么都一样的……)

样例输入

1

样例输出

4

样例解释

切一次,小杉会把蛋糕切成两个部分,每个部分两种上色可能,一共四种可能(2*2)。