Yet Another Expression Mining

Time limit2sMemory limit512 MB

Summary

Count subsequences of a string of digits and plus signs, with no leading, trailing, or doubled plus, whose arithmetic evaluation equals A.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Math, Implementation
Solved: No attempts yet

Problem

You are given an integer $A$ and a string $S$ consisting of the following 10 characters: the addition operator '+' and the digits '1', '2', ..., '9'.

Count the subsequences of $S$ that satisfy all of the following conditions.

The subsequence is not empty.
The first character of the subsequence is not '+'.
The last character of the subsequence is not '+'.
'+' does not appear consecutively in the subsequence.
Reading the subsequence as a mathematical expression, its evaluation result is $A$ .

A subsequence is a sequence that can be obtained from the given sequence by removing zero or more elements without changing the order of the remaining elements.

Two subsequences are considered different if the sets of indices of the removed elements differ.

Input

The input consists of a single test case in the format below.

$S$

$A$

The first line contains a single string $S$ ( $1 \le |S| \le 36$ ). Each character of $S$ is either '+' or a digit between '1' and '9'. The second line contains a single integer $A$ ( $1 \le A \le 10^{18}$ ).

Output

Output the number of subsequences that satisfy the given conditions in a single line.

Examples3

Example 1
Input
```
1+2+3+4+5+6
18
```
Expected output
```
9
```
Example 2
Input
```
+391+49++21+9934
43
```
Expected output
```
47
```
Example 3
Input
```
1111111111111111
1111111111
```
Expected output
```
8008
```