对上界容斥得到答案：

$$ \sum_{S\subseteq \{1,2,\dots,m\}}(-1)^{|S|}\binom{n-1-\sum_{i\in S}(b^i-c+1)+m}{m} $$

枚举 $|S|=i$，此时要求 $\sum_{i\in S}b^i\le n+m-1+i(c-1)=N_i$。枚举 $b$ 进制下 $\sum_{i\in S}b^i$ 第一个小于 $N_i$ 的位置，剩下的低位随便填 $0/1$。从高位到低位考虑，记录选的位置之和 $s$ 和选了多少个。设低位选了的集合为 $T$，要求一个形如 $\sum_{T} \binom{C-\sum_{j\in T} (b^i-c+1)}{m}$ 的式子。

把 $\binom{C-x}{m}$ 展开为 $m$ 次多项式 $\sum_{i=0}^m p_ix^i$。

$$ \sum_{T}\binom{C-\sum_{j\in T} (b^j-c+1)}{m}=\sum_{T}\sum_{k=0}^m p_k \left(\sum_{j\in T} (b^j-c+1)\right)^k=\sum_{k=0}^m p_k\sum_T\left(\sum_{j\in T} (b^j-c+1)\right)^k $$

设 $f_{i,j,k}$ 表示低 $i$ 位，选了 $j$ 个，和的 $k$ 次幂之和。转移用二项式定理合并即可。

预处理 $f$ 的时间复杂度为 $O(m^4)$。枚举 $|S|,lcp$ 复杂度为 $O(m^2)$，展开多项式复杂度为 $O(m^2)$，这一部分复杂度也为 $O(m^4)$。总复杂度为 $O(m^4)$。

也可以记录所有方案中前后缀选的和的 $k$ 次幂之和 $s_k$，这样 $C=n+m-1$，只需要合并前后缀，不过合并前后缀也是 $O(m^2)$ 的。

两种做法都可以用 NTT 优化到 $O(m^3\log m)$。