题目描述

小青遇到了这样一个问题：TeStatic and Moat played poker at teaching building 9 yesterday for a whole night. TeStatic owed Moat 1024 yuan. TeStatic asks Sheath for help. Sheath is puzzled by a problem about power sum. He'd like to find the double of the sum of the product of C(n,k) and ps(2j-1,n), when j passes through the first k positive integers.

输入格式

The input consists of multiple test cases. Each test case contains three integers n, k, and m.

输出格式

For each test case, output the remainder when the value divided by 10^9+7.

样例

样例 1

输入 # 1

3 1 100

输出 # 1

2048