问题描述

$f(1) = 1$

$f(2) = 3$

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

请使用递归的方法计算，结果对 $49999$ 取余

输入格式

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

输出格式

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

3

11