BZOJ3028 食物

明明这次又要出去旅游了，和上次不同的是，他这次要去宇宙探险！我们暂且不讨论他有多么 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}$；