El maestro mago So le ha estado enseñando a sus pupilos algunos hechizos relacionados con los divisores de un número. Se dice que un número ~a~ es divisor de ~b~ si existe un entero ~k~ tal que ~a * k = b~. Su pupilo estrella Mo ha estado leyendo libros de magia negra y le ha interesado un hechizo peculiar que hablaba sobre hechizos ~k-~perfectos.

Sea ~d(x)~ la cantidad de divisores de ~x~. Se dice que un hechizo de ~m~ elementos ~s_1, s_2, \dots, s_m~ es ~k-~perfecto si para todo ~1 \le i < m~ se cumple que ~d(s_i * s_{i+1}) \mod 2 = k~. Por ejemplo, ~[3, 5, 6]~ es un hechizo ~0~-perfecto y ~[3, 3, 3]~ es un hechizo ~1~-perfecto, pero ~[4, 3, 3]~ no es un hechizo ~0~-perfecto ni ~[1, 5, 12]~ tampoco es un hechizo ~1~-perfecto.

Dada una secuencia ~a~ de longitud ~n~, Mo necesita contar la cantidad de formas de reorganizar esta secuencia de forma tal que la nueva secuencia sea un hechizo ~k~-perfecto, es decir, contar la cantidad de permutaciones ~p_1, p_2, \dots, p_n~ tal que la secuencia ~a_{p_1}, a_{p_2}, \dots, a_{p_n}~ sea un hechizo ~k~-perfecto. Como la respuesta puede ser muy grande, imprímela módulo ~10^9+7~.

Subtareas:

• Subtarea 1 (10 puntos): ~a_1 = a_2 = \dots = a_n~.
• Subtarea 2 (7 puntos): ~1 \le n \le 5~.
• Subtarea 3 (12 puntos): ~k=1~.
• Subtarea 4 (21 puntos): ~1 \le n \le 16~.
• Subtarea 5 (50 puntos): Sin restricciones adicionales.

Entrada

La primera línea de la entrada contiene dos enteros ~n~ y ~k~ (~1 \le n \le 500~, ~0 \le k < 2~).

La siguiente línea contiene ~n~ enteros ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^7~).

Salida

Imprime un entero: el número de formas de reorganizar la secuencia ~a~ tal que la nueva secuencia sea un hechizo ~k-~perfecto, módulo ~10^9+7~.

Ejemplo de entrada 1

3 0
8 1 4

Ejemplo de salida 1

2

Ejemplo de entrada 2

3 1
8 3 2

Ejemplo de salida 2

0

Ejemplo de entrada 3

5 0
101 577 101 577 577

Ejemplo de salida 3

12

Nota

En el primer ejemplo, los hechizos válidos son:

• ~[1, 8, 4]~ ya que cumple que ~d(a_1 * a_2) = d(8) = 4 \mod 2 = 0~ y ~d(a_2 * a_3) = d(32) = 6 \mod 2 = 0~
• ~[4, 8, 1]~ ya que cumple que ~d(a_1 * a_2) = d(32) = 6 \mod 2 = 0~ y ~d(a_2 * a_3) = d(8) = 4 \mod 2 = 0~