取模啥的就小费马搞一搞即可，最终复杂度$\Theta(n \log n)$
```cpp
inline LL expow(LL A, LL B){
LL res = 1 ;
while (B){
if (B & 1) (res *= A) %= Mod ;
B >>= 1, (A *= A) %= Mod ;
}
return res % Mod ;
}
inline LL get_symbol(LL x){ return (!x ? 1 : Mod - 1) ; }
int main(){
cin >> N ; Fac[0] = qwq = 1 ;
for (i = 0 ; i <= N ; ++ i)
scanf("%lld", &base[i]), (Fac[i + 1] = Fac[i] * (i + 1)) %= Mod ;
cin >> T ; Ans = 0 ;
if (T <= N) return printf("%lld\n", base[T]) ;
for (i = 0 ; i <= N ; ++ i) (qwq *= (T - i + Mod)) %= Mod ;
for (i = 0 ; i <= N ; ++ i){
M = (N - i) & 1, _qwq = qwq * expow((T - i), Mod - 2) % Mod ;
t = expow(Fac[i] * Fac[N - i] % Mod, Mod - 2) % Mod ;
t = t * (get_symbol(M) * _qwq % Mod) % Mod, t = (t * base[i]) % Mod ;
(Ans += t) %= Mod ;
// cout << Ans << endl ;
}
printf("%lld\n", Ans) ; return 0 ;
}
```