咋没人做啊（

考虑从 $n$ 到 $n+1$ 递推：

4          o
           
3       o  o
       /    
2    o--o  o
    /      
1 o--o--o  o
  1  2  3  4

已知 $(n,1)$ 到 $(n,n)$ 都连通，则只需要数 $(n+1,1)$ 到 $(n+1,n+1)$ 有多少种方案连边。而由于每一个点只能从前面最多一个连边，我们可以枚举 $1\le i\le n$，$(n,1)$ 到 $(n,i)$ 连 $(n+1,1)$ 到 $(n+1,i)$，$(n,i)$ 到 $(n,n)$ 连 $(n+1,i+1)$ 到 $(n+1,n+1)$。

则答案为 $1\times 2\times\dots\times n-1$，可以分段打表。