Croatian Mathematical Olympiad 2014 Problem I-2

Neka je $N$ prirodni broj. Stepenicama zovemo dio kvadratne ploče dimenzija $N \times N$ koji se sastoji od prvih $K$ polja u $K$-tom retku za $K = 1, 2, \ldots, N$. Na koliko je načina moguće razrezati stepenice na pravokutnike različitih površina koji se sastoje od polja dane ploče?