Description

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. Y*wan 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, y*wan 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

Format

Input

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. Y*wan 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, y*wan 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

Output

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

Samples

2
3 3 3
4 4 4

8
668

Limitation