题目描述

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

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

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

每种食物的限制如下：

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

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

输入格式

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

输出格式

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

1

1

5

35

提示

• 对于 $40\%$ 的数据，但是 $1\leq n\leq 10^5$；
• 对于所有数据，$1\leq n\leq 10^{500}$；