累積和を用いて区間和を高速に求めることができるのと同様に、累積積を用いることで区間積を高速に求めることができます。

\(A\) の index を 0 から始まるようにずらします。 \((A_0,\ldots,A_{N-1})\) の累積積 \(P\) を

\(P_i=\begin{cases} 1 & (i=0)\\ P_{i-1}\times A_{i-1} &(i>0) \end{cases}\)

と定めます。 \(P_i\) は \(A\) の先頭 \(i\) 項の積になります。

このとき \(A_i\times\dots\times A_{i+K-1} = \frac{P_{i+K}}{P_i}\) となるので、これは \(O(\log\mathrm{MOD})\) で計算することができます。（制約の条件下では \(P_i\not\equiv 0 \bmod 10^9+7\) が成り立つことに注意してください）

よって各 \(i\) について \(\frac{P_{i+K}}{P_i}\) を実際に計算して和を取ることで、この問題を \(O(N\log\mathrm{MOD})\) で解くことができます。

実装例 (C++)

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using modint = atcoder::modint1000000007;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int>a(n);
  for(int i=0; i<n; i++) cin >> a[i];
  vector<modint>p(n+1);
  p[0]=1;
  for(int i=0; i<n; i++){
    p[i+1] = p[i] * a[i];
  }

  modint ans = 0;
  for(int i=0; i<n-k+1; i++){
    ans += p[i+k] / p[i];
  }
  cout << ans.val() << endl;
}

実装例 (Python)

MOD = 10**9 + 7
N, K = map(int, input().split())
A = list(map(int, input().split()))
P = [1]
for a in A:
  P.append(P[-1] * a % MOD)

ans = 0
for i in range(N-K+1):
  ans += P[i+K] * pow(P[i], -1, MOD) % MOD

print(ans % MOD)