Brainstuck

You've invented a new programming language called Brainstuck. A Brainstuck program consists of a sequence of characters. The allowed characters are +, -, [, and ]. There is a single memory cell. This cell can hold a single integer of arbitrary size. Initially the cell’s value is 0. The Brainstuck interpreter processes each character in sequence using an instruction pointer. At the beginning of the execution of the program, the instruction pointer points to the first character of the program. After processing a character, the instruction pointer moves forward by one character. Each character corresponds to a command:

• + increases the value of the memory cell by 1.
• - decreases the value of the memory cell by 1.
• [ looks at the value of the memory cell. If it is zero, the instruction pointer moves to the matching ] command.
• ] looks at the value of the memory cell. If it is non-zero, the instruction pointer moves to the matching [ command.

The [ which matches a ] is decided according to the usual way of matching nested brackets. See the Notes for a formal definition. The program terminates when the instruction pointer moves past the last character.

A Brainstuck program is valid if and only if:

• There are no unmatched [ or ] characters.
• The execution of the program terminates after a finite number of steps.

Please count the number of valid Brainstuck programs that consist of exactly N characters and return this value modulo M.