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 Format:
Line 1: A sequence of ones or zeroes, up to 10000 characters long, corresponding to a pattern of stressed and unstressed syllables. 0 represents an unstressed syllable, 1 represents a stressed syllable.

Output Format:
An integer, on a single line - the number of ways that the given line can be broken down into feet, modulo 10007.

Sample Input:

Sample Output:

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jan 24, 2009
Author: bbi5291

Languages Allowed:

Comments (Search)

OMG this made me so confused and I checked my program for bugs for so many times.
It's kinda stupid I didn't realize that, but I think it would be better to include that in the problem description as well.

This problem gives me the chills, lol. brings back unpleasant memories of an even more unpleasant unit.

My brain + scansion = NO.

I can never figure out stressed/unstressed syllables.


Am I exceeding stack space?
Are the strings passed by value not set to 10k chars?
Is it something wrong with the memoizing?

Well, you're using a ton of memory. Every time you recurse, you create a new copy of the string ss, which can be 10000 chars long. And you might recurse with depth 10000.
Make recursive vars global whenever possible.

Any way of decomposing a line of one or more syllables into feet must consist of a foot at the end plus a way of decomposing the remaining syllables into feet. Also, if two decompositions end with different feet, they are different. This suggests a substructure.

I bet almost no one knows/remembers who that is.
Brian, I can't believe you put him in a problem =P