CF305D Olya and Graph

Olya has got a directed non-weighted graph, consisting of $ n $ vertexes and $ m $ edges. We will consider that the graph vertexes are indexed from 1 to $ n $ in some manner. Then for any graph edge that goes from vertex $ v $ to vertex $ u $ the following inequation holds: $ v<u $ . Now Olya wonders, how many ways there are to add an arbitrary (possibly zero) number of edges to the graph so as the following conditions were met: 1. You can reach vertexes number $ i+1,i+2,...,n $ from any vertex number $ i $ $ (i<n) $ . 2. For any graph edge going from vertex $ v $ to vertex $ u $ the following inequation fulfills: $ v<u $ . 3. There is at most one edge between any two vertexes. 4. The shortest distance between the pair of vertexes $ i,j $ $ (i<j) $ , for which $ j-i

The first line contains three space-separated integers $ n,m,k $ $ (2

Print a single integer — the answer to the problem modulo $ 1000000007 $ $ (10^{9}+7) $ .

In the first sample there are two ways: the first way is not to add anything, the second way is to add a single edge from vertex $ 2 $ to vertex $ 5 $ .