阿尔卡迪的一位朋友在一台巨大的射电望远镜前工作。几十年前,望远镜向一个遥远的星系发送了一个信号$$$s$$$。最近他们收到了回复$$$t$$$,他们认为这是来自外星人的回复!科学家们现在想要检查信号 $$$t$$$ 是否与 $$$s$$$ 相似。
原始信号 $$$s$$$ 是一个由 0 和 1 组成的序列(每个人都知道二进制代码是宇宙范围内的语言)。然而,返回的信号$$$t$$$看起来并不像$$$s$$$那么容易,但科学家们并没有放弃!他们将 $$$t$$$ 表示为英文字母序列,并表示 $$$t$$$ 与 $$$s$$$ 类似,如果你可以用某个字符串 $$$r_0$$$ 替换 $$$s$$$ 中的所有零,并用其他字符串 $$$r_1$$$ 替换 $$$s$$$ 中的所有零,并获得 $$$t$$$。字符串 $$$r_0$$$ 和 $$$r_1$$$ 必须不同且非空。
请帮助 Arkady 的朋友找出将 $$$s$$$ 转换为 $$$t$$$ 的 0 和 1 的可能替换数量(字符串 $$$r_0$$$ 和 $$$r_1$$$ 的对数)。
输入
第一行包含一个由零和一组成的字符串 $$$s$$$ ($$$2 \le |s| \le 10^5$$$) — 原始信号。
第二行包含一个仅由小写英文字母组成的字符串 $$$t$$$ ($$$1 \le |t| \le 10^6$$$) — 接收到的信号。
保证字符串 $$$s$$$ 包含至少一个“0”和至少一个“1”。
输出
打印单个整数 - 将 $$$s$$$ 转换为 $$$t$$$ 的字符串对 $$$r_0$$$ 和 $$$r_1$$$ 的数量。
如果没有这样的对,则打印 $$$0$$$。
示例
输入 #1
01 aaaaaa
输出 #1
4
输入 #2
001 kokokokotlin
输出 #2
2
注意
在第一个示例中,可能的对 $$$(r_0, r_1)$$$ 如下:
- “一个”,“aaaaa”
- “aa”,“aaaa”
- “aaaa”,“aa”
- “aaaaa”,“a”
不允许使用“aaa”、“aaa”对,因为 $$$r_0$$$ 和 $$$r_1$$$ 必须不同。
在第二个示例中,可能有以下对:
- “ko”,“kokotlin”
- “科科”,“特林”