Районная олимпиада, 2003-2004 учебный год, 11 класс

В левом нижнем углу шахматной доски $7 \times 7$ стоит король. Он может ходить на одну клетку либо в право, либо вверх, либо по диагонали вправо вверх. Сколькими путями король может пройти в правый верхний угол доски, если его маршрут не должен содержать клетки, расположенные выше главной диагонали доски.