No.033 D

$T \leq N$ ならば $P(T)$ をそのまま出力する.

$T \gt N$ ならばラグランジュ補間を使う.

ラグランジュ補間の式は

$$P(T) = \sum_{j=0}^N \left( P(j) \prod_{i \neq j}\frac{T-i}{j-i} \right)$$

であり, 加減乗除のみであるので $10^9+7$ を法とする剰余環上で計算すればいい.

しかし, 愚直に計算すると $O(N^2)$ なので TLE するので, 高速化が必要である.

まずは $\prod$ の分子だが,

$$\prod_{i \neq j} (T-i) = \frac{T(T-1) \cdots (T-N)}{T-j}$$

であるので, $T(T-1) \cdots (T-N)$ をあらかじめ計算しておけば間に合う.

分母は,

$$\prod_{i \neq j} (j-i) = j(j-1) \cdots 1 \times (-1)(-2) \cdots (j-N) = j!(N-j)!(-1)^{N-j}$$

となるので, 階乗を計算しておけば間に合う.