alternant

#include <bits/stdc++.h>
#define maxN 102
#define maxM 1000000000
#define mod 1000000009
using namespace std;
FILE *fin = freopen("alternant.in", "r", stdin);
FILE *fout = freopen("alternant.out", "w", stdout);
int dp[2][maxN], v[maxN];
int T[maxN][maxN], Ans[maxN][maxN];

int lgPow(int a, int b)
{
    int ret = 1;
    for (int i = 0; (1 << i) <= b; ++ i, a = (1LL * a * a) % mod)
        if (b & (1 << i))
            ret = (1LL * ret * a) % mod;
    return ret;
}

void mul(int n, int a[maxN][maxN], int b[maxN][maxN])
{
    int res[maxN][maxN];
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < n; ++ j)
        {
            res[i][j] = 0;
            for (int k = 0; k < n; ++ k)
                res[i][j] = (1LL * res[i][j] + 1LL * a[i][k] * b[k][j]) % mod;
        }
    memcpy(a, res, sizeof(res));
}

void printProb(const int &n, const int &m, const int &A, const int &B)
{
    int pos = 0;
    for (int i = 0; i < n; i += 2)
    {
        if (v[i] == 0)
           ++ pos;
    }
    for (int i = 0; (1 << i) <= m; ++ i, mul(n, T, T))
        if (m & (1 << i))
            mul(n, Ans, T);
    int ans = lgPow(n * n, mod - 1 - m);
    ans = (1LL * ans * Ans[pos][A]) % mod;
    printf("%d\n", ans);
}

void computeMat(const int &n, const int &m, const int &A, const int &B)
{
    for (int j = 0; j <= n; ++ j)
    Ans[j][j] = 1;
    for (int j = 1; j <= A; ++ j)
    {
        int goodA = j, badA = A - j, goodB = B - (A - j), badB = A - j;
        T[j][j] = A * A + B * B + 2 * goodA * badB + 2 * goodB * badA;
        int goodA2 = j - 1, badA2 = A - j + 1, goodB2 = B - (A - j + 1), badB2 = A - j + 1;
        if (j > 1) T[j - 1][j] = 2 * badA2 * badB2;
        if (j < A)
        {
            int goodA3 = j + 1, badA3 = A - j - 1, goodB3 = B - (A - j - 1), badB3 = A - j - 1;
            T[j + 1][j] = 2 * (goodA3 * goodB3);
        }
    }

}

void readData(int &n, int &m, int &A, int &B)
{
    scanf("%d%d", &n, &m);

    for (int i = 0 ; i < n; ++ i)
    {
        scanf("%d", &v[i]);
        if (v[i] > 0)
        ++ A;
        else
        ++ B;
    }
}

void updateData(const int &n, int &A, int &B)
{
    bool morePositives = (A > B);
    if (!morePositives)
    swap(A, B);
    for (int i=0;i<n;++i)
    {
        if (!morePositives)
        v[i] = -v[i];
        if (v[i] > 0)
           v[i] = 0;
           else
           v[i] = 1;
    }
}

int main()
{
    int n, m, A = 0, B = 0;
    readData(n, m, A, B);
    updateData(n, A, B);
    computeMat(n, m, A, B);
    printProb(n, m, A, B);
    return 0;
}