代码拍卖会(Code Auction)

题目描述

随着 iPig 在 P++ 语言上的造诣日益提升，他形成了自己一套完整的代码库。猪王国想参加 POI 的童鞋们都争先恐后问 iPig 索要代码库。iPig 不想把代码库给所有想要的小猪，只想给其中的一部分既关系好又肯出钱的小猪，于是他决定举行了一个超大型拍卖会。

在拍卖会上，所有的 $N$ 头小猪将会按照和 iPig 的好感度从低到高，从左到右地在 iPig 面前站成一排。每个小猪身上都有 $9$ 猪币（与人民币汇率不明），从最左边开始，每个小猪依次举起一块牌子，上面写上想付出的买代码库的猪币数量（$1$ 到 $9$ 之间的一个整数）。大家都知道，如果自己付的钱比左边的猪少，肯定得不到梦寐以求的代码库，因此从第二只起，每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪（们）会得到 iPig 的代码库真传，向着保送 PKU（Pig Kingdom University）的梦想前进。

iPig 对自己想到的这个点子感到十分满意，在去现场的路上，iPig 就在想象拍卖会上会出现的场景，例如一共会出现多少种出价情况之类的问题，但这些问题都太简单了，iPig 早已不感兴趣了，他想要去研究更加困难的问题。iPig 发现如果他从台上往下看，所有小猪举的牌子从左到右将会正好构成一个 $N$ 位的整数，他现在想要挑战的问题是所有可能构成的整数中能正好被 $P$ 整除的有多少个。由于答案过大，他只想要知道答案 $\bmod\ 999911659$ 就行了。

输入格式

有且仅有一行两个数 $N\ (1 \le N \le 10^{18})$ 和 $P\ (1 \le P \le 500)$，用一个空格分开。

输出格式

有且仅有一行一个数，表示答案除以 $999911659$ 的余数。

样例输入 #1

2 3

样例输出 #1

15

数据范围

样例解释

方案可以是：$12,\allowbreak 15,\allowbreak 18,\allowbreak 24,\allowbreak 27,\allowbreak 33,\allowbreak 36,\allowbreak 39,\allowbreak 45,\allowbreak 48,\allowbreak 57,\allowbreak 66,\allowbreak 69,\allowbreak 78,\allowbreak 99$，共 $15$ 种。

数据规模

知识点与难度

本题涉及的知识点从属于 NOI，难度（CF Rating）：2300。

测试点分布

出处：原题链接