No Unique Mode Replacement

You are given a non‐negative integer sequence \(A\) of length \(N\). Some elements of \(A\) may be zero. You need to replace every zero with an integer from \(1\) to \(M\) such that for every contiguous subarray of length at least \(2\) the array does not have a unique mode.

A contiguous subarray is a sequence of consecutive elements in \(A\). The mode of a sequence is the value that occurs most frequently. A sequence is said to have a unique mode if exactly one number achieves the highest frequency. In other words, for every contiguous subarray \(B\) with \( |B|\ge2 \), if \(f(x)\) denotes the frequency of \(x\) in \(B\), then there must be at least two different numbers \(x\) and \(y\) satisfying \[ f(x)=f(y)=\max_{z} f(z). \]

It can be proven that when \(N\ge2\) a valid replacement exists if and only if in the final sequence every two elements are distinct (so that every subarray has all distinct elements and every frequency is \(1\)).

Two replacement schemes are considered different if the final arrays differ in at least one position. Since the answer can be large, output it modulo \(1145141923\).

inputFormat

The first line contains two integers \(N\) and \(M\) (with \(1\le N\le\text{large}\) and \(1\le M\le\text{large}\)).

The second line contains \(N\) non-negative integers \(A_1, A_2, \dots, A_N\). Nonzero elements are fixed; zeros can be replaced by any integer between \(1\) and \(M\).

outputFormat

Output a single integer, the number of valid replacement schemes modulo \(1145141923\).

sample

1 5
0

5