#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2")
using namespace std;
int mod = 998244353;
int A[100077];
int B[100077];
int N[100077];
int dp[100077];
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, k, ai;
  cin >> n >> k;
  dp[0] = 1;
  signed long long sum = 1;
  for (int i = 1; i <= n; i++) {
    cin >> ai;
    for (int j = B[ai]; j < A[ai]; j++)
      if (--N[j] == k) sum += dp[j];
    for (int j = A[ai]; j < i; j++)
      if (++N[j] == k + 1) sum -= dp[j];
    sum %= mod;
    dp[i] = sum;
    B[ai] = A[ai];
    A[ai] = i;
    sum = (sum + dp[i]) % mod;
  }
  cout << (dp[n] % mod + mod) % mod << endl;
  return 0;
}

### Prompt

Please formulate a cpp solution to 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 target("avx,avx2")
using namespace std;
int mod = 998244353;
int A[100077];
int B[100077];
int N[100077];
int dp[100077];
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, k, ai;
  cin >> n >> k;
  dp[0] = 1;
  signed long long sum = 1;
  for (int i = 1; i <= n; i++) {
    cin >> ai;
    for (int j = B[ai]; j < A[ai]; j++)
      if (--N[j] == k) sum += dp[j];
    for (int j = A[ai]; j < i; j++)
      if (++N[j] == k + 1) sum -= dp[j];
    sum %= mod;
    dp[i] = sum;
    B[ai] = A[ai];
    A[ai] = i;
    sum = (sum + dp[i]) % mod;
  }
  cout << (dp[n] % mod + mod) % mod << endl;
  return 0;
}

```