Fill Array Zeros to Satisfy Adjacent Difference at Most 1 (Count Ways)

Problem: Given an array arr of length n with some elements equal to 0, fill those zero positions with positive integers from [1, M] such that for every adjacent pair, |arr[i] - arr[i+1]| <= 1. Count the number of valid full arrays (modulo some value, typically).

Constraints: Array length n, fill values bounded by M.

Approach: This is a counting-DP problem: process the array left to right, tracking dp[i][v] = number of ways to validly fill positions 1..i such that position i has value v (only tracking possible v's, which is bounded since each step can only change the running value by at most 1 from the previous). Fixed (non-zero) positions constrain v directly; zero positions allow v to range over [1, M] subject to the adjacent-difference-<=1 rule from the previous position. Sum dp[n][*] for the final answer, using prefix-sum tricks over v to keep each transition O(1) amortized instead of O(M) per position.