The easiest way to approach this subtask without much thought would be to try several different sequences of folds and cuts. By experimenting, you could find that when the cut is horizontal, only folds along a horizontal line (i.e. Top and Bottom) do actually matter (similarly with vertical cuts). You could probably even discern the correct formula: if there are n horizontal folds and a vertical cut, the number of paper pieces is 2n + 1.
The reason for this is quite simple: imagine unfolding the paper that underwent n vertical and m horizontal folds. It consists 2n × 2m little pieces of paper connected by folds. If the final cut was horizontal, each row contains one cut from left to right (if it was vertical, each column contains one cut). Thus there are 2n cuts resulting in 2n + 1 pieces of paper.
In the easy subproblem, we could find the answer by looking at the unfolded paper. While it may be possible to construct the solution for corners in this way, our solution will unfold the paper gradually, one fold at a time. And we will be counting holes in the paper. Each hole will correspond with one piece of paper apart from the “main” one.
We will split the holes into 9 categories as shown in the picture below: 0-1 hole in each of the corners, some number of holes on one of the sides (but not in any corner) and holes completely contained inside of our paper. Note how the interesting areas are arranged in a 3 × 3 array.
In the beginning, we have one hole in one of the corners. Afterwards, we process the unfolds in reverse order. During each unfold, we update counts in areas. We will describe the update for Left unfold, all the others are analogous. Please refer to the picture below, if anything becomes unclear.
All the counts in interesting areas in the right column stay the same. All the counts in the left column will become equal to the counts in the right column. The counts in the middle column are the most interesting: we double the original count and add the count from left column.
After we’re done processing the unfolds, we just sum up all the holes we found: each hole corresponds with a fallen out piece of paper. Don’t forget to add one for the original paper!