У каждой из $N$ коров Farmer John ($(4 \le N \le 16)$) уникальный номер $S_{i}$ ($(1 \le S_{i} \le 25,000)$). Они гордятся им и по-гангстерски носят золотую пластину с крупно выгравированным номером на своей массивной шее.

Мятежные коровы идут на дойку «перемешанными»: номера любых двух соседних должны отличаться более чем на $K$ ($(1 \le K \le 3400)$). Например, при $N = 6$ и $K = 1$ ряд 1, 3, 5, 2, 6, 4 подходит, а 1, 3, 6, 5, 2, 4 нет: соседние5 и6 отличаются на1.

Сколькими способами перемешать $N$ коров?

Для первых10 отправок вам дадут результаты на части настоящих тестов.

Входные данные

• Строка1: два целых через пробел, $N$ и $K$.
• Строки $2,\ldots,N+1$: строка $i+1$ содержит номер коровы $i$, целое $S_{i}$.

Выходные данные

• Строка1: число способов для $N$ коров. Ответ гарантированно помещается в64-битное целое.

Примеры

Входные данные 1

4 1
3
4
2
1

Выходные данные 1

2

Примечание

Два возможных ряда: 3 1 4 2 2 4 1 3.

Подзадачи

Баллы:200

Автор задачи: Don Piele, 2007