Our chef Remy ate all the delicious food he made. As a result, he has become really fat :). Chef’s assistant Linguini has taken up the herculean task of bringing back chef Remy to shape.
Linguini has built a fence which has N planks in a straight line. The planks are numbered 1 to N from left to right. In front of M of these N planks, he has put a bucket of paint. The paints may be of different colors. Each color is represented by any uppercase letter (A-Z). Chef Remy needs to paint the fence. He uses his painting brush to paint the fence.
Chef Remy starts the task by choosing a plank which has a bucket of paint in front of it and dips his brush in the bucket. He starts walking randomly along the straight fence passing the planks. He never moves out of the fence. Note that walking randomly along a fence means that Remy keeps walking all the time along his current direction. He can change his direction any time he wishes. Moving along a straight fence has just two directions, forward and backward.
Linguini has devised the following recipe for painting the fence.
Each bucket has an infinite supply of paint. The brush can carry paint of a single color at any time. When Remy passes a paint bucket, the brush acquires the color in the bucket first. Every plank that Remy passes in his random walk must be colored with the color in the brush. A plank will be colored completely. A plank can be colored multiple times. A plank's color is the latest color it is painted with.
A fence coloring is complete when each plank is painted with some color. Linguini is watching Remy dance around with colors. He wonders how many different complete fence colorings will he be able to see. Two fence colorings are different if there is atleast one plank numbered x whose color differs in both the colorings. Find out the number of different complete fence colorings modulo 1000000009.
can someone explain me the last four lines in simple way,that what i have to do and what is asking here to find.thanks in advace