고마치잔은 주어진 숫자의 순서를 유지하면서 숫자 사이에 연산자를 넣어 목표값을 만드는 놀이이다.

\(N\)개의 숫자와 목표값 \(T\)가 주어진다. 이웃한 두 숫자 사이에는 다음 다섯 가지 중 하나를 선택할 수 있다.

• +를 넣는다.
• -를 넣는다.
• *를 넣는다.
• /를 넣는다.
• 두 숫자를 이어 붙인다.

숫자를 이어 붙이면 여러 숫자가 하나의 수가 된다. 예를 들어 2, 3, 4를 모두 이어 붙이면 234가 된다.

사칙연산에는 우선순위가 없으며, 모든 연산은 식의 왼쪽부터 차례대로 계산한다. 예를 들어 2 + 3 * 4의 값은 \((2+3)\times4=20\)이다.

나눗셈은 C 언어의 정수 나눗셈과 같이 소수 부분을 버린다. 음수인 경우에도 \(0\)을 향해 버린다. 예를 들어 \(7/3=2\)이고, \(-7/3=-2\)이다.

각 숫자 사이의 선택에 따라 만들어지는 식의 값이 목표값 \(T\)가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 \(N\)과 목표값 \(T\)가 공백으로 구분되어 주어진다.

둘째 줄에 \(N\)개의 숫자가 순서대로 주어진다. 같은 숫자가 여러 번 주어질 수 있다.

출력

만들어진 식의 값이 목표값 \(T\)가 되는 경우의 수를 출력한다.

제한 사항

• \(1 \le N \le 9\)
• 주어지는 각 숫자는 \(1\) 이상 \(9\) 이하이다.
• \(-1,000,000,000 \le T \le 1,000,000,000\)
• 숫자의 순서를 바꿀 수 없다.
• 괄호를 사용할 수 없다.

예제 입력 1

3 20
2 3 4

예제 출력 1

1

예제 설명 1

2 + 3 * 4를 왼쪽부터 계산하면 \((2+3)\times4=20\)이 된다. 목표값을 만드는 다른 방법은 없다.

예제 입력 2

4 36
1 2 3 4

예제 출력 2

3

예제 설명 2

목표값을 만드는 식은 다음과 같이 3개이다.

• 1 + 2 * 3 * 4: 왼쪽부터 계산하면 \(((1+2)\times3)\times4=36\)이다.
• 1 * 2 + 34: 왼쪽부터 계산하면 \((1\times2)+34=36\)이다.
• 12 - 3 * 4: 왼쪽부터 계산하면 \((12-3)\times4=36\)이다.