Arranging Fenceposts
Ruby: 106 98 93 bytes
Update: Changed cache key type from strings to arrays. (-5)
Update:  Storing the initial condition in the cache payed out quite well. (-8)
However, it increases the runtime for the test case to roughly 2 seconds.
I simply use memoization. I guess it can be further golfed as my Ruby skills are far from perfect.
@m={[0,0]=&gt;1}
def f(l,u,c,s)
  @m[[c,s]]||=s&lt;0?0:(l..u).map{|x|f(l,u,c-1,s-x)}.reduce(:+)
end

Note that it runs for only one test case at a time, since I don't cache the min and max values (l and u, respectively). Here is my output for 1 10 100 700:
121130639107583774681451741625922964085713989291260198434849317132762403014516376282321342995

real    0m0.316s
user    0m0.312s
sys     0m0.004s