题目描述

一段楼梯有 $n$ 节台阶。有一个超人，他可以一步上 $1$ 至 $20$ 节台阶。他想知道他从第 $1$ 节台阶上到第 $n$ 节台阶有多少种不同的方案。

输入格式

一行，一个整数 $n$，表示一共有 $n$ 节台阶。

输出格式

一行，一个整数，表示超人从第 $1$ 节台阶上到第 $n$ 节台阶有多少中的方案，输出答案 $mod$ $10^6$ 的值。（不含前导 $0$）

样例 #1

样例输入 #1

4

样例输出 #1

4

样例 #2

样例输入 #2

25

样例输出 #2

777168

提示

对于 $100\%$ 的数据，$1 \le n \le 10^6$。