背景

小学生们放假了!他们厌倦了常玩的“石头剪刀布”、“捉迷藏”、“过家家”……他们开始自己创造游戏!

描述

MT学校的小学生来自全国各地,放假以后很难在一起玩,所以他们创造了一个只需自己一人就可以玩的游戏!一行有N个格子,编号为0~N-1,编号为0的格子上的数为1,然后他们要依次算出每个格子上的数,开学以后他们要比比谁算的最多。对于编号为i的格子(i > 0),他们计算出步长 L = gcd(i + 1, M),其中M为他们商量好的正整数,gcd(a, b)表示a和b的最大公约数。编号为i的格子上的数等于所有编号为k的格子上的数的和,其中 k mod L = 0,且 0 <= k < i。小学生LJ非常聪明,他自己定义了一个函数:

f(0) = 1,f(x) = 9f(x - 1) (x > 0)

他算出了第f(99)个格子上的数字!显然正常人不可能完成这个任务,所以我们只需要算出前1018个格子上的数字对109+9取模的值就可以了!

输入格式

两个用空格隔开的整数N和M。

输出格式

一个整数,表示第N个格子(即编号为N-1的格子)上的数字对109+9取模的值。

样例输入

10 3

样例输出

84

样例解释

前10个格子上的数分别是 1, 1, 1, 3, 6, 4, 16, 32, 20, 84

数据范围与约定

对于100%的数据,1 <= N <= 1018,1 <= M <= 200。

单点时间限制2s(如果你总是超时,请再仔细想想哪里可以优化……)。

来源

原创