f와 g

\uC815\uC218 $N$\uAC1C $a_1, a_2, \dots, a_N$\uC774 \uC8FC\uC5B4\uC9C4\uB2E4. \uD568\uC218 $f$\uC640 $g$\uB97C \uB2E4\uC74C\uACFC \uAC19\uC774 \uC815\uC758\uD55C\uB2E4.

[f(x,k) = (x + a_1)^k + (x + a_2)^k + \cdots + (x + a_N)^k]

[g(t,k) = f(0,k) + f(1,k) + \cdots + f(t,k)]

\uC815\uC218 $T$, $K$\uC640 \uC218\uC5F4 $a_1, a_2, \dots, a_N$\uC774 \uC8FC\uC5B4\uC9C8 \uB54C, \uBAA8\uB4E0 \uC815\uC218 $i$\uC5D0 \uB300\uD574 $g(T,i)$\uB97C $10^9+7$\uB85C \uB098\uB208 \uB098\uBA38\uC9C0\uB97C \uAD6C\uD558\uB77C. \uC5EC\uAE30\uC11C $0 \le i \le K$\uC774\uB2E4.

\uCCAB\uC9F8 \uC904\uC5D0 \uC815\uC218 $N$, $K$, $T$\uAC00 \uC8FC\uC5B4\uC9C4\uB2E4.

\uB458\uC9F8 \uC904\uC5D0 \uC815\uC218 $a_1, a_2, \dots, a_N$\uC774 \uC8FC\uC5B4\uC9C4\uB2E4.

$g(T,0), g(T,1), \dots, g(T,K)$\uB97C $10^9+7$\uB85C \uB098\uB208 \uB098\uBA38\uC9C0\uB97C \uACF5\uBC31 \uD55C \uCE78\uC73C\uB85C \uAD6C\uBD84\uD574 \uCD9C\uB825\uD55C\uB2E4.

• $1 \le N \le 10^5$
• $1 \le K \le 5 \cdot 10^4$
• $1 \le T \le 10^{18}$
• $0 \le a_i < 10^9 + 7$