\(0 \le i \lt M\) について「\(i\) から開始して \(2^d\) 回関数を作用させたときに、経由した値の総和と最終的な値は何になるか」はダブリングを用いて計算可能です。したがって繰り返し二乗法による累乗の計算などと同様の管理を行うことでこの問題を解くことができます。