Description

Kiara is a fast food shop owner. Today, she made too many chicken nuggets. She only has boxes with k different sizes that can contain a₁, a_2, … a_k nuggets respectively. She wants to put all n nuggets into boxes without any excess nuggets. Please help her determine how many ways she can pack the nuggets.

For example, if she has 14 nuggets and boxes of 3 sizes: for 2, 3, and 4 nuggets, there would be 8 ways to pack the nuggets.

Input

The first line contains two positive integers n and k. (1 ≤ n ≤ 10⁷, 1 ≤ k ≤ 20) 

The following line contains k numbers, the number of nuggets that could be packed inside each box. It is guaranteed to be in a strictly increasing order between 1 and n, which means 1 ≤ a₁ < a₂ < a₃ < ... < a_n ≤ n.

Output

The number of the way to pack the nuggets without any leftovers. Please print a '\n' character at the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Domo is a very smart dog. He also likes trolling people. One day, his teacher announced that only non-programmable calculators are allowed during the test, so he modified his non-programmable calculator into a programmable one. Knowing about his plan, you decided to give him a lesson by making it calculate prefix expressions instead of infix expressions.

 

Hint: Here are some functions you might want to use

int ungetc(int char, FILE *stream)

This is a function to return the character c to the stream. It is the opposite of int getc(FILE *stream). Try running this code for reference.

#include <stdio.h>

int main() {
    double f;
    char c;

    //to get the character c from the input stream
    c = getc(stdin);

    //uncomment the function below and see what will happen
    //ungetc(c, stdin);

    scanf("%lf", &f);
    printf("char: %c\ndouble: %lf\n", c, f);
}

double atof(const char *str)

This is a function for converting a string str to a double-precision floating point. It is included in the <stdlib.h>.

#include <stdio.h>
#include <stdlib.h>

int main() {
    //this is a string
    char flt[] = "3.141593";
    
    //now this is a double
    printf("%lf", atof(flt));
}

Input

There will be only one line of an expression in prefix notation, which contains no more than 10,000 non-negative double-precision floats and operators +, -, *, or /. There will be a space after every number and operator.

Output

The result of calculation in 4 decimal place precision with a trailing '\n'. You can use %.4lf to achieve this.

Sample Input  Download

Sample Output  Download

Tags

Discuss