Cutting Cake

Chef recently cooked a big cake that can be represented as a grid of N rows and M columns, each cell can be either empty or contain a currant, Chef wants to cut out a sub-rectangle from the cake which contains even number of currants. Before cutting such a sub-rectangle, he is interested in knowing how many sub-rectangles are there which contains even number of currants. Input There is a single