Pie Tasting

Chef, who is a chef by profession as well, has created $N$ pies (enumerated $1$ through $N$) and has placed them in a row. Now he wants to taste all the pies, but by following a rather peculiar order of tasting. At each step, he chooses (uniformly randomly and independently) either the current leftmost pie or the rightmost pie, and eats that pie. For example, if $N = 7$, then one valid order of