题目描述

There is an old country and the king fell in love with a devil. The devil always ask the king to do some crazy things. Although the king used to be wise and beloved by his people. Now he is just like a boy in love and can’t refuse any request from the devil. Also, this devil is looking like a very cute Loli. Something bad actually happen. The devil makes this kingdom's people infected by a disease called lolicon. Lolicon will take away people's life in silence.  Although zp is died, his friend, ywan is not a lolicon. Ywan is the only one in the country who is immune of lolicon, because he like the adult one so much.  As this country is going to hell, ywan want to save this country from lolicon, so he starts his journey. You heard about it and want to help ywan, but ywan questioned your IQ, and give you a question, so you should solve it to prove your IQ is high enough. The problem is about counting. How many undirected graphs satisfied the following constraints?

1. This graph is a complete graph of size n.
2. Every edge has integer cost from 1 to L.
3. The cost of the shortest path from 1 to n is k. Can you solve it? output the answer modulo 10^9+7

输入格式

The first line contains an integer T, denoting the number of the test cases. For each test case, the first line contains 3 integers n,k,L. T<=5 n,k<=12,L<=10^9.

输出格式

For each test case, output the answer in one line.

2
3 3 3
4 4 4

8
668

提示

没有写明提示

题目来源

By WJMZBMR