题目描述

Than 讨厌距离太近。

他认为一个自然数是坏的，当且仅当存在两个相邻的数字相差为 $0$ 或 $1$。例如 $2022,346440$ 是坏的，而 $5307,142857$ 是好的。现在他想知道，在区间 $[0,n]$ 中有多少个数是好的。

输入文件(than.in)

一行一个整数 $n$。

输出文件(than.out)

一行一个数，为答案对 $10^9+7$​ 取模的结果。

10

10

114

74

998244353

76088419

1145141919810114514191981011451419198101145141919810

963934887

数据范围

对于 $20\%$ 的数据，$n\le 10^3$；

对于 $40\%$ 的数据，$n\le 10^6$；

对于 $60\%$ 的数据，$n\le 10^9$；

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