题目描述

小爱想用 $n$ 个点，$k$ 条边来构造一张简单无向联通图（即无重边、无自环），她希望构造出的图能够满足前 $m$ 个点度数恰好为 $2$ 。

请你帮忙求出满足条件的简单无向联通图的个数，由于答案可能很大，输出答案对 $10^9+7$ 取模的结果。

输入格式

输入仅一行，包含 $3$ 个整数 $n, m, k$

输出格式

输出一行，表示答案对 $10^9 + 7$ 取模的结果

4 1 4

9

数据范围

对于 $30\%$的数据， $1 \leq n,k \leq 10$ ，其中 $m=0,1,2$ 各占 $10\%$ 对于 $60\%$的数据， $1 \leq n,k \leq 20$ ，其中 $m=0,1,2$ 各占 $20\%$ 对于 $100\%$的数据， $1 \leq n,k \leq 50 , 0 \leq m \leq 2$