Азиатско-Тихоокеанская математическая олимпиада, 2026 год

Пусть $n$ — положительное целое число. Имеется $n(n+1)$ комнат, расположенных в клетках таблицы размера $(n+1)\times n$. Между любыми двумя соседними по стороне комнатами есть дверь.
   Найдите число способов выбрать некоторое подмножество дверей, что после их запирания существовали две комнаты $S$ и $G$, удовлетворяющие следующим условиям:
   (i) $S$ находится в первой строке, а $G$ — в $(n+1)$-й строке;
   (ii) из $S$ можно попасть в $G$ только через незапертые двери.