题目描述

给定整数 $\red{n,q}$ ，计算 $\red{ q^{ \sum{_{d|n} C_n^d } } Mod \ 999911659 }$

输入格式

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

输出格式

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

样例

输入样例

4 2

输出样例

2048

提示

$\red{1≤n,q≤10^9}$

对于 $\red n$ 的每一个正因数 $\red d$ ，都有一个 $\red{C_n^d}$ ​的值，将它们全部加起来得到的和就是 $\red{ \sum_{d|n} C_n^d}$