思路：数位DP

定义$dp(i,mask,isLimit,isNum)$表示构造第$i$位及其之后的数位的合法方案数

• $mask$表示前面选过的数字集合，换句话说，第$i$位要选的数字不能出现在$mask$中
• $isLimit$表示当前是否受到了$n$的约束。若为真，则第$i$位填入的数字至多为 $s[i]$，否则可以是$9$
• $isNum$表示$i$前面是否填了数字，若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1（不允许出现前导0）；若为真，则要填入的数字可以从 0 开始。

题目描述

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

如何定义一道美食为美味呢，我塔子百思不得其解，我修院解释道：假设一道美食有一个美味值，当且仅当它的相邻数位都不相同。例如: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.