题目描述

非常的新鲜，非常的美味，这是薯条哥对美食的极大赞赏。

如何定义一道美食为美味呢，鸭哥百思不得其解，薯条哥解释道：假设一道美食有一个美味值，当且仅当它的相邻数位都不相同。例如:$114514$是不美味的，但$1919810$则美味的很呐！

薯条哥有些困惑，想做更多的尝试（大悲），他想知道，美味值不大于$x$的美食中有多少道是美味的?

答案对$10^9+7$取模。

输入描述

一个正整数$x(1\lt x\lt 10^{100000})$.

输出描述

不大于$x$的美味的菜的数量，对$10^9+7$取模

样例

输入

15

输出

14

样例解释

不大于$15$的正整数中，只有$11$是不美味的