Capba is doing a poetry analysis. He has scanned the lines of a poem and
determined which syllables are stressed and which are unstressed. There
are nineteen different "feet", that is, patterns of stressed and
unstressed syllables. `0`

represents an unstressed syllable and `1`

represents a stressed syllable:

```
00 pyrrhic
01 iamb
10 trochee
11 spondee
000 tribrach
001 anapest
010 amphibrach
011 bacchius
100 dactyl
101 amphimacer
110 antibacchius
111 molossos
0001 fourth paeon
0010 third paeon
0011 ionic a minore
0100 second paeon
0110 antispast
1000 first paeon
1001 choriamb
```

A line with the pattern `001001`

, for example could be

- two anapests;
- a pyrrhic, a trochee, and an iamb;
- a pyrrhic and a choriamb; or
- a third paeon and an iamb.

Capba is having some trouble determining which.

He decides to guess the breakdown of the line into feet, and, through
extensive shovelling, justify his assertion whether or not it be right
(this leads to excellent results if done properly.) He would like to
know how many different ways each line can be broken down into the feet
as listed above.

#### Input Specification

Line : A sequence of ones or zeroes, up to characters long,
corresponding to a pattern of stressed and unstressed syllables. `0`

represents an unstressed syllable, `1`

represents a stressed syllable.

#### Output Specification

An integer, on a single line – the number of ways that the given line can be broken down into feet, modulo .

#### Sample Input

`001001`

#### Sample Output

`4`

## Comments