Last Nonzero Digits of a Factorial in Base You should write a program or function which given three positive integers n b k as input outputs or returns the last k digits before the trailing zeros in the base b representation of n!.

Example

n=7 b=5 k=4
factorial(n) is 5040
5040 is 130130 in base 5
the last 4 digits of 130130 before the trailing zeros are 3013
the output is 3013


Input


3 positive integers n b k where 2 &lt;= b &lt;= 10.
The order of the input integers can be chosen arbitrarily.


Output


A list of digits returned or outputted as an integer or integer list.
Leading zeros are optional.
Your solution has to solve any example test case under a minute on my computer (I will only test close cases. I have a below-average PC.).


Examples

New tests added to check correctness of submissions. (They are not part of the under 1 minute runtime rule.)

Input => Output (with the choice of omitting leading zeros)

3 10 1  =&gt;  6

7 5 4  =&gt;  3013

3 2 3  =&gt;  11

6 2 10  =&gt;  101101

9 9 6  =&gt;  6127

7 10 4  =&gt;  504

758 9 19  =&gt;  6645002302217537863

158596 8 20  =&gt;  37212476700442254614

359221 2 40  =&gt;  1101111111001100010101100000110001110001

New tests:
----------

9 6 3  =&gt;  144

10 6 3  =&gt;  544


This is code-golf, so the shortest entry wins.
Mathematica, 57 48 bytes
Saved 9 bytes thanks to @2012rcampion .
IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&amp;