### 问题描述 玲玲和希希刚刚购买了新的房子，他们正在考虑房屋的装修计划。 在这个屋子中，有 $N$ 个房间，每个房间里都有 $M$ 个位置可以安装饰品（一个位置只能安装一个饰品）。安装一个饰品的费用为 $1$ 元，玲玲和希希共有 $K$ 元的装修预算。 现在，他们想知道，一共有多少种装修方案，满足以下要求： - 在每个房间里，至少安装一个饰品。 - 装修的总成本不能超过 $K$ 元。 由于方案数量可能很大，他们只需要输出答案对 $10^9 + 7$ 取模的结果。 ### 输入格式 一行三个整数 $N,M$（$1\leq N,M \leq 30$） 和 $K$（$1\leq K \leq N\cdot M$），分别表示房间数、安装饰品的位置数和预算。 ### 输出格式 一个整数，表示满足条件的装修方案数对 $10^9 + 7$ 取模的结果。 ### 样例输入 ``` 2 3 5 ``` ### 样例输出 ``` 8 ```