暗証番号が \(1, 2, \ldots, N\) のいずれかからなる \(M\) 文字の文字列だったときに答えを求める方法を紹介します。（ \(N \leq 10^5, M \leq 10^9\) ）

与えられた文字について、oの数を \(T\) 、? の数を \(U\) としましょう。

このとき、fpsで立式すると、答えは

\(\displaystyle M! [x^M] \Big(\frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots \Big)^T \Big(\frac{x^0}{0!} + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \ldots \Big)^U\)

\(= M![x^M] (e^x - 1)^T (e^x)^U\)

\(\displaystyle = M! [x^M] \Big( \sum_{k = 0}^T \binom{T}{k} e^{kx} (-1)^{T-k} \Big) e^{Ux}\)

\(\displaystyle = M![x^M] \sum_{k = 0}^T \binom{T}{k} (-1)^{T-k} e^{(k+U)x}\)

\(\displaystyle = M! \sum_{k = 0}^T \binom{T}{k} (-1)^{T-k} \frac{(k+U)^M}{M!}\)

\(\displaystyle = \sum_{k = 0}^T \binom{T}{k} (-1)^{T-k} (k+U)^M\)

となります。

この式に従えば、階乗・階乗逆元を \(O(N)\) で前計算し、\((k+U)^M\) を繰り返し二乗法で求めることで、答えを \(O(N \log M)\) で計算することができます。

実装例：https://atcoder.jp/contests/abc201/submissions/72248006