정수 \(0\)에서 시작하여, 주어진 \(N\)개의 정수를 차례로 더하거나 빼려고 한다.

각 정수는 정확히 한 번 사용해야 한다. 각 정수마다 더할지 뺄지를 하나씩 선택했을 때, 최종 결과가 목표값 \(M\)이 되는 부호 선택의 수를 구하시오.

같은 값을 가진 정수가 여러 개 있더라도 입력에서의 위치가 다르면 서로 다른 정수로 취급한다. 또한 어떤 정수가 \(0\)인 경우, 그 정수에 +를 선택한 경우와 -를 선택한 경우도 서로 다른 방법으로 센다.

입력

첫째 줄에 목표값 \(M\)이 주어진다.

둘째 줄에 사용할 정수의 개수 \(N\)이 주어진다.

셋째 줄에 \(N\)개의 정수 \(a_1,a_2,\ldots,a_N\)이 공백으로 구분되어 주어진다. \(N=0\)이면 셋째 줄은 비어 있다.

출력

모든 정수를 정확히 한 번씩 더하거나 빼서 \(M\)을 만드는 방법의 수를 출력한다.

제한 사항

• \(0 \le N \le 20\)
• \(M\)과 모든 \(a_i\)는 32비트 부호 있는 정수이다.
• \(|a_1|+|a_2|+\cdots+|a_N| \le 2,147,483,647\)

예제 입력 1

0
4
1 2 3 4

예제 출력 1

2

예제 설명 1

다음 두 가지 부호 선택으로 결과를 \(0\)으로 만들 수 있다.

1-2-3+4=0
-1+2+3-4=0

예제 입력 2

2
3
1 2 4

예제 출력 2

0

예제 설명 2

세 정수를 각각 더하거나 빼서 결과를 \(2\)로 만드는 방법은 없다.