A. 计算异或和
time limit per test
3 s
memory limit per test
512 megabytes
input
standard input
output
standard output

给定两个正整数 $$$n,m$$$，对于所有满足以下两个条件的有序 $$$m$$$ 元组 $$$\{a_1,a_2,...,a_m\}$$$：

  1. $$$a_1+a_2+...+a_m=n$$$
  2. 任意 $$$1 \le i \le m$$$，$$$a_i$$$ 为非负整数

计算 $$$a_1 \bigoplus a_2 \bigoplus ... \bigoplus a_m$$$ 的和。

其中，两个有序 $$$m$$$ 元组 $$$\{a_1,a_2,...,a_m\}$$$ 与 $$$\{b_1,b_2,...,b_m\}$$$ 不同，当且仅当存在 $$$(1 \le i \le m)$$$，使得 $$$a_i\neq b_i$$$

输出答案对 $$$10^9+7$$$ 取模后的结果

Input

输入两个正整数 $$$n,m(1 \le n \le 10^{15} ,1 \le m \le 500)$$$

Output

输出一个整数，表示答案对 $$$10^9+7$$$ 取模后的结果

Examples
Input
4 2
Output
12
Input
20 10
Output
51871212
Note

样例解释：

对于第一个样例，所有符合条件的二元组为：$$$(0,4),(1,3),(2,2),(3,1),(4,0)$$$，对应的 $$$a_1 \bigoplus a_2$$$ 分别为 $$$4,2,0,2,4$$$，总和为 $$$12$$$。