# 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:

1. Begin with 0
2. When you see a + sign, add 1 to get the next term
3. 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.

×