p_order

Let a be a list that stores a permutation a = (a₀, a₁, a₂, …, a_n – 1) of order n, and let p be a natural number. We say that the permutation is p-sorted if for any x > 0 index, it is true that a_x > a_{[(x – 1) / p]}, where [(x – 1) / p] is used to denote the integer part of (x – 1) / p.

For example, (1,3,2,5,4) is a 3-sorted order 5 permutation, because a₁ = 3 > 1 = a₀, a₂ = 2 > 1 = a₀, a₃ = 5 > 1 = a₀, a₄ = 4 > 3 = a₁.

There exist altogether 12 different order 5 permutations that are 3-sorted. These are the following: (1,2,3,4,5), (1,2,3,5,4), (1,2,4,3,5), (1,2,4,5,3), (1,2,5,3,4), (1,2,5,4,3), (1,3,2,4,5), (1,3,2,5,4), (1,3,4,2,5), (1,3,5,2,4), (1,4,2,3,5), (1,4,3,2,5).

Given n and p, calculate the number of p-sorted order n permutations modulo 666013.

Input Specification

The input has 10 lines, each of which containing natural numbers n and p, separated by a space (1 < p < n ≤ 600 000). Each tuple represents a problem that needs to be solved.

Output Specification

The output needs to contain 10 numbers in separate lines, giving the corresponding answers for the 10 input problems.

Sample Input

1. 5 2
2. 5 3
3. 6 3
4. 1234 8
5. 5000 100
6. 141414 200
7. 414141 101
8. 345 234
9. 54321 321
10. 600000 81

download as text file

Output for Sample Input

1. 8
2. 12
3. 40
4. 530546
5. 141922
6. 142664
7. 471427
8. 526978
9. 151098
10. 596797

download as text file