Statement

Johnnie Walker is now in Bucharest! Even though it's getting late, he still wants to go for a walk. The neighborhood Johnnie stays in has N intersections of its streets, labeled from 1 to N. Johnnie's house is really close to intersection 1: the walk has to start and end there. Given his prodigious walking abilities, at any time Johnnie can go from any intersection to any other one in approximately one minute (he is capable of adjusting the walking speed appropriately!). The only thing our hero hates is standing still and getting cold: that's why he will never pause at intersections. After walking along different paths for a couple of evenings for K minutes, Johnnie wonders how many such paths of exactly K minutes are possible. Compute the answer for him!