GCD and Bitwise XOR Summation

Given two positive integers \( n \) and \( k \). Define the function \( f(x)=\sum_{i=1}^{x}\gcd(i, i\oplus x)^k \), where \( \gcd(a,b) \) denotes the greatest common divisor of \( a \) and \( b \), and \( \oplus \) denotes the bitwise XOR operator (as in C++ with the ^ operator). Compute \( \sum_{x=1}^{n} f(x) \) modulo \( 10^9+7 \).

inputFormat

The input consists of a single line containing two space-separated positive integers, \( n \) and \( k \).

outputFormat

Output a single integer: the value of \( \sum_{x=1}^{n} f(x) \) modulo \( 10^9+7 \).

sample

3 1

9