The Stress Test Lied

State of play: your solution fails on test 3 of 40. You have run a stress test against a brute force on 100,000 random cases with $n$ between 1 and 8 and values in $[1, 5]$ , and they agree on every one. You have 25 minutes left.

What does this combination of facts point at?

It is almost certainly integer overflow, which is the most common cause of Wrong Answer.

The bug is somewhere the generator cannot reach. Test 3 is early, so it is probably still small, which means the mismatch is most likely in reading input, in output format, or in a constraint corner the generator excludes (a value at the maximum, $n$ at the maximum, an empty answer). Re-read the statement and your I/O before you touch the algorithm.

The core algorithm is wrong and the stress test was simply lucky. Rewrite the solution from the recurrence.

The generator needs more iterations; 100,000 is low for this class of bug. Extend the run to several million.