← 返回题目列表

AtCoder · icpc2013autumn_b

B. 恢复计算

中文机器翻译题面 查看原题

问题陈述

动物学校是一所为动物儿童开设的小学。 你是一只在这所学校上学的狐狸。

有一天,兔子老师花子给你一道题,叫做“算术恢复”。 算术恢复是类似以下的问题:

  • 给定三个正整数:$A$、$B$ 和$C$。

  • 这些号码中的几位数字已被删除。

  • 您应该在每个空白位置分配一个数字,使数字满足公式 $A+B=C$。

  • 每个数字的第一位不能为零。对于单位数也是如此。

你数学很聪明,所以你立即解决了这个问题。 此外,您决定考虑一个更困难的问题,计算给定算术恢复问题的可能分配数量。 如果你能解决这个难题,你就会取得好成绩。

开始新任务后不久,您注意到可能有太多可能的作业无法手动枚举。因此,作为学校里最好的程序员,您现在正在尝试编写一个程序来计算算术恢复问题的可能作业数量。


输入

输入是数据集序列。 数据集数量小于100。 每个数据集的格式如下。

$A$
$B$
$C$

每个数据集由三个字符串组成:$A$、$B$ 和 $C$。 它们表明$A$ 和$B$ 的总和应该是$C$。 每个字符串由数字 (0-9)和/或问号(?)。 一个问号(?) 表示已删除的数字。 您可以假设每个字符串的第一个字符不是 0 并且每个数据集至少有一个 ?.

确保每个字符串包含 1 到 50 个字符(含 1 和 50 个字符)。 您还可以假设三个字符串的长度相等。

输入结束由带有单个零的行表示。

输出

对于每个数据集,输出给定问题的可能分配数量以 1,000,000,007 为模。 请注意,由于花子女士是一只粗心的兔子,因此可能无法解决给定的问题。


示例输入

3?4
12?
5?6
?2?4
5?7?
?9?2
?????
?????
?????
0

样本输入的输出

2
40
200039979

注意

第一个数据集的答案是 2。如下所示。

  • 384 + 122 = 506

  • 394 + 122 = 516