問題文
以下の条件を全て満たす数列A1,A2,...は何通り存在するでしょうか?1,000,000,007で割った余りを求めてください。
・要素数はA個以上B個以下である。
・各要素は全て非負整数である。
・各要素は0以上2K未満である。
・i=jなる任意の正整数の組(i,j)について、Ai,Ajがともに存在するならば、(Ai⊕Aj)−(Ai+Aj)=0である。ただし、ここで⊕はbitごとの排他的論理和を表す。
なお、2つの数列X,Yが異なるとは、X,Yの要素数が異なる、またはXk=Ykとなるような正整数kが存在することを指します。
制約
・入力は全て整数である。
・2≦A≦B≦1000
・0≦K≦500
入力
入力は以下の形式で与えられる。
出力
条件を全て満たすような数列の個数を1,000,000,007で割った余りを出力してください。
入力例1
出力例1
0のみからなる要素数8,9,10,...62の計55個の数列が条件を満たします。
入力例2
出力例2