def number_of_ways_of_cutting_a_pizza_brute_force(pizza, number_of_cuts):
    rows = len(pizza)
    columns = len(pizza[0])
    number_of_valid_ways = 0

    def is_valid_cut(pieces):
        for piece in pieces:
            has_apple = False
            for row_index in range(len(piece)):
                for column_index in range(len(piece[0])):
                    if piece[row_index][column_index] == 'A':
                        has_apple = True
                        break
                if has_apple:
                    break
            if not has_apple:
                return False
        return True

    def generate_cuts(current_cuts):
        nonlocal number_of_valid_ways

        if len(current_cuts) == number_of_cuts:
            # After all cuts are placed, divide the pizza into pieces
            pieces = divide_pizza(current_cuts)

            if is_valid_cut(pieces):
                number_of_valid_ways += 1
            return

        # Iterate over all possible row and column cut positions
        for row_cut in range(1, rows):
            generate_cuts(current_cuts + [('H', row_cut)])
        
        for column_cut in range(1, columns):
            generate_cuts(current_cuts + [('V', column_cut)])

    def divide_pizza(cuts):
        cuts.sort(key=lambda x: x[1])
        horizontal_cuts = [cut[1] for cut in cuts if cut[0] == 'H']
        vertical_cuts = [cut[1] for cut in cuts if cut[0] == 'V']

        pieces = []
        row_start = 0

        # Split the pizza by each horizontal cut
        for row_end in horizontal_cuts + [rows]:
            column_start = 0
            # Split the pizza by each vertical cut
            for column_end in vertical_cuts + [columns]:
                piece = []

                for row_index in range(row_start, row_end):
                    row_segment = pizza[row_index][column_start:column_end]
                    piece.append(row_segment)

                pieces.append(piece)
                column_start = column_end
            row_start = row_end

        return pieces

    generate_cuts([])
    return number_of_valid_ways

def number_of_ways_of_cutting_a_pizza(pizza, number_of_cuts_needed):
    rows = len(pizza)
    cols = len(pizza[0])
    modulo = 10**9 + 7

    prefix_sum = [[0] * (cols + 1) for _ in range(rows + 1)]
    for row_index in range(1, rows + 1):
        for col_index in range(1, cols + 1):
            prefix_sum[row_index][col_index] = prefix_sum[row_index - 1][col_index] + prefix_sum[row_index][col_index - 1] - prefix_sum[row_index - 1][col_index - 1] + (pizza[row_index - 1][col_index - 1] == 'A')

    memo = {}

    def has_ingredient(row_start, col_start, row_end, col_end):
        return prefix_sum[row_end + 1][col_end + 1] - prefix_sum[row_start][col_end + 1] - prefix_sum[row_end + 1][col_start] + prefix_sum[row_start][col_start] > 0

    def solve(remaining_cuts, row_start, col_start):
        # Base cases: no more cuts needed
        if remaining_cuts == 0:
            return 1 if has_ingredient(row_start, col_start, rows - 1, cols - 1) else 0

        # Check if the result is already memoized
        if (remaining_cuts, row_start, col_start) in memo:
            return memo[(remaining_cuts, row_start, col_start)]

        ways = 0

        # Horizontal cuts
        for row_index in range(row_start, rows - 1):
            # Ensuring each piece has at least one 'A'
            if has_ingredient(row_start, col_start, row_index, cols - 1):
                ways = (ways + solve(remaining_cuts - 1, row_index + 1, col_start)) % modulo

        # Vertical cuts
        for col_index in range(col_start, cols - 1):
            # Ensuring each piece has at least one 'A'
            if has_ingredient(row_start, col_start, rows - 1, col_index):
                ways = (ways + solve(remaining_cuts - 1, row_start, col_index + 1)) % modulo

        # Store the result in the memo
        memo[(remaining_cuts, row_start, col_start)] = ways
        return ways

    # We need to handle the initial state where 0 cuts are required, and there are no ingredients.
    if not has_ingredient(0, 0, rows - 1, cols - 1) and number_of_cuts_needed >= 0:
      return 0

    # Initiate the recursive process with the full pizza
    result = solve(number_of_cuts_needed, 0, 0)
    return result