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 a1, a2, … ak 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 ≤ 107, 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 ≤ a1 < a2 < a3 < ... < an ≤ n.
Output
The number of the way to pack the nuggets without any leftovers. Please print a '\n' character at the end.