Рассмотрим стопку бутылок вина. В стопке $n$ слоев, верхний слой состоит из одной бутылки, нижний - из $n$ бутылок. При $n=4$ стопка будет выглядеть как на изображении ниже:

Обвал бутылок просиходит каждый раз, когда из стопки вынимают бутылку. В стопке образуется пустое пространство, которое заполняется в соответствии со следующими рекурсивными шагами:

• Если сверху нет ни одной бутылки: ничего не происходит. Например, если вынуть бутылку $F$.
• Если сверху касается одна бутылка: она упадет и займет пустое место, создав новое пустое место на слой выше. Например, если вынуть бутылку $D$.
• Если сверху касаются две бутылки: одна из них упадет и займет пустое место, создав новое пустое место на слой выше. Например, если вынуть бутылку $C$.

Этот процесс происходит рекурсивно. Например, при вынимании бутылки $A$ на схеме выше, на ее место упадет или $B$, или $C$. Если туда упадет $C$, ее освободившееся место может занять $D$ или $E$. Итого может произойти 3 разных процесса обвала, если вынуть бутылку $A$, но в этом примере финальная форма стопки всегда будет одинаковой.

Определим $f(n)$ как количество способов, которыми можно вынуть все бутылки из стопки в $n$ слоев. Два способа считаются различными, если в какой-то из шагов была вынута другая бутылка или обвал произошел иначе.

Известно, что $f(1) = 1$, $f(2) = 6$ и $f(3) = 1008$.

Найдите $S(10^4)$. В качестве ответа приведите остаток от деления полученного результата на $1\,000\,000\,033$.