题目描述

定义P为Σ_{d|N}C(N,d)，求G^P对999911659取模的结果。C(N,d)为从N个不同文字中选d个的方案数。

本题为一本通1651的本地训练修订版。

输入

一行N G，1≤N,G≤10^9。

输出

输出一个0..999911658整数。

输入样例

4 2

输出样例

2048

修订说明

纠正描述出现9999116594与输出999911659冲突，统一为999911659；保留原N/G完整范围。

本地修订与来源

本题为经授权补全的本地训练修订版，原始公开题面保留在采集档案；修订了：纠正描述出现9999116594与输出999911659冲突，统一为999911659；保留原N/G完整范围。。此处题意、范围和输出约定以本修订版为准，不冒称原站或官方原版。原题链接：https://ybt.ssoier.cn/problem_show.php?pid=1651。

评测数据说明

本题使用按题意独立构造、以独立程序核对的训练数据及公开样例，共7个测试点，非原站或官方原始数据。总分100分。