已知$n,d$,它们2个同阶,求 $\sum_{k=0}^{d-1}(1+\omega_d^k)^n$ 的值,模一个素数p,如果你想的话可以是NTT模数,我想找一个$O(\sqrt n)$(或更好)的算法,目前已有$O(\sqrt n\log^2(n))$的方法,做了好几天了qwq