bzoj#P3028. 食物

食物

题目描述

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

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

当然,他又有一些稀奇古怪的限制:

每种食物的限制如下:

  • 承德汉堡:偶数个
  • 可乐:00 个或 11
  • 鸡腿:00 个,11 个或 22
  • 蜜桃多:奇数个
  • 鸡块:44 的倍数个
  • 包子:00 个,11 个,22 个或 33
  • 土豆片炒肉:不超过一个
  • 面包:33 的倍数个

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

输入格式

一个整数 nn,表示总数。

输出格式

一个整数,表示方案数模 1000710007

1
1
5
35

数据范围

对于 40%40\% 的数据,1n1×1051\leq n\leq 1\times 10^5

对于 100%100\% 数据,1n105001\leq n\leq 10^{500}