CF587B Duff in Beach

While Duff was resting in the beach, she accidentally found a strange array $ b_{0},b_{1},...,b_{l-1} $ consisting of $ l $ positive integers. This array was strange because it was extremely long, but there was another (maybe shorter) array, $ a_{0},...,a_{n-1} $ that $ b $ can be build from $ a $ with formula: $ b_{i}=a_{i\ mod\ n} $ where $ a\ mod\ b $ denoted the remainder of dividing $ a $ by $ b $ . Duff is so curious, she wants to know the number of subsequences of $ b $ like $ b_{i1},b_{i2},...,b_{ix} $ ( $ 0

The first line of input contains three integers, $ n,l $ and $ k $ ( $ 1

Print the answer modulo $ 1000000007 $ in one line.

In the first sample case, . So all such sequences are: , , , , , , , ,  and .