# modulo fft
from math import *

def fft(m, f=[]): #genera fft
    result = []
    n=2<<(m-1)
    nesp=0.5
    for k in range(1,m+1):
        d=n/(2<<(k-1)
        nesp=nesp*2
        s=0
        for i in range(1,nesp+1):
            r=s
            z1=r>>(m-k)
            z=0
            for q in range(k):
                z=(((z1>>q) & 01) | (z<<1)
            w=2*pi*z/(2<<(k-1))
            e=cos(w)-sin(w)j
            for l in range (d):
                r=l+s
                r1=r+d
                t=e*f[r1]
                f[r1]=f[r]-t
                f[r]=f[r]+t
                s=s+2*d
    #bitReversal(n, m, f=[])
    for x in range(1, n-1):
        y=0
        for i in range(m):
            y=(((x>>i) & 01) | (y<<1))
        if x<y :
            t=f[x]
            f[x]=f[y]
            f[y]=t
    #Ampiezze fasi
    nmezzi=n/2
    for i in range(n):
        f[i]=f[i]/nmezzi
    A[0]=f[0].real
    phi[0]=0
    for k in range(1, nmezzi+1):
        A[k]=sqrt(f[k].real*f[k].real+f[k].imag*f[k].imag])
        result.append(A[k])
    if f[k].real == 0:
        if f[k].imag>0:
            phi[k]=pi
        if f[k].imag==0:
            phi[k]=0
        if f[k].imag<0:
            phi[k]=2*pi-pi/2
    if f[k].real>0:
        if f[k]>=0:
            phi[k]=atan(f[k].imag, f[k].real)
        if f[k]<0:
            phi[k]=2*pi + atan(f[k].imag, f[k].real)
    if f[k].real<0:
        phi[k]=atan(f[k].imag, f[k].real)
    return result