Given an 2n size rectangle, we wish to split it into pieces of size 12 (each piece can be either vertical or horizontal). Figure [1 shows an example of such a splitting for 24 rectangle. We want to figure out how many splitting of into pieces of size 12 are there. Figure 1: Splitting of 24 rectangle into 12 pieces 1. How many splittings are possible for rectangles of size 12,22,23 and 24 ? 2. Denote the number of splittings of 2n rectangle by Sn. Come up with a recursive formula for Sn. (Hint: look at the rightmost 12 rectangle in the splitting and consider two cases depending on whether it is horizontal or vertical.) 3. Show that Sn can be computed in polynomial time. (Hint: you can either write down an algorithm from scratch, or you can refer to some other problem we discussed in class.)