#5138. 一道简单的数数问题

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:无测试数据
上传者: Laffey

题目描述

给定一个数 N ,请输出集合 \{1, \dots, N\} 的满足所有元素和为 5 的倍数的子集的数目。答案对 19260817 取模。

输入格式

N

输出格式

你的答案。

样例

样例输入 #1

5

样例输出 #1

8

样例输入 #2

2000

样例输出 #2

6411641

数据范围与提示

对于 10\% 的数据, 0 < N \leq 20

对于另外 20\% 的数据, 0 < N \leq 10^6

对于另外 30\% 的数据, 0 < N \leq 2^{10^6}

对于另外 40\% 的数据, 0 < N \leq 10^{10^6}