从前，有一位伟大的将军名叫左（Tso），他以擅长将士兵分成小组执行不同任务而闻名。如果可能的话，左将军会尽可能多地将士兵分组，以提高灵活性。然而，有一个只有极少数人知道的小秘密：左将军年轻时，一位算命先生警告他，“9”对他来说是一个超级不吉利的数字。因此，现在每当左将军将士兵分组时，他都会确保这些小组中任意组合的士兵总数都不会等于 9。

例如，当有 $N = 11$ 名士兵时，我们可以将士兵分成三组，每组人数分别为 3、4、4，这样任意组合的总和都不会正好等于 9（总和只能是 3、4、7、8 或 11）。另一种方法是将士兵分成四组，每组人数分别为 1、3、3、4，这样任意组合的总和同样不会正好等于 9（总和只能是 1、3、4、5、6、7、8、10 或 11）。由于后一种方法的分组数量更多，因此它比前一种方法更好。

相比之下，如果我们把士兵分成 11 组，每组 1 人，虽然分组数量更多，但某些组合（取其中 9 组）的总人数会正好等于 9，因此这对左将军来说不是一种可行的分组方式。

作为左将军最可靠的助手之一，你被分配了以下任务：给定士兵总数 $N$（其中 $N \neq 9$），帮助左将军找到可以形成的最大分组数 $K$。

输入格式

输入仅包含一行，为一个正整数 $N$。

输出格式

设 $K$ 为所求的最大分组数。输出仅包含一行，打印一个非负整数 $X$，使得 $X$ 为 $K$ 除以 $10^9 + 7$ 的余数。即 $X \equiv K \pmod{10^9 + 7}$，且 $0 \leq X < 10^9 + 7$。

数据范围

• $1 \leq N \leq 10^{15}$
• $N \neq 9$
• $0 \leq X < 10^9 + 7$

样例

输入 1

11

输出 1

4

输入 2

8

输出 2

8

输入 3

12345678901234

输出 3

839407413