States: . Transitions per state: up to (all ways to fill a row). Total time: .
Time complexity: .
Space complexity: . This is exponential in but linear in . improvement: precompute valid transitions. If many transitions are invalid, the actual count is smaller. Matrix exponentiation: if is huge, use matrix power in . Matrix exponentiation helps when the number of rows is huge. The matrix size is the number of valid profiles.