#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wincompatible-pointer-types"
typedef struct {
  int32_t a;
  int32_t b;
} hw;
typedef struct {
  int64_t a;
  int64_t b;
} hwll;
typedef struct {
  int64_t a;
  int64_t b;
  int64_t c;
} hwllc;
typedef struct {
  hwll a;
  hwll b;
} linell;
uint64_t n, m;
uint64_t h, w;
uint64_t k;
uint64_t q;
int64_t va, vb, vc, vd, ve, vf;
uint64_t ua, ub, uc, ud, ue, uf;
long double vra, vrb, vrc;
double vda, vdb, vdc;
char ch, dh;
uint64_t umin(uint64_t x, uint64_t y) { return (x < y) ? x : y; }
uint64_t umax(uint64_t x, uint64_t y) { return (x > y) ? x : y; }
int64_t smin(int64_t x, int64_t y) { return (x < y) ? x : y; }
int64_t smax(int64_t x, int64_t y) { return (x > y) ? x : y; }
uint64_t gcd(uint64_t x, uint64_t y) {
  if (x < y) {
    return gcd(y, x);
  } else if (y == 0) {
    return x;
  } else {
    return gcd(y, x % y);
  }
}
uint64_t bitpow(uint64_t a, uint64_t x, uint64_t modulo) {
  uint64_t result = 1;
  while (x) {
    if (x & 1) {
      result *= a;
      result %= modulo;
    }
    x /= 2;
    a = (a * a) % modulo;
  }
  return result;
}
uint64_t divide(uint64_t a, uint64_t b, uint64_t modulo) {
  return (a * bitpow(b, modulo - 2, modulo)) % modulo;
}
uint64_t udiff(uint64_t a, uint64_t b) {
  if (a >= b) {
    return a - b;
  } else {
    return b - a;
  }
}
int64_t sdiff(int64_t a, int64_t b) {
  if (a >= b) {
    return a - b;
  } else {
    return b - a;
  }
}
int bitcount(uint64_t n) {
  int result = 0;
  while (n) {
    if (n & 1) result++;
    n /= 2;
  }
  return result;
}
int32_t pullcomp(const void *left, const void *right) {
  uint64_t l = *(uint64_t *)left;
  uint64_t r = *(uint64_t *)right;
  if (l < r) {
    return -1;
  }
  if (l > r) {
    return +1;
  }
  return 0;
}
int32_t prevcomp(const void *left, const void *right) {
  uint64_t l = *(uint64_t *)left;
  uint64_t r = *(uint64_t *)right;
  if (l > r) {
    return -1;
  }
  if (l < r) {
    return +1;
  }
  return 0;
}
int32_t psllcomp(const void *left, const void *right) {
  int64_t l = *(int64_t *)left;
  int64_t r = *(int64_t *)right;
  if (l < r) {
    return -1;
  }
  if (l > r) {
    return +1;
  }
  return 0;
}
int32_t pcharcomp(const void *left, const void *right) {
  char l = *(char *)left;
  char r = *(char *)right;
  if (l < r) {
    return -1;
  }
  if (l > r) {
    return +1;
  }
  return 0;
}
int32_t pdoublecomp(const void *left, const void *right) {
  double l = *(double *)left;
  double r = *(double *)right;
  if (l < r) {
    return -1;
  }
  if (l > r) {
    return +1;
  }
  return 0;
}
int32_t pstrcomp(const void *left, const void *right) {
  char *l = *(char **)left;
  char *r = *(char **)right;
  return strcmp(l, r);
}
int32_t phwllABcomp(const void *left, const void *right) {
  hwll l = *(hwll *)left;
  hwll r = *(hwll *)right;
  if (l.a < r.a) {
    return -1;
  }
  if (l.a > r.a) {
    return +1;
  }
  if (l.b < r.b) {
    return -1;
  }
  if (l.b > r.b) {
    return +1;
  }
  return 0;
}
int32_t phwllREVcomp(const void *left, const void *right) {
  hwll l = *(hwll *)left;
  hwll r = *(hwll *)right;
  if (l.b < r.b) {
    return -1;
  }
  if (l.b > r.b) {
    return +1;
  }
  if (l.a < r.a) {
    return -1;
  }
  if (l.a > r.a) {
    return +1;
  }
  return 0;
}
int32_t ptriplecomp(const void *left, const void *right) {
  hwllc l = *(hwllc *)left;
  hwllc r = *(hwllc *)right;
  if (l.a < r.a) {
    return -1;
  }
  if (l.a > r.a) {
    return +1;
  }
  if (l.b < r.b) {
    return -1;
  }
  if (l.b > r.b) {
    return +1;
  }
  if (l.c < r.c) {
    return -1;
  }
  if (l.c > r.c) {
    return +1;
  }
  return 0;
}
int32_t ptripleREVcomp(const void *left, const void *right) {
  hwllc l = *(hwllc *)left;
  hwllc r = *(hwllc *)right;
  if (l.b < r.b) {
    return -1;
  }
  if (l.b > r.b) {
    return +1;
  }
  if (l.a < r.a) {
    return -1;
  }
  if (l.a > r.a) {
    return +1;
  }
  if (l.c < r.c) {
    return -1;
  }
  if (l.c > r.c) {
    return +1;
  }
  return 0;
}
int32_t pquadcomp(const void *left, const void *right) {
  linell l = *(linell *)left;
  linell r = *(linell *)right;
  int64_t ac = phwllABcomp(&(l.a), &(r.a));
  if (ac) return ac;
  int64_t bc = phwllABcomp(&(l.b), &(r.b));
  if (bc) return bc;
  return 0;
}
bool isinrange(int64_t left, int64_t x, int64_t right) {
  return (left <= x && x <= right);
}
bool isinrange_soft(int64_t left, int64_t x, int64_t right) {
  return (left <= x && x <= right) || (left >= x && x >= right);
}
int64_t a[1000000 + 5];
int64_t b[1000000 + 5];
int64_t c[1000000 + 5];
int64_t d[1000000 + 5];
char s[1000000 + 1];
char t[1000000 + 1];
hwll xy[1000000];
hwllc tup[1000000];
int64_t table[3000][3000];
hwll apress[1000000];
uint64_t len = 0;
int64_t pos[1000000];
int64_t rev[1000000];
int64_t candi[1000000];
int64_t width[1000000];
int64_t prob[1000000];
int64_t pwid[1000000];
bool setpos(uint64_t v, uint64_t x) {
  if (pos[v] >= 0 && pos[v] == x) return true;
  if (pos[v] >= 0 && pos[v] != x) return false;
  if (rev[x] >= 0 && rev[x] != v) return false;
  pos[v] = x;
  rev[x] = v;
  return true;
}
hwll slick[1000000];
int64_t beg = 0, end = 0;
void spush(int64_t x, int64_t c) {
  while (beg < end && slick[end - 1].a <= x) {
    end--;
  }
  slick[end] = (hwll){x, c};
  end++;
}
int64_t swhat() { return slick[beg].a; }
void spop(int64_t c) {
  if (slick[beg].b == c) beg++;
}
void slider(int64_t base, int64_t d) {
  int64_t i;
  base = (base + d - 1) % n;
  for (i = d; i >= 1; i--) {
    spush(a[(n + base - i) % n], -i);
  }
  for (i = 0; i < n; i++) {
    spush(a[(base + i) % n], i);
    spop(i - d);
    prob[i] = swhat();
  }
}
uint64_t frac[1000000];
uint64_t solve() {
  int64_t i, j, ki, li;
  int64_t result = 0;
  double dresult = 0;
  int64_t maybe = 0;
  int64_t sum = 0;
  int64_t item;
  uint64_t *dpcell;
  frac[0] = 1;
  for (i = 1; i <= n; i++) {
    frac[i] = (frac[i - 1] * i) % 998244353;
  }
  uint64_t d;
  uint64_t base;
  for (i = 0; i < n; i++) {
    if (a[i ? (i - 1) : (n - 1)] > 0 && a[i] == 0) {
      base = i;
      break;
    }
  }
  if (i == n) {
    for (i = 0; i < n; i++) {
      if (a[i] > 0) goto fail;
    }
    result = frac[n];
    goto success;
  }
  i = 0;
  while (i < n) {
    j = i;
    while (a[(base + i) % n] == a[(base + j) % n]) i++;
    apress[len] = (hwll){a[(base + j) % n], i - j};
    len++;
  }
  d = apress[0].b;
  for (i = 0; i < n; i++) {
    pos[i] = rev[i] = -1;
  }
  pos[0] = 0;
  rev[0] = 0;
  sum = 0;
  for (i = 0; i < len; i++) {
    if (apress[i].b > d) goto fail;
    sum += apress[i].b;
    if (apress[i].a < apress[(i + 1) % len].a) {
      if (!setpos((n + sum - d) % n, apress[i].a)) goto fail;
    } else {
      if (!setpos(sum % n, apress[(i + 1) % len].a)) goto fail;
    }
    if (apress[i ? (i - 1) : (len - 1)].a < apress[i].a &&
        apress[i].a > apress[(i + 1) % len].a) {
      rev[apress[i].a] = 2000000007;
      j = (n + sum - d) % n;
      while (true) {
        candi[j] = apress[i].a;
        if (j == (sum - apress[i].b) % n) break;
        j = (j + 1) % n;
      }
    }
  }
  slider(base, d);
  for (i = 0; i < n; i++) {
    if (pos[i] < 0 && candi[i] >= 0) {
      width[candi[i]]++;
    }
    pwid[prob[i]]++;
  }
  result = 1;
  for (i = 0; i < n; i++) {
    if (rev[i] != 2000000007) continue;
    result = (result * width[i]) % 998244353;
  }
  sum = 0;
  for (i = 0; i < n; i++) {
    sum += pwid[i];
    if (!sum) goto fail;
    if (rev[i] < 0) result = (result * sum) % 998244353;
    sum--;
  }
  printf("%lld\n", result);
  return 0;
success:
  printf("%llu\n", result);
  return 0;
fail:
  puts("0");
  return 1;
}
int32_t main(void) {
  int32_t i, j;
  int32_t x, y;
  scanf("%llu", &n, &m);
  for (i = 0; i < n; i++) {
    scanf("%lld", &a[i]);
    a[i]--;
  }
  solve();
  return 0;
}
