Se forma un grupo de \(N\) personas que llegan una a una, y cada una aporta entre \(1\) y \(K\) globos. Se exige que, después de cada llegada, el total de globos aportados hasta ese momento sea divisible por la cantidad de personas presentes. Es decir, si la persona \(i\) aporta \(a_i\) globos, para todo \(j = 1, \dots, N\) se debe cumplir que \(j\) divide a \(a_1 + \dots + a_j\).

Cuenta cuántas secuencias \((a_1, \dots, a_N)\), con \(1 \le a_i \le K\), cumplen la regla. Dos secuencias son distintas si difieren en alguna posición.

Entrada

Una línea con dos enteros \(N\) \((1 \le N \le 10^9)\) y \(K\) \((1 \le K \le 2000)\).

Salida

Una línea con la cantidad de secuencias, módulo \(998244353\).

Notas

En el primer ejemplo (\(N = 3\), \(K = 3\)) las secuencias válidas son \([1,1,1]\), \([1,3,2]\), \([2,2,2]\), \([3,1,2]\) y \([3,3,3]\). En el segundo, con \(K = 1\) la única secuencia es la de puros unos.

Ejemplo 1

Entrada

3 3

Salida

5

Ejemplo 2

Entrada

4 1

Salida

1

Regional Latinoamericana 2025 del ICPC, problema B («Balanced Balloons»). Versión en español redactada para este juez; el enunciado oficial, en inglés, está aquí abajo.