有一群恶棍,有几个排成一排的孔,每个孔恰好包含一个恶棍。
每个群体排列可以表示为偶数长度的字符串,其中字符串的第$$$i$$$个字符代表第$$$i$$$个洞中的恶棍类型。
只有当殖民地的安排使得某种类型的所有恶棍要么住在殖民地的前半部分,要么生活在殖民地的后半部分时,钢铁侠才能摧毁一个殖民地。
他的助手贾维斯拥有特殊的能力。它可以交换任意两个洞的小人,即交换字符串中的任意两个字符;他可以多次执行此操作。
现在钢铁侠问贾维斯 $$$q$$$ 问题。在每个问题中,他给贾维斯两个数字 $$$x$$$ 和 $$$y$$$。贾维斯必须告诉钢铁侠,他可以使用自己的能力从原来的殖民地安排中创建出多少个不同的殖民地安排,以便所有与最初生活在第 $$$x$$$ 洞或第 $$$y$$$ 洞中的恶棍具有相同类型的恶棍都生活在同一半中,并且钢铁侠可以摧毁该殖民地安排。
如果存在一个洞,使得排列中的该洞中存在不同类型的恶棍,则两个群体排列被认为是不同的。
输入
第一行包含字符串 $$$s$$$ ($$$2 \le |s| \le 10^{5}$$$),表示初始菌落排列。字符串$$$s$$$可以同时包含小写和大写英文字母,且长度为偶数。
第二行包含一个整数 $$$q$$$ ($$$1 \le q \le 10^{5}$$$) — 问题数。
接下来的 $$$q$$$ 行的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i, y_i \le |s|$$$, $$$x_i \ne y_i$$$) - 为第 $$$i$$$ 行提供给 Jarvis 的两个数字问题。
输出
对于每个问题,输出可能的排列数以 $$$10^9+7$$$ 为模。
示例
输入 #1
abba 2 1 4 1 2
输出 #1
2 0
输入 #2
AAaa 2 1 2 1 3
输出 #2
2 0
输入 #3
abcd 1 1 3
输出 #3
8
注意
考虑第一个例子。对于第一个问题,可能的排列是“aabb”和“bbaa”,对于第二个问题,索引$$$1$$$包含“a”,索引$$$2$$$包含“b”,并且不存在所有“a”和“b”在同一半中的有效排列。