Крипто

Пешо шифрует перестановку из n чисел, в которой каждое число от 1 до n встречается ровно один раз. Он использует следующий алгоритм:

1. Заменить все числа в перестановке, число x заменяется на x-е простое число.

2. Выбрать случайное положительное k, не превышающее n.

3. Рассмотрим все отрезки, состоящие из подряд идущих элементов получившейся последовательности, содержащие хотя бы k элементов. Для каждого из них выпишем произведение k минимальных чисел.

4. Пусть p равно количеству различных произведений, получившихся на предыдущем шаге.

5. Шифром перестановки будет тройка "n k p".

Например, посмотрим, как Пешо зашифрует перестановку {4, 1, 3, 2}:

1. Первые 4 простых числа это 2, 3, 5 и 7. Поэтому он заменяет в перестановке

• 4 на четвертое простое число, то есть 7;

• 1 на первое простое число, то есть 2;

• 3 на третье простое число, то есть 5;

• 2 на второе простое число, то есть 3.

Пешо получает последовательность 7, 2, 5, 3.

2. Теперь он выбирает случайное число k. Пусть k = 2.

3. Все отрезки получившейся последовательности:{7}, {2}, {5}, {3}, {7, 2}, {2, 5}, {5, 3}, {7, 2, 5}, {2, 5, 3}, {7, 2, 5, 3}

Из них он оставляет только те, которые содержат хотя бы k = 2 элемента и для каждого из них вычисляет произведение двух минимальных элементов:

• {7, 2} 2 * 7 = 14

• {2, 5} 2 * 5 = 10

• {5, 3} 3 * 5 = 15

• {7, 2, 5} 2 * 5 = 10

• {2, 5, 3} 2 * 3 = 6

• {7, 2, 5, 3} 2 * 3 = 6

Получаются следующие произведения {14, 10, 15, 10, 6, 6}

4. Всего в наборе четыре разных произведения: {6, 10, 14, 15}, таким образом p = 4.

5. Шифр исходной перестановки "4 2 4".

Пешо быстро понял, что алгоритм шифрует последовательности лучше, чем он ожидал. Он хотел, чтобы код был взаимно-однозначным, но оказалось, что не всегда можно расшифровать получившийся шифр.

Напишите программу, которая по заданному шифру вычисляет количество различных возможных исходно заданных перестановок. Вывести остаток от деления ответа на 1 000 000 007.

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

Одна строка содержит три целых числа n, k (1 ≤ k ≤ n ≤ 400) и p (1 ≤ p ≤ 10^9).

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

Выведите количество перестановок с шифром "n k p". Ответ вывести по модулю 1 000 000 007.

Примеры

Примечание

В первом примере перестановки {1, 3, 2} и {2, 3, 1} могут быть зашифрованы как "3 2 3".

Во втором примере подходят перестановки {1, 2, 4, 3}, {1, 3, 2, 4}, {1, 4, 2, 3}, {2, 1, 4, 3}, {2, 3, 1, 4}, {2, 4, 1, 3}, {3, 1, 4, 2}, {3, 2, 4, 1}, {3, 4, 1, 2}, {3, 4, 2, 1}, {4, 1, 3, 2}, {4, 2, 3, 1}.