题目描述

给定整数 $n,q$，计算 $q^{\sum_{d|n} C_n^d} \bmod 999911659$。

输入格式

输入包括一行，包含两个整数 $n，q$，用一个空格隔开。

输出格式

输出包括一行，包含一个整数表示最终结果。

样例

输入样例：

4 2

输出样例：

2048

样例解释

$n=4, q=2$

$n$ 的正因数 $d$：$1,2,4$

• $C_4^1 = 4$
• $C_4^2 = 6$
• $C_4^4 = 1$

$\sum_{d|n} C_n^d = 4 + 6 + 1 = 11$

$q^{\sum_{d|n} C_n^d} = 2^{11} = 2048$

取模 $999911659$ 后（因为 $2048 < 999911659$），结果仍为 $2048$。 提示：对于 $n$ 的每一个正因数 $d$，都有一个 $C_n^d$ 的值，将它们全部加起来得到的和就是 $\sum_{d|n} C_n^d$。

数据范围

• $1 \le n,q \le 10^9$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB