If this is the intended solution then I really think the time limit is unfair. I had the exact same solution but mine was taking around 6 seconds for n=2\cdot 10^6. Also, n\log^2n for n = 2\cdot 10^6 is around 8.8\cdot 10^8.
Plus the n \log n in that is from NTT/FFT which has a high constant.
Plus there is an additional n \log k for actually calculating the polynomial you want to exponentiate. I even used a faster way to exponentiate ( as discussed here ) but still TLE.
If anyone got AC using NTT/FFT then I’m definitely stealing your code. 