题目描述

明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带 $n$ 件物品的方案数。

他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。

当然，他又有一些稀奇古怪的限制：

每种食物的限制如下：

• 承德汉堡：偶数个
• 可乐：$0$ 个或 $1$ 个
• 鸡腿：$0$ 个，$1$ 个或 $2$ 个
• 蜜桃多：奇数个
• 鸡块：$4$ 的倍数个
• 包子：$0$ 个，$1$ 个，$2$ 个或 $3$ 个
• 土豆片炒肉：不超过一个
• 面包：$3$ 的倍数个

注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以“个”为单位（反正是幻想嘛），只要总数加起来是 $n$ 就算一种方案。因此，对于给出的 $n$，你需要计算出方案数，并对 $10007$ 取模。

输入格式

一个整数 $n$，表示总数。

输出格式

一个整数，表示方案数模 $10007$。

输入样例 #1

1

输出样例 #1

1

输入样例 #2

5

输出样例 #2

35

数据范围与约定

对于 $40\%$ 的数据，$1\leq n\leq 1\times 10^5$。

对于 $100\%$ 数据，$1\leq n\leq 10^{500}$。