Fear and pandemonium have struck the hippopotami of North Yorkshire! A monstrous creature from the wilderness of Australia has found its way to the county. It is a horrifying yellow-green winged beast, over half a foot tall. The hippos have dubbed it The Terrifying Canary-Bird. They cower whenever its wings darken the skies, and worse still, the fear is making them lose their appetites.
The hippopotami sleep in the Great Glen, which may be thought of as an R by C grid of squares of varying heights. The Great Glen is rather hilly - no two adjacent squares (squares sharing an edge) have the same height. The Terrifying Canary-Bird regularly swoops across the grass of the Great Glen, terrorising all the hippos it passes.
As part of their grand plan to scare the Terrifying Canary-Bird away from North Yorkshire forever, the hippos set out to study the Canary-Bird's movements closely. Based on many weeks of careful note-taking, the hippos have constructed a formal mathematical definition for a canary-bird path.
A canary-bird path is a sequence of 1 or more squares such that:
Your task is to write a program that takes as input a description of the Great Glen and outputs the number of possible canary-bird paths, modulo 1,000,003.
Output should consist of a single integer, the number of possible canary-bird paths modulo 1,000,003.
2 3 7 6 7 6 8 9
The local maxima are the top-left and bottom-right squares. The local minima are the squares of height six. The five canary-bird paths are shown below.
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.
For 30% of the available marks, R, C ≤ 50.