題目傳送門

題目背景

有一個奇奇怪怪的火車站，奇奇怪怪的站長JTZ想要解決一個奇奇怪怪的問題，

題目描述

現在有 N N N 列火車要進出站，對于同一列車進站和出站有且只有一次鳴笛，笛聲有 1 ? M 1-M 1?M 種音調，要求相鄰的兩次鳴笛之間音調的差的絕對值不能小于 K K K （不鳴笛笛聲音調看作 1 e 100 1e100 1e100 ），不然耳朵不好的車站管理員XYH分不清楚是哪一列車，現在XYH給出了每一列火車的進出，JTZ想知道總共有多少種鳴笛的方案，而他又不想太麻煩，所以只需要方案數除以 43621789 43621789 43621789 的余數，
某中學八年級大佬RSJ知道了這個訊息后，覺得太簡單了，幾下算出了結果 x x x （取余數后），于是他想讓你算出 M x m o d ?? 43621789 M^x \mod 43621789 Mxmod43621789 ，

輸入格式

第一行三個整數 N , M , K N,M,K N,M,K ，
第二行有 2 N 2N 2N 個整數，每個整數是 0 0 0 或 1 1 1 代表車進站和出站，保證資料合法，也就是說當車站沒有車的時候沒有車出站，最后車站沒有車，

輸出格式

一行，表示答案，( M x m o d ?? 43621789 M^x \mod 43621789 Mxmod43621789 )

輸入輸出樣例

輸入#1

2 1 0
0 0 1 1

輸出#1

1

輸入#2

3 5 2
0 0 0 1 1 1

輸出#2

40308287

提示/說明

圖非常重要

樣例解釋：

樣例1： x = 4 , M = 1 x=4,M=1 x=4,M=1 答案為 1 4 m o d ?? 43621789 = 1 1^4 \mod 43621789=1 14mod43621789=1
樣例2： x = 250 , M = 5 x=250,M=5 x=250,M=5 答案為 5 250 m o d ?? 43621789 = 40308287 5^{250} \mod 43621789=40308287 5250mod43621789=40308287

資料范圍

本題采用 Subtask
Subtask 1 \text{Subtask}\ 1 Subtask 1: 測驗點 1 ? 5 1-5 1?5 30 % 30\% 30% N ≤ 3 , M ≤ 7 N\le 3,M\le 7 N≤3,M≤7
Subtask 2 \text{Subtask}\ 2 Subtask 2: 測驗點 6 ? 12 6-12 6?12 40 % 40\% 40% N ≤ 100 ， M ≤ 7 N\le 100，M\le 7 N≤100，M≤7
Subtask 3 \text{Subtask}\ 3 Subtask 3: 測驗點 13 ? 20 13-20 13?20 40 % 40\% 40% N ≤ 500 , M ≤ 7 N\le 500,M\le 7 N≤500,M≤7
你只有通過每個 Subtask \text{Subtask} Subtask 的所有測驗點才能獲得該 Subtask \text{Subtask} Subtask 的分值，

題目決議

這道題目的出題靈感來自于CF149D，我們只要把火車進站看成左括號，火車出站看成右括號，其實應該是堆疊，
排列與組合是行不通的，因為對于同一列車進站和出站有且只有一次鳴笛，由于沒有要求輸出步驟，又可以搜索，考慮DP，無疑是區間DP，因為對于鳴笛的音調會影響到其他的方案數量，那么需要將左右側的鳴笛音調列入方程轉移式，
令函式 f ( i , j , x , y ) f(i,j,x,y) f(i,j,x,y) 為區間 [ i , j ] [i,j] [i,j] 中，左右端點中，左端點的鳴笛音調為 x x x ，右端點的鳴笛音調為 y y y 的種數，不鳴笛記為 0 0 0 ，分兩種情況考慮，
我們需要預處理出輛火車的進出站，存在陣列里，要求能 Θ ( 1 ) \Theta (1) Θ(1) 查詢，
情況一：第 i i i j j j 次進出站時相同的車，
那么我們需要列舉 i , j i,j i,j 的音調以及相鄰的 i + 1 , j ? 1 i+1,j-1 i+1,j?1 的音調，并且要保證資料合法，
f ( i , j , x , y ) = ∑ f ( i + 1 , j ? 1 , a , b ) f(i,j,x,y)=\sum f(i+1,j-1,a,b) f(i,j,x,y)=∑f(i+1,j?1,a,b)
其中 ∣ a ? x ∣ ≥ k |a-x|\geq k ∣a?x∣≥k 或者 x = 0 , a =? 0 x=0,a\not=0 x=0,a?=0 或者 x =? 0 , a = 0 x\not=0,a=0 x?=0,a=0
并且 ∣ b ? y ∣ ≥ k |b-y|\geq k ∣b?y∣≥k 或者 b = 0 , y =? 0 b=0,y\not=0 b=0,y?=0 或者 b =? 0 , y = 0 b\not=0,y=0 b?=0,y=0
并且 x = 0 , y =? 0 x=0,y\not=0 x=0,y?=0 或者 x =? 0 , y =? 0 x\not= 0,y\not= 0 x?=0,y?=0

情況二：第 i i i j j j 次進出站時不是相同的車，
設第 i i i 輛車的出站為 m i d mid mid ，那么就可以將區間 [ i , j ] [i,j] [i,j] 分割成區間 [ i , m i d ] , [ m i d + 1 , j ] [i,mid],[mid+1,j] [i,mid],[mid+1,j] ，然后列舉四個端點音調的即可，也要保證資料合法，
f ( i , j , x , y ) = ∑ f ( i , m i d , x , a ) × f ( m i d + 1 , b , y ) f(i,j,x,y)=\sum f(i,mid,x,a)\times f(mid+1,b,y) f(i,j,x,y)=∑f(i,mid,x,a)×f(mid+1,b,y)
其中 ∣ a ? b ∣ ≥ x |a-b|\geq x ∣a?b∣≥x 或者 a = 0 , b =? 0 a=0,b\not=0 a=0,b?=0 或者 a =? 0 , b = 0 a\not= 0,b=0 a?=0,b=0
并且 x = 0 , a =? 0 x=0,a\not=0 x=0,a?=0 且 x =? 0 , a = 0 x\not= 0,a=0 x?=0,a=0 （因為 x , a x,a x,a 同一輛車）

最后注意一些細節就可以了，
演算法復雜度是 Θ ( N 2 M 4 + N ) \Theta \left( N^2M^4+N\right) Θ(N2M4+N) 的，雖然可以優化成 Θ ( N 2 M 3 + N ) \Theta \left( N^2M^3+N\right) Θ(N2M3+N) 但是因為我懶所以我就不寫了，

最后記得輸出 M x m o d ?? 43621789 M^x \mod 43621789 Mxmod43621789 ，記得加上快速冪和 long long，