题目描述

ことり给战舰机密设置了一个密码，并打算让 おりがみ 测试，おりがみ觉得太烦了（还要去跟踪 しどう），便把这个任务抛给了你，但又因为心里过意不去（出题人不想太毒），她只要你给她答案对 $1e9+7$ 取模后的结果。

密码形同下面这个问题: 对于给定的 $n,k$ 求有多少有序数对 $(a,b,c)$ 满足 $1\le a,b,c\leq n (a,b,c\in N^*)$ 且 $a+b+c=t\times k (t\in N)$。

注意有序数对的意思是 $(A,B,C)$ 与 $(A,C,B)$ 视为不同的方案。

输入格式

输入共一行两个整数 $n,k$。

输出格式

输入共一行。即答案对 $10^9+7$ 取模后的结果。

3 2

13

10 2

500

样例说明 1

1 1 2
1 2 1
1 2 3
1 3 2
2 1 1
2 1 3
2 2 2
2 3 1
2 3 3
3 1 2
3 2 1
3 2 3
3 3 2

数据规模与约定

对于 $15\%$ 的数据 $n\leq 200$。
对于 $30\%$ 的数据 $n\leq 2\times 10^3$。
对于 $45\%$ 的数据 $n\leq 3\times10^5$。
对于 $60\%$ 的数据 $n\leq 10^7$。
对于 $80\%$ 的数据 $n\leq 10^{12}$，且保证 $\frac{n}{k}\leq 5\times10^6$。
对于 $100\%$ 的数据 $1\le n\leq10^{12}$，$1\le k\leq n\times3$。