Count sign sequences
A sequence of + and - signs, such as this one:
can be transformed into a sequence of integers according to the following rules:
- Begin with 0
- When you see a + sign, add 1 to get the next term
- When you see a - sign, subtract 1 to get the next term
For example, the sequence +-++-+-++--- gives rise to the following sequence of integers: 0, 1, 0, 1, 2, 1, 2, 1, 2, 3, 2, 1, 0.
Call a sequence of + and - signs good if the resulting sequence of integers contains no negative numbers and ends with 0. Our sequence +-++-+-++--- is a good sequence of length 12. The sequences +++-- and +--+ are not good.
Let N be the number of all good sequences of + and - signs of length 40. Find the first three digits of N.