题目背景

Problem	Score	Idea	Std	Data	Check	Solution
\(\text{C - Creating a Queue}\)	\(400\)	joe_zxq	fanchuanyu & joe_zxq	joe_zxq	remmymilkyway	Link by joe_zxq

题目描述

给定一个长度为 \(N\) 的非负整数序列 \(A\)。

现在你需要用 \(1\sim M\) 之间的正整数替换所有序列 \(A\) 中的 \(0\)，使得对于其中的任何一段长度大于等于 \(2\) 的子数组，不能存在唯一众数。

子数组：在一个数组中，选择一些连续的元素组成的新数组。

唯一众数：众数指的是一个数字序列中出现次数最多的元素。如果一个数字序列众数只有一个，我们称这个序列有唯一众数。

求有多少种不同方案，答案对 \(1145141923\) 取模。两种方案称为不同，当且仅当替换后的序列至少有一位上的数不同。

输入格式

第一行包含两个正整数 \(N\) 和 \(M\)，表示序列的长度和替换数的最大限度。

第二行包含 \(N\) 个非负整数，表示序列 \(A\) 的元素。

输出格式

一行一个非负整数，表示方案的数量，答案对 \(1145141923\) 取模。

输入输出样例 #1

输入 #1

2 3
1 0

输出 #1

2

输入输出样例 #2

输入 #2

4 1046
114 514 191 981

输出 #2

1

说明/提示

样例解释 #1

有 \(2\) 个满足条件的序列，分别为 \(\{1,2\}\) 和 \(\{1,3\}\)。

样例解释 #2

序列已经完全固定，本身就是一种合法的序列，于是答案为 \(1\)。

数据范围

对于 \(100\%\) 的数据，保证 \(1 \le N \le 10^6\)，\(1 \le M \le 10^9\)，\(0 \le A_i \le M\)。