#P9675. 第一题

    ID: 6292 传统题 1000ms 256MiB 尝试: 3 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-计数 DP固定一个变量消去另一维阶乘逆元预处理滚动数组

第一题

题目描述

神犇 xzyo 听说 sl 很弱,于是出了一题来虐一虐 sl。

一个长度为 2n2n(可能有前导 00)的非负整数 xx 是 good 的,当且仅当存在两个长度为 nn(可能有前导 00)的非负整数 a,ba,b 满足 a+b=10na+b=10^n,并且对于 0∼90\sim 9 每个数位 dd,都有 Sd(x)=Sd(a)+Sd(b)S_d(x)=S_d(a)+S_d(b)(Sd(x)S_d(x) 为 xx 的十进制中 dd 出现了多少次)。例如 08290829 是 good 的,98+02==10098+02==100。

给出一个长度为 2n2n 的数,其中有些位置是问号。将每个问号替换为 0∼90\sim 9 任意一个数位后,有多少个 good 数,答案对 109+710^9+7 取模。

输入格式

一行长度为 2n2n 的字符串,有 0∼90\sim 9 和 ? 构成。

输出格式

一个整数表示答案。

样例

2?4?
4

另有若干组大样例位于附加文件中。

数据范围

设 mm 为 ? 的个数。

  • 对于 30%30\% 的数据,n≤6n\le 6。
  • 对于另外 30%30\% 的数据,m≤6m\le 6。
  • 对于 100%100\% 的数据,1≤n≤5×1041\le n\le 5\times 10^4,0≤m≤min⁡(n,103)0\le m\le \min(n,10^3)。