#P2000. 拯救世界

拯救世界

题目背景

公元 2000 年,根据预言家诺查丹玛斯的预言,世界就要毁灭了!!!

题目描述

为了拯救世界,小 a 和 uim 决定召唤出 kkksc03 大神和 lzn 大神。根据古籍记载,召唤出任何一位大神,都需要使用金木水火土五种五行神石来摆一个特定的大阵。而在古籍中,记载是这样的:

kkksc03 大神召唤方法:

  • 金神石的块数必须是 66 的倍数;
  • 木神石最多用 99 块;
  • 水神石最多用 55 块;
  • 火神石的块数必须是 44 的倍数;
  • 土神石最多用 77 块。

lzn 大神召唤方法:

  • 金神石的块数必须是 22 的倍数;
  • 木神石最多用 11 块;
  • 水神石的块数必须是 88 的倍数;
  • 火神石的块数必须是 1010 的倍数;
  • 土神石最多用 33 块。

现在是公元 1999199912123131 日,小 a 和 uim 从 00:00:0000{:}00{:}00 开始找,一直找到 23:00:0023{:}00{:}00,终于,还是没找到神石。

不过,他们在回到家后在自家地窖里发现了一些奇怪的东西,一查古籍,哎呦妈呀,怎么不早点来呢?这里有一些混沌之石,可以通过敲击而衰变成五行神石。于是,他们拼命地敲,终于敲出了 nn 块神石,在 23:59:5923{:}59{:}59 完成了两座大阵。

然而,kkksc03 大神和 lzn 大神确实出现了,但是由于能量不够,无法发挥神力。只有把所有用 nn 块神石可能摆出的大阵都摆出来,才能给他们充满能量。这下小 a 和 uim 傻了眼了,赶快联系上了你,让你帮忙算一下,一共有多少种大阵。

输入格式

输入一个正整数 nn

输出格式

输出用 nn 块混沌之石能摆出的大阵的种数。

2
15

提示

数据范围及约定

对于全部数据,1099999n<1010000010^{99999}\leq n\lt 10^{100000}

提示

由于现在已经是 23:59:5923{:}59{:}59,所以你只有 0.50.5 秒时间。(小 a 与 uim 需要 0.5s0.5\texttt s 排出所有阵法)。