Considere todas las permutaciones ~p~ de tamaño ~N~, halle el arreglo de inversiones para cada una (en un arreglo de inversiones se cumple que la posición ~i~ del arreglo es igual a la cantidad de elementos ~p_j > p_i~ donde ~1 \leq j < i \leq N~), dado un ~K~, diga la cantidad de permutaciones que cumplen que ~K~ es igual al máximo común divisor del arreglo de inversiones módulo ~1234567891~. (No tenga en cuenta el arreglo de inversiones donde todos sus elementos son ~0~).

Restricciones

~1 \leq N \leq 2*10^5~

~1 \leq K \leq 10^{18}~

Entrada

La entrada consta de una línea con dos enteros separados por un espacio ~N~ y ~K~.

Salida

La salida consta de una línea con un entero, la respuesta al problema dado.

Ejemplo #1 de Entrada

3 1

Ejemplo #1 de Salida

4

Ejemplo #2 de Entrada

3 2

Ejemplo #2 de Salida

1

Ejemplo #3 de Entrada

1013 1013

Ejemplo #3 de Salida

0