做题网站推荐: OpenJudge VIJOS UOJ CF JOYOI CODEVS 洛谷 RQNOJ BZOJ POJ HDU 牛客网

本站题目推荐: 高精度 模拟 排序 递推 贪心 递归 搜索 动态规划 数学 图论 数据结构 签到 实名认证 卡评测举报

输入输出 变量类型 顺序结构 选择结构 循环结构 一维数组 NOIP 资源下载


问题 2931. -- 「一本通 6.6 例 4」古代猪文

2931: 「一本通 6.6 例 4」古代猪文

时间限制: 1 Sec  内存限制: 512 MB
提交: 0  解决: 0
[上一题][提交][讨论版][状态][下一题]

题目描述

原题来自:SDOI 2010

猪王国的文明源远流长,博大精深。

iPig 在大肥猪学校图书馆中查阅资料,得知远古时期猪文文字总个数为 NNN。当然,一种语言如果字数很多,字典也相应会很大。当时的猪王国国王考虑到如果修一本字典,规模有可能远远超过康熙字典,花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然,猪王国的文字后来随着历史变迁逐渐进行了简化,去掉了一些不常用的字。

iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载,那个朝代流传的猪文文字恰好为远古时期的 kkk 分之一,其中 kkkNNN 的一个正约数(可以是 111NNN)。不过具体是哪 kkk 分之一,以及 kkk 是多少,由于历史过于久远,已经无从考证了。

iPig 觉得只要符合文献,每一种能整除 NNNkkk 都是有可能的。他打算考虑到所有可能的 kkk。显然当 kkk 等于某个定值时,该朝的猪文文字个数为 Nkfrac NkkN。然而从 NNN 个文字中保留下 Nkfrac NkkN 个的情况也是相当多的。iPig 预计,如果所有可能的 kkk 的所有情况数加起来为 PPP 的话,那么他研究古代文字的代价将会是 GGGPPP 次方。

现在他想知道猪王国研究古代文字的代价是多少。由于 iPig 觉得这个数字可能是天文数字,所以你只需要告诉他答案除以 999911659999911659999911659 的余数就可以了。

输入

输入有且仅有一行:两个数 N,GN,GN,G,用一个空格分开。

输出

输出有且仅有一行:一个数,表示答案除以 999911659999911659999911659 的余数。

提示

样例输入

4 2

样例输出

2048

10%10\%10% 的数据中,1≤N≤501le Nle 501N50

20%20\%20% 的数据中,1≤N≤10001le Nle 10001N1000

40%40\%40% 的数据中,1≤N≤1051le Nle 10^51N105

100%100\%100% 的数据中,1≤G≤1091le Gle 10^91G1091≤N≤1091le Nle 10^91N109

标签

[上一题][提交][讨论版][状态][下一题]