Circular Limited Sums Challenge

Let's imagine an N-tuple of integers between 0 and M inclusive, and let's call it F.

There are (M + 1) ** N possible Fs in total.

How many such Fs satisfy all of the following inequalities (index is one-based)?


F[n] + F[n+1] &lt;= M for 1 &lt;= n &lt; N
F[N] + F[1] &lt;= M


Write a program or function that takes two positive integers N and M and outputs the answer in any convenient form.

Test Cases

(N,M) =&gt; Answer

(1,1) =&gt; 1
(2,1) =&gt; 3
(3,1) =&gt; 4
(4,1) =&gt; 7

(1,2) =&gt; 2
(2,2) =&gt; 6
(3,2) =&gt; 11
(4,2) =&gt; 26

(10,3) =&gt; 39175
(10,4) =&gt; 286555
(10,5) =&gt; 1508401

(25,3) =&gt; 303734663372
(25,4) =&gt; 43953707972058
(25,5) =&gt; 2794276977562073

(100,3) =&gt; 8510938110502117856062697655362747468175263710
(100,4) =&gt; 3732347514675901732382391725971022481763004479674972370
(100,5) =&gt; 60964611448369808046336702581873778457326750953325742021695001


Explanation

M (max value of element) = 1

F[1] + F[1] &lt;= 1; F = [0]
(1,1) =&gt; 1

F[1] + F[2] &lt;= 1; F = [0,0], [0,1], [1,0]
(2,1) =&gt; 3

F = [0,0,0], [0,0,1], [0,1,0], [1,0,0]
(3,1) =&gt; 4

F = [0,0,0,0], [0,0,0,1], [0,0,1,0], [0,1,0,0], [0,1,0,1], [1,0,0,0], [1,0,1,0]
(4,1) =&gt; 7

---

M = 2

F[1] + F[1] &lt;= 2; F = [0], [1]
(1,2) =&gt; 2

F = [0,0], [0,1], [0,2], [1,0], [1,1], [2,0]
(2,2) =&gt; 6

F = [0,0,0], [0,0,1], [0,0,2], [0,1,0], [0,1,1], [0,2,0], [1,0,0], [1,0,1],
[1,1,0], [1,1,1], [2,0,0]
(3,2) =&gt; 11

(4,2) =&gt; 26 (left as exercise for you)


Rules


This is a restricted-complexity challenge. The time complexity of your code should be polynomial in M and N (e.g. you can't generate all (M + 1) ** N tuples and then check for the condition). Please explain your approach in your submission.
Standard code-golf rules apply. The shortest answer in bytes wins.
Python with numpy, 59 bytes



lambda M,N:trace(mat(tri(M+1)[::-1])**N)
from numpy import*


Try it online!

Uses matrix multiplication to count paths. If float precision is an issue, the mat could specify mat(...,int).