RMO 2014 M4

A person moves in the $x-y$ plane moving along points with integer co-ordinates $x$ and $y$ only. When she is at a point $(x,y)$ , she takes a step based on the following rules: (a) if $x+y$ is even she moves to either $(x+1,y)$ or $(x+1,y+1)$ ; (b) if $x+y$ is odd she moves to either $(x,y+1)$ or $(x+1,y+1)$ . How many distinct paths can she take to go from $(0,0)$ to $(8,8)$ given that she took exactly three steps to the right $((x,y)$ to $(x+1,y))$ ?