题目背景

学校资料室有一种自动复印任务单。每张任务单刚进入系统时需要先进行准备，准备完成后才会开始派生新的任务单。

在第 $0$ 小时时，系统中有且仅有 $1$ 张刚刚出现的任务单。老师想知道，经过 $n$ 个小时后，系统中共有多少张任务单。

题目描述

每张任务单从出现时开始计时，刚出现时的存在时间记为 $0$ 小时。

每经过一个小时，系统按照以下规则处理所有任务单：

也就是说，每张任务单会分别在其出现后的第 $3$ 小时和第 $4$ 小时各产生 $2$ 张新任务单，并在第 $4$ 小时产生新任务单后被移除。

请计算经过 $n$ 小时后，系统中任务单的数量。由于答案可能很大，只需要输出答案对 $21474836$ 取模后的结果。

输入一行一个整数 $n$ ，表示经过的小时数。

输出一行一个整数，表示经过 $n$ 小时后系统中的任务单数量对 $21474836$ 取模后的结果。

对于样例 $1$ ，初始任务单在前两个小时内只进行准备，不会产生新的任务单，因此经过 $2$ 小时后，系统中仍然只有 $1$ 张任务单。

对于样例 $2$ ，任务单在各个时刻的数量如下表所示。表中的“存在 $x$ 小时”表示已经在系统中完整存在了 $x$ 个小时的任务单数量。

经过时间	存在 $0$ 小时	存在 $1$ 小时	存在 $2$ 小时	存在 $3$ 小时	本小时发生的变化	系统总数
$0$ 小时	$1$	$0$	$0$	$0$	系统中初始有 $1$ 张任务单	$1$
$1$ 小时	$0$	$1$	$0$	$0$	初始任务单完成第 $1$ 小时的准备	$1$
$2$ 小时	$0$	$0$	$1$	$0$	初始任务单完成第 $2$ 小时的准备	$1$
$3$ 小时	$2$	$0$	$0$	$1$	初始任务单产生 $2$ 张新任务单	$3$
$4$ 小时	$2$	$2$	$0$	$0$	初始任务单再次产生 $2$ 张新任务单，随后被移除	$4$

第 $4$ 小时结束时，第 $3$ 小时产生的 $2$ 张任务单已经存在 $1$ 小时，第 $4$ 小时又产生了 $2$ 张新任务单，而最初的任务单已经被移除，因此系统中共有 $4$ 张任务单。

对于 $60%$ 的数据，保证 $1\le n\le30$ 。

对于另外 $20%$ 的数据，保证 $31\le n<110$ 。

对于全部数据，保证 $1\le n<150$ 。