To Good Arrays

Problem Overview

• Count arrays A of length N with exactly K indices where A[i] * A[i+1] = M; return the count modulo 1e9+7.
• Input: integers N, M, K. Output: number of such arrays. Constraints: 2≤N≤1e9, 3≤M≤1e9, 0≤K≤min(50, N−1).
• Array counting/combinatorics problem with an adjacency product condition.
• From Microsoft interviews, this coding interview problem is a common interview question on counting under constraints.