题号：NC20331
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
随着iPig在P++语言上的造诣日益提升，他形成了自己一套完整的代 码库。猪王国想参加POI的童鞋们都争先恐后问iPig索要代码库。iPig不想把代码库给所有想要的小猪，只想给其中的一部分既关系好又 肯出钱的小猪，于是他决定举行了一个超大型拍卖会。 在拍卖会上 ，所有的N头小猪将会按照和iPig的好感度从低到高，从左到右地在i Pig面前站成一排。
每个小猪身上都有9猪币（与人民币汇率不明）， 从最左边开始，每个小猪依次举起一块牌子，上面写上想付出的买代码库的猪币数量（1到9之间的一个整数）。大家都知道，如果自己付的钱比左边的猪少，肯定得不到梦寐以求的代码库，因此从第二只起 ，每只猪出的钱都大于等于左边猪出的价钱。最终出的钱最多的小猪 （们）会得到iPig的代码库真传，向着保送PKU（Pig Kingdom Unive rsity）的梦想前进。
iPig对自己想到的这个点子感到十分满意，在 去现场的路上，iPig就在想象拍卖会上会出现的场景，例如一共会出 现多少种出价情况之类的问题，但这些问题都太简单了，iPig早已不敢兴趣了，他想要去研究更加困难的问题。
iPig发现如果他从台上往 下看，所有小猪举的牌子从左到右将会正好构成一个N位的整数，他现在想要挑战的问题是所有可能构成的整数中能正好被P整除的有多 少个。由于答案过大，他只想要知道答案mod 999911659就行了。
输入描述:
一行：两个数N（1 ≤ N ≤ 10^18）、P(1 ≤ P ≤ 500)，用一个空格分开。
输出描述:
一行：一个数，表示答案除以999911659的余数。
