pffffffFFT ! I would think this should be classified as advanced if not expert in order to be consistent with other expert level problems requiring similar techniques.

It seems the crux of the problem is calculating .

Letting there is the relation and hence the problem yields to dynamic programming where a buffer can be used to update . However it seems that even this is not fast enough so I think there is another trick that is missing. Any hints?

Tricks I already used

• raising to a power by breaking up the exponent into powers of 2 and repeated squaring
• for prime

X, A and m：
x_1 + x_2 + .. + x_m = X
a_1 + a_2 + .. + a_m = A
For a given (a_1, a_2, .. a_m), to maximize x_1^a_1 * x_2^a_2 * ... * x_m^a_m, which is Qm(X, (a_1, a_2, .. a_m)).

Question:
When trying to find Qm(X, (a_1, a_2, .. a_m)), is there an existing formula to get Qm(X, (a_1, a_2, .. a_m)), or we need to calculate x_1^a_1 * x_2^a_2 * ... * x_m^a_m for all (x_1, x_2, .. x_m) combinations?

I am stuck at 38/100. Two tests keep timing out. The unsuccessful test cases switch around between "wrong answer" and "runtime error", depending on my various attempts to optimize.

My correct test cases seem to finish fast (around 0.2s), while the wrong ones seem slower (around 7s). This could point to some error when the calculations involve more steps.

I am starting to suspect that the recognition of runtime errors is not working correctly. So the wrong answers might be actually resource exhaustions.

Some results for comparison:

X A m -> sum Q (mod 10^9+7)
6 4 2 -> 375000357
6 5 2 -> 214721813
6 6 2 -> 9027
7 5 3 -> 886720700
7 6 3 -> 834194410
7 7 3 -> 19002

What is the significance of X?