Hipocamp

Time limit: 0.7s Memory limit: 64MB Input: Output:

Considerăm următoarea funcție care primește ca input o permutare, PP, a mulțimii {1,2,,N}\{1, 2, \dots, N\}.

int count_max_changes(const std::vector<int>& P) {
  int max_value = 0, count = 0;
  for (const int value : P) {
    if (value > max_value) {
      max_value = value;
      count++;
    }
  }
  return count;
}

Cerință

Dându-se două numere naturale, NN și KK, să se numere pentru câte permutări, PP, ale mulțimii {1,2,,N}\{1, 2, \dots, N\} avem count_max_changes(P)Kcount\_max\_changes(P) \leq K. De vreme ce acest număr poate fi foarte mare, se cere doar restul său la împărțirea cu 998 244 353998 \ 244 \ 353.

Date de intrare

Pe prima linie se găsesc două numere naturale, NN și KK.

Date de ieșire

Pe prima linie se va găsi un singur număr natural, numărul de permutări pentru care funcția de mai sus returnează un număr mai mic sau egal decât KK, modulo 998 244 353998 \ 244 \ 353.

Restricții și precizări

  • 1KN200 0001 \leq K \leq N \leq 200 \ 000;
  • Pentru teste valorând 99 puncte, 1KN101 \leq K \leq N \leq 10;
  • Pentru teste valorând alte 3939 de puncte, 1KN1 0001 \leq K \leq N \leq 1 \ 000;
  • Pentru restul de 5252 de puncte, nu există restricții suplimentare.

Exemplul 1

stdin

5 3

stdout

109

Exemplul 2

stdin

319 123

stdout

182709129

Log in or sign up to be able to send submissions!