解题思路

设数字 $x$ 的十进制长度为 $n$，第 $i$ 位数字为 $d_i$。

题目要求的是：

• 等概率选一个数位，概率为 $\frac{1}{n}$
• 再把这一位替换成 $0 \sim 9$ 中任意一个数字，概率为 $\frac{1}{10}$
• 统计新数 $x'$ 严格大于原数 $x$ 的概率

题目内容

对于给定的数字$x$，任选一个数位，将其替换成$0$~ $9$任意一个数字，得到的新数字$x’$大于原数字$x$的概率是多少。

可以证明答案可以表示为一个不可约分数$\frac {p} {q}$，为了避免精度问题，请直接输出整数$(p·q^{-1} mod M)$作为答案，其中 $M$ 为模数，$q^{-1}$是满足$(q×q^{-1} mod M)=1的$整数。

在本题中， $mod$ 的含义是取模，例如 $4$ $mod$ $2$即为将 $4$对$2$ 取模。

提示:$q^{-1}$可以使用公式$(q^{M-2} mod M)$得到，例如$M=7$且$q=4$时，$q^{-1}$=$(1024 mod 7)=2$，满足$(4×2 mod 7)=1$。

输入描述

在一行上输入两个整数

$x, M (1 ≤ x ≤ 10^{100000} ; 1 ≤ M ≤ 10^9 + 7)$代表给定的数字、模数。

输入数据保证上述公式成立。

输出描述

在一行上输出一个整数，代表得到的新数字$x’$大于原数字 $x$ 的概率。

样例1

输入

12 1000000007

输出

750000006

说明

• 选中第一位数字的概率为$\frac {1} {2}$，替换为$2$~ $9$都会比原数字更大，概率为$\frac {1} {2}$×$\frac {8} {10}$；

• 选中第二位数字的概率为$\frac {1} {2}$，替换为$3$~ $9$都会比原数字更大，概率为$\frac {1} {2}$×$\frac {7} {10}$；

综上，总概率为$\frac {8} {20}$+$\frac {7} {20}$=$\frac {1} {2}$$mod$ $M$。当$q^{-1}=250000002$时，因为$4×q^{-1}≡1(mod M)$,我们应该输出$3×q^{-1}mod M=750000006$