TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4364
  • 题目
  • P4364Hard Nim
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : Time Limit: 1 Sec Memory Limit: 128 MB
    问题描述

    Claris和NanoApe在玩石子游戏,他们有n堆石子,规则如下:

    1. Claris和NanoApe两个人轮流拿石子,Claris先拿。

    2. 每次只能从一堆中取若干个,可将一堆全取走,但不可不取,拿到最后1颗石子的人获胜。

    不同的初始局面,决定了最终的获胜者,有些局面下先拿的Claris会赢,其余的局面Claris会负。

    Claris很好奇,如果这n堆石子满足每堆石子的初始数量是不超过m的质数,而且他们都会按照最优策略玩游戏,那么NanoApe能获胜的局面有多少种。

    由于答案可能很大,你只需要给出答案对10^9+7取模的值。

    输入格式

    含若干组数据

    对于每组数据:

    共一行两个正整数n和m。

    每组数据有1<=n<=10^9, 2<=m<=50000。

    不超过10组数据。

    输出格式

    对于每组数据,输出一行一个整数,表示计算结果

    样例输入

    3 7
    4 13

    样例输出

    6
    120


    来源  Topcoder SRM 518 Div1