Maybe it is not very fast, but you can calculate the ways that you make $$$i$$$ steps without going out by fft. Edit: Actually, we don't need fft, because we only need to know the sum of the coefficients.

To compute the 1 dimensional case, you need to know $$$\frac{\text{maxsteps}}{n}$$$ many times of answers of $$$\sum_{i=0}^y C^x_i$$$, I remember this can be done in around $$$O(T \log^2T)$$$ time, but I don't think it would be very efficient (https://www.cnblogs.com/tiatto/p/17224480.html) or (https://www.luogu.com.cn/blog/ducati/zu-ge-shuo-qian-zhui-hu-wen-ti)

In practice, The best way to compute the 1-dimensional case might be naive dp, and the time complexity is $$$O(n\times \text{maxsteps})$$$, where $$$n = \max(n, m)$$$