题目描述

“非常的新鲜，非常的美味”，这是我修院对美食的极大赞赏。

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

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

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

输入描述

一个正整数$x$, $1$ $<$ $x$ $<$ $10^{100000}$

输出描述

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

样例

输入

15

输出

14

说明

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

Limitation

1s, 1024KiB for each test case.