problem
一个长为 \(n\) 的序列，每一个数是 \([0,k)\) 的整数。说一个数列幸运，当且尽当 \(\exists i\) 使得 \(a_i\equiv(\sum_j a_j)-a_i\pmod k\)，求方案数，\(n\leq 10^{18},k\leq 2000\)。
引理：若钦定数列的和为 \(s\) ，则方案数为 \(k^{n-1}\)，注意 \(n=0\) 特判。
引理：\(\sum_j a_j\equiv 2 a_i\pmod k\)
solution when \(k\) is odd
这时 \(i\to 2i\) 形成一个双射。设和为 \(2i\) 则我们需要有 \(i\) 这个数在里面。
\[\sum_{i=0}\binom{n}{i}(-1)^i k^{n-i-1}
\]
注意致命边界，应为
\[\frac{1}{k}\sum_{i=0}^{n}\binom{n}{i}(-1)^i k^{n-i}-\frac{(-1)^n}{k}+(-1)^n
\]
\[=\frac{(k-1)^n}{k}-\frac{(-1)^n}{k}+(-1)^n
\]