给定 9 个数字   a_1, a_2, \dots, a_9 （ 1 \le a_i \le 9 ）  和一个整数 S 。

你需要在相邻两个数字之间的 **8 个空格** 中，分别选择以下四种操作之一：

- `+`（加法）

- `-`（减法）

- `*`（乘法）

- 不放（将左右两个数字直接拼接成一个多位数，例如 `1` 和 `2` 拼接成 `12`）

通过这 9 个数字和 8 个操作（含拼接），可以组成一个合法的表达式。  

**运算优先级**：先处理拼接（形成多位数），然后按照常规四则运算规则（先乘除，后加减）计算表达式的值。

请问有多少种不同的操作序列（即 8 个空位的选择方案），使得表达式的计算结果等于 S ？

> 注意：不同的拼接方式（例如 `1 2` 拼成 `12`，`1 2 3` 连续无符号拼成 `123`）视为不同的方案。  

> 表达式中的数字顺序必须与给定的 a_1, a_2, \dots, a_9 一致。

第一行：9 个空格隔开的整数 a_1, a_2, \dots, a_9 。  

第二行：一个整数 S 。

一个整数 N ，表示可行的方案总数。

样例1解释：

在 9 个数字的 8 个空位中，每个空位有 4 种选择（`+`、`-`、`*`、拼接）。  

其中一种可行方案是：  

`1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45` （全部填加号）  

另一种是：  

`12 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45` （前两个数字拼接成 12）  

总共有 40 种不同的运算符/拼接组合使得结果等于 45。

数据范围

- 1 \le a_i \le 9

- -10^9 \le S \le 10^9

- 输入的 9 个数字均为整数。