Description

$Z$ 国有 $N+1$ 个城市，序号为 $1 \dots N+1$。

这 $N+1$ 个城市排布是奇怪的：这 $N+1$ 个城市在一条线上，对于第 $i(i < N+1)$ 个城市只能到达第 $i+1$ 个城市，并且有 $a_i$ 种路径。

求从城市 $1$ 到城市 $N+1$ 共有多少种不同路径。

Format

Input

第一行包含一个整数 $N$ ，城市个数为 $N+1$ 。

第二行包含 $N$ 个整数，第 $i$ 个数 $a_i$ 表示从第 $i$ 个城市到第 $i + 1$ 个城市的路径数。

$1 \le N \le 10, 1 \le a_i \le 4$ 。

Output

一个整数，表示从城市 $1$ 到城市 $N$ 的不同路径数。

Samples

3
2 4 3

24