28612번 - Нужно больше энергии 다국어

Машины матрицы потребляют невообразимое количество энергии. Некоторые люди, взаимодействуя в Матрице, выделяют очень много энергии, поэтому Архитектор Матрицы задумался над новым помещением для расположения крио-камер с людьми.

По задумке, новое помещение будет представлять собой прямоугольную комнату длины $n$ и ширины $x$, вдоль горизонтальной стороны которой будет расположена большая аккумуляторная батарея для накопления энергии. В каждом из рядов помещения (для $1 \leqslant i \leqslant n$) планируется разместить одну криокамеру на некотором расстоянии от нижней стены $p_i$ ($1 \leqslant p_i \leqslant x$).

Криокамера расположена энергетически выгодно, если криокамеры слева и справа (если такие есть) расположены на меньшем расстоянии от аккумулятора, чем текущая криокамера, то есть $p_{i - 1} < p_i$ и $p_i > p_{i + 1}$.

Назовем конфигурацией криокамер набор чисел $p_1, \ldots, p_n$. Архитектор Матрицы задумался, сколько существует конфигураций расположения криокамер в комнате длины $n$, таких что энергетически выгодно расположенных криокамер будет ровно $k$. Он смог ответить на этот вопрос, а сможете ли ответить на него вы?

Так как ответ на задачу может быть достаточно большим, найдите его по модулю числа $10^9 + 7$.

В первой и единственной строке ввода через пробел даны три целых числа $n$, $x$ и $k$ --- длинна комнаты, максимальное расстояние, на котором может быть расположена криокамера от аккумулятора, и количество криокамер, расположенных энергетически выгодно $(1 \leq n, x, k \leq 500)$.

В единственной строке выведите ответ на задачу по модулю $10^9 + 7$ --- количество конфигураций криокамер, удовлетворяющих условиям.

Ниже находится иллюстрация к первому примеру: