OI题库

描述

今天是情人节，小杉得到了一个蛋糕（怎么那么多蛋糕……）。

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

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

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

输入格式

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

输出格式

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

样例输入

1

样例输出

4

样例解释

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