题目内容

小蓝有一个密码，是一串由数字字符组成的字符串 $S$（仅包含字符 0 到 9）。他在一次操作中，随机等概率地选择 $S$ 中的一个位置，然后将该位置上的字符等概率地修改为 0 到 9 中的任意一个字符。求操作后得到的新字符串 $T$ 字典序严格大于 $S$ 的概率。可以证明该概率可表示为一个最简分数 $\frac{p}{q}$。请你输出整数 $p \cdot q^{-1} \bmod M$，其中 $M$ 为给定的模数，$q^{-1}$ 是 $q$ 在模 $M$ 意义下的乘法逆元（满足 $q \cdot q^{-1} \equiv 1 \pmod M$）。

约束：字符串 $S$ 的长度 $|S|$ 不超过 10^5。模数 $M$ 是一个不超过 10^9+7 的质数，且保证 $10 \times |S|$ 与 $M$ 互质（从而逆元存在）。

输入描述

输入共一行，包含一个由数字字符组成的字符串 $S$（$|S|$ 不超过 10^5）和一个整数 $M$（质数，不超过 10^9+7），两者之间用一个空格分隔。

输出描述

输出一个整数，表示 $p \cdot q^{-1} \bmod M$ 的值。

样例1

输入

9 11

输出

0

说明

字符串长度为 1，仅有一个位置。要使新字符串字典序严格大于原串，必须将这一位修改为比 9 更大的数字，但可选数字只有 0 到 9，不存在大于 9 的数字，因此成功方案数为 0。

总方案数为 $1 \times 10 = 10$。概率为 $0/10 = 0$。在模 11 下，结果为 0。

样例2

输入

12 1000000007

输出

750000006

说明

字符串长度为 2，各位数字分别为 1 和 2。成功方案数 $p = (9-1)+(9-2)=8+7=15$。

总方案数为 $10 \times 2 = 20$，即分母 $q = 20$。最简分数为 $15/20 = 3/4$。在模 1000000007 下，$3 \times 4^{-1} \equiv 750000006$。因此输出 750000006。

样例3

输入

100 7

输出

6

说明

字符串长度为 3，各位分别为 1，0，0。成功方案数 $p = (9-1)+(9-0)+(9-0)=8+9+9=26$。

总方案数为 $10 \times 3 = 30$，即分母 $q = 30$。概率为 $26/30 = 13/15$。

在模 7 下，$13 \equiv 6$，$15 \equiv 1$，逆元为 1，故结果为 $6 \times 1 \equiv 6$。输出 6。