The FFT algorithm we described in this lecture is limited to polynomials with 2k coefficients for some integer k. Of course, we can always pad the coefficient vector with zeros to force it into this form, but this padding artificially inflates the input size, leading to a slower algorithm than necessary. Describe and analyze a similar DFT algorithm that works for polynomials with 3k coefficients, by splitting the coefficient vector into three smaller vectors of length 3k-1, recursively computing the DFT of each smaller vector, and correctly combining the results.