#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,popcnt,tune=native")
using namespace std;
const int MN = 100005, inf = 1000000005, mod = 998244353;
const long long INF = 1000000000000000005LL;
int t[MN], dp[MN], ile[MN], ost[MN], gdzie[MN];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &t[i]);
    gdzie[i] = ost[t[i]];
    ost[t[i]] = i;
  }
  dp[0] = 1;
  long long res = 0LL;
  for (int i = 1; i <= n; ++i) {
    int a = gdzie[i], b = gdzie[gdzie[i]];
    for (int j = a; j < i; ++j) ++ile[j];
    for (int j = b; j < a; ++j) --ile[j];
    for (int j = 0; j < i; ++j) res += (ile[j] <= k) * dp[j];
    res %= mod;
    dp[i] = res;
    res = 0LL;
  }
  printf("%d", dp[n]);
}

### Prompt

Your task is to create 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,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,popcnt,tune=native")
using namespace std;
const int MN = 100005, inf = 1000000005, mod = 998244353;
const long long INF = 1000000000000000005LL;
int t[MN], dp[MN], ile[MN], ost[MN], gdzie[MN];
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &t[i]);
    gdzie[i] = ost[t[i]];
    ost[t[i]] = i;
  }
  dp[0] = 1;
  long long res = 0LL;
  for (int i = 1; i <= n; ++i) {
    int a = gdzie[i], b = gdzie[gdzie[i]];
    for (int j = a; j < i; ++j) ++ile[j];
    for (int j = b; j < a; ++j) --ile[j];
    for (int j = 0; j < i; ++j) res += (ile[j] <= k) * dp[j];
    res %= mod;
    dp[i] = res;
    res = 0LL;
  }
  printf("%d", dp[n]);
}

```