You are given a set S={s1, s2, . . . , sn} of n distinct natural numbers such that 0s_i100n.Your task is to design an algorithm that takes as input S and a natural number N, and outputs True if the equations i+s_j+s_k=N has at least one solution, and return False otherwise. There is a simple solution that runs in O(n^3) time, but you can improve on that time using FFT! Example: For N= 6 and S={1,2,3,5,10} your design should output True since 1 + 2 + 3 = 6. For N= 20 and the same set S the answer should be True again since 5 + 5 + 10 = 20 (yes, you can have s_i=s_j=s_k!) but for N= 19 the answer is False since no three numbers add up to 19. You can use FFT as a black box. Explicitly write the polynomials you will use as input for FFT and explain how you use the output to answer your problem. State and justify the running time of your algorithm. Also start with defining the simple O(n^3) solution then the defined solution. Using FFT as a black box means you do not need to descibe FFT (fast fourier transform) itself.