E. Дэд дарааллуудыг тооцоолох

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

$k$-тын тооллын системд бичигдсэн $n$ тооны цифрүүдийн нийлбэр нь $s_{k}(n)$-тэй тэнцүү гэж үзье. Жишээлбэл: $s_{2}(5) = s_{2}(101_{2}) = 1 + 0 + 1 = 2$, $s_{3}(14) = s_{3}(112_{3}) = 1 + 1 + 2 = 4$.

$a_{0}, ..., a_{n - 1}$ бүхэл тоонуудын дарааллыг $a_{j}=s_{k}(j)\ mod\ k$ дүрмээр үүсгэе. Таны даалгавар бол $a_{0}, ..., a_{n - 1}$ дарааллын ялгаатай дэд дарааллуудын тоог тооцоолох юм. Хариуг $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Хэрвээ $a_{1} = b_{i_{1}}$, ..., $a_{k} = b_{i_{k}}$ байх $1 ≤ i_{1} < ... < i_{k} ≤ l$ индексүүдийн дараалал байдаг бол $a_{1}, ..., a_{k}$ дарааллыг $b_{1}, ..., b_{l}$ дарааллын дэд дараалал гэнэ. Мөн хоосон дараалал (тэг ширхэг элементттэй дараалал) нь ямар ч дарааллын дэд дараалал болно.

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан $n$ ба $k$ ($1 ≤ n ≤ 10^{18}$, $2 ≤ k ≤ 30$) бүхэл тоонуудыг агуулна.

Гаралт

Бодлогын хариуг $10^{9} + 7$-д хуваагаад гарсан үлдэгдлийг нэг мөрөнд хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
4 2
Гаралт
11
Оролт
7 7
Гаралт
128

Тэмдэглэл

Эхний жишээнд $a_{i}$ дараалал нь дараах байдалтай харагдана: $(0, 1, 1, 0)$. Боломжит бүх дэд дарааллууд нь:

$(), (0), (0, 0), (0, 1), (0, 1, 0), (0, 1, 1), (0, 1, 1, 0), (1), (1, 0), (1, 1), (1, 1, 0).$

Хоёр дахь жишээнд $a_{i}$ дараалал нь дараах байдалтай харагдана: $(0, 1, 2, 3, 4, 5, 6)$. Энэ дарааллын дэд дарааллууд нь 0-ээс 6 хүртэлх тоонуудаар байгуулагдсан бүх өсөх дарааллууд юм. Тиймээс $2^{7} = 128$ дарааллууд байгааг хялбархан харж болно.

Сэтгэгдлүүдийг ачааллаж байна...