小红的完全k叉树
题号：NC254951
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小红想知道，n层的完全k叉树，共有多少条不同的长度为m的路径？

输入描述:

三个正整数n,m,k
1\leq n \leq 10^9
2 \leq k \leq 10^9
1\leq m \leq 1000

输出描述:

长度为m的路径数量。由于答案过大，请对10^9+7取模。
示例1

输入

复制 
3 2 2

输出

复制 
7
示例2

输入

复制 
2 2 3

输出

复制 
3