# Count sign sequences

**Computer Science**Level 4

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**.