背包
题号：NC207746
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

tacmon准备带大家去YZ一日游，他要带很多东西，一共有以下种： 肥宅快乐水，鸡腿，鸡翅，鸡块，鸡汤，鸡蛋，大盘鸡，啤酒鸡 真香。
他要带得东西太多了，所以你理所当然的要帮他算带个东西的方案数啦。
另外，在tacmon的眼里，所有的东西都是以“个”为单位的，而且每一种物品都有一些奇怪的限制。

  • tacmon最多会带1个肥宅快乐水（当然可以不带）
  • 他也认为大盘鸡和啤酒鸡太贵了，所以这两个东西他分别最多带2个和3个
  • 总所周知，鸡翅总是要成对出现的
  • tacmon认为偶数个鸡汤不好分，所以他准备带奇数个
  • 鸡块实在太好吃了，tacmon认为一个人一定会吃个，所以他一定会带的倍数个鸡块
  • tacmon最讨厌吃鸡腿了，所以他最多带一个鸡腿
  • 而鸡蛋，他准备带三的倍数个...

良心的tacmon觉得他的限制有点小多，所以他要好心的告诉大家，除了鸡汤，其他的东西不带也是符合要求的。


输入描述:

一行一个整数N，表示tacmon要带的物品个数

输出描述:

一行一个整数，即答案对取模的结果。
示例1

输入

复制 
1

输出

复制 
1
示例2

输入

复制 
5

输出

复制 
35

备注:

对于10分的数据：
对于30分的数据：
对于60分的数据：
对于100分的数据：