[Question]
  [
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 <= b <= 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  =>  6
7 5 4  =>  3013
3 2 3  =>  11
6 2 10  =>  101101
9 9 6  =>  6127
7 10 4  =>  504
758 9 19  =>  6645002302217537863
158596 8 20  =>  37212476700442254614
359221 2 40  =>  1101111111001100010101100000110001110001
New tests:
----------
9 6 3  =>  144
10 6 3  =>  544
```
This is code-golf, so the shortest entry wins.
  
[Answer]
# Mathematica, ~~57~~ 48 bytes
Saved 9 bytes thanks to @2012rcampion .
```
IntegerString[#!/#2^#!~IntegerExponent~#2,##2]&
```
[Answer]
## Python, 198 192 181 chars
```
def F(n,b,k):
 p=5820556928/8**b%8;z=0;e=f=x=1
 while n/p**e:z+=n/p**e;e+=1
 z/=1791568/4**b%4;B=b**(z+k)
 while x<=n:f=f*x%B;x+=1
 s='';f/=b**z
 while f:s=str(f%b)+s;f/=b
 return s
```
It's fast enough, ~23 seconds on the biggest example. And no factorial builtin (I'm looking at you, Mathematica!).
[Answer]
# Pyth, ~~26~~ 35 bytes
```
M?G%GHg/GHH.N>ju%g*GhHT^T+YslNN1T_Y
```
This is a function of 3 arguments, number, base, number of digits.
[Demonstration.](https://pyth.herokuapp.com/?code=M%3FG%25GHg%2FGHH.N%3Eju%25g*GhHT%5ET%2BYslNN1T_Y%3A9+6+3&debug=0)
The slowest test case, the final one, takes 15 seconds on my machine.
[Answer]
## PARI/GP, 43 bytes
Trading speed for space yields this straightforward algorithm:
```
(n,b,k)->digits(n!/b^valuation(n!,b)%b^k,b)
```
Each of the test cases runs in less than a second on my machine.
[Answer]
# Haskell, ~~111~~ 109 bytes
```
import Data.Digits
f n b k=digits b$foldl(((unDigits b.reverse.take k.snd.span(<1).digitsRev b).).(*))1[1..n]
```
Usage: `f 158596 8 20` -> `[3,7,2,1,2,4,7,6,7,0,0,4,4,2,2,5,4,6,1,4]`
Takes about 8 seconds for `f 359221 2 40` on my 4 year old laptop.
How it works: fold the multiplication (`*`) into the list `[1..n]`. Convert every intermediate result to base `b` as a list of digits (least significant first), strip leading zeros, then take the first `k` digits and convert to base 10 again. Finally convert to base `b` again, but with most significant digit first.
[Answer]
# [Dyalog APL](http://goo.gl/9KrKoM), 23 bytes
```
⌽k↑⌽{⍵↓⍨-⊥⍨0=⍵}b⊥⍣¯1⊢!n
```
This program works as long as the factorial does not exceed internal representation limit. In Dyalog APL, the limit can be raised by `⎕FR←1287`.
Assumes the variables n, b, and k have been set (e.g. `n b k←7 5 4`), but if you rather want prompting for *n*, *b*, and *k* (in that order) then replace the three characters with `⎕`.
[Answer]
# Python 3, 146 bytes
```
import math
i,f=input(),int
n=i.split()
e=math.factorial(f(n[0]))
d=''
while e>0:
 d=str((e%f(n[1])))+d;e=e//f(n[1])
print(d.strip('0')[-f(n[2]):])
```
I'm not sure the test cases will all run fast enough - the larger ones are very slow (as it is looping through the number).
Try it online [here](http://repl.it/lsT) (but be careful).
[Answer]
# Java, ~~303~~ ~~299~~ 296 bytes
```
import java.math.*;interface R{static void main(String[]a){BigInteger c=new BigInteger(a[1]),b=c.valueOf(1);for(int i=new Integer(a[0]);i>0;i--){b=b.multiply(b.valueOf(i));while(b.mod(c).equals(b.ZERO))b=b.divide(c);b=b.mod(c.pow(new Integer(a[2])));}System.out.print(b.toString(c.intValue()));}}
```
On my computer, this averages a little under a third of a second on the `359221 2 40` testcase. Takes input via command line arguments.
[Answer]
# bc, 75 bytes
```
define void f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(!x%b)x/=b}
x}
```
This uses some GNU extensions to reduce code size; a POSIX-conforming equivalent weighs in at 80 bytes:
```
define f(n,b,k){
obase=b
for(x=1;n;x%=b^k){
x*=n--
while(x%b==0)x/=b}
return(x)}
```
To keep run times reasonable, we trim the trailing zeros (`while(!x%b)x/=b`) and truncate to the final `k` digits (`x%=b^k`) as we compute the factorial (`for(x=1;n;)x*=n--`).
### Test program:
```
f(3, 10, 1)
f(7, 5, 4)
f(3, 2, 3)
f(6, 2, 10)
f(9, 9, 6)
f(7, 10, 4)
f(758, 9, 19)
f(158596, 8, 20)
f(359221, 2, 40)
f(9, 6, 3)
f(10, 6, 3)
quit
```
Runtime of the full test suite is approx 4¼ seconds on my 2006-vintage workstation.
[Answer]
## PHP, 80 bytes
```
function f($a,$b,$c){echo substr(rtrim(gmp_strval(gmp_fact($a),$b),"0"),-1*$c);}
```
Used as `f(359221,2,40)` for the last test case. Runs pretty smoothly for all test cases. 
[Try here !](https://ideone.com/yt2zb9)
]