E. Ярослав и расстановки
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

Ярослав называет массив из r целых чисел a1, a2, ..., ar хорошим, если выполняются условия: |a1 - a2| = 1, |a2 - a3| = 1, ..., |ar - 1 - ar| = 1, |ar - a1| = 1, при этом .

Массив целых чисел b1, b2, ..., br называется замечательным, если выполняются следующие условия:

  1. Элементы в нем не убывают (bi ≤ bi + 1).
  2. Если выполняются неравенства, 1 ≤ r ≤ n и 1 ≤ bi ≤ m.
  3. Если переставляя его элементы можно получить не менее одного и не более k различных хороших массивов.

У Ярослава есть три целых числа n, m, k. Ему нужно посчитать количество различных замечательных массивов. Помогите Ярославу! Так как ответ может быть достаточно большим, нужно вывести его остаток от деления на 1000000007 (109 + 7).

Два массива считаются различными, если найдется позиция, на которой в них стоят различные числа.

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

В единственной строке даны три целых числа n, m, k (1 ≤ n, m, k ≤ 100).

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

В единственную строку выведите остаток от деления ответа на задачу на число 1000000007 (109 + 7).

Примеры
Входные данные
1 1 1
Выходные данные
0
Входные данные
3 3 3
Выходные данные
2