问题陈述
动物学校是一所为动物儿童开设的小学。 你是一只在这所学校上学的狐狸。
有一天,兔子老师花子给你一道题,叫做“算术恢复”。 算术恢复是类似以下的问题:
给定三个正整数:$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