{"problem":{"name":"[ROIR 2021] A+B (Day 2)","description":{"content":"有三个长为 $n$ 的可能含前导零的整数 $a,b,c$，按如下方式排成三行 $n$ 列： ``` a b c ``` 问有多少种不同的**列**的排列方式，使得被横着念出来的三个整数 $x,y,z$ 有 $x+y=z$ 成立且三个整数均没有前导零。 排列方式的个数可能很多，输出其 $\\bmod \\ 10^9+7$ 即可。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9768"},"statements":[{"statement_type":"Markdown","content":"有三个长为 $n$ 的可能含前导零的整数 $a,b,c$，按如下方式排成三行 $n$ 列：\n\n```\na\nb\nc\n```\n问有多少种不同的**列**的排列方式，使得被横着念出来的三个整数 $x,y,z$ 有 $x+y=z$ 成立且三个整数均没有前导零。\n\n排列方式的个数可能很多，输出其 $\\bmod \\ 10^9+7$ 即可。\n\n## Input\n\n第一行为一个长 $n$ 的整数 $a$。\n\n第二行为一个长 $n$ 的整数 $b$。\n\n第三行为一个长 $n$ 的整数 $c$。\n\n## Output\n\n一行一个整数，表示不同的排列方式的个数对 $10^9+7$ 取模的结果。\n\n[samples]\n\n## Background\n\n**译自 [ROIR 2021](http://neerc.ifmo.ru/school/archive/2020-2021.html) Day2 T4  [A+B](http://neerc.ifmo.ru/school/archive/2020-2021/ru-olymp-regional-2021-day2.pdf)**。\n\n## Note\n\n【样例解释1】：所有排列方式均可。\n\n【样例解释2】：我们只计算 $10+20=30$，而不计算 $01+02=03$，因为 $03$ 含前导零。\n\n【样例解释3】：显然有 $10121 + 21909 = 32030$ 与 $12101 + 20919 = 33020$ 两种合法等式，但由于有两个相同的列，所以它们都有两种方式得到答案，总方案数为 $2\\times 2=4$。\n\n【数据范围】：\n\n对于所有子任务，有 $2\\le n\\le 2\\times 10^5$。\n\n| 子任务编号 |特殊限制| 分值 |\n| :-: | :-: | :-: |\n|$1$|$n\\le 6$| $7$  |\n|$2$|$n\\le 18$| $14$ |\n|$3$| $n\\le 200$，读入的数字中不含 $0$ | $15$ |\n|$4$|$n\\le 200$| $5$  |\n|$5$| $n\\le 750$，读入的数字中不含 $0$ | $17$ |\n|$6$|$n\\le 750$| $5$  |\n|$7$|读入的数字中不含 $0$| $20$ |\n|$8$|无特殊限制| $17$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9768","tags":["2021","ROIR（俄罗斯）"],"sample_group":[["123\n123\n246","6"],["01\n02\n03","1"],["01211\n12099\n23300","4"],["121\n214\n999","0"]],"created_at":"2026-03-03 11:09:25"}}