AT_icpc2013autumn_b Restore Calculation

题目描述

有一天,兔子老师花子给了你一道题为“算术还原”的题。算术恢复是如下问题: 给你三个正整数 `A A A` 、 `B B B` 和 `C C C`。 这些数字中的几个数字已被 ljy 涂掉。 lmw 应该在每个空白位置分配一个数字,以便每个数字满足公式 $A+B=C$ 。 每个数字的第一位不能为$0$。单位数也一样。 lmw 数学很聪明,所以 lmw 马上解决了这个问题。此外,lmw 决定考虑一个更困难的问题,即计算给定算术恢复问题的可能分配数量。如果你能解决这个难题,你就会得到一个好成绩。 开始新任务后不久,lmw 注意到可能有太多可能的任务无法手动列举。所以,作为学校里最优秀的程序员,lmw 现在正尝试编写一个程序来计算可能分配给算术恢复问题的数量。

输入格式

输入是一系列数据集。数据集的数量少于 $100$。每个数据集的格式如下。 ``` A A A B B B C C C ``` 每个数据集由三个字符串 A A A 、 B B B 和 C C C 组成。它们表明 A A A 和 B B B 的总和应该是 C C C 。每个字符串由数字 (0-9) 和/或问号 (?) 组成。问号 (?) 表示已删除的数字。您可以假设每个字符串的第一个字符不是 $0$,并且每个数据集至少有一个?。 保证每个字符串包含 $1$ 到 $50$ 个字符(包括 $1$ 到 $50$ 个字符)。您还可以假设三个字符串的长度相等。 输入结束由带有单个$0$的行表示。

输出格式

对于每个数据集,输出给定问题模 $10^9+7$ 的可能分配数。请注意,可能无法解决给定的问题,因为花子女士是~~烤乳兔~~粗心的兔子。