Problem with tiling a rectangular area with an L-shaped tile

Question

Python

There is a task: It is
required to enter the length, width of the area. Output the number of all possible paving options.
Examples:
1. Input - L = 3, W = 4
Output - 4
2. Input - L = 69, W = 2 Output
- 8388608
the presence of zeros, but alas.

Answer 1

To solve coverage problems, there is a special "Algorithm X" by Donald Knuth.
There is a good article on this topic on Habré: habrahabr.ru/post/194410

Answer 2

You can try to fill the area in rows.
Break each row into segments (length 1 or 2) related to one tile.
Each fill will generate constraints (pattern) for filling the next row.
Specifically, each new (not from the template) segment generates two variants of filling in adjacent cells for the next row.
[_][2][2][_]
[_][1][_][_]
[_][2][2][_]
[_][_][1][_]
[_ ][_][1][_][_]
[_][2][2][_][_]
[_][_][1][_][_]
[_][_][ 2][2][_]
Well, you just need to store it a little more cunningly than just cells.