Count Fillings with Adjacent Difference at Most 1

Problem Given an array arr of length n in which some positions hold 0 (a blank) and the rest hold fixed positive values, fill every blank with an integer from [1, M] such that every adjacent pair satisfies |arr[i] - arr[i+1]| <= 1. Count how many complete valid arrays exist, modulo a given value.

Input / Output

• Input: array arr of length n with zeros marking blanks, an upper bound M, and a modulus.
• Output: the number of valid fillings, taken modulo the given value.

Constraints

• n and M up to ~10^5, so an O(n·M^2) transition that pairs every previous value with every next value is too slow; O(n·M) is the target.
• Fill values come from [1, M]; fixed non-zero entries must be left untouched.
• Two fixed neighbours may already violate the adjacency rule, in which case the answer is 0.

Example

• arr = [1, 0, 3], M = 3 → 0: the blank would have to be within 1 of both 1 and 3, and no such value exists.
• arr = [0, 0], M = 2 → 4: (1,1), (1,2), (2,1) and (2,2) all satisfy |diff| <= 1.
• arr = [2, 0, 2], M = 3 → 3: the blank can be 1, 2 or 3.