#include <iostream>
#include <vector>
using namespace std;
const int MOD = 376544743;
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> first_row(m), last_row(m);
    for (int i = 0; i < m; ++i) {
        cin >> first_row[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> last_row[i];
    }
    if (n == 1) {
        bool valid = true;
        for (int i = 0; i < m; ++i) {
            if (first_row[i] != last_row[i]) {
                valid = false;
                break;
            }
        }
        cout << (valid ? 1 : 0) << endl;
        return 0;
    }
    vector<vector<vector<long long>>> dp(m, vector<vector<long long>>(k, vector<long long>(k, 0)));
    for (int i = 0; i < m - 1; ++i) {
        if (first_row[i] != first_row[i + 1]) {
            dp[i][first_row[i]][first_row[i + 1]] = 1;
        }
    }
    for (int row = 1; row < n - 1; ++row) {
        vector<vector<vector<long long>>> new_dp(m, vector<vector<long long>>(k, vector<long long>(k, 0)));
        for (int i = 0; i < m; ++i) {
            for (int c1 = 0; c1 < k; ++c1) {
                for (int c2 = 0; c2 < k; ++c2) {
                    if (dp[i][c1][c2] > 0) {
                        for (int new_c1 = 0; new_c1 < k; ++new_c1) {
                            if (new_c1 != c1) {
                                for (int new_c2 = 0; new_c2 < k; ++new_c2) {
                                    if (new_c2 != c2 && new_c2 != new_c1) {
                                        new_dp[i][new_c1][new_c2] = (new_dp[i][new_c1][new_c2] + dp[i][c1][c2]) % MOD;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        dp = new_dp;
    }
    long long result = 0;
    for (int i = 0; i < m - 1; ++i) {
        for (int c1 = 0; c1 < k; ++c1) {
            if (c1 == last_row[i]) continue;
            for (int c2 = 0; c2 < k; ++c2) {
                if (c2 == last_row[i + 1]) continue;
                result = (result + dp[i][c1][c2]) % MOD;
            }
        }
    }
    cout << result << endl;
    return 0;
}