Let $n$ be a positive integer. Let $S$ be the set of $n^2$ cells in an $n\times n$ grid. Call a subset $T$ of $S$ a [b]double staircase [/b] if
[list]
[*] $T$ can be partitioned into $n$ horizontal nonoverlapping rectangles of dimensions $1 \times 1,
1 \times 2, ..., 1 \times n,$ and
[*]$T$ can also be partitioned into $n$ vertical nonoverlapping rectangles of dimensions $1\times1,
2 \times 1, ..., n \times 1$.
[/list]
In terms of $n$, how many double staircases are there? (Rotations and reflections are considered distinct.)
An example of a double staircase when $n = 3$ is shown below.

[asy]
unitsize(1cm);
for (int i = 0; i <= 3; ++i)
{
draw((0,i)--(3,i),linewidth(0.2));
draw((i,0)--(i,3),linewidth(0.2));
}
filldraw((0,0)--(1,0)--(1,1)--(0,1)--cycle, lightgray, linewidth(0.2));
filldraw((1,0)--(2,0)--(2,1)--(1,1)--cycle, lightgray, linewidth(0.2));
filldraw((2,0)--(3,0)--(3,1)--(2,1)--cycle, lightgray, linewidth(0.2));
filldraw((0,1)--(1,1)--(1,2)--(0,2)--cycle, lightgray, linewidth(0.2));
filldraw((1,1)--(2,1)--(2,2)--(1,2)--cycle, lightgray, linewidth(0.2));
filldraw((1,2)--(2,2)--(2,3)--(1,3)--cycle, lightgray, linewidth(0.2));
[/asy]
1. **Define the Problem and Initial Setup:**
   We are given an \( n \times n \) grid with \( n^2 \) cells. We need to determine the number of ways to form a "double staircase" in this grid. A double staircase is defined as a subset \( T \) of \( S \) (the set of all cells) that can be partitioned into \( n \) horizontal non-overlapping rectangles of dimensions \( 1 \times 1, 1 \times 2, \ldots, 1 \times n \) and also into \( n \) vertical non-overlapping rectangles of dimensions \( 1 \times 1, 2 \times 1, \ldots, n \times 1 \).

2. **Lemma 1: Distinct Rows and Columns:**
   Each of the \( n \) horizontal rectangles must be in distinct rows, and each of the \( n \) vertical rectangles must be in distinct columns.
   - **Proof:** Assume for contradiction that two horizontal rectangles are in the same row. This would leave at least one row uncolored, contradicting the requirement that each column must be fully colored. Similarly, vertical rectangles must be in distinct columns.

3. **Lemma 2: Contiguous Coloring:**
   Given two colored cells in the same row, all cells between them in that row must also be colored.
   - **Proof:** If there were uncolored cells between two colored cells in the same row, it would imply the existence of two separate horizontal rectangles in the same row, contradicting Lemma 1. The same logic applies to columns.

4. **Labeling Rows and Columns:**
   Label each row with a distinct number from \( 1 \) to \( n \) corresponding to the number of colored cells in that row. Let these numbers be \( a_1, a_2, \ldots, a_n \) from top to bottom. Similarly, define \( b_1, b_2, \ldots, b_n \) for the columns from left to right.

5. **Lemma 3: Sequence Order:**
   Suppose row \( a_k \) is the fully colored row for some \( 1 \leq k \leq n \). Then \( a_1 < a_2 < \ldots < a_k > a_{k+1} > \ldots > a_n \).
   - **Proof:** For any row \( a_i \) with \( i < k \), any colored cell in row \( a_i \) implies that the cells in the same column but in rows \( a_{i+1}, a_{i+2}, \ldots, a_{k-1} \) must also be colored. Thus, \( a_i \leq a_{i+1}, a_{i+2}, \ldots, a_{k-1} \leq a_k \). Since all \( a_1, \ldots, a_k \) are distinct, we have \( a_i < a_{i+1}, a_{i+2}, \ldots, a_{k-1} < a_k \). Similarly, for \( i > k \), we have \( a_i < a_{i-1}, a_{i-2}, \ldots, a_{k+1} < a_k \). This proves the lemma. The same logic applies to \( b_1, b_2, \ldots, b_n \).

6. **Counting Valid Sequences:**
   There are \( 2^{n-1} \) ways to pick \( a_1, a_2, \ldots, a_n \) satisfying Lemma 3. This is because if the fully colored row is \( a_k \), there are \( \binom{n-1}{k-1} \) ways to order the rest, and summing over \( 1 \leq k \leq n \) gives \( 2^{n-1} \). Similarly, there are \( 2^{n-1} \) ways to pick \( b_1, b_2, \ldots, b_n \).

7. **Claim: Unique Double Staircase for Each Pair of Sequences:**
   For any two sequences \( a_1, a_2, \ldots, a_n \) and \( b_1, b_2, \ldots, b_n \) satisfying Lemma 3, there is exactly one double staircase corresponding to these sequences.
   - **Proof:** Place the \( 1 \times n \) rectangle in its corresponding row. One of \( b_1 \) or \( b_n \) must be \( 1 \). Suppose \( b_1 = 1 \). Then, the \( 1 \times (n-1) \) rectangle must intersect columns \( b_2, b_3, \ldots, b_n \). Continue this logic iteratively to see that there is always exactly one position for the next rectangle. Thus, there is exactly one double staircase for each pair of sequences.

8. **Final Calculation:**
   The total number of double staircases is \( 2^{n-1} \times 2^{n-1} = 2^{2n-2} \).

The final answer is \( \boxed{2^{2n-2}} \)