PEG Judge - WC15 Finals

2015-16 Woburn Challenge Finals - Senior Division

Problem 1: FuzzBiz

After 14 years of living in fearful hiding, the Head-Monkey and her band of primates have finally perfected their battle strategy to regain control of their native home of Scarberia. At last, they're ready to launch a ruthless series of attacks against the wicked cows who, under the leadership of Bo Vine, unjustly exiled the monkeys all those years ago!

Now, the cows had really become quite content with their Scarberian lives, free to eat their feed on farmer Daniel MacDonald's farm in peace. However, they weren't about to be taken by surprise by this turn of events. As everyone knows, all cows possess a geomagnetic sixth sense, which historically guided their ancestors during migrations. One day, while Bo Vine was out chewing his cud, his particularly potent sixth sense picked up on something rather peculiar. Detecting a disturbance in the electromagnetic field surrounding the Sacred Farm, Bo Vine swiftly realized that the monkeys' long overdue counterattack was imminent! As fast as he could, he rushed back to the barn, where the lethargic farmer had been nibbling a stalk of wheat. Standing before him, Bo Vine let out a thunderous bellow which could be heard throughout the entire countryside – "Dang, Daniel! The monkeys are back at it again with the bright plans!"

However bright these plans are, the Head-Monkey knows that victory will require a great deal of money to purchase supplies and ammunition. Alas, the monkeys have been in hiding for so many years that they were never able to find jobs and make money. To make up for this financial deficit, the Head-Monkey has decided to run a business on the side. Unfortunately, the monkeys do not possess many belongings that are in demand by the market... except for one – monkey fur is one of the most luxurious and prized materials in the fashion industry! The smooth, silky locks of any monkey's fur are in high demand by the world's finest coat designers and couturiers. In a stroke of genius, the Head-Monkey ordered all of her subordinates to shave off the fuzz on their bodies and donate it to the business. Before long, sales seemed to be booming – and yet, there were still some problems.

Monkeys aren't particularly renowned for their arithmetic. As sales grew, accounting errors were slipping through the cracks, resulting in unnecessary losses to their income. To practice their division skills, the Head-Monkey proposed that her accountants play the classic game of FizzBuzz. In FizzBuzz, players sit around in a circle and take turns counting incrementally, replacing any number divisible by three with the word "fizz", and any number divisible by five with the word "buzz". Numbers divisible by both three and five are replaced with "fizzbuzz". The game ends once a player misspeaks or once they hit N (1 ≤ N ≤ 10⁹). For example, a perfect game of FizzBuzz where N = 16 would sound like this:

1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, 16

Monkeys aren't particularly renowned for their articulateness. When the game gets long, no monkey is a fan of saying "…, five thousand seven hundred and ninety two, fizz, five thousand seven hundred and ninety four, buzz, …". Thus, the Head-Monkey invented her own variation of the game – FizzBuzzOok – which is streamlined for primates. The rules of FizzBuzzOok are almost identical to FizzBuzz, except that whenever a number is supposed to be said in FizzBuzz, the player should instead say "ook". As such, a perfect game of FizzBuzzOok where N = 16 would sound like this:

ook, ook, fizz, ook, buzz, fizz, ook, ook, fizz, buzz, ook, fizz, ook, ook, fizzbuzz, ook

Monkeys aren't particularly renowned for their memory. Sometimes, games of FizzBuzzOok would have to be paused as the monkeys went on banana breaks. When they returned, they would quickly lose track of where they had stopped! However, they would be able to remember what their desired goal of N was, along with what may have been said in the past M (1 ≤ M ≤ 10⁵; M ≤ N) turns. For example, the monkeys may remember that they were going for a game of N = 16 turns and vaguely recall the last M = 3 turns had been "ook, fizz, ook". In this case, there are two possible positions at which they could have paused – after either turn 4 or 13.

Given a sequence of words representing the past M turns, your task is to determine the number of possible positions at which the accountants could have paused, within a perfect game of N turns. Their recollection of what was said in the past M turns could very well be faulty, in which case the given sequence may not be a contiguous subsequence of the N turns of the game. In that case, you should report 0 as the number of possible positions.

In test cases worth 3/9 of the points, N ≤ 1000 and M ≤ 1000.

Input Format

The first line of input consists of two space-separated integers N and M.
M lines follow, with the i-th of these lines consisting of a single word that is either "ook", "fizz", "buzz", or "fizzbuzz" (for i = 1..M).

Output Format

Output a single integer – the number of possible positions that the game could have been paused at, or 0 if the given sequence of turns will never occur in a game of FizzBuzzOok up to N.