그림 칠하기

올리버는 버그를 찾는 것뿐 아니라 그림 그리기도 좋아하는 고무 오리다. 올리버의 최근 그림은 $n$개의 부분으로 이루어져 있고, 각 부분은 서로 다른 색으로 칠해져 있다. 그림이 너무 뻔하다는 비평을 많이 들은 올리버는 $t$번의 반복으로 그림을 고치기로 했다. 각 반복에서 올리버는 다음 단계를 수행한다.

1. 올리버는 $1 \le i \le n$인 인덱스 $i$를 같은 확률로 무작위로 고르고, $i$번째 부분의 색을 기억한다.
2. 올리버는 다시 $1 \le j \le n$인 인덱스 $j$를 같은 확률로 무작위로 고르고, $j$번째 부분을 $i$번째 부분의 색으로 다시 칠한다. $j$번째 부분이 이미 그 색이면 아무것도 바뀌지 않는다. $i$와 $j$는 같을 수 있다.

올리버는 그림이 단조롭고 지루해질까 걱정한다. 그림에 서로 다른 색이 $k$개 이상 있으면 좋은 그림으로 본다. 마지막에 그림이 좋은 그림일 확률을 구하라.

첫 번째 줄에 문제 설명의 수 $n$, $t$, $k$가 주어진다 ($2 \le k \le n \le 10$, $1 \le t \le 10^{18}$).

답을 $10^9 + 7$로 나눈 나머지를 출력한다.

형식적으로, $m = 10^9 + 7$이라 하자. 답은 기약분수 $\frac{p}{q}$로 나타낼 수 있고, $p$와 $q$는 정수이며 $q \not\equiv 0 \pmod m$이다. $p q^{-1} \bmod m$과 같은 정수를 출력한다. 다른 말로, $0 \le x < m$이고 $x q \equiv p \pmod m$인 정수 $x$를 출력한다.

첫 번째 예제 설명: 그림에 색이 두 가지 있으므로, 한 번의 반복 후에도 그림이 그대로일 확률은 $\frac{1}{2}$이다.

두 번째 예제 설명: 두 번의 반복 후 색의 개수는 10에서 5보다 적은 수로 줄어들 수 없다. 따라서 모든 경우에 그림에는 색이 5개 이상 있다.