CF1111D Destroy the Colony

有一个反派的聚居地，里面有若干个洞排成一排，每个洞里恰好有一个反派。 每种聚居地的排列可以表示为一个偶数长度的字符串，第 $i$ 个字符表示第 $i$ 个洞里的反派类型。 只有当某种类型的所有反派都只生活在聚居地的前半部分或后半部分时，钢铁侠才能摧毁这个聚居地。 他的助手 Jarvis 有一种特殊能力，可以任意交换两个洞里的反派，即可以任意交换字符串中的任意两个字符，这个操作可以进行任意多次。 现在钢铁侠向 Jarvis 提出了 $q$ 个问题。每个问题给出两个数字 $x$ 和 $y$，Jarvis 需要告诉钢铁侠：通过他的能力，从原始排列中可以构造出多少种不同的聚居地排列，使得原本在第 $x$ 个洞或第 $y$ 个洞的反派类型的所有反派都只生活在同一半部分，并且钢铁侠可以摧毁这个聚居地。 如果存在某个洞，在两个排列中该洞里的反派类型不同，则认为这两个排列是不同的。

第一行包含一个字符串 $s$（$2 \le |s| \le 10^{5}$），表示初始的聚居地排列。字符串 $s$ 可能包含大小写英文字母，且长度为偶数。 第二行包含一个整数 $q$（$1 \le q \le 10^{5}$），表示问题的数量。 接下来的 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le |s|$，$x_i \ne y_i$），表示 Jarvis 在第 $i$ 个问题中得到的两个数字。

对于每个问题，输出一个整数，表示满足条件的不同排列数，对 $10^9+7$ 取模。

考虑第一个样例。对于第一个问题，可能的排列有 "aabb" 和 "bbaa"；对于第二个问题，第 $1$ 个位置是 'a'，第 $2$ 个位置是 'b'，不存在一种有效的排列使得所有 'a' 和 'b' 都在同一半部分。 由 ChatGPT 4.1 翻译