luogu#P9006. [入门赛 #9] 神树大人挥动魔杖 (Hard Version)

[入门赛 #9] 神树大人挥动魔杖 (Hard Version)

题目背景

本题与 Easy Version 题意完全相同,仅有 n,kn,k 的数据范围有所不同。

题目描述

神树大人挥动魔杖,召唤出了 9×10n19 \times 10^{n-1} 只家养小精灵。每只家养小精灵都有一个互不相同的 nn 位数编号 aia_i

神树大人希望将这些家养小精灵分为 kk 组。第 pp 组的所有家养小精灵满足编号 aia_ikk 取模余 p1p-1,即 aip1(modk)a_i \equiv p-1 \pmod k

神树大人想要知道,每一组小精灵分别有多少只。由于答案可能很大,你只需要输出答案对 100,000,007100,000,007 取模的结果

输入格式

输入共一行两个整数,依次为 n,kn,k

输出格式

输出一行 kk 个整数,由空格分隔。第 ii 个整数代表第 ii 组小精灵的个数。

3 10
90 90 90 90 90 90 90 90 90 90

提示

对于 100%100\% 的数据,1n50001 \le n \le 50001k10001 \le k \le 1000