Ярослав называет массив из r целых чисел a₁, a₂, ..., a_r хорошим, если выполняются условия: |a₁ - a₂| = 1, |a₂ - a₃| = 1, ..., |a_r - 1 - a_r| = 1, |a_r - a₁| = 1, при этом .

Массив целых чисел b₁, b₂, ..., b_r называется замечательным, если выполняются следующие условия:

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

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

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