该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

P10780 BZOJ3028 食物

题目描述

明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 NC，他又幻想了他应该带一些什么东西。理所当然的，你当然要帮他计算携带 $n$ 件物品的方案数。 他这次又准备带一些受欢迎的食物，如：蜜桃多啦，鸡块啦，承德汉堡等等。 当然，他又有一些稀奇古怪的限制： 每种食物的限制如下：

• 承德汉堡：偶数个；
• 可乐：$0$ 个或 $1$ 个；
• 鸡腿：$0$ 个，$1$ 个或 $2$ 个；
• 蜜桃多：奇数个；
• 鸡块：$4$ 的倍数个；
• 包子：$0$ 个，$1$ 个，$2$ 个或 $3$ 个；
• 土豆片炒肉：不超过一个；
• 面包：$3$ 的倍数个； 注意，这里我们懒得考虑明明对于带的食物该怎么搭配着吃，也认为每种食物都是以『个』为单位（反正是幻想嘛），只要总数加起来是 $n$ 就算一种方案。因此，对于给出的 $n$，你需要计算出方案数，并对 $10007$ 取模。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

1

输出 #1

1

输入输出样例 #2

输入 #2

5

输出 #2

35

说明/提示

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