Chef and Soccer

Chef is a big fan of soccer! He loves soccer so much that he even invented soccer for dogs! Here are the rules of soccer for dogs: - $N$ dogs (numbered $1$ through $N$) stand in a line in such a way that for each valid $i$, dogs $i$ and $i + 1$ are adjacent. - Each dog has a skill level, which is either $1$ or $2$. - At the beginning of the game, Chef passes a ball to dog $1$ (dog $1$ receives