斯特林数简单题。
\[\sum_S{f(S)^k}\\=\sum_S{\sum_{i=1}^k{k \brace i}{\binom{f(S)}{i}}}i!\\=\sum_{i=1}^k{k \brace i}i!\sum_S{\binom{f(S)}{i}}
\]
考虑第二层求和的组合意义：
选取一个选球方案，再从其中标号为奇数的球中取出 \(i\) 个。
也就等价于先钦定选 \(i\) 个标号为奇数的球，剩下的随便选的方案数。
\[\sum_S{\binom{f(S)}{i}}=\binom{n}{i}\lceil\frac{m}{2}\rceil^im^{n-i}
\]
带入计算即可，单次查询时间复杂度 \(\mathcal O(k)\)。