思路与算法

先枚举一行的三色方案，保留相邻列颜色不同的行状态。M列共有S=3*2^(M-1)个合法状态，M≤5时S≤48。两行兼容，当且仅当每一列的颜色都不同，因为其它更早行不会再影响未来。

设g_t[s]为高度t+1、最后一行固定为s的自由条带数量。初始g_0[s]=1，转移为对所有与s兼容的上一行p累加g_(t-1)[p]，全程模10^6。只需滚动数组。

设给定第K行为状态f。上半部分含固定行有g_(K-1)[f]种；由于行兼容关系对称，把下半部分上下反转，其数量为g_(N-K)[f]。两部分只共享已经确定的一行，最终答案是这两个数量的乘积。一次滚动计算中记录所需的两个长度即可。若给定行自身存在水平同色，立即输出0。

正确性说明

一行内部的冲突已由合法状态筛掉，两行之间的冲突只可能是同列同色，所以兼容关系准确描述全部新增限制。固定末行s后，按倒数第二行p分类，各类互不重叠且覆盖所有条带，因此g的递推和初始值正确。

固定第K行后，上下两部分的待选择格子互不相交，也没有跨越固定行的额外相邻关系。下半部分反转不改变相邻异色条件，因而可使用同一条带统计。任意一对合法上下方案唯一拼成完整方案，任意完整方案也唯一拆成这一对，故数量相乘正确。

复杂度

枚举三进制行及检查水平限制O(3^MM)，预处理兼容关系O(S^2M)，初始化滚动数组O(S)。滚动至多N-1次，每次O(S^2)。总时间O(3^MM+S^2M+NS^2)，空间O(SM+S^2)，包含行状态、兼容表和滚动数组。

易错点

本题是三色果酱计数，颜色1、2、3彼此有区别，不能套用炮兵或二值占用限制。给定行不能修改，若它已水平冲突就没有解。K=1或K=N时，对应一侧只有固定行，数量为1；N=1且给定行合法时答案也为1。乘积使用long long后取模10^6。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> fixed(m);
    bool valid = true;
    for (int j = 0; j < m; ++j) {
        cin >> fixed[j];
        --fixed[j];
        if (j && fixed[j] == fixed[j - 1])
            valid = false;
    }
    if (!valid) {
        cout << 0 << '\n';
        return 0;
    }
    int all = 1;
    for (int j = 0; j < m; ++j)
        all *= 3;
    vector<vector<int>> state;
    int target = -1;
    for (int s = 0; s < all; ++s) {
        vector<int> color(m);
        int x = s;
        bool okay = true;
        for (int j = 0; j < m; ++j) {
            color[j] = x % 3;
            x /= 3;
            if (j && color[j] == color[j - 1])
                okay = false;
        }
        if (okay) {
            if (color == fixed)
                target = state.size();
            state.push_back(color);
        }
    }
    int S = state.size();
    vector<vector<int>> previous(S);
    for (int a = 0; a < S; ++a)
        for (int b = 0; b < S; ++b) {
            bool okay = true;
            for (int j = 0; j < m; ++j)
                if (state[a][j] == state[b][j])
                    okay = false;
            if (okay)
                previous[a].push_back(b);
        }
    vector<int> dp(S, 1), next(S);
    long long left = k == 1 ? 1 : 0, right = k == n ? 1 : 0;
    for (int length = 1; length < n; ++length) {
        for (int a = 0; a < S; ++a) {
            int sum = 0;
            for (int b : previous[a])
                sum += dp[b];
            next[a] = sum % MOD;
        }
        dp.swap(next);
        if (length == k - 1)
            left = dp[target];
        if (length == n - k)
            right = dp[target];
    }
    cout << left * right % MOD << '\n';
}