#include <cstdio>
#include <vector>
using namespace std;
 
// Hàm sinh hoán vị tiếp theo trong thứ tự từ điển.
// Trả về `k` là vị trí mà hoán vị bắt đầu thay
// đổi so với hoán vị trước.
// k < 0 nếu đây đã là hoán vị cuối cùng.
int next(vector<int> &a) {
    int k, l, n = a.size();
    for (k = n-2; k>=0; k--) if (a[k] < a[k+1]) break;
    if (k<0) return k;
    for (l = n-1; l>k; l--) if (a[k] < a[l]) break;
    swap(a[k], a[l]);
    for (int i=k+1, j=n-1; i<j; i++, j--) swap(a[i], a[j]);
    return k;
}
 
bool f[1000];
int seed = 0;
int cache[1001];
 
// Kiểm tra xem tại a[i] có thỏa điều kiện L < R
// như đã giải thích ở trên hay không.
bool check(const vector<int> &a, int i) {
    int n = a.size();
    seed += 1;
    int r = 1e9;
    // Tìm R là giá trị nhỏ nhất ở bên phải a[i]
    // Đồng thời đánh dấu các giá trị xuất hiện
    // ở bên phải a[i]
    for (int j=i+1; j<n; j++) {
        cache[a[j]] = seed;
        r = min(r, a[j]);
    }
    // Tìm L là giá trị lớn nhất nhỏ hơn a[i]
    // ở bên trái a[i] => L không xuất hiện ở bên phải
    int l = 0;
    for (int j=a[i]-1; j>=1; j--) {
        if (cache[j] != seed) {
            l = j;
            break;
        }
    }
    return l < r;
}
 
// Lần lượt kiểm tra và cập nhật các phần tử
// từ a[k] trở lên, đồng thời kiểm tra xem
// tất cả các phần tử có thỏa mãn điều kiện
// L < R hay không.
bool ok(const vector<int> &a, int k) {
    int n = a.size();
    for (int i=k; i<n; i++) {
        f[i] = check(a, i);
        if (i>0) f[i] &= f[i-1];
    }
    return f[n-1];
}
 
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<int> a(n);
    for (int i=0; i<n; i++) scanf("%d", &a[i]);
 
    int k = 0, count = 0;
    while (m--) {
        if (ok(a, k)) count++;
        k = next(a);
        if (k < 0) break;
    }
 
    printf("%d", count);
    return 0;
}
 

I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPHZlY3Rvcj4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCi8vIEjDoG0gc2luaCBob8OhbiB24buLIHRp4bq/cCB0aGVvIHRyb25nIHRo4bupIHThu7EgdOG7qyDEkWnhu4NuLgovLyBUcuG6oyB24buBIGBrYCBsw6AgduG7iyB0csOtIG3DoCBob8OhbiB24buLIGLhuq90IMSR4bqndSB0aGF5Ci8vIMSR4buVaSBzbyB24bubaSBob8OhbiB24buLIHRyxrDhu5tjLgovLyBrIDwgMCBu4bq/dSDEkcOieSDEkcOjIGzDoCBob8OhbiB24buLIGN14buRaSBjw7luZy4KaW50IG5leHQodmVjdG9yPGludD4gJmEpIHsKICAgIGludCBrLCBsLCBuID0gYS5zaXplKCk7CiAgICBmb3IgKGsgPSBuLTI7IGs+PTA7IGstLSkgaWYgKGFba10gPCBhW2srMV0pIGJyZWFrOwogICAgaWYgKGs8MCkgcmV0dXJuIGs7CiAgICBmb3IgKGwgPSBuLTE7IGw+azsgbC0tKSBpZiAoYVtrXSA8IGFbbF0pIGJyZWFrOwogICAgc3dhcChhW2tdLCBhW2xdKTsKICAgIGZvciAoaW50IGk9aysxLCBqPW4tMTsgaTxqOyBpKyssIGotLSkgc3dhcChhW2ldLCBhW2pdKTsKICAgIHJldHVybiBrOwp9Cgpib29sIGZbMTAwMF07CmludCBzZWVkID0gMDsKaW50IGNhY2hlWzEwMDFdOwoKLy8gS2nhu4NtIHRyYSB4ZW0gdOG6oWkgYVtpXSBjw7MgdGjhu49hIMSRaeG7gXUga2nhu4duIEwgPCBSCi8vIG5oxrAgxJHDoyBnaeG6o2kgdGjDrWNoIOG7nyB0csOqbiBoYXkga2jDtG5nLgpib29sIGNoZWNrKGNvbnN0IHZlY3RvcjxpbnQ+ICZhLCBpbnQgaSkgewogICAgaW50IG4gPSBhLnNpemUoKTsKICAgIHNlZWQgKz0gMTsKICAgIGludCByID0gMWU5OwogICAgLy8gVMOsbSBSIGzDoCBnacOhIHRy4buLIG5o4buPIG5o4bqldCDhu58gYsOqbiBwaOG6o2kgYVtpXQogICAgLy8gxJDhu5NuZyB0aOG7nWkgxJHDoW5oIGThuqV1IGPDoWMgZ2nDoSB0cuG7iyB4deG6pXQgaGnhu4duCiAgICAvLyDhu58gYsOqbiBwaOG6o2kgYVtpXQogICAgZm9yIChpbnQgaj1pKzE7IGo8bjsgaisrKSB7CiAgICAgICAgY2FjaGVbYVtqXV0gPSBzZWVkOwogICAgICAgIHIgPSBtaW4ociwgYVtqXSk7CiAgICB9CiAgICAvLyBUw6xtIEwgbMOgIGdpw6EgdHLhu4sgbOG7m24gbmjhuqV0IG5o4buPIGjGoW4gYVtpXQogICAgLy8g4bufIGLDqm4gdHLDoWkgYVtpXSA9PiBMIGtow7RuZyB4deG6pXQgaGnhu4duIOG7nyBiw6puIHBo4bqjaQogICAgaW50IGwgPSAwOwogICAgZm9yIChpbnQgaj1hW2ldLTE7IGo+PTE7IGotLSkgewogICAgICAgIGlmIChjYWNoZVtqXSAhPSBzZWVkKSB7CiAgICAgICAgICAgIGwgPSBqOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gbCA8IHI7Cn0KCi8vIEzhuqduIGzGsOG7o3Qga2nhu4NtIHRyYSB2w6AgY+G6rXAgbmjhuq10IGPDoWMgcGjhuqduIHThu60KLy8gdOG7qyBhW2tdIHRy4bufIGzDqm4sIMSR4buTbmcgdGjhu51pIGtp4buDbSB0cmEgeGVtCi8vIHThuqV0IGPhuqMgY8OhYyBwaOG6p24gdOG7rSBjw7MgdGjhu49hIG3Do24gxJFp4buBdSBraeG7h24KLy8gTCA8IFIgaGF5IGtow7RuZy4KYm9vbCBvayhjb25zdCB2ZWN0b3I8aW50PiAmYSwgaW50IGspIHsKICAgIGludCBuID0gYS5zaXplKCk7CiAgICBmb3IgKGludCBpPWs7IGk8bjsgaSsrKSB7CiAgICAgICAgZltpXSA9IGNoZWNrKGEsIGkpOwogICAgICAgIGlmIChpPjApIGZbaV0gJj0gZltpLTFdOwogICAgfQogICAgcmV0dXJuIGZbbi0xXTsKfQoKaW50IG1haW4oKSB7CiAgICBpbnQgbiwgbTsKICAgIHNjYW5mKCIlZCVkIiwgJm4sICZtKTsKICAgIHZlY3RvcjxpbnQ+IGEobik7CiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSBzY2FuZigiJWQiLCAmYVtpXSk7CgogICAgaW50IGsgPSAwLCBjb3VudCA9IDA7CiAgICB3aGlsZSAobS0tKSB7CiAgICAgICAgaWYgKG9rKGEsIGspKSBjb3VudCsrOwogICAgICAgIGsgPSBuZXh0KGEpOwogICAgICAgIGlmIChrIDwgMCkgYnJlYWs7CiAgICB9CgogICAgcHJpbnRmKCIlZCIsIGNvdW50KTsKICAgIHJldHVybiAwOwp9Cg==