How on earth can the length of palindrome "ee" be 1 ??? Sorry, but it's true, I vote for calling this rubbish.

import java.io.; import java.util.;

class Result {

private static final int MOD = 1000000007;
private static int[][] prefixFreq;
private static long[] fact;
private static long[] invFact;

public static void initialize(String s) {
    int n = s.length();
    prefixFreq = new int[n + 1][26];

    for (int i = 0; i < n; i++) {
        System.arraycopy(prefixFreq[i], 0, prefixFreq[i + 1], 0, 26);
        prefixFreq[i + 1][s.charAt(i) - 'a']++;
    }

    fact = new long[n + 1];
    invFact = new long[n + 1];
    fact[0] = invFact[0] = 1;

    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    invFact[n] = modInverse(fact[n]);
    for (int i = n - 1; i >= 1; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

public static int answerQuery(int l, int r) {
    int[] freq = new int[26];
    for (int i = 0; i < 26; i++) {
        freq[i] = prefixFreq[r][i] - prefixFreq[l - 1][i];
    }

    int pairs = 0;
    int oddCount = 0;
    int[] halfFreq = new int[26];

    for (int i = 0; i < 26; i++) {
        halfFreq[i] = freq[i] / 2;
        pairs += halfFreq[i];
        if (freq[i] % 2 == 1) {
            oddCount++;
        }
    }

    long numerator = fact[pairs];
    long denominator = 1;
    for (int i = 0; i < 26; i++) {
        if (halfFreq[i] > 0) {
            denominator = (denominator * invFact[halfFreq[i]]) % MOD;
        }
    }

    long result = (numerator * denominator) % MOD;
    result = (result * Math.max(1, oddCount)) % MOD;

    return (int) result;
}

private static long modInverse(long x) {
    return modPow(x, MOD - 2);
}

private static long modPow(long base, long exp) {
    long result = 1;
    base %= MOD;
    while (exp > 0) {
        if ((exp & 1) == 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

}

public class Solution { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    String s = bufferedReader.readLine();
    Result.initialize(s);

    int q = Integer.parseInt(bufferedReader.readLine().trim());

    for (int qItr = 0; qItr < q; qItr++) {
        String[] input = bufferedReader.readLine().trim().split(" ");
        int l = Integer.parseInt(input[0]);
        int r = Integer.parseInt(input[1]);

        int result = Result.answerQuery(l, r);
        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();
    }

    bufferedReader.close();
    bufferedWriter.close();
}

}

the part I don't like Hackerrank is that some problem is like a min math-oplymiad – in case you don't know the math concept/formula behind you cannot get the solution right even if you got the right idea/thought about how to solve.

For example, this problem comes down to count how many permutations are there for the left half of palindrome (and then times that by number of odd chars) – and the answer is the multinomial (n, k).

Anyway I got the code right, but cannot think of why it still got "time exceeded" – the multinomial calculation should be minimal, I'm not using factor(n) at atll. would appreciate if some big-shot in math can point out how to further improve

n res //= i n -= 1 return res

This is rubbish problem. In C++, we can use long double which is 128-bit on a 64-bit processor/OS. If I modulo everywhere, the result ends up smaller than expected. If I modulo only at the end, it ends up bigger than expected. And why does this test case have a smaller count?

"cstniwwvbkyrxzvjpegpgtwwxkdujwbmsqrmkurdprzfftazyonxmawydyjgmipyassxnafluvaouoiuxrqrbrjmzisptfhqqaxq", 5, 100

compared to:

"cstniwwvbkyrxzvjpegpgtwwxkdujwbmsqrmkurdprzfftazyonxmawydyjgmipyassxnafluvaouoiuxrqrbrjmzisptfhqqaxq", 20, 82