How Many Holidays?
Daniel is going on a adventure holiday lasting nine days. Each day he either skis, snowboards, surfs, kayaks or rests. Each day he does exactly one of these activities. He never does different watersports on consecutive days or different sports involving snow on consecutive days and he never rests for more than one day in a row. What are the last three digits in the number of possible different holidays he can go on.