You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

人类被k激光打的落花流水，并举旗投降。土拨鼠军队胜利凯旋。在庆功宴上，土拨鼠们玩起了"真逢7必过"。

Description

游戏规则：从1开始报数，如果自己将报的数，数字各位都不是7，直接报数字。反之，就说"过"；"过"也算一个数字，后面的人继续报，因此就会出现好多人连续报"过"的情况。举个例子，从1报到17：1，2，3，4，5，6，过，8，9，10，11，12，13，14，15，16，过。土拨鼠们从1报到了n，他们想知道，在游戏过程中，大家到底说了多少个"过"。由于答案可能很大，你只需输出他对10007取模的结果。

Format

Input

一个数，n

Output

answer

Samples

17

2

100

19

1716

421

Limitation

$0 \leq n \leq 10^{666}$