把可能的$a_i$记作$x$，$a_i$的和记作$Sum$

记状态$dp_{i,j}$为前$i$个数，选的和$modk$为$j$的方案数，外面还要再枚举一个不知道是$Sum$还是$x$。

采用矩阵加速

如何做到 $k^3logn$

矩阵复杂度$k^3$枚举$k$快速幂$logn$

不应该是$k^4logn$吗

如何做到$k^3logn$