"""
DP solution:

Space: O(d*target)
Time: O(d*f*target)
"""

def get_ways(d, f, target):
   # exclude invalid targets
   if target not in xrange(d, f*d+1):
       return 0
   # Initialize a 2d array where
   # each cell stores number of ways to get target per (i+1) dice
   targets = [ [0] * target for i in xrange(0, d) ]

   # fill in 1's for targets that can be got by 1 die
   # i.e., 1 way for each target that is
   # in range of [1, f] by 1 die
   for i in xrange(0, f):
       targets[0][i] = 1

   # calculate number of ways from 2-dice case to d-dice case
   # result in (N+1)-dice case will be based on N-dice case
   for i in xrange(0, d-1):
       # for each reachble N-dice target that we have rolled into
       for t in xrange(i+1, (i+1)*f+1):
           # since we added a new die, for each possible face
           for fs in xrange(1, min(target-t, f)+1):
               # add x more ways to (N+1) dice case for target t+fs
               # where x is the number of ways for N-dice case target t
               targets[i+1][t+fs-1] += targets[i][t-1]

   return targets[d-1][target-1]

if __name__ == "__main__":
   print get_ways(2, 6, 1)
   print get_ways(2, 6, 13)
   print get_ways(2, 6, 7)
   print get_ways(2, 6, 12)
   print get_ways(3, 6, 15)
   print get_ways(3, 6, 18)
   print get_ways(3, 6, 20)
   print get_ways(1000, 10, 10000)

"""
2 6-face dice to get 12:
6, 6

3 6-face dice to get 15:

3, 6, 6
6, 6, 3
6, 3, 6
4, 5, 6
4, 6, 5
5, 6, 4
5, 4, 6
6, 5, 4
6, 4, 5
5, 5, 5

test output:
6
1
10
1
1

"""