#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const int N = 100100;
const int Q = 250200;
const long long mod = 998244353;
using namespace std;
int n;
int k;
int d[N];
int f[N];
int l[N];
int p[N];
void add(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  } else if (x < 0) {
    x += mod;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> k;
  int s = 1, x, h;
  d[0] = 1;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    for (int j = l[x] + 1; j <= i; j++) {
      if (f[j] == k) {
        s -= d[j - 1];
        if (s < 0) {
          s += mod;
        }
      }
      f[j] += 1;
    }
    h = p[x];
    for (int j = l[x]; j > h; j--) {
      f[j] -= 1;
      if (f[j] == k) {
        s += d[j - 1];
        if (s >= mod) {
          s -= mod;
        }
      }
    }
    p[x] = l[x];
    l[x] = i;
    d[i] = s;
    add(s, s);
  }
  cout << d[n] << "\n";
}

### Prompt

Create a solution in Cpp for the following problem:

Find the number of ways to divide an array a of n integers into any number of disjoint non-empty segments so that, in each segment, there exist at most k distinct integers that appear exactly once.

Since the answer can be large, find it modulo 998 244 353.

Input

The first line contains two space-separated integers n and k (1 ≤ k ≤ n ≤ 10^5) — the number of elements in the array a and the restriction from the statement.

The following line contains n space-separated integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — elements of the array a.

Output

The first and only line contains the number of ways to divide an array a modulo 998 244 353.

Examples

Input


3 1
1 1 2


Output


3


Input


5 2
1 1 2 1 3


Output


14


Input


5 5
1 2 3 4 5


Output


16

Note

In the first sample, the three possible divisions are as follows.

  * [[1], [1], [2]] 
  * [[1, 1], [2]] 
  * [[1, 1, 2]] 



Division [[1], [1, 2]] is not possible because two distinct integers appear exactly once in the second segment [1, 2].

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
const int N = 100100;
const int Q = 250200;
const long long mod = 998244353;
using namespace std;
int n;
int k;
int d[N];
int f[N];
int l[N];
int p[N];
void add(int &x, int y) {
  x += y;
  if (x >= mod) {
    x -= mod;
  } else if (x < 0) {
    x += mod;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> k;
  int s = 1, x, h;
  d[0] = 1;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    for (int j = l[x] + 1; j <= i; j++) {
      if (f[j] == k) {
        s -= d[j - 1];
        if (s < 0) {
          s += mod;
        }
      }
      f[j] += 1;
    }
    h = p[x];
    for (int j = l[x]; j > h; j--) {
      f[j] -= 1;
      if (f[j] == k) {
        s += d[j - 1];
        if (s >= mod) {
          s -= mod;
        }
      }
    }
    p[x] = l[x];
    l[x] = i;
    d[i] = s;
    add(s, s);
  }
  cout << d[n] << "\n";
}

```