solutions: ["from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "import sys, math\nMOD = 10 ** 9 + 7\nfact = [1]\ncur = 1\nfor i in range(1, 6 * 10 ** 4):\n\tcur *= i\n\tcur %= MOD\n\tfact.append(cur)\nalpha = 'abcdefghijklmnopqrstuvwxyz'\ndp = [0]\ndp2 = [[0] * 26]\n\ndef bitm(c):\n\treturn 1 << alpha.find(c)\n\ndef initialize(s):\n\tcur = 0\n\tfor c in s:\n\t\ttmp = [i for i in dp2[-1]]\n\t\ttmp[alpha.find(c)] += 1\n\t\tcur ^= bitm(c)\n\t\tdp.append(cur)\n\t\tdp2.append(tmp)\n\ndef modInv(x, pow=MOD - 2):\n\tif pow <= 3:\n\t\treturn x ** pow % MOD\n\telse:\n\t\ttmp = modInv(x, pow // 2)\n\t\ttmp *= tmp\n\t\ttmp %= MOD\n\t\tif pow % 2 == 0:\n\t\t\treturn tmp\n\t\telse:\n\t\t\treturn tmp * x % MOD\nmi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]\n\ndef answerQuery(l, r):\n\ttmp = dp[l - 1] ^ dp[r]\n\ttmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]\n\tpossLetters = 0\n\tfor c in range(26):\n\t\tif tmp & 1 << c:\n\t\t\tpossLetters += 1\n\tmiddle = max(possLetters, 1)\n\tothers = (r - l + 1 - possLetters) // 2\n\tans = fact[others] * middle % MOD\n\tfor i in tmp2:\n\t\tif i > 0:\n\t\t\tans *= mi[i]\n\t\t\tans %= MOD\n\treturn ans\ns = input().strip()\ninitialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r)\n\tprint(result % MOD)\n", "import collections\nimport functools\nimport sys\nMOD = 1000000007\nstring = None\nhistogram = [[0] * 26]\nfactorial_cache = [1]\nfor i in range(1, 10 ** 5 + 1):\n\tfactorial_cache.append(factorial_cache[-1] * i % MOD)\n\ndef mulinv(b, n):\n\n\tdef egcd(b, n):\n\t\t(x0, x1, y0, y1) = (1, 0, 0, 1)\n\t\twhile n != 0:\n\t\t\t(q, b, n) = (b // n, n, b % n)\n\t\t\t(x0, x1) = (x1, x0 - q * x1)\n\t\t\t(y0, y1) = (y1, y0 - q * y1)\n\t\treturn (b, x0, y0)\n\t(g, x, _) = egcd(b, n)\n\tif g == 1:\n\t\treturn x % n\n\ndef initialize(s):\n\tglobal string\n\tstring = s\n\tfor i in s:\n\t\tx = list(histogram[-1])\n\t\tx[ord(i) - ord('a')] += 1\n\t\thistogram.append(x)\n\ndef answerQuery(l, r):\n\n\tdef count(counter):\n\t\t(c1, nl) = (sum((i & 1 for i in counter)), [i >> 1 for i in counter if i > 1])\n\t\tif c1 == 0:\n\t\t\tc1 = 1\n\t\tdivisor = functools.reduce(lambda lhs, rhs: lhs * rhs % MOD, map(factorial_cache.__getitem__, nl), 1)\n\t\treturn c1 * factorial_cache[sum(nl)] * mulinv(divisor, MOD) % MOD\n\treturn count(list(map(lambda x, y: x - y, histogram[r], histogram[l - 1])))\ns = input().strip()\ninitialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "mod = 10 ** 9 + 7\nstring = input().strip()\nq = int(input())\narray = [[0] * (len(string) + 1) for _ in range(26)]\nfact_length = (len(string) + 2) // 2\nfact = [1] * fact_length\nfact_inv = [1] * fact_length\n\ndef initialize():\n\tfor i in range(2, len(fact)):\n\t\tfact[i] = fact[i - 1] * i % mod\n\t\tfact_inv[i] = pow(fact[i], mod - 2, mod)\n\tfor i in range(len(string)):\n\t\taffected = ord(string[i]) - ord('a')\n\t\tfor j in range(26):\n\t\t\tarray[j][i] += array[j][i - 1]\n\t\tarray[affected][i] += 1\ninitialize()\nfor _ in range(q):\n\t(odd, even) = (0, [])\n\t(l, r) = [int(x) - 1 for x in input().split()]\n\tfor i in range(26):\n\t\tcount = array[i][r] - array[i][l - 1]\n\t\todd += int(count & 1)\n\t\teven.append(count // 2)\n\todd = max(odd, 1)\n\ttotal = fact[sum(even)] * odd\n\tfor x in even:\n\t\ttotal *= fact_inv[x]\n\t\ttotal %= mod\n\ttotal %= mod\n\tprint(total)\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "import sys, math\nMOD = 10 ** 9 + 7\nfact = [1]\ncur = 1\nfor i in range(1, 6 * 10 ** 4):\n\tcur *= i\n\tcur %= MOD\n\tfact.append(cur)\nalpha = 'abcdefghijklmnopqrstuvwxyz'\ndp = [0]\ndp2 = [[0] * 26]\n\ndef bitm(c):\n\treturn 1 << alpha.find(c)\n\ndef initialize(s):\n\tcur = 0\n\tfor c in s:\n\t\ttmp = [i for i in dp2[-1]]\n\t\ttmp[alpha.find(c)] += 1\n\t\tcur ^= bitm(c)\n\t\tdp.append(cur)\n\t\tdp2.append(tmp)\n\ndef modInv(x, pow=MOD - 2):\n\tif pow <= 3:\n\t\treturn x ** pow % MOD\n\telse:\n\t\ttmp = modInv(x, pow // 2)\n\t\ttmp *= tmp\n\t\ttmp %= MOD\n\t\tif pow % 2 == 0:\n\t\t\treturn tmp\n\t\telse:\n\t\t\treturn tmp * x % MOD\nmi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]\n\ndef answerQuery(l, r):\n\ttmp = dp[l - 1] ^ dp[r]\n\ttmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]\n\tpossLetters = 0\n\tfor c in range(26):\n\t\tif tmp & 1 << c:\n\t\t\tpossLetters += 1\n\tmiddle = max(possLetters, 1)\n\tothers = (r - l + 1 - possLetters) // 2\n\tans = fact[others] * middle % MOD\n\tfor i in tmp2:\n\t\tif i > 0:\n\t\t\tans *= mi[i]\n\t\t\tans %= MOD\n\treturn ans\ns = input().strip()\ninitialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r)\n\tprint(result % MOD)\n", "import sys\n\ndef power(x, n, m):\n\tif n == 1:\n\t\treturn x % m\n\telif n == 0:\n\t\treturn 1\n\tres = power(x, n // 2, m)\n\tif n % 2 == 0:\n\t\treturn res * res % m\n\telse:\n\t\treturn res * res * x % m\n\ndef initialize(s, factorials, invfacts, counts):\n\tcharacters = []\n\tn = len(s)\n\tfor i in range(26):\n\t\tcharacters.append(chr(ord('a') + i))\n\tcurindex = 0\n\tfor c in s:\n\t\tcurindex += 1\n\t\tfor i in range(26):\n\t\t\tcounts[i].append(0)\n\t\tcounts[ord(c) - ord('a')][curindex] = 1\n\tfor i in range(n):\n\t\tfor j in range(26):\n\t\t\tcounts[j][i + 1] += counts[j][i]\n\tMOD = 1000000007\n\tfactorials.append(1)\n\tinvfacts.append(1)\n\tfor i in range(1, n // 2 + 3):\n\t\tcurfact = factorials[i - 1] * i % MOD\n\t\tcurinv = power(curfact, MOD - 2, MOD)\n\t\tfactorials.append(curfact)\n\t\tinvfacts.append(curinv)\n\treturn\n\ndef answerQuery(l, r, factorials, invfacts, counts):\n\tMOD = 1000000007\n\toddtotal = 0\n\teventotal = 0\n\ttotal = 1\n\tfor i in range(26):\n\t\tcurcount = counts[i][r] - counts[i][l - 1]\n\t\ttotal = total * invfacts[curcount // 2] % MOD\n\t\teventotal += curcount // 2\n\t\toddtotal += curcount % 2\n\tif oddtotal == 0:\n\t\toddtotal = 1\n\ttotal = total * factorials[eventotal] * oddtotal % MOD\n\treturn total\ns = input().strip()\nfactorials = []\ninvfacts = []\ncounts = []\nfor i in range(26):\n\tcounts.append([0])\ninitialize(s, factorials, invfacts, counts)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r, factorials, invfacts, counts)\n\tprint(result)\n", "import sys\nimport copy\n\ndef initialize(s):\n\tn = len(s)\n\td = [[] for i in range(n + 1)]\n\td[0] = [0] * 26\n\tcurr_arr = d[0]\n\tfor idx in range(1, n + 1):\n\t\tcurr_arr = copy.copy(curr_arr)\n\t\tcurr_arr[ord(s[idx - 1]) - ord('a')] += 1\n\t\td[idx] = curr_arr\n\treturn d\nmem = {2: 2}\n\ndef nChooseArr(arr):\n\tk = 1000000007\n\tn = sum(arr)\n\tnumerator = 1\n\tdenominator = 1\n\tfor i in range(n, 1, -1):\n\t\tif i in mem:\n\t\t\tnumerator = numerator * mem[i] % k\n\t\t\tmem[n] = numerator\n\t\t\tbreak\n\t\tnumerator *= i\n\t\tif numerator > k:\n\t\t\tnumerator = numerator % k\n\tfor idx in range(26):\n\t\ttemp = 1\n\t\tfor j in range(arr[idx], 1, -1):\n\t\t\tif j in mem:\n\t\t\t\ttemp = temp * mem[j] % k\n\t\t\t\tmem[arr[idx]] = temp\n\t\t\t\tbreak\n\t\t\ttemp *= j\n\t\t\tif temp > k:\n\t\t\t\ttemp = temp % k\n\t\tdenominator = denominator * temp % k\n\tinv_denom = pow(denominator, k - 2, k)\n\tres = numerator * inv_denom % k\n\treturn res\n\ndef answerQuery(l, r, d):\n\tk = 1000000007\n\tcurr_arr = [0] * 26\n\tarr_l = d[l - 1]\n\tarr_r = d[r]\n\tfor idx in range(26):\n\t\tcurr_arr[idx] = arr_r[idx] - arr_l[idx]\n\tflag = False\n\tnew_arr = copy.copy(curr_arr)\n\tnew_arr_odd = copy.copy(curr_arr)\n\tfor idx in range(26):\n\t\tnew_arr[idx] = curr_arr[idx] // 2\n\t\tnew_arr_odd[idx] = curr_arr[idx] % 2\n\tres = nChooseArr(new_arr) * max(1, sum(new_arr_odd))\n\treturn res % k\ns = input().strip()\nd = initialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r, d)\n\tprint(result)\n", "import sys\nfrom collections import Counter\nfrom functools import lru_cache\nfrom math import factorial\n\ndef initialize(s):\n\tstats = [[0] * 26]\n\tfor c in s:\n\t\tcc = list(stats[-1])\n\t\tcc[ord(c) - 97] += 1\n\t\tstats.append(cc)\n\tfactorials = [1]\n\tinverse_factorials = [1]\n\tfor i in range(1, 10 ** 5 + 1):\n\t\tfactorials.append(factorials[-1] * i % (10 ** 9 + 7))\n\t\tinverse_factorials.append(pow(factorials[-1], 10 ** 9 + 5, 10 ** 9 + 7))\n\treturn (stats, factorials, inverse_factorials)\n\ndef answerQuery(l, r, stats, factorials, inverse_factorials):\n\trr = stats[r][:]\n\tfor i in range(26):\n\t\trr[i] -= stats[l - 1][i]\n\todd = 0\n\tfor i in range(26):\n\t\tif rr[i] % 2 == 1:\n\t\t\todd += 1\n\t\t\trr[i] -= 1\n\ts = sum(rr) // 2\n\tres = odd or 1\n\trr.sort(reverse=True)\n\tf = factorials[s]\n\tfor x in rr:\n\t\tf = f * inverse_factorials[x // 2] % (10 ** 9 + 7)\n\treturn res * f % (10 ** 9 + 7)\ns = input().strip()\nstats = initialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r, *stats)\n\tprint(result)\n", "max = 100005\nmod = 1000000007\nfact = [0] * max\ninv = [0] * max\nfact[0] = 1\nfor i in range(1, max):\n\tfact[i] = i * fact[i - 1] % mod\n\ndef modInverse(a, m):\n\tg = gcd(a, m)\n\tif g != 1:\n\t\tprint(\"Inverse doesn't exist\")\n\telse:\n\t\treturn power(a, m - 2, m)\n\ndef power(x, y, m):\n\tif y == 0:\n\t\treturn 1\n\tp = power(x, y // 2, m) % m\n\tp = p * p % m\n\tif y % 2 == 0:\n\t\treturn p\n\telse:\n\t\treturn x * p % m\n\ndef gcd(a, b):\n\tif a == 0:\n\t\treturn b\n\treturn gcd(b % a, a)\nfor i in range(max):\n\tinv[i] = modInverse(fact[i], mod)\ns = list(input())\nn = len(s)\ns2 = [[0] * 26 for i in range(n)]\ns2[0][ord(s[0]) - ord('a')] += 1\nfor i in range(1, n):\n\tfor j in range(26):\n\t\ts2[i][j] += s2[i - 1][j]\n\ts2[i][ord(s[i]) - ord('a')] += 1\nnum = int(input())\nfor _ in range(num):\n\t(l, r) = map(int, input().split(' '))\n\t(l, r) = (l - 1, r - 1)\n\tcone = 0\n\tctwo = 0\n\tans = 1\n\tc = [0] * 26\n\tfor i in range(26):\n\t\tc[i] = s2[r][i]\n\t\tif l > 0:\n\t\t\tc[i] -= s2[l - 1][i]\n\t\tif c[i] % 2 == 1:\n\t\t\tcone += 1\n\t\t\tc[i] -= 1\n\t\tc[i] = int(c[i] / 2)\n\t\tctwo += c[i]\n\t\tans = ans * inv[c[i]] % mod\n\tans = ans * fact[ctwo] % mod\n\tif cone > 0:\n\t\tans *= cone\n\tans %= mod\n\tprint(ans)\n", "import sys, math\nMOD = 10 ** 9 + 7\nfact = [1]\ncur = 1\nfor i in range(1, 6 * 10 ** 4):\n\tcur *= i\n\tcur %= MOD\n\tfact.append(cur)\nalpha = 'abcdefghijklmnopqrstuvwxyz'\ndp = [0]\ndp2 = [[0] * 26]\n\ndef bitm(c):\n\treturn 1 << alpha.find(c)\n\ndef initialize(s):\n\tcur = 0\n\tfor c in s:\n\t\ttmp = [i for i in dp2[-1]]\n\t\ttmp[alpha.find(c)] += 1\n\t\tcur ^= bitm(c)\n\t\tdp.append(cur)\n\t\tdp2.append(tmp)\n\ndef modInv(x, pow=MOD - 2):\n\tif pow <= 3:\n\t\treturn x ** pow % MOD\n\telse:\n\t\ttmp = modInv(x, pow // 2)\n\t\ttmp *= tmp\n\t\ttmp %= MOD\n\t\tif pow % 2 == 0:\n\t\t\treturn tmp\n\t\telse:\n\t\t\treturn tmp * x % MOD\nmi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]\n\ndef answerQuery(l, r):\n\ttmp = dp[l - 1] ^ dp[r]\n\ttmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]\n\tpossLetters = 0\n\tfor c in range(26):\n\t\tif tmp & 1 << c:\n\t\t\tpossLetters += 1\n\tmiddle = max(possLetters, 1)\n\tothers = (r - l + 1 - possLetters) // 2\n\tans = fact[others] * middle % MOD\n\tfor i in tmp2:\n\t\tif i > 0:\n\t\t\tans *= mi[i]\n\t\t\tans %= MOD\n\treturn ans\ns = input().strip()\ninitialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r)\n\tprint(result % MOD)\n", "import sys\nfrom collections import Counter\nfrom functools import reduce\nfrom math import factorial\n\ndef modular_inverse(a, m):\n\tm0 = m\n\ty = 0\n\tx = 1\n\twhile a > 1:\n\t\tq = a // m\n\t\tt = m\n\t\tm = a % m\n\t\ta = t\n\t\tt = y\n\t\ty = x - q * y\n\t\tx = t\n\tif x < 0:\n\t\tx = x + m0\n\treturn x\n\ndef ways(evens, odds, permutations, m, factorials, inverse_factorials):\n\ta = factorials[evens]\n\tways = reduce(lambda x, y: x * inverse_factorials[y] % m, permutations, a) % m\n\tif odds > 0:\n\t\tways *= odds % m\n\treturn ways % m\n\ndef initialize(s):\n\tcounters = [[0] * 26 for i in range(len(s) + 1)]\n\tfor (i, c) in enumerate(map(ord, s)):\n\t\tfor j in range(26):\n\t\t\tcounters[i + 1][j] = counters[i][j]\n\t\tk = c - ord('a')\n\t\tcounters[i + 1][k] = counters[i][k] + 1\n\tfactorials = [1, 1]\n\tfor i in range(2, len(s) + 1):\n\t\tfactorials.append(factorials[i - 1] * i % (10 ** 9 + 7))\n\tinverse_factorials = []\n\tfor f in factorials:\n\t\tinverse_factorials.append(modular_inverse(f, 10 ** 9 + 7))\n\treturn (factorials, inverse_factorials, counters)\n\ndef answerQuery(l, r, counters, factorials, inverse_factorials):\n\tl_counter = counters[l - 1]\n\tr_counter = counters[r]\n\tevens = 0\n\todds = 0\n\tpermutations = []\n\tfor (c1, c2) in zip(l_counter, r_counter):\n\t\tv = c2 - c1\n\t\tif v == 0:\n\t\t\tcontinue\n\t\tp = v // 2\n\t\tevens += p\n\t\todds += 0 if v % 2 == 0 else 1\n\t\tif p > 1:\n\t\t\tpermutations.append(p)\n\treturn ways(evens, odds, permutations, 10 ** 9 + 7, factorials, inverse_factorials)\ns = input()\n(factorials, inverse_factorials, counters) = initialize(s)\nq = int(input())\nfor _ in range(q):\n\t(l, r) = map(int, input().split())\n\tresult = answerQuery(l, r, counters, factorials, inverse_factorials)\n\tprint(result)\n", "import sys\nfrom collections import defaultdict as dd\nMOD = int(10 ** 9 + 7)\nMAX_N = 10 ** 5\nFACTORIAL = [0] * MAX_N\nINV_FACTORIAL = [0] * MAX_N\nFACTORIAL[0] = 1\nINV_FACTORIAL[0] = 1\nfor n in range(1, MAX_N):\n\tFACTORIAL[n] = FACTORIAL[n - 1] * n % MOD\n\tINV_FACTORIAL[n] = pow(FACTORIAL[n], MOD - 2, MOD)\n\ndef warn(*args, **kwargs):\n\tpass\n\ndef get_int():\n\treturn int(input())\n\ndef get_ints():\n\treturn [int(x) for x in input().split()]\n\ndef binomial(n, k, mod):\n\tnum = FACTORIAL[n]\n\tinv_denom = INV_FACTORIAL[k] * INV_FACTORIAL[n - k] % MOD\n\treturn num * inv_denom % MOD\n\ndef distinct_permutations(char_counts):\n\tlength = sum(char_counts)\n\tdp = 1\n\tfor cnt in char_counts[:-1]:\n\t\tdp = dp * binomial(length, cnt, MOD) % MOD\n\t\tlength -= cnt\n\treturn dp\n\ndef max_palindrome_count(counts):\n\thalf = []\n\todd = []\n\tfor (c, cnt) in counts.items():\n\t\tif cnt % 2 == 0:\n\t\t\thalf.append(cnt // 2)\n\t\telse:\n\t\t\todd.append(cnt)\n\tpalindroms = 1\n\tif len(odd) > 0:\n\t\tpalindroms *= len(odd)\n\t\tfor cnt in odd:\n\t\t\tif cnt - 1 > 0:\n\t\t\t\thalf.append((cnt - 1) // 2)\n\tpalindroms *= distinct_permutations(half)\n\treturn palindroms % MOD\n\ndef main():\n\tstring = input().strip()\n\ttest_cases = get_int()\n\tcounts_total = {}\n\tcur_cnt = {}\n\tl = len(string)\n\tfor c in set(string):\n\t\tcounts_total[c] = [0] * (l + 1)\n\t\tcur_cnt[c] = 0\n\tfor i in range(l):\n\t\tcur_cnt[string[i]] += 1\n\t\tfor (char, cnt) in cur_cnt.items():\n\t\t\tcounts_total[char][i] = cnt\n\tfor _ in range(test_cases):\n\t\t(l, r) = get_ints()\n\t\ts = string[l - 1:r]\n\t\twarn('looking for max len palindromes in ', s)\n\t\tcounts = {}\n\t\tfor char in counts_total:\n\t\t\tcnt = counts_total[char][r - 1] - counts_total[char][l - 2]\n\t\t\tif cnt > 0:\n\t\t\t\tcounts[char] = cnt\n\t\tprint(max_palindrome_count(counts))\n\t\twarn('-' * 78)\nmain()\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom collections import Counter\nfrom math import factorial\nf = [1 for _ in range(10 ** 5 + 1)]\nmod = 10 ** 9 + 7\nfor i in range(1, 10 ** 5 + 1):\n\tf[i] = f[i - 1] * i % mod\ninv_f = f[:]\ninv_f[-1] = pow(f[-1], mod - 2, mod)\nfor i in range(10 ** 5 - 1, 0, -1):\n\tinv_f[i] = inv_f[i + 1] * (i + 1) % mod\n\ndef initialize(s):\n\tc = Counter()\n\tdp = []\n\tfor ch in s:\n\t\tc[ch] += 1\n\t\tdp.append({k: v for (k, v) in c.items()})\n\treturn dp\n\ndef fac(evens, mod):\n\ts = sum(evens)\n\tres = f[s]\n\tfor v in evens:\n\t\tres *= inv_f[v]\n\treturn res % mod\n\ndef answerQuery(dp, l, r):\n\tmod = 10 ** 9 + 7\n\td = dp[l - 1] if l else {}\n\tans = [v - d.get(c, 0) for (c, v) in dp[r].items()]\n\tevens = [x // 2 for x in ans if x > 1]\n\todds = max(sum((1 for x in ans if x % 2 == 1)), 1)\n\treturn odds * fac(evens, mod) % mod\ns = input()\ndp = initialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(dp, l - 1, r - 1)\n\tprint(result)\n", "import sys, math\nMOD = 10 ** 9 + 7\nfact = [1]\ncur = 1\nfor i in range(1, 6 * 10 ** 4):\n\tcur *= i\n\tcur %= MOD\n\tfact.append(cur)\nalpha = 'abcdefghijklmnopqrstuvwxyz'\ndp = [0]\ndp2 = [[0] * 26]\n\ndef bitm(c):\n\treturn 1 << alpha.find(c)\n\ndef initialize(s):\n\tcur = 0\n\tfor c in s:\n\t\ttmp = [i for i in dp2[-1]]\n\t\ttmp[alpha.find(c)] += 1\n\t\tcur ^= bitm(c)\n\t\tdp.append(cur)\n\t\tdp2.append(tmp)\n\ndef modInv(x, pow=MOD - 2):\n\tif pow <= 3:\n\t\treturn x ** pow % MOD\n\telse:\n\t\ttmp = modInv(x, pow // 2)\n\t\ttmp *= tmp\n\t\ttmp %= MOD\n\t\tif pow % 2 == 0:\n\t\t\treturn tmp\n\t\telse:\n\t\t\treturn tmp * x % MOD\nmi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]\n\ndef answerQuery(l, r):\n\ttmp = dp[l - 1] ^ dp[r]\n\ttmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]\n\tpossLetters = 0\n\tfor c in range(26):\n\t\tif tmp & 1 << c:\n\t\t\tpossLetters += 1\n\tmiddle = max(possLetters, 1)\n\tothers = (r - l + 1 - possLetters) // 2\n\tans = fact[others] * middle % MOD\n\tfor i in tmp2:\n\t\tif i > 0:\n\t\t\tans *= mi[i]\n\t\t\tans %= MOD\n\treturn ans\ns = input().strip()\ninitialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r)\n\tprint(result % MOD)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nMOD = 10 ** 9 + 7\n\ndef generateFactorial(n):\n\tresult = [0] * n\n\tresult[0] = 1 % MOD\n\tfor i in range(1, n):\n\t\tresult[i] = result[i - 1] * i % MOD\n\treturn result\n\ndef generateReverse(n):\n\tresult = [0] * n\n\tif n > 1:\n\t\tresult[1] = 1\n\tfor i in range(2, n):\n\t\tresult[i] = (MOD - MOD // i * result[MOD % i] % MOD) % MOD\n\treturn result\n\ndef generateReverseFactorial(n):\n\tresult = generateReverse(n)\n\tresult[0] = 1\n\tfor i in range(1, n):\n\t\tresult[i] = result[i] * result[i - 1] % MOD\n\treturn result\n\ndef combine(n, k):\n\tif k < 0 or k > n:\n\t\treturn 0\n\treturn factorial[n] * reverseFactorial[k] % MOD * reverseFactorial[n - k] % MOD\n\ndef initialize(s):\n\tn = len(s)\n\tglobal quantity\n\tquantity = [[0] * 26] * (n + 1)\n\tfor i in range(n):\n\t\tquantity[i + 1] = quantity[i][:]\n\t\tquantity[i + 1][ord(s[i]) - ord('a')] += 1\n\tglobal factorial\n\tfactorial = generateFactorial(n)\n\tglobal reverseFactorial\n\treverseFactorial = generateReverseFactorial(n)\n\ndef answerQuery(l, r):\n\todd = 0\n\ttotal = 0\n\tanswer = 1\n\tfor i in range(26):\n\t\tnum = quantity[r][i] - quantity[l - 1][i]\n\t\ttotal += num >> 1\n\t\tanswer *= combine(total, num >> 1)\n\t\tanswer %= MOD\n\t\todd += num & 1\n\tanswer *= max(1, odd)\n\tanswer %= MOD\n\treturn answer\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "MOD = 10 ** 9 + 7\nb = 'abcdefghijklmnopqrstuvwxyz'\ns = input().strip()\nx = (0,) * len(b)\na = [x]\nd = {v: i for (i, v) in enumerate(b)}\nf = [1]\ninv = [0] * 100001\nfor i in range(1, 100000):\n\tf.append(f[-1] * i % MOD)\n\ndef inv_f(i):\n\tif not inv[i]:\n\t\tinv[i] = pow(f[i], MOD - 2, MOD)\n\treturn inv[i]\nfor v in s:\n\ti = d[v]\n\tx = x[:i] + (x[i] + 1,) + x[i + 1:]\n\ta.append(x)\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tl -= 1\n\tc = [j - i for (i, j) in zip(a[l], a[r]) if i != j]\n\to = sum((i & 1 for i in c))\n\tc = [i // 2 for i in c if i > 1]\n\te = sum(c)\n\tans = f[e]\n\tfor i in c:\n\t\tans = inv_f(i) * ans % MOD\n\tif o:\n\t\tans = ans * o % MOD\n\tprint(ans)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nimport array\np = 1000000007\nmaxs = 10000\n\ndef egcd(a, b):\n\t(x, y, u, v, bb) = (0, 1, 1, 0, b)\n\twhile b != 0:\n\t\tq = a // b\n\t\t(a, b) = (b, a % b)\n\t\t(x, u) = (u - q * x, x)\n\t\t(y, v) = (v - q * y, y)\n\treturn u if u > 0 else u + bb\nf = [1]\ninvf = [1]\nlet = [0] * 26\n\ndef initialize(s):\n\tfor i in range(1, len(s) + 1):\n\t\tf.append(f[-1] * i % p)\n\t\tinvf.append(egcd(f[-1], p))\n\tfor (i, c) in enumerate(s):\n\t\tlet.extend(let[-26:])\n\t\tlet[-26 + ord(c) - ord('a')] += 1\n\ndef answerQuery(l, r):\n\td = [let[r * 26 + i] - let[(l - 1) * 26 + i] for i in range(26)]\n\tse = sum((x // 2 for x in d))\n\tso = sum((x % 2 for x in d)) or 1\n\tff = f[se]\n\tfor x in d:\n\t\tff = ff * invf[x // 2] % p\n\treturn ff * so % p\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nMOD = 10 ** 9 + 7\nalphabet = 'abcdefghijklmnopqrstuvwxyz'\ncount = {c: [0] for c in alphabet}\nfact = [1]\n\ndef initialize(s):\n\tfor c in s:\n\t\tfor c_ in alphabet:\n\t\t\tcount[c_].append(count[c_][-1] + (1 if c == c_ else 0))\n\tfor n in range(1, len(s) + 1):\n\t\tfact.append(fact[-1] * n % MOD)\n\ndef gcde(a, b):\n\t(r, u, v, r2, u2, v2) = (a, 1, 0, b, 0, 1)\n\twhile r2 > 0:\n\t\tq = r // r2\n\t\t(r, u, v, r2, u2, v2) = (r2, u2, v2, r - q * r2, u - q * u2, v - q * v2)\n\treturn (r, u, v)\n\ndef invMod(a, m):\n\t(r, u, v) = gcde(a, m)\n\tif r != 1:\n\t\treturn None\n\treturn u\n\ndef answerQuery(l, r):\n\ttotal = 0\n\tdivisor = 1\n\tunique = 0\n\tfor c in alphabet:\n\t\t(n, nr) = divmod(count[c][r] - count[c][l - 1], 2)\n\t\tunique += nr\n\t\ttotal += n\n\t\tdivisor *= fact[n]\n\treturn fact[total] * invMod(divisor, MOD) * max(1, unique) % MOD\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "import math\nimport os\nimport random\nimport re\nimport sys\n\ndef initialize(s):\n\tn = len(s)\n\tglobal facts\n\tfacts = [1] * (n + 1)\n\tglobal st\n\tst = []\n\tfor i in range(26):\n\t\tst.append([0] * (n + 1))\n\tfor i in range(1, n + 1):\n\t\tfacts[i] = facts[i - 1] * i % 1000000007\n\t\tch = s[i - 1]\n\t\tk = ord(ch) - 97\n\t\tfor j in range(26):\n\t\t\tst[j][i] = st[j][i - 1] + int(k == j)\n\treturn\n\ndef modInverse(a, m):\n\tm0 = m\n\ty = 0\n\tx = 1\n\tif m == 1:\n\t\treturn 0\n\twhile a > 1:\n\t\tq = a // m\n\t\tt = m\n\t\tm = a % m\n\t\ta = t\n\t\tt = y\n\t\ty = x - q * y\n\t\tx = t\n\tif x < 0:\n\t\tx = x + m0\n\treturn x\n\ndef fact(x):\n\tr = 1\n\tfor i in range(2, x + 1):\n\t\tr = r * i\n\t\tif r > 1000000007:\n\t\t\tr = r % 1000000007\n\treturn r\n\ndef answerQuery(l, r):\n\tpairs = []\n\tsingles = 0\n\tfor j in range(26):\n\t\ti = st[j][r] - st[j][l - 1]\n\t\tt = i // 2\n\t\tif t > 0:\n\t\t\tpairs.append(t)\n\t\tif i % 2 == 1:\n\t\t\tsingles += 1\n\tres = facts[sum(pairs)]\n\tres_inv = 1\n\tfor p in pairs:\n\t\tres_inv = res_inv * facts[p] % 1000000007\n\tres_inv = modInverse(res_inv, 1000000007)\n\tres = res * res_inv % 1000000007\n\tif singles > 0:\n\t\tres = res * singles % 1000000007\n\treturn res\n\ndef answerQueryOld(l, r):\n\ts = st[l - 1:r]\n\tch_cnt = [0] * 26\n\tfor ch in s:\n\t\tch_cnt[ord(ch) - 97] += 1\n\tpairs = []\n\tsingles = 0\n\tfor i in ch_cnt:\n\t\tt = i // 2\n\t\tif t > 0:\n\t\t\tpairs.append(t)\n\t\tif i % 2 == 1:\n\t\t\tsingles += 1\n\tres = math.factorial(sum(pairs))\n\tfor p in pairs:\n\t\tres = res // math.factorial(p)\n\tif singles > 0:\n\t\tres = res * singles\n\treturn res % 1000000007\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom collections import Counter\nfrom copy import copy\n\ndef initialize(s):\n\tglobal a, m, f, inv\n\t(m, f, inv) = (1000000007, [1], {})\n\tfor i in range(1, 100000):\n\t\tf.append(f[-1] * i % m)\n\ta = [Counter()]\n\tfor x in s:\n\t\td = copy(a[-1])\n\t\td[x] += 1\n\t\ta.append(d)\n\ndef recurse(a, b):\n\tif a == 0:\n\t\treturn (0, 1)\n\telse:\n\t\t(y, x) = recurse(b % a, a)\n\t\treturn (x - b // a * y, y)\n\ndef invf(a):\n\tglobal inv\n\tif a in inv:\n\t\treturn inv[a]\n\t(x, y) = recurse(a, m)\n\tinv[a] = x % m\n\treturn x % m\n\ndef answerQuery(l, r):\n\td = Counter()\n\tfor x in a[r]:\n\t\td[x] += a[r][x]\n\tfor x in a[l - 1]:\n\t\td[x] -= a[l - 1][x]\n\t(o, r, t) = (0, 1, 0)\n\tfor (k, v) in d.items():\n\t\tif v & 1:\n\t\t\to += 1\n\t\tr *= invf(f[v // 2])\n\t\tt += v // 2\n\t\tr %= m\n\treturn max(1, o) * r * f[t] % m\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import sys\nfrom time import time\n\nclass Cache:\n\n\tdef __init__(self, s):\n\t\tself.rows = ord('z') - ord('a') + 1\n\t\tself.cols = len(s) + 1\n\t\tself.data = [None] * self.rows * self.cols\n\t\tfor r in range(self.rows):\n\t\t\tself.set(r, 0, 0)\n\t\tfor (c, ch) in enumerate(s):\n\t\t\tj = ord(ch) - ord('a')\n\t\t\tfor r in range(0, self.rows):\n\t\t\t\tv = self.get(r, c)\n\t\t\t\tif r == j:\n\t\t\t\t\tv += 1\n\t\t\t\tself.set(r, c + 1, v)\n\n\tdef index(self, r, c):\n\t\treturn r * self.cols + c\n\n\tdef get(self, r, c):\n\t\treturn self.data[self.index(r, c)]\n\n\tdef set(self, r, c, v):\n\t\tself.data[self.index(r, c)] = v\n\ndef modinv(n, p):\n\treturn pow(n, p - 2, p)\n\ndef f_gen(p):\n\t(f, i) = (1, 0)\n\twhile True:\n\t\tyield (f, modinv(f, p))\n\t\ti += 1\n\t\tf *= i\n\t\tf %= p\n\ndef frf_cache(n, p):\n\t(ff, rff) = ([], [])\n\tfor (i, (f, rf)) in enumerate(f_gen(p)):\n\t\tff.append(f)\n\t\trff.append(rf)\n\t\tif i == n:\n\t\t\tbreak\n\treturn (ff, rff)\n\ndef binomial(n, k, p, ff, rff):\n\trval = ff[n] * rff[k]\n\trval %= p\n\trval *= rff[n - k]\n\trval %= p\n\treturn rval\n\ndef calc(vv, ones, p, ff, rff):\n\trval = 1\n\tl = sum(vv)\n\tfor v in vv:\n\t\trval *= binomial(l, v, p, ff, rff)\n\t\trval %= p\n\t\tl -= v\n\tif ones:\n\t\trval *= ones\n\t\trval %= p\n\treturn rval\n\ndef solve(fr, to, m, cache, ff, rff):\n\t(vv, ones) = ([], 0)\n\tfor r in range(cache.rows):\n\t\tv = cache.get(r, to) - cache.get(r, fr)\n\t\tif v > 1:\n\t\t\tvv.append(v // 2)\n\t\tif v % 2 == 1:\n\t\t\tones += 1\n\treturn calc(vv, ones, m, ff, rff)\ntm = time()\nm = pow(10, 9) + 7\nN = pow(10, 5)\n(ff, rff) = frf_cache(N, m)\nprint('factorial cache generated: %s' % (time() - tm,), file=sys.stderr)\nprint('ff=%s\\nrff=%s' % (ff[:10], rff[:10]), file=sys.stderr)\ns = input()\ncache = Cache(s)\nprint('cache generated: %s' % (time() - tm,), file=sys.stderr)\nn = int(input())\nfor _ in range(n):\n\t(fr, to) = map(int, input().split())\n\tprint(solve(fr - 1, to, m, cache, ff, rff))\nprint('time elapsed: %s' % (time() - tm,), file=sys.stderr)\n", "from collections import Counter\nfrom functools import reduce, lru_cache\nfrom operator import mul\nM = 10 ** 9 + 7\nMAX = 50001\nFAC_M = [1] * MAX\nfor n in range(1, MAX):\n\tFAC_M[n] = n * FAC_M[n - 1] % M\n\n@lru_cache(None)\ndef modular_inv(n, prime):\n\tif n <= 1:\n\t\treturn 1\n\treturn modular_inv(prime % n, prime) * (prime - prime // n) % prime\n\ndef get_counts(s):\n\tcounts = [None for _ in range(len(s))]\n\tfor (i, c) in enumerate(s):\n\t\to = ord(c) - 97\n\t\tif i == 0:\n\t\t\tcounts[i] = [0] * 26\n\t\t\tcounts[i][o] = 1\n\t\telse:\n\t\t\tcounts[i] = counts[i - 1][:]\n\t\t\tcounts[i][o] += 1\n\tcounts.append([0] * 26)\n\treturn counts\n\ndef maxpali(l, r, counts):\n\tcs = [counts[r][i] - counts[l - 1][i] for i in range(26)]\n\tevens = [v // 2 for v in cs if v >= 2]\n\todd = sum((1 for v in cs if v % 2 == 1))\n\tp = FAC_M[sum(evens)]\n\tq = reduce(mul, map(FAC_M.__getitem__, evens)) % M if evens else 1\n\treturn p * modular_inv(q, M) * max(1, odd) % M\ns = input()\nq = int(input())\ncounts = get_counts(s)\nfor _ in range(q):\n\t(l, r) = map(int, input().split())\n\tprint(maxpali(l - 1, r - 1, counts))\n", "import math\nimport os\nimport random\nimport re\nimport sys\nimport math\nfrom functools import wraps\n\ndef my_cache(func):\n\tcache = {}\n\n\tdef set(key, val):\n\t\tcache[key] = val\n\n\t@wraps(func)\n\tdef wrapper(*args, **kwargs):\n\t\tkey = hash(args)\n\t\tif key in cache:\n\t\t\treturn cache.get(key)\n\t\telse:\n\t\t\tval = func(*args, **kwargs)\n\t\t\tset(key, val)\n\t\t\treturn val\n\treturn wrapper\n\ndef ordered_cache(func):\n\tcache = {}\n\n\tdef set(key, val):\n\t\tcache[key] = val\n\n\t@wraps(func)\n\tdef wrapper(x):\n\t\tkey = x\n\t\tif key in cache:\n\t\t\treturn cache.get(key)\n\t\telse:\n\t\t\tmax_current = max(list(cache.keys()) + [0])\n\t\t\tfor i in range(max_current + 1, x):\n\t\t\t\tset(i, func(i))\n\t\t\tval = func(x)\n\t\t\tset(x, val)\n\t\t\treturn val\n\treturn wrapper\n\n@ordered_cache\ndef fact(x):\n\tif x == 0:\n\t\treturn 1\n\telse:\n\t\treturn x * fact(x - 1) % (10 ** 9 + 7)\n\n@my_cache\ndef exp(x, n):\n\tif n < 0:\n\t\treturn exp(1 / x, -n) % (10 ** 9 + 7)\n\telif n == 0:\n\t\treturn 1\n\telif n == 1:\n\t\treturn x % (10 ** 9 + 7)\n\telif n % 2 == 0:\n\t\treturn exp(x * x % (10 ** 9 + 7), n / 2) % (10 ** 9 + 7)\n\telse:\n\t\treturn x * exp(x * x % (10 ** 9 + 7), (n - 1) / 2) % (10 ** 9 + 7) % (10 ** 9 + 7)\n\n@my_cache\ndef mod_inverse(x):\n\treturn exp(x, 10 ** 9 + 5) % (10 ** 9 + 7)\n\ndef initialize(s):\n\tindex = [tuple((0 for i in range(26)))]\n\tfor i in range(0, len(s)):\n\t\tval = ord(s[i]) - 97\n\t\tprev = index[i]\n\t\tnew_tup = tuple((prev[j] + 1 if j == val else prev[j] for j in range(26)))\n\t\tindex.append(new_tup)\n\treturn index\n\ndef answerQuery(l, r, index):\n\tfrequencies = tuple([index[r][i] - index[l - 1][i] for i in range(26)])\n\todds = max(1, sum([1 if x % 2 == 1 else 0 for x in frequencies]))\n\tpairs = [x // 2 for x in frequencies if x >= 2]\n\toffset = 0\n\tproduct = 1\n\tproduct = product * fact(sum(pairs)) % (10 ** 9 + 7)\n\tfor pair in pairs:\n\t\tproduct = product * mod_inverse(fact(pair)) % (10 ** 9 + 7)\n\t\toffset += pair\n\tproduct = product * odds % (10 ** 9 + 7)\n\treturn int(product)\ns = input()\nindex = initialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r, index)\n\tprint(result)\n", "from itertools import islice\nM = 10 ** 9 + 7\nmin_code = ord('a')\n\ndef egcd(a, b):\n\t(x0, x1, y0, y1) = (1, 0, 0, 1)\n\twhile b != 0:\n\t\t(q, a, b) = (a // b, b, a % b)\n\t\t(x0, x1) = (x1, x0 - q * x1)\n\t\t(y0, y1) = (y1, y0 - q * y1)\n\treturn (a, x0, y0)\n\ndef inverse(a, mod):\n\t(g, x, y) = egcd(a, mod)\n\treturn x\n\ndef index(letter):\n\treturn ord(letter) - min_code\n\ndef prepare_fact(size, M):\n\tcache = [None] * (size + 1)\n\tcache[0] = 1\n\tfor i in range(1, len(cache)):\n\t\tcache[i] = cache[i - 1] * i % M\n\treturn cache\n\ndef initialize(s):\n\tcounts = [None] * (index('z') + 1)\n\tfor i in range(len(counts)):\n\t\tcounts[i] = [0] * len(s)\n\tcounts[index(s[0])][0] = 1\n\tfor (i, sym) in islice(enumerate(s), 1, None):\n\t\tfor c in range(len(counts)):\n\t\t\tcounts[c][i] = counts[c][i - 1]\n\t\tcounts[index(sym)][i] += 1\n\treturn counts\n\ndef answerQuery(counts, fact, l, r):\n\todds = 0\n\tfor i in range(len(counts)):\n\t\tupper = counts[i][r - 1]\n\t\tlower = counts[i][l - 2] if l > 1 else 0\n\t\todds += int((upper - lower) % 2 == 1)\n\tpairs = (r - l + 1 - odds) // 2\n\torders = fact[pairs]\n\tdivisor = 1\n\tfor i in range(len(counts)):\n\t\tupper = counts[i][r - 1]\n\t\tlower = counts[i][l - 2] if l > 1 else 0\n\t\tdivisor = divisor * fact[(upper - lower) // 2] % M\n\torders = orders * inverse(divisor, M) % M\n\treturn orders * max(odds, 1) % M\ns = input()\nfact = prepare_fact(len(s), M)\ncounts = initialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(counts, fact, l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom functools import reduce\nbigN = 1000000007\n\ndef str2array(s):\n\tar2 = [[0] * 26 for ii in range(1 + len(s))]\n\ts_asInt = [ord(ch) - 97 for ch in s]\n\tfor dex in range(len(s_asInt)):\n\t\tar2[1 + dex] = [ar2[dex][jj] for jj in range(26)]\n\t\tar2[1 + dex][s_asInt[dex]] += 1\n\treturn ar2\n\ndef binaryExpansion(a):\n\tremainder = a\n\texpansion = []\n\twhile remainder:\n\t\texpansion.append(remainder % 2)\n\t\tremainder = remainder // 2\n\treturn expansion\n\ndef precomputeFactorials(n):\n\tfactorialDict = {0: 1, 1: 1}\n\tinvFactorialDict = {0: 1, 1: 1}\n\tbinary_bigNminus2 = binaryExpansion(bigN - 2)\n\tfor jj in range(2, 1 + n):\n\t\tfactorialDict[jj] = jj * factorialDict[jj - 1] % bigN\n\t\ta = factorialDict[jj]\n\t\ta_toPower_2totheDex = [a]\n\t\twhile len(a_toPower_2totheDex) < len(binary_bigNminus2):\n\t\t\ta_toPower_2totheDex.append(a_toPower_2totheDex[-1] * a_toPower_2totheDex[-1] % bigN)\n\t\ttempProduct = 1\n\t\tfor dex in range(len(binary_bigNminus2)):\n\t\t\tif binary_bigNminus2[dex]:\n\t\t\t\ttempProduct = tempProduct * a_toPower_2totheDex[dex] % bigN\n\t\tinvFactorialDict[jj] = tempProduct\n\treturn [factorialDict, invFactorialDict]\n\ndef answerQuery(ar2, l, r, factorialDict, invFactorialDict):\n\t[arL, arR] = [ar2[l - 1], ar2[r]]\n\tL = [arR[ii] - arL[ii] for ii in range(26)]\n\tnumOddValues = sum([el % 2 for el in L])\n\tBE = [el // 2 for el in L]\n\tBE = [el for el in BE if el != 0]\n\tnumPermutations_BE = factorialDict[sum(BE)]\n\tfor el in BE:\n\t\tnumPermutations_BE = numPermutations_BE * invFactorialDict[el] % bigN\n\ttotalPerms = numPermutations_BE * max(1, numOddValues) % bigN\n\treturn totalPerms\ns = input()\nar2 = str2array(s)\nq = int(input())\n[factorialDict, invFactorialDict] = precomputeFactorials(len(s))\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(ar2, l, r, factorialDict, invFactorialDict)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom collections import defaultdict\ns = ''\nM = 1000000007\n\ndef initialize(S):\n\tglobal s\n\ts = S\n\tpre_populate_fact_table(len(s) // 2, M)\n\tpre_calculate_frequencies(s)\ndebug = False\n\ndef dummy_print(*args):\n\tpass\nif debug:\n\tprintd = print\nelse:\n\tprintd = dummy_print\n\ndef fast_power(a, p, M):\n\tif p == 1:\n\t\treturn a\n\tif p == 0:\n\t\treturn 1\n\tif p % 2 == 0:\n\t\tnum = fast_power(a, p // 2, M) % M\n\t\treturn num * num % M\n\telse:\n\t\treturn a * fast_power(a, p - 1, M) % M\nfact_cache = {}\n\ndef cached_factorial_mod(a, M):\n\tif a in fact_cache:\n\t\treturn fact_cache[a]\n\tf = 1\n\tfor i in range(1, a + 1):\n\t\tf = f * i % M\n\tfact_cache[a] = f\n\treturn f\n\ndef pre_populate_fact_table(a, M):\n\tf = 1\n\tfor i in range(1, a + 1):\n\t\tf = f * i % M\n\t\tfact_cache[i] = f\nletter_freq = []\n\ndef pre_calculate_frequencies(s):\n\trunning_freq = [0] * 26\n\tletter_freq.append(list(running_freq))\n\tfor i in s:\n\t\trunning_freq[ord(i) - ord('a')] += 1\n\t\tletter_freq.append(list(running_freq))\n\ndef calc_frequencies_at(l, r):\n\ta = letter_freq[l - 1]\n\tb = letter_freq[r]\n\treturn [b[i] - a[i] for i in range(26)]\n\ndef answerQuery(l, r):\n\tprintd('=====')\n\tss = s[l - 1:r]\n\tprintd(ss)\n\tpermutations = 1\n\tfactorial_bottom = 1\n\tfactorial_top = 1\n\ttotal_letter_pairs = 0\n\tsingle_letters = 0\n\tletter_freq = calc_frequencies_at(l, r)\n\tfor v in letter_freq:\n\t\tletter_pairs = v // 2\n\t\tsingle_letters += v % 2\n\t\tif letter_pairs:\n\t\t\tprintd('letter_pairs', letter_pairs)\n\t\t\ttotal_letter_pairs += letter_pairs\n\t\t\tfactorial_letter = cached_factorial_mod(letter_pairs, M)\n\t\t\tfactorial_bottom = factorial_bottom * factorial_letter % M\n\tfactorial_top = cached_factorial_mod(total_letter_pairs, M)\n\tprintd(factorial_top, factorial_bottom)\n\tfactorial_bottom_inverse = fast_power(factorial_bottom, M - 2, M)\n\tprintd('factorial_bottom_inverse', factorial_bottom_inverse)\n\tpermutations = factorial_top * factorial_bottom_inverse % M\n\tprintd('permutations', permutations)\n\tif single_letters > 0:\n\t\tpermutations = permutations * single_letters % M\n\tprintd('permutations', permutations)\n\treturn permutations\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\n\ndef initialize_fact(fact, n):\n\tf = 1\n\tfor i in range(1, n + 1):\n\t\tf *= i\n\t\tfact.append(f)\n\ndef initialize(s):\n\ta = ord('a')\n\tchar_freq = len(s) * [26 * [0]]\n\tchar_freq[0][ord(s[0]) - a] = 1\n\tfor i in range(1, len(s)):\n\t\tchar_freq[i] = char_freq[i - 1].copy()\n\t\tchar_freq[i][ord(s[i]) - a] += 1\n\treturn char_freq\n\ndef counts_int(l, r):\n\t(l, r) = (l - 1, r - 1)\n\tif r >= len(s):\n\t\tprint('Error count index', len(s), r)\n\tif l == 0:\n\t\treturn freq[r]\n\telse:\n\t\treturn [freq[r][i] - freq[l - 1][i] for i in range(26)]\n\ndef modularInverse(n, p, a=[]):\n\tif a == []:\n\t\ta = [int(c) for c in bin(p - 2)[-1:1:-1]]\n\tk = len(a) * [0]\n\tk[0] = n % p\n\tfor i in range(1, len(a)):\n\t\tk[i] = k[i - 1] ** 2 % p\n\tprod = 1\n\tfor i in range(len(a)):\n\t\tif a[i] > 0:\n\t\t\tprod = prod * a[i] * k[i] % p\n\treturn prod % p\n\ndef answerQuery(l, r):\n\tcounts = counts_int(l, r)\n\todds = sum([1 for c in counts if c % 2 == 1])\n\tbase = [c // 2 for c in counts if c // 2 > 0]\n\tL = sum(base)\n\tassert L <= 50000\n\tF = fact[L]\n\tfor b in base:\n\t\tF = F * fact_inv_mod[b] % p\n\tif odds == 0:\n\t\treturn F % 1000000007\n\telse:\n\t\treturn odds * F % 1000000007\ns = input()\np = 10 ** 9 + 7\np2_bin = [int(c) for c in bin(p - 2)[-1:1:-1]]\nfact = 50001 * [1]\nfor i in range(1, 50001):\n\tfact[i] = i * fact[i - 1] % p\nfact_inv_mod = 500001 * [1]\nfor i in range(1, 50001):\n\tfact_inv_mod[i] = modularInverse(fact[i], p, p2_bin)\nfreq = initialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nP = 10 ** 9 + 7\nhistograms = []\nfactorials = []\ninv_factorials = []\n\ndef inv(x, p):\n\tsprev = 1\n\ts = 0\n\t(q, r) = divmod(x, p)\n\twhile r > 0:\n\t\tsnext = sprev - q * s\n\t\tsprev = s\n\t\ts = snext\n\t\tx = p\n\t\tp = r\n\t\t(q, r) = divmod(x, p)\n\treturn s\n\ndef initialize(s):\n\tn = len(s)\n\tfor i in range(1 + n):\n\t\tif i <= 1:\n\t\t\tfactorials.append(1)\n\t\t\tinv_factorials.append(1)\n\t\telse:\n\t\t\tf = factorials[i - 1] * i % P\n\t\t\tfactorials.append(f)\n\t\t\tinvi = inv(i, P)\n\t\t\tinv_factorials.append(inv_factorials[i - 1] * invi % P)\n\t\t\tassert factorials[i] * inv_factorials[i] % P == 1\n\thistogram = [0] * 26\n\tfor c in s:\n\t\thistograms.append(histogram.copy())\n\t\thistogram[ord(c) - ord('a')] += 1\n\thistograms.append(histogram)\n\ndef answerQuery(l, r):\n\tdiff = []\n\tfor (i, j) in zip(histograms[l - 1], histograms[r]):\n\t\tdiff.append(j - i)\n\tpairs = []\n\tfor i in range(len(diff)):\n\t\tcount = diff[i]\n\t\tpairs.append(count // 2)\n\t\tdiff[i] = count % 2\n\tdenom = 1\n\tfor p in pairs:\n\t\tdenom = denom * inv_factorials[p] % P\n\tif sum(pairs) == 0:\n\t\tnum = sum(diff)\n\telse:\n\t\tnum = factorials[sum(pairs)] * max(1, sum(diff))\n\treturn num * denom % P\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom collections import defaultdict\nfrom copy import copy\n\ndef find_inv(n, p):\n\tif n in inv_dict:\n\t\treturn inv_dict[n]\n\telse:\n\t\tinv_dict[n] = find_inv(p % n, p) * (p - p // n) % p\n\t\treturn find_inv(p % n, p) * (p - p // n) % p\n\ndef find_fact(n, p):\n\tfact_list = [0] * (n + 1)\n\tfact_list[0] = fact_list[1] = 1\n\tfor i in range(2, n + 1):\n\t\tfact_list[i] = fact_list[i - 1] * i % p\n\treturn fact_list\n\ndef answerQuery(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= find_inv(fact_list[v // 2], p_large)\n\t\ttotal += v // 2\n\t\tres %= p_large\n\treturn max(1, odds) * res * fact_list[total] % p_large\ns = input()\nN = len(s)\ninv_dict = {0: 1, 1: 1}\np_large = 1000000007\nfact_list = find_fact(N // 2, p_large)\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "from functools import reduce\nfrom copy import copy\nN = int(1000000000.0) + 7\n\ndef mul(a, b):\n\treturn a * b % N\n\ndef div(a, b):\n\treturn mul(a, pow(b, N - 2, N))\n\nclass Factorial:\n\n\tdef __init__(self, n):\n\t\tself.data = [0] * n\n\t\tself.data[0] = 1\n\t\tfor i in range(1, n):\n\t\t\tself.data[i] = mul(self.data[i - 1], i)\n\n\tdef __call__(self, n):\n\t\ttry:\n\t\t\treturn self.data[n]\n\t\texcept IndexError:\n\t\t\tprint('Factorial data not extended far enough!!!\\narg: {}, n: {}'.format(n, len(self.data)))\n\t\t\traise\nORDA = ord('a')\n\ndef construct_cumulative_letters(a):\n\tz = [[0] * 26 for _ in range(len(a))]\n\tz[0][ord(a[0]) - ORDA] = 1\n\tfor i in range(1, len(a)):\n\t\tfor j in range(26):\n\t\t\tz[i][j] = z[i - 1][j]\n\t\tz[i][ord(a[i]) - ORDA] += 1\n\treturn z\n\ndef letters(z, l, r):\n\tu = copy(z[r])\n\tif l != 0:\n\t\tfor j in range(26):\n\t\t\tu[j] -= z[l - 1][j]\n\treturn u\n\ndef max_palindrome_characteristics(letters):\n\tone_side_letters = 0\n\tmatching_sets = []\n\tcentral_letters = 0\n\tfor x in letters:\n\t\tto_add = x // 2\n\t\tone_side_letters += to_add\n\t\tif to_add > 1:\n\t\t\tmatching_sets.append(to_add)\n\t\tif x % 2:\n\t\t\tcentral_letters += 1\n\treturn (one_side_letters, central_letters, matching_sets)\n\ndef number_arrangements(f, n, central_letters, matching_sets):\n\tdenom = reduce(mul, map(f, matching_sets), 1)\n\tnum = f(n)\n\tif central_letters > 1:\n\t\tnum = mul(num, central_letters)\n\treturn div(num, denom)\na = input()\nz = construct_cumulative_letters(a)\nf = Factorial(1 + len(a) // 2)\nq = int(input())\nfor _ in range(q):\n\t(l, r) = (int(x) for x in input().split())\n\tprint(number_arrangements(f, *max_palindrome_characteristics(letters(z, l - 1, r - 1))))\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom collections import Counter\nfrom itertools import permutations\nfrom math import factorial\n\ndef initialize(s):\n\treturn s\nrl = []\nfact = []\nfactinv = []\n\ndef result_list(s):\n\trl.append(Counter(initialize(s[:1])))\n\tfor i in range(2, len(s) + 1):\n\t\trl.append(rl[i - 2] + Counter(initialize(s[i - 1:i])))\n\ndef power(x, y, m):\n\tif y == 0:\n\t\treturn 1\n\tp = power(x, y // 2, m) % m\n\tp = p * p % m\n\treturn p if y % 2 == 0 else x * p % m\n\ndef mod_inverse(a, m=10 ** 9 + 7):\n\treturn power(a, m - 2, m)\n\ndef mod_factorial(n, m=10 ** 9 + 7):\n\tfact.append(1)\n\tif n == 0:\n\t\treturn 1\n\tf = 1\n\tfor i in range(1, n + 1):\n\t\tf = f * i % m\n\t\tfact.append(f)\n\treturn f\n\ndef factor():\n\tfor i in range(0, rl[-1].most_common(1)[0][1] // 2 + 1):\n\t\tfactinv.append(mod_inverse(fact[i]))\n\ndef answerQuery(l, r):\n\tm = 10 ** 9 + 7\n\tif l != 1:\n\t\tfreq = rl[r - 1] - rl[l - 2]\n\telse:\n\t\tfreq = rl[r - 1]\n\tpairs = 0\n\tmiddle = 0\n\tdivider = 1\n\tfor i in freq.values():\n\t\tpairs += i // 2\n\t\tdivider = divider * factinv[i // 2] % m\n\t\tif i % 2 != 0:\n\t\t\tmiddle += 1\n\tpairs_mod = fact[pairs]\n\tif middle == 0:\n\t\treturn pairs_mod * divider % m\n\telse:\n\t\treturn pairs_mod * middle % m * divider % m\ns = input()\ninitialize(s)\nresult_list(s)\nmod_factorial(50000)\nfactor()\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\n\ndef modmult(a, b):\n\treturn a * b % 1000000007\n\ndef fastpow(a, n):\n\tif n == 1:\n\t\treturn a % 1000000007\n\tif n == 0:\n\t\treturn 1\n\tx = fastpow(a, n // 2)\n\tx = modmult(x, x)\n\tif n % 2 == 0:\n\t\treturn x\n\telse:\n\t\treturn modmult(a, x)\n\ndef answerQuery(frequencies, l, r):\n\tif l == 1:\n\t\tvalues = frequencies[r - 1]\n\telse:\n\t\tvalues = []\n\t\tfor i in range(26):\n\t\t\tvalues.append(frequencies[r - 1][i] - frequencies[l - 2][i])\n\tsingleletter = 0\n\tdoubleletter = 0\n\ttmf = 1\n\tfor value in values:\n\t\tdoubleletter += value // 2\n\t\tsingleletter += value % 2\n\t\ttmf = modmult(tmf, modinvfact[value // 2])\n\tcombinations = modmult(fact[doubleletter], tmf)\n\tif singleletter:\n\t\treturn combinations * singleletter % 1000000007\n\telse:\n\t\treturn combinations\ns = input()\nalphabets = 'abcdefghijklmnopqrstuvwxyz'\nfrequencies = []\na = [0] * 26\nfor char in s:\n\ta[alphabets.find(char)] += 1\n\tb = a[:]\n\tfrequencies.append(b)\nfact = [1]\nfor i in range(1, len(s) // 2 + 1):\n\tfact.append(modmult(fact[-1], i))\nmodinvfact = []\nfor num in fact:\n\tmodinvfact.append(fastpow(num, 1000000005))\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(frequencies, l, r)\n\tprint(result)\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "import math\nimport os\nimport random\nimport re\nimport sys\n\nclass initialize(object):\n\n\tdef __init__(self, s):\n\t\tself.s = s\n\t\tself.sSet = 'abcdefghijklmnopqrstuvwxyz'\n\t\tself.start()\n\n\tdef fastExpMod(self, b, e, m):\n\t\tresult = 1\n\t\twhile e != 0:\n\t\t\tif e & 1 == 1:\n\t\t\t\tresult = result * b % m\n\t\t\te >>= 1\n\t\t\tb = b * b % m\n\t\treturn result\n\n\tdef start(self):\n\t\tf = {i: {0: 0} for i in self.sSet}\n\t\tff = {0: 1, 1: 1}\n\t\tfff = {0: 1, 1: 1}\n\t\tfor (i, j) in enumerate(self.s):\n\t\t\tfor m in self.sSet:\n\t\t\t\tif j == m:\n\t\t\t\t\tf[m][i + 1] = f[m][i] + 1\n\t\t\t\telse:\n\t\t\t\t\tf[m][i + 1] = f[m][i]\n\t\tfor i in range(2, len(self.s) // 2 + 1):\n\t\t\tff[i] = ff[i - 1] * self.fastExpMod(i, 10 ** 9 + 5, 10 ** 9 + 7) % (10 ** 9 + 7)\n\t\t\tfff[i] = fff[i - 1] * i % (10 ** 9 + 7)\n\t\tself.f = f\n\t\tself.ff = ff\n\t\tself.fff = fff\n\n\tdef answerQuery(self, l, r):\n\t\tsall = 0\n\t\ts0 = 1\n\t\ts1 = 0\n\t\tfor i in self.sSet:\n\t\t\tj = self.f[i][r] - self.f[i][l - 1]\n\t\t\ts1 += j % 2\n\t\t\tnum = j // 2\n\t\t\tsall += num\n\t\t\ts0 *= self.ff[num]\n\t\ts1 = max(1, s1)\n\t\treturn self.fff[sall] * s0 * s1 % (10 ** 9 + 7)\ns = input()\nmp = initialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = mp.answerQuery(l, r)\n\tprint(result)\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "import math\nimport os\nimport random\nimport re\nimport sys\nimport copy\nsumchars = []\nMOD = 1000000007\nfactorials = [1] * 100001\ninverses = [1] * 100001\n\ndef initialize(s):\n\tsumchars.append([0] * 26)\n\tsumchars[0][ord(s[0]) - ord('a')] += 1\n\tfor i in range(1, len(s)):\n\t\ttoAdd = copy.deepcopy(sumchars[i - 1])\n\t\ttoAdd[ord(s[i]) - ord('a')] += 1\n\t\tsumchars.append(toAdd)\n\tfor i in range(2, len(factorials)):\n\t\tfactorials[i] = i * factorials[i - 1] % MOD\n\t\tinverses[i] = pow(factorials[i], MOD - 2, MOD)\n\ndef listSubtract(a, b):\n\tresult = [0] * len(a)\n\tfor i in range(len(a)):\n\t\tresult[i] = a[i] - b[i]\n\treturn result\n\ndef answerQuery(l, r):\n\tl -= 1\n\tr -= 1\n\tcharCounts = sumchars[r]\n\tif l > 0:\n\t\tcharCounts = listSubtract(sumchars[r], sumchars[l - 1])\n\tdivisionCounts = [x // 2 for x in charCounts]\n\tresult = factorials[sum(divisionCounts)]\n\tfor i in divisionCounts:\n\t\tif i > 1:\n\t\t\tresult = result * inverses[i] % MOD\n\tmoduloCounts = [x % 2 for x in charCounts]\n\tresult = result * max(1, sum(moduloCounts)) % MOD\n\treturn result\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nimport time\n\ndef initialize(s):\n\tglobal minv_arr, facmod, g_count\n\tnumAlpha = ord('z') - ord('a') + 1\n\tls = len(s)\n\tg_count = [0] * (ls + 1)\n\tfor i in range(ls + 1):\n\t\tg_count[i] = [0] * numAlpha\n\tfor i in range(1, ls + 1):\n\t\tfor j in range(numAlpha):\n\t\t\tg_count[i][j] = g_count[i - 1][j]\n\t\tg_count[i][ord(s[i - 1]) - 97] += 1\n\tmaxNum = 0\n\tmaxNum1 = 0\n\tfor i in g_count[-1]:\n\t\tif i > maxNum:\n\t\t\tmaxNum = i\n\tminv_arr = [0] * (maxNum // 2 + 1 + 1)\n\tminv_arr[0] = minv_arr[1] = 1\n\tm = 1000000007\n\tfor i in range(2, maxNum // 2 + 1 + 1):\n\t\tminv_arr[i] = modInverse(i, m) * minv_arr[i - 1] % m\n\tfacmod = [0] * 50001\n\tfacmod[0] = 1\n\tfacmod[1] = 1\n\tfor i in range(2, 50001):\n\t\tfacmod[i] = facmod[i - 1] * i % m % m\n\treturn 1\n\ndef modFact(n, d, p):\n\tif n >= p:\n\t\treturn 0\n\tresult = 1\n\tfor i in range(d, n + 1):\n\t\tresult = result * i % p\n\treturn result\n\ndef modInverse(a, m):\n\tg = gcd(a, m)\n\tif g != 1:\n\t\tprint(\"Inverse doesn't exist\")\n\telse:\n\t\treturn power(a, m - 2, m)\n\ndef power(x, y, m):\n\tif y == 0:\n\t\treturn 1\n\tp = power(x, y // 2, m) % m\n\tp = p * p % m\n\tif y % 2 == 0:\n\t\treturn p\n\telse:\n\t\treturn x * p % m\n\ndef gcd(a, b):\n\tif a == 0:\n\t\treturn b\n\treturn gcd(b % a, a)\n\ndef modularInverse(n, prime):\n\tdp = [0] * (n + 1)\n\tdp[0] = dp[1] = 1\n\tfor i in range(2, n + 1):\n\t\tdp[i] = dp[prime % i] * (prime - prime // i) % prime\n\treturn dp[n]\n\ndef modInverseFac(n, p):\n\tres = 1\n\tfor i in range(1, n + 1):\n\t\tres = res * modInverse(i, p) % p\n\treturn res\n\ndef modInverseMul(arrFac, p):\n\tres = 1\n\tfor i in arrFac:\n\t\tfor j in range(1, i + 1):\n\t\t\tres = res * minv_arr[j] % p\n\treturn res\n\ndef answerQuery(s, l, r):\n\tstart_time = time.time()\n\tcount = [0] * (ord('z') - ord('a') + 1)\n\tglobal dp\n\tfor i in range(len(count)):\n\t\tcount[i] = g_count[r][i] - g_count[l - 1][i]\n\tmaxLen = 0\n\tmark = 0\n\tcount_odd = 0\n\tcount_cinstr = []\n\tfor c in count:\n\t\tif c > 0 and c % 2 == 0:\n\t\t\tmaxLen += c\n\t\t\tcount_cinstr.append(c // 2)\n\t\telif c % 2 == 1:\n\t\t\tmark = 1\n\t\t\tmaxLen += c - 1\n\t\t\tif c > 1:\n\t\t\t\tcount_cinstr.append((c - 1) // 2)\n\t\t\tcount_odd += 1\n\thalf_max = maxLen // 2\n\tif mark == 1:\n\t\tmaxLen += 1\n\tm = 1000000007\n\ttmp = 1\n\tlargest = 0\n\tind_large = -1\n\tb = 1\n\ta = facmod[half_max]\n\tfor i in count_cinstr:\n\t\tb = b * minv_arr[i] % m\n\ttotal = a * b % m\n\tif count_odd > 0:\n\t\ttotal = total % m * count_odd % m\n\treturn total % m\ns = input()\ninitialize(s)\nq = int(input())\nfor q_itr in range(q):\n\tlr = input().split()\n\tl = int(lr[0])\n\tr = int(lr[1])\n\tresult = answerQuery(s, l, r)\n\tprint(result)\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom collections import defaultdict\nfrom collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "import math\nimport os\nimport random\nimport re\nimport sys\nfrom collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "(W, F, G, X, M) = (input(), [1], [1], [[0] * 26], 10 ** 9 + 7)\nfor i in range(1, len(W) + 1):\n\tF.append(i * F[i - 1] % M)\n\tG.append(pow(F[i], M - 2, M))\n\tL = list(X[i - 1])\n\tL[ord(W[i - 1]) - 97] += 1\n\tX.append(L)\nfor _ in range(int(input())):\n\t(L, R) = map(int, input().split())\n\t(A, B, C) = (0, 1, 0)\n\tfor i in range(26):\n\t\tx = X[R][i] - X[L - 1][i]\n\t\tif x:\n\t\t\t(A, B, C) = (A + x // 2, B * G[x // 2] % M, C + x % 2)\n\tprint(F[A] % M * B * max(1, C) % M)\n", "from collections import defaultdict\nfrom copy import copy\nmod = 1000000007\nmax_ele = 50000\nfact = dict()\nifact = dict()\nregister = dict()\n(fact[0], fact[1]) = (1, 1)\nfor i in range(2, max_ele + 1, 1):\n\tfact[i] = fact[i - 1] * i % mod\nifact[max_ele] = pow(fact[max_ele], mod - 2, mod)\nfor i in range(max_ele, 0, -1):\n\tifact[i - 1] = ifact[i] * i % mod\n\ndef counter(s, l, r):\n\tsingle = 0\n\tnon_single = []\n\tfor letter in occurance_of_letter[r]:\n\t\tj = occurance_of_letter[r][letter] - occurance_of_letter[l - 1][letter]\n\t\tif j == 1:\n\t\t\tsingle += 1\n\t\telif j % 2 == 0:\n\t\t\tnon_single.append(j // 2)\n\t\telse:\n\t\t\tnon_single.append(j // 2)\n\t\t\tsingle += 1\n\ty = fact[sum(non_single)]\n\tfor i in non_single:\n\t\tif i == 1:\n\t\t\tcontinue\n\t\ty = y * ifact[i] % mod\n\tif single == 0:\n\t\tans = y % mod\n\telse:\n\t\tans = y * single % mod\n\treturn int(ans)\ns = input()\ncount = int(input())\noccurance_of_letter = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occurance_of_letter[-1])\n\tnewd[ch] += 1\n\toccurance_of_letter.append(newd)\nfor i in range(count):\n\tget_sting = input().split()\n\tl = int(get_sting[0])\n\tr = int(get_sting[1])\n\tif (l, r) in register:\n\t\tprint(register[l, r])\n\telse:\n\t\tcollect = counter(s, l, r)\n\t\tregister[l, r] = collect\n\t\tprint(collect)\n", "mod = 10 ** 9 + 7\n\ndef factorials(n):\n\tres = [0] * (n + 1)\n\tprev = 1\n\tfor i in range(1, n + 1):\n\t\tprev = prev * i % mod\n\t\tres[i] = prev\n\treturn res\n\ndef init(s):\n\t(cnt, data) = ([0] * 26, [[]] * (len(s) + 1))\n\tdata[0] = list(cnt)\n\tfor (i, c) in enumerate(s):\n\t\tcnt[ord(c) - 97] += 1\n\t\tdata[i + 1] = list(cnt)\n\treturn (data, factorials(sum(cnt)))\n\ndef modInv(a, mod):\n\n\tdef egcd(a, b):\n\t\t(x, y, u, v) = (0, 1, 1, 0)\n\t\twhile a != 0:\n\t\t\t(q, r) = (b // a, b % a)\n\t\t\t(m, n) = (x - u * q, y - v * q)\n\t\t\t(b, a, x, y, u, v) = (a, r, u, v, m, n)\n\t\tGCD = b\n\t\treturn (GCD, x, y)\n\t(_, x, y) = egcd(a, mod)\n\treturn x % mod\n\ndef calculate_palindromes(parts, middle, fact):\n\tif len(parts) == 0:\n\t\treturn middle\n\t(A, B) = (fact[sum(parts)], 1)\n\tfor v in parts:\n\t\tB = B * fact[v] % mod\n\tres = A * modInv(B, mod) % mod\n\tif middle:\n\t\treturn middle * res % mod\n\treturn res\n\ndef find(data, fact, s, e):\n\t(middle, parts) = (0, [])\n\tfor (v_s, v_e) in zip(data[s - 1], data[e]):\n\t\ttmp = v_e - v_s\n\t\tif tmp > 0:\n\t\t\tmiddle += tmp % 2\n\t\tif tmp // 2:\n\t\t\tparts.append(tmp // 2)\n\treturn calculate_palindromes(parts, middle, fact)\n(data, fact) = init(input())\nres = []\nfor _ in range(int(input())):\n\t(s, e) = tuple(map(int, input().split()))\n\tres.append(find(data, fact, s, e))\nprint('\\n'.join(map(str, res)))\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "s = input()\nfrom math import factorial\nmod = 10 ** 9 + 7\nF = [1]\nfor i in range(1, 10 ** 5 + 2):\n\tF.append(F[-1] * i % mod)\nA = {'a': [0], 'b': [0], 'c': [0], 'd': [0], 'e': [0], 'f': [0], 'g': [0], 'h': [0], 'i': [0], 'j': [0], 'k': [0], 'l': [0], 'm': [0], 'n': [0], 'o': [0], 'p': [0], 'q': [0], 'r': [0], 's': [0], 't': [0], 'u': [0], 'v': [0], 'w': [0], 'x': [0], 'y': [0], 'z': [0]}\nfor c in s:\n\tfor a in A:\n\t\tA[a].append(A[a][-1])\n\tA[c][-1] += 1\nq = int(input())\nfor _ in range(q):\n\t(l, r) = map(int, input().split())\n\teven = []\n\tnumodd = 0\n\tfor a in A:\n\t\tcount = A[a][r] - A[a][l - 1]\n\t\tif count <= 0:\n\t\t\tcontinue\n\t\tif count % 2:\n\t\t\tnumodd += 1\n\t\t\teven.append(count - 1)\n\t\telse:\n\t\t\teven.append(count)\n\tS = 0\n\tdiv = 1\n\tfor e in even:\n\t\te //= 2\n\t\tS += e\n\t\tdiv = div * F[e] % mod\n\tres = F[S] % mod * pow(div, mod - 2, mod)\n\tif numodd:\n\t\tres *= numodd\n\tprint(res % mod)\n", "from collections import defaultdict\nfrom copy import copy\nM = int(1000000000.0) + 7\nfact = [1]\nfor i in range(1, int(100000.0) + 10):\n\tfact.append(fact[-1] * i % M)\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\nmemo = {}\n\ndef modinv(a, m):\n\tif a in memo:\n\t\treturn memo[a]\n\twhile a < 0:\n\t\ta += m\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('Modular inverse does not exist')\n\telse:\n\t\tmemo[a] = x % m\n\t\treturn x % m\ns = input().strip()\nocc = [defaultdict(int)]\nfor ch in s:\n\tnewd = copy(occ[-1])\n\tnewd[ch] += 1\n\tocc.append(newd)\n\ndef query(l, r):\n\td = defaultdict(int)\n\tfor ch in occ[r]:\n\t\td[ch] += occ[r][ch]\n\tfor ch in occ[l - 1]:\n\t\td[ch] -= occ[l - 1][ch]\n\todds = 0\n\tfor (k, v) in copy(d).items():\n\t\tif v & 1:\n\t\t\todds += 1\n\t\td[k] = v - (v & 1)\n\tres = 1\n\ttotal = 0\n\tfor (k, v) in d.items():\n\t\tres *= modinv(fact[v // 2], M)\n\t\ttotal += v // 2\n\t\tres %= M\n\treturn max(1, odds) * res * fact[total] % M\nfor _ in range(int(input())):\n\t(l, r) = map(int, input().split())\n\tprint(query(l, r))\n", "import sys, math\nMOD = 10 ** 9 + 7\nfact = [1]\ncur = 1\nfor i in range(1, 6 * 10 ** 4):\n\tcur *= i\n\tcur %= MOD\n\tfact.append(cur)\nalpha = 'abcdefghijklmnopqrstuvwxyz'\ndp = [0]\ndp2 = [[0] * 26]\n\ndef bitm(c):\n\treturn 1 << alpha.find(c)\n\ndef initialize(s):\n\tcur = 0\n\tfor c in s:\n\t\ttmp = [i for i in dp2[-1]]\n\t\ttmp[alpha.find(c)] += 1\n\t\tcur ^= bitm(c)\n\t\tdp.append(cur)\n\t\tdp2.append(tmp)\n\ndef modInv(x, pow=MOD - 2):\n\tif pow <= 3:\n\t\treturn x ** pow % MOD\n\telse:\n\t\ttmp = modInv(x, pow // 2)\n\t\ttmp *= tmp\n\t\ttmp %= MOD\n\t\tif pow % 2 == 0:\n\t\t\treturn tmp\n\t\telse:\n\t\t\treturn tmp * x % MOD\nmi = [modInv(fact[x]) for x in range(6 * 10 ** 4)]\n\ndef answerQuery(l, r):\n\ttmp = dp[l - 1] ^ dp[r]\n\ttmp2 = [(dp2[r][i] - dp2[l - 1][i]) // 2 for i in range(26)]\n\tpossLetters = 0\n\tfor c in range(26):\n\t\tif tmp & 1 << c:\n\t\t\tpossLetters += 1\n\tmiddle = max(possLetters, 1)\n\tothers = (r - l + 1 - possLetters) // 2\n\tans = fact[others] * middle % MOD\n\tfor i in tmp2:\n\t\tif i > 0:\n\t\t\tans *= mi[i]\n\t\t\tans %= MOD\n\treturn ans\ns = input().strip()\ninitialize(s)\nq = int(input().strip())\nfor a0 in range(q):\n\t(l, r) = input().strip().split(' ')\n\t(l, r) = [int(l), int(r)]\n\tresult = answerQuery(l, r)\n\tprint(result % MOD)\n"]

difficulty: MEDIUM

source: hacker rank

question:
Madam Hannah Otto, the CEO of Reviver Corp., is fond of palindromes, or words that read the same forwards or backwards. She thinks palindromic brand names are appealing to millennials.

As part of the marketing campaign for the company's new juicer called the Rotator™, Hannah decided to push the marketing team's palindrome-searching skills to a new level with a new challenge.

In this challenge, Hannah provides a string $\boldsymbol{\mathrm{~S~}}$ consisting of lowercase English letters. Every day, for $\textit{q}$ days, she would select two integers $\boldsymbol{l}$ and $\textbf{r}$, take the substring ${\mbox{S}}_{\mbox{l}\ldots\mbox{r}}$ (the substring of $\boldsymbol{\mathrm{~S~}}$ from index $\boldsymbol{l}$ to index $\textbf{r}$), and ask the following question:

Consider all the palindromes that can be constructed from some of the letters from ${\mbox{S}}_{\mbox{l}\ldots\mbox{r}}$. You can reorder the letters as you need. Some of these palindromes have the maximum length among all these palindromes. How many maximum-length palindromes are there?

For example, if $s=\textbf{madamimadam}$, $l=4$ and $r=7$, then we have,

![image](1.png)
Your job as the head of the marketing team is to answer all the queries. Since the answers can be very large, you are only required to find the answer modulo $10^9+7$.

Complete the functions initialize and answerQuery and return the number of maximum-length palindromes modulo $10^9+7$.

Input Format

The first line contains the string $\boldsymbol{\mathrm{~S~}}$.

The second line contains a single integer $\textit{q}$.

The $i^{th}$ of the next $\textit{q}$ lines contains two space-separated integers $\mathbf{l}_i$, $r_i$ denoting the $\boldsymbol{l}$ and $\textbf{r}$ values Anna selected on the $i^{th}$ day.

Constraints

Here, $\left|s\right|$ denotes the length of $\boldsymbol{\mathrm{~S~}}$.

$1\leq|s|\leq10^5$
$1\leq q\leq10^5$
$1\leq l_i\leq r_i\leq|s|$

Subtasks

For 30% of the total score:

$1\leq|s|\leq100$
$1\leq q\leq1000$
$r_i-l_i\leq3$

For 60% of the total score:

$1\leq|s|\leq100$
$1\leq q\leq1000$

Output Format

For each query, print a single line containing a single integer denoting the answer.

Sample Input 0
week
2
1 4
2 3

Sample Output 0
2
1

Explanation 0

On the first day, $l=1$ and $r=4$. The maximum-length palindromes are "ewe" and "eke".

On the second day, $l=2$ and $r=3$. The maximum-length palindrome is "ee".

![image](2.png)
Sample Input 1
abab
1
1 4

Sample Output 1
2

Explanation 1

Here, the maximum-length palindromes are "abba" and "baab".

image_tags:
Linear Data Structure
Linear Data Structure

data_split: test


raw_problem:
The minimum number of cubes to cover every visible face on a cuboid measuring $3 \times 2 \times 1$ is twenty-two.

If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.

However, the first layer on a cuboid measuring $5 \times 1 \times 1$ also requires twenty-two cubes; similarly the first layer on cuboids measuring $5 \times 3 \times 1$, $7 \times 2 \times 1$, and $11 \times 1 \times 1$ all contain forty-six cubes.

We shall define $C(n)$ to represent the number of cuboids that contain $n$ cubes in one of its layers. So $C(22) = 2$, $C(46) = 4$, $C(78) = 5$, and $C(118) = 8$.

It turns out that $154$ is the least value of $n$ for which $C(n) = 10$.

Find the least value of $n$ for which $C(n) = 1000$.

problem:
The minimum number of cubes to cover every visible face on a cuboid measuring $3 \times 2 \times 1$ is twenty-two.

![image](images/ep_126/1.png)
If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.
However, the first layer on a cuboid measuring $5 \times 1 \times 1$ also requires twenty-two cubes; similarly the first layer on cuboids measuring $5 \times 3 \times 1$, $7 \times 2 \times 1$, and $11 \times 1 \times 1$ all contain forty-six cubes.
We shall define $C(n)$ to represent the number of cuboids that contain $n$ cubes in one of its layers. So $C(22) = 2$, $C(46) = 4$, $C(78) = 5$, and $C(118) = 8$.
It turns out that $154$ is the least value of $n$ for which $C(n) = 10$.
Find the least value of $n$ for which $C(n) = 1000$.

question:
The minimum number of cubes to cover every visible face on a cuboid measuring $3 \times 2 \times 1$ is twenty-two.

![image](1.png)
If we then add a second layer to this solid it would require forty-six cubes to cover every visible face, the third layer would require seventy-eight cubes, and the fourth layer would require one-hundred and eighteen cubes to cover every visible face.
However, the first layer on a cuboid measuring $5 \times 1 \times 1$ also requires twenty-two cubes; similarly the first layer on cuboids measuring $5 \times 3 \times 1$, $7 \times 2 \times 1$, and $11 \times 1 \times 1$ all contain forty-six cubes.
We shall define $C(n)$ to represent the number of cuboids that contain $n$ cubes in one of its layers. So $C(22) = 2$, $C(46) = 4$, $C(78) = 5$, and $C(118) = 8$.
It turns out that $154$ is the least value of $n$ for which $C(n) = 10$.
Find the least value of $n$ for which $C(n) = 1000$.

data_split: test

source: project euler


Magic Square

source: 9th PC Koshien, Final

raw_problem:
魔法陣

人里離れた森の奥深くに、マリーという名の魔女が住んでいました。彼女は魔女なので、食料・水・燃料など、生活に必要なものを魔法によってまかなっています。

彼女の魔法は、魔力を込めたいくつかの石と紐を使って、魔法陣を描くことによって発動します。この魔法陣は、石を設置し、いくつかの石のペアを紐で繋ぐことで描かれます。ただし、紐は弛んでいてはいけません。さらに、どの紐も、(両端を除いて) 他の紐や石に触れてはいけません。もちろん、同じ場所に複数の石を置くこともできません。この制約が守られる限り、石と石の位置関係や紐の長さに制限はありません。また、石は十分小さいので点として扱うことができ、紐は十分細いので線分として扱うことができます。さらに、彼女は同じ石のペアを2本以上の紐で繋ぐことも、ある紐の両端を同じ石に結ぶこともありません。

マリーは初め、石を彼女の家の平らな壁に貼り付けて魔法陣を描いていました。しかし、彼女はやがて、どうしても作ることのできない魔法陣があることに気付いたのです。しばらくして、彼女は魔法陣を平らな壁、つまり二次元平面の上で作ることができるか判定する方法を編み出しました。ある魔法陣は、次のような部分を含む場合、またその場合に限って、二次元平面上で作ることができないのです。

図１ 頂点数 5 の完全グラフ

図２ 頂点数 3, 3 の完全二部グラフ

このような魔法陣を描くために、彼女は石を空中に固定する魔法を編み出しました。三次元空間では、これらの魔法陣も描くことができるのです。それどころか、どんな魔法陣も三次元空間中では描くことができることを彼女は突き止めたのです。

さて、ここからが問題です。ある日マリーは、彼女の家の玄関に足元灯の魔法陣を作ることにしました。しかし、彼女は既に狭い玄関にいろいろな魔法陣を設置していたので、足元灯の魔法陣を、残された唯一のスペースである一次元の直線の上に描かなければなりません。彼女が設計したいくつかの足元灯の魔法陣について、それが直線の上に描けるかどうかを判定し、描ける場合 yes と、そうでない場合 no と出力するプログラムを作成して下さい。

魔法陣は、石の個数 <var>n</var>、紐の本数 <var>m</var>、<var>m</var> 個の紐の情報で与えられます。紐は、その両端の石の番号 <var>u</var>、<var>v</var> で表されます。石には 1 から <var>n</var> までの番号が与えられ、<var>n</var> は 1 以上 100,000 以下、<var>m</var> は 0 以上 1,000,000 以下とします。

入力

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。各データセットは以下のとおりです。

1 行目 石の個数 <var>n</var> 紐の本数 <var>m</var>（整数 整数；半角空白区切り）

2 行目 第1の紐の情報 <var>u</var> <var>v</var>（整数 整数；半角空白区切り）

3 行目 第2の紐の情報

:

<var>m+1 </var>行目 第 <var>m</var> の紐の情報

データセットの数は 20 を超えません。

出力

入力データセットごとに、yes または no と１行に出力します。

入力例

5 4
1 2
2 3
3 4
4 5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
5 0
0 0

出力例

yes
no
yes

solutions: ["# AOJ 0251: Magic Square\n# Python3 2018.6.25 bal4u\n\n# UNION-FIND library\nclass UnionSet:\n\tdef __init__(self, nmax):\n\t\tself.size = [1]*nmax\n\t\tself.id = [i for i in range(nmax+1)]\n\tdef root(self, i):\n\t\twhile i != self.id[i]:\n\t\t\tself.id[i] = self.id[self.id[i]]\n\t\t\ti = self.id[i]\n\t\treturn i\n\tdef connected(self, p, q): return self.root(p) == self.root(q)\n\tdef unite(self, p, q):\n\t\ti, j = self.root(p), self.root(q)\n\t\tif i == j: return\n\t\tif self.size[i] < self.size[j]:\n\t\t\tself.id[i] = j\n\t\t\tself.size[j] += self.size[i]\n\t\telse:\n\t\t\tself.id[j] = i\n\t\t\tself.size[i] += self.size[j]\n# UNION-FIND library\n\nwhile True:\n\tn, m = map(int, input().split())\n\tif n == 0: break\n\tn += 1\n\tu = UnionSet(n)\n\tf = [0]*n\n\tans = True\n\tfor i in range(m):\n\t\tif ans:\n\t\t\ta, b = map(int, input().split())\n\t\t\tf[a] += 1\n\t\t\tf[b] += 1\n\t\t\tif f[a] > 2: ans = False\n\t\t\tif f[b] > 2: ans = False\n\t\t\tif u.connected(a, b): ans = False\n\t\t\tu.unite(a, b)\n\t\telse: input()\n\tprint(\"yes\" if ans else \"no\")\n\n", "import sys\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\ndef solve():\n    N, M = map(int, readline().split())\n    if N == M == 0:\n        return False\n    G = [[] for i in range(N)]\n    ok = 1\n    for i in range(M):\n        u, v = map(int, readline().split())\n        G[u-1].append(v-1)\n        G[v-1].append(u-1)\n        if u == v:\n            ok = 0\n    used = [0]*N\n    for i in range(N):\n        if used[i] or len(G[i]) != 1:\n            continue\n        used[i] = 1\n        v = i\n        while 1:\n            if len(G[v]) == 1:\n                if used[G[v][0]]:\n                    break\n            elif len(G[v]) != 2:\n                ok = 0\n                break\n            v = (G[v][0] if G[v][0] != v else G[v][1])\n            used[v] = 1\n    for i in range(N):\n        if len(G[i]) != 0 and not used[i]:\n            ok = 0\n    if ok:\n        write(\"yes\\n\")\n    else:\n        write(\"no\\n\")\n    return True\nwhile solve():\n    ...\n", "from collections import Counter\ndef get_par(x, par_lst):\n  if x == par_lst[x]:\n    return x\n  ret = get_par(par_lst[x], par_lst)\n  par_lst[x] = ret\n  return ret\n\ndef main():\n  while True:\n    n, m = map(int, input().split())\n    if n == 0:\n      break\n    par_lst = [i for i in range(n)]\n    counter = [0] * n\n    flag = False\n    for _ in range(m):\n      u, v = map(int, input().split())\n      u -= 1\n      v -= 1\n      counter[u] += 1\n      counter[v] += 1\n      pu, pv = get_par(u, par_lst), get_par(v, par_lst)\n      if pu == pv:\n        flag = True\n      else:\n        par_lst[pu] = pv\n    \n    if max(counter) > 2:\n      flag = True\n    if flag:\n      print(\"no\")\n    else:\n      print(\"yes\")\nmain()\n", "import sys\n\n# READ_FROM_FILE = True\nREAD_FROM_FILE = False\n\n\ndef is_there_cycle(n, adjacency_list):\n    is_visited = [False] * n\n    for r in range(n):\n        if is_visited[r]:\n            continue\n\n        stack = [(r, -1)]\n        while stack:\n            v, pv = stack.pop()\n            if is_visited[v]:\n                return True\n\n            is_visited[v] = True\n            for u in adjacency_list[v]:\n                if u != pv:\n                    stack.append((u, v))\n\n    return False\n\n\ndef main():\n    if READ_FROM_FILE:\n        f = open('test0.txt', 'r')\n    else:\n        f = sys.stdin\n\n    while True:\n        n, m = map(int, f.readline().split())\n        if n == m == 0:\n            break\n\n        degree_list = [0] * n\n        adjacency_list = [[] for _ in range(n)]\n        is_valid = True\n        for _ in range(m):\n            u, v = map(int, f.readline().split())\n            u -= 1\n            v -= 1\n            if not is_valid:\n                continue\n            degree_list[u] += 1\n            if degree_list[u] == 3:\n                is_valid = False\n            degree_list[v] += 1\n            if degree_list[v] == 3:\n                is_valid = False\n\n            adjacency_list[u].append(v)\n            adjacency_list[v].append(u)\n\n        if is_valid:\n            if is_there_cycle(n, adjacency_list):\n                is_valid = False\n\n        print('yes' if is_valid else 'no')\n\n    if READ_FROM_FILE:\n        f.close()\n    return\n\n\nif __name__ == '__main__':\n    main()\n\n"]

source: aizu

question:
Magic Circle

Deep in a secluded forest, there lived a witch named Marie. As she was a witch, she managed to cover her necessities such as food, water, and fuel through magic.

Her magic involved using several stones infused with magical energy and strings to create magic circles by arranging these elements. The magic circle is drawn by placing stones and connecting some pairs of stones with strings. However, the strings must not be slack. Furthermore, no string may touch any other string or stone (except at the ends). Of course, you cannot place multiple stones in the same location. As long as these constraints are met, there are no restrictions on the positional relations between the stones or the lengths of the strings. In addition, since the stones are sufficiently small, they can be treated as points, and the strings are sufficiently thin, they can be treated as line segments. Moreover, she does not connect the same pair of stones with more than one string or tie both ends of the same string to the same stone.

Initially, Marie used to create her magic circles by attaching the stones to the flat walls of her house. However, she soon realized that there were magic circles that she simply could not create. After a while, she devised a method to determine whether a magic circle could be created on a flat wall, that is, on a two-dimensional plane. A magic circle can't be created on a two-dimensional plane if and only if it contains parts like the following:

![image](1.png)

![image](2.png)

Figure 1 Complete graph with 5 vertices

Figure 2 Complete bipartite graph with 3, 3 vertices

To draw such magic circles, she devised a spell to fix the stones in mid-air. In three-dimensional space, these magic circles can be drawn. In fact, she discovered that any magic circle could be drawn in three-dimensional space.

Now, here's the problem. One day, Marie decided to create a footlight magic circle at the entrance of her house. However, since she had already installed various magic circles in the narrow entrance, she had to draw the footlight magic circle on the only space left, which was a one-dimensional line. For some of the footlight magic circles she designed, please create a program that determines whether they can be drawn on a line and outputs "yes" if it can be drawn and "no" otherwise.

The magic circle is given by the number of stones $n$, the number of strings $m$, and information about $m$ strings. A string is represented by the numbers $u$, $v$ of the stones at both ends. Each stone is assigned a number from 1 to $n$, with $n$ being 1 to 100,000 and $m$ being 0 to 1,000,000.

Input

Multiple datasets are given as input. The end of the input is indicated by a line with two zeros. Each dataset is as follows:

First line Number of stones $n$ Number of strings $m$ (integer integer; separated by a space)
Second line Information about the first string $u$ $v$ (integer integer; separated by a space)
Third line Information about the second string:
:
Line $m+1$ Information about string $m$

The number of datasets does not exceed 20.

Output

For each input dataset, output "yes" or "no" on one line.

Input example

5 4
1 2
2 3
3 4
4 5
4 6
1 2
1 3
1 4
2 3
2 4
3 4
5 0
0 0

Output example

yes
no
yes

image_tags: Graph Graph

data_split: test


I. Fake News (hard)

problem_index: I

time_limit: 5 seconds

memory_limit: 256 megabytes

question:
Now that you have proposed a fake post for the HC^{2} Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about the impact of fractal structure on multimedia messages and she is now trying to measure the self-similarity of the message, which is defined as
![image](1.png)where the sum is over all nonempty strings p and ![image](2.png) is the number of occurences of p in s as a substring. (Note that the sum is infinite, but it only has a finite number of nonzero summands.)
Heidi refuses to do anything else until she knows how to calculate this self-similarity. Could you please help her? (If you would like to instead convince Heidi that a finite string cannot be a fractal anyway – do not bother, we have already tried.)

Input
The input starts with a line indicating the number of test cases T (1 ≤ T ≤ 10). After that, T test cases follow, each of which consists of one line containing a string s (1 ≤ |s| ≤ 100 000) composed of lowercase letters (a-z).

Output
Output T lines, every line containing one number – the answer to the corresponding test case.

Example
Input
4
aa
abcd
ccc
abcc

Output
5
10
14
12

Note
A string s contains another string p as a substring if p is a contiguous subsequence of s. For example, ab is a substring of cab but not of acb.

difficulty: HARD

source: codeforces

sample_tests: {"inputs": ["4\naa\nabcd\nccc\nabcc"], "outputs": ["5\n10\n14\n12"]}

raw_problem:
I. Fake News (hard)

time limit per test
5 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Now that you have proposed a fake post for the HC2 Facebook page, Heidi wants to measure the quality of the post before actually posting it. She recently came across a (possibly fake) article about the impact of fractal structure on multimedia messages and she is now trying to measure the self-similarity of the message, which is defined as

where the sum is over all nonempty strings p and  is the number of occurences of p in s as a substring. (Note that the sum is infinite, but it only has a finite number of nonzero summands.)

Heidi refuses to do anything else until she knows how to calculate this self-similarity. Could you please help her? (If you would like to instead convince Heidi that a finite string cannot be a fractal anyway – do not bother, we have already tried.)

Input

The input starts with a line indicating the number of test cases T (1 ≤ T ≤ 10). After that, T test cases follow, each of which consists of one line containing a string s (1 ≤ |s| ≤ 100 000) composed of lowercase letters (a-z).

Output

Output T lines, every line containing one number – the answer to the corresponding test case.

Example

Input

4
aa
abcd
ccc
abcc

Output

5
10
14
12

Note

A string s contains another string p as a substring if p is a contiguous subsequence of s. For example, ab is a substring of cab but not of acb.

image_tags: Math Math

data_split: test