Problem statement: Given a floor of size M x N units and tiles of size 1 x 1 square unit and 2 x 2 square units, count the number of ways in which the tiles can be arranged on the floors such that each square unit of the floor is covered with a tile and if any square unit is covered by a tile different from that of other arrangements, then that arrangement is different from others. The number of unit-squares in the column-wise direction can be at most 7.

Solution:
Some sample cases: Floor dimensions: M x N as

1 x 2 = > 1 arrangement
2 x 2 => 2 arrangements
3 x 3 => 5 arrangements
2 * 4 => 5 arrangements
3 x 4 => 11 arrangements ( 1 (all-small-tile) + 6 (1-big-tile) + 4 (double-big-tiles) )

Assume there are big tiles across a horizontal line representing a row where the occurrence sequence is governed by an isValid method that makes big tiles don’t overlap. We can also infer two rows instead of one because a row running through big tiles can have the other row only as an adjacent to the big tile and not crossing the big tiles. Representing the matrix distribution for varying positions of I and j along row and column for big tiles sequences to be valid, we have the essential block to compute the Fibonacci sequence with. Since we have a matrix, we use matrix  exponentiation to compute the Fibonacci sequence. At the end of the iterations, we look up the value corresponding to the requirement that the top and bottom horizontal lines do not cross any big tiles while they can be adjacent to those tiles.

    public static boolean isValid(int x) {

        boolean valid = true;

        while (x > 0){

            if ((x & 1) == 1) {

                valid = !valid;

            } else if (!valid) {

                return false;

            }

            x >>= 1;

        }

        return valid;

    }

   public static int[][] getMatrix(int column) {

        int length = (int)Math.pow(2,column);

        int[][] A = new int[length][length];

        for (int i = 0; i < length; i++) {

            if (isValid(i)) {

                for (int j = 0; j < length; j++){

                    if (isValid(j) && (i & j) == 0) {

                        A[i][j] = 1;

                    }

                }

            }

        }

        return A;

    }

    public static int[][] identity(int size) {

           int[][] I = new int[size][size];

           for (int i = 0; i < size; i++) {

               I[i][i] = 1;

           }

           return I;

    }

    public static int[][] matrixMultiplication(int[][] A, int[][] B, int modulo) {

        int[][] C = new int[A.length][A.length];

        for (int i = 0; i < A.length; i++) {

            for (int j = 0; j < A.length; j++) {

                int value = 0;

                for (int k = 0; k < A.length; k++) {

                    value = (value + (A[i][k] % modulo) * (B[k][j] % modulo)) % modulo;

                }

                C[i][j] = value;

            }

        }

        return C;

    }

    public static int[][] matrixExponentiation(int[][] A, int row, int modulo ) {

        int [][] B = identity(A.length);

        while (row > 0) {

            if ((row & 1) == 1) {

                B = matrixMultiplication(A, B, modulo);

            }

            A = matrixMultiplication(A, A, modulo);

            row >>= 1;

        }

        return B;

    }

    public static int getFillCountFromMatrix(int row, int col) {

        int[][] B = matrixExponentiation(getMatrix(col), row, 10000007);

        return B[0][0];

    }

getFillCountFromMatrix(3,4) => 11

getFillCountFromMatrix(4,4) => 35