munte2

// Andrei Constantinescu, ETH Zurich
// Linear
#include <algorithm>
#include <bits/stdc++.h>

// 6:03
using namespace std;

const int MOD = 111181111;

namespace gabi {
int CountLinear(const vector<int> &v) {
    const int n = v.size();
    vector<pair<int, int>> pairs((n + 1) / 2 + 1);
    for (int i = 1; i <= n; i++) {
        if (i > (n + 1) / 2) {
            pairs[n / 2 + 1 - (i - (n + 1) / 2)].second = v[i - 1];
        } else {
            pairs[i].first = v[i - 1];
        }
    }
    for (int i = 1; i <= n / 2; i++) {
        if (pairs[i].first > pairs[i].second) {
            swap(pairs[i].first, pairs[i].second);
        }
    }
    sort(pairs.begin() + 1, pairs.begin() + 1 + n / 2);
    int ans = 2;
    for (int i = 2; i <= n / 2; i++) {
        if (pairs[i].first > pairs[i - 1].second) {
            ans = (ans * 2) % MOD;
        }
    }
    return ans;
}
} // namespace gabi

bool IsMountain(const vector<int> &v) {
    if (v[0] == v.size() || v.back() == v.size())
        return false;
    bool have_more = false;
    for (int i = 0; i + 1 < v.size(); ++i) {
        if (v[i] < v[i + 1]) {
            if (have_more)
                return false;
        } else {
            have_more = true;
        }
    }
    return true;
}

// 4: 0 1 2 3
// 5: 0 1 2 3 4
int CountBack(const vector<int> &v) {
    const int N = v.size() / 2;
    vector<int> perm(N);
    int ans = 0;
    iota(perm.begin(), perm.end(), 0);
    do {
        vector<int> t(v.size(), -1);
        for (int i = 0; i < N; ++i) {
            t[i] = v[perm[i]];
            t[v.size() - 1 - i] = v[v.size() - 1 - perm[i]];
        }
        if (v.size() % 2 == 1) {
            t[N] = v[N];
        }
        for (int mask = 0; mask < (1 << N); ++mask) {
            vector<int> t_copy(t);
            for (int i = 0; i < N; ++i) {
                if (mask & (1 << i)) {
                    swap(t_copy[i], t_copy[v.size() - 1 - i]);
                }
            }
            ans += IsMountain(t_copy);
        }
    } while (next_permutation(perm.begin(), perm.end()));
    return ans;
}

int CountLinear(const vector<int> &v) {
    assert(v.size() >= 3);
    const int N = v.size() / 2;
    vector<pair<int, int>> intervs(N);
    for (int i = 0; i < N; ++i) {
        const int a = v[i], b = v[v.size() - 1 - i];
        if (a < b) {
            intervs[i] = {a, b};
        } else {
            intervs[i] = {b, a};
        }
    }
    sort(intervs.begin(), intervs.end());
    if (v.size() % 2 == 1) {
        if (v[N] == v.size()) {
            // Maximum is in the middle.
            if (intervs[N - 1].second != v.size() - 1) {
                return 0;
            }
        } else if (v[N] < intervs[N - 1].first ||
                   intervs[N - 1].second < v[N]) {
            return 0;
        }
    }
    if (intervs[0].second == v.size()) {
        return 0;
    }
    // From now on we can ignore middle.
    int maximum = -1, where_max = -1;
    for (int i = 0; i < N; ++i) {
        if (intervs[i].second > maximum) {
            maximum = intervs[i].second, where_max = i;
        }
    }
    int ans = 2;
    // To the left of max we need:
    // a < c or a < d
    // b < d    b < c
    for (int i = 0; i + 1 <= where_max; ++i) {
        const int a = intervs[i].first, b = intervs[i].second;
        const int c = intervs[i + 1].first, d = intervs[i + 1].second;
        int ways = (a < c && b < d) + (a < d && b < c);
        ans = (ways * ans) % MOD;
    }
    // To the right of max we need a < c < d < b.
    for (int i = where_max; i + 1 < N; ++i) {
        const int a = intervs[i].first, b = intervs[i].second;
        const int c = intervs[i + 1].first, d = intervs[i + 1].second;
        if (a > c || b < d)
            return 0;
    }
    return ans;
}

void Submit() {
    ifstream cin("munte.in");
    ofstream cout("munte.out");
    int N, C;
    cin >> C >> N;
    vector<int> v(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i];
    }
    int ans = CountLinear(v);
    if (C == 2) {
        cout << ans << endl;
    } else {
        cout << ((ans == 0) ? "NU" : "DA") << endl;
    }
}

void StressTest() {
    for (int N = 3;; ++N) {
        cerr << "Attempting N = " << N << endl;
        vector<int> perm(N, -1);
        iota(perm.begin(), perm.end(), 1);
        do {
            const int ans = CountBack(perm);
            if (ans != CountLinear(perm)) {
                for (int i = 0; i < N; ++i) {
                    cout << perm[i] << ' ';
                }
                cout << endl;
                exit(1);
            }
            // assert(ans == 0 || ans == gabi::CountLinear(perm));
        } while (next_permutation(perm.begin(), perm.end()));
    }
}

int main() {
    // StressTest();
    Submit();
    return 0;
}