問題文

以下の条件を全て満たす数列$A_1,A_2,...$は何通り存在するでしょうか？$1,000,000,007$で割った余りを求めてください。
・要素数は$A$個以上$B$個以下である。
・各要素は全て非負整数である。
・各要素は$0$以上$2^K$未満である。
・$i≠j$なる任意の正整数の組$(i,j)$について、$A_i,A_j$がともに存在するならば、$(A_i⊕A_j)-(A_i+A_j)=0$である。ただし、ここで$⊕$はbitごとの排他的論理和を表す。
なお、2つの数列$X,Y$が異なるとは、$X,Y$の要素数が異なる、または$X_k≠Y_k$となるような正整数$k$が存在することを指します。

制約

・入力は全て整数である。
・$2≦A≦B≦10^9$
・$0≦K≦5×10^4$

入力

入力は以下の形式で与えられる。

A B K

出力

条件を全て満たすような数列の個数を$1,000,000,007$で割った余りを出力してください。

入力例1

8 62 0 

出力例1

55

$0$のみからなる要素数$8,9,10,...62$の計$55$個の数列が条件を満たします。

入力例2

41 82 69

出力例2

116525415

入力例3

8 11 2014

出力例3

811000209