问题描述

$f(1) = 1$

$f(2) = 2$

$f(n) = 3 f(n - 1) + 2 f(n - 2)$

结果对 $49999$ 取余

输入格式

正整数 $n(1<n\le1000)$ 。

输出格式

一个数字，表示结果，对 $49999$ 取余。

样例

3

8