Problem: Igor K. very much likes a multiplayer role playing game WineAge II. Who knows, perhaps, that might be the reason for his poor performance at the university. As any person who plays the game, he is interested in equipping his hero with as good weapon and outfit as possible. 

One day, as he was reading the game's forum yet again, he discovered a very interesting fact. As it turns out, each weapon in the game is characterised with k different numbers: a1, ..., ak. They are called hit indicators and according to the game developers' plan they are pairwise coprime. 

The damage that is inflicted during a hit depends not only on the weapon's characteristics, but also on the hero's strength parameter. Thus, if the hero's strength equals n, than the inflicted damage will be calculated as the number of numbers on the segment <image>, that aren't divisible by any hit indicator ai.

Recently, having fulfilled another quest, Igor K. found a new Lostborn sword. He wants to know how much damage he will inflict upon his enemies if he uses it.

Input

The first line contains two integers: n and k (1 ≤ n ≤ 1013, 1 ≤ k ≤ 100). They are the indicator of Igor K's hero's strength and the number of hit indicators.

The next line contains space-separated k integers ai (1 ≤ ai ≤ 1000). They are Lostborn sword's hit indicators. The given k numbers are pairwise coprime.

Output

Print the single number — the damage that will be inflicted by Igor K.'s hero when he uses his new weapon. 

Please, do not use the %lld specificator to read or write 64-bit integers in C++. It is preferred to use the cin, cout streams or the %I64d specificator.

Examples

Input

20 3
2 3 5


Output

6


Input

50 2
15 8


Output

41

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {

    int[] a;
    long n;

    long calc(long n,int m){
        long res=0;

        for(int i=m;i<a.length;i++){            
            long q=n/a[i];
            if(q==0)break;
            res+=q;
            res-=calc(q,i+1);
        }

        return res;
    }

    void solve() throws IOException {
        n=nextLong();
        int k=nextInt();
        a=new int[k];
        for(int i=0;i<k;i++)
            a[i]=nextInt();
        Arrays.sort(a);
        long res=0;
        long[] x=new long[1];
        long[] y=new long[1];
        x[0]=n;
        y[0]=1l;
        int l=1;
        for(int i=k-1;i>=0;i--){
            long[] newx=new long[l];
            long[] newy=new long[l];
            int h=0;
            for(int j=0;j<l;j++){
                long q=x[j]/a[i];
                if(q!=0){
                    if(h>0&&newx[h-1]==q){
                        newy[h-1]= newy[h-1]-y[j];
                    }
                    else{
                        newy[h]=-y[j];
                        newx[h++]=q;
                    }
                }
            }
            long[] x1=new long[l+h];
            long[] y1=new long[l+h];
            int i1=0;
            int i2=0;
            int m=0;
            while(i1<l||i2<h){
                if(i1==l){
                    while(i2<h){
                        x1[m]=newx[i2];
                        y1[m]=newy[i2];
                        m++;
                        i2++;
                    }
                }
                else
                    if(i2==h){
                        while(i1<l){
                            x1[m]=x[i1];
                            y1[m]=y[i1];
                            m++;
                            i1++;
                        }
                    }
                    else{
                        while(i1<l&&x[i1]>newx[i2]){
                            x1[m]=x[i1];
                            y1[m]=y[i1];
                            m++;
                            i1++;
                        }
                        if(i1<l){
                            if(x[i1]==newx[i2]){
                                x1[m]=x[i1];
                                y1[m]=y[i1]+newy[i2];
                                m++;
                                i1++;i2++;
                            }
                            else{
                                while(i2<h&&x[i1]<newx[i2]){
                                    x1[m]=newx[i2];
                                    y1[m]=newy[i2];
                                    i2++;m++;
                                }
                            }
                        }
                    }
            }
            x=x1;
            y=y1;
            l=m;
        }
        for(int i=0;i<l;i++){
            res+=x[i]*y[i];
        }
        out.println(res);
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }


   void run() throws IOException {
       reader = new BufferedReader(new InputStreamReader(System.in));
       tokenizer = null;
       out=new PrintWriter(new OutputStreamWriter(System.out));
       solve();
       reader.close();
       out.flush();

    }

    BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}