You are given a 2^k 2^k board with one missing cell. Give an O(2^2k )-time algorithm for filling the board with L-shaped tiles. (See Figure 1 below.)

Figure 1: On the left is an example grid with a missing cell, with k 3. In the middle is the "L-shaped" tile, to be used for tiling. On the right is an example solution