Yet Another Expression Mining

정수 $A$와 다음 10개 문자, 덧셈 연산자 '+'와 숫자 '1', '2', ..., '9'로 이루어진 문자열 $S$가 주어진다.

$S$의 부분 수열 중 다음 조건을 모두 만족하는 것의 개수를 세어라.

• 부분 수열은 비어 있지 않다.
• 부분 수열의 첫 문자가 '+'가 아니다.
• 부분 수열의 마지막 문자가 '+'가 아니다.
• 부분 수열에서 '+'가 연속해서 나타나지 않는다.
• 부분 수열을 수식으로 읽었을 때 계산 결과가 $A$이다.

부분 수열이란 주어진 수열에서 원소를 0개 이상 제거하되 남은 원소의 순서를 바꾸지 않고 얻을 수 있는 수열을 말한다.

두 부분 수열은 제거한 원소의 인덱스 집합이 다르면 서로 다른 것으로 본다.

입력은 아래 형식의 단일 테스트 케이스로 주어진다.

$S$

$A$

첫째 줄에는 문자열 $S$가 주어진다 ($1 \le |S| \le 36$). $S$의 각 문자는 '+' 또는 '1'과 '9' 사이의 숫자이다. 둘째 줄에는 정수 $A$가 주어진다 ($1 \le A \le 10^{18}$).

주어진 조건을 만족하는 부분 수열의 개수를 한 줄에 출력한다.