Description

——你现在还留着那个时间转换器？你竟然做出这样草率而愚蠢的事！

——教授，我向你保证—

——真是可耻，赫敏 · 格兰杰！（面对教授的怒气，赫敏往后退缩）

· · · · · ·

仿佛又回到了在霍格沃茨的第三个年头，为了营救小天狼星布莱克和鹰头马身有翼兽巴克比克，赫敏等很好的利用了时间转换器。

时间停止，然后掉头，踌躇须臾，开始倒转，起初转的很慢……

而时间转换器的使用是有一定要求的。每个转换器上，都标有一个数字 $k$ 代表它的型号。时间轴可看做一个长度为 $n$ 的整数序列 $a$。当序列 $a$ 满足以下两个条件时，我们就认为它符合要求：

1. $1 \leq a_i \leq k$.
2. 序列上任意非空子段和 $S \bmod k \neq 0$.

现在赫敏已经知道了 $n,k$，她想知道有多少个序列 $a$ 符合要求。由于答案可能很大，请你输出答案对 $10^9+7$ 取模的值。

Format

Input

一行两个数 $n,k$。

Output

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

Samples

2 3

2

33 782

765974260

解释

对于样例一，满足条件的序列仅有 $[1,1]$ 和 $[2,2]$。

Limitation