有$n$种颜色的小球，其中第$i$种颜色的小球有$k_i$个。将这些小球从左到右排成一行，使得相同颜色的小球不相邻，求有多少种方案。

相同颜色的小球之间没有区别，经过翻转等任意操作后才相同的两种方案算作不同的方案。 输入

第一行一个正整数$N$，表示颜色种类数。

第二行$N$个正整数$k_i$，$k_i$表示第i种颜色的数量(1 ≤ $k_i$ ≤ 3)。 输出

一个整数，表示相同颜色的小球不相邻的方案数。

样例

输入1

3
1 2 3

输出1

10

输入2

4
1 3 2 1

输出2

96

输入的所有数字均为正整数。

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n, m, k[N], path[N * 3];
int ans = 0;

void dfs(int step) {
	if (step == m + 1) {
		ans ++;
//		for (int i = 1; i <= m; i ++)
//			printf("%d ", path[i]);
//		printf("\n");

		return ;
	}

	for (int i = 1; i <= n; i ++) {
		if ((path[step - 1] == i && step != 1) || ! k[i])
			continue;

		path[step] = i;
		k[i] --;
		dfs(step + 1);
		k[i] ++;
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &k[i]);
		m += k[i];
	}

	dfs(1);

	printf("%d\n", ans);

	return 0;
}

TLE了，求大神时间优化或者剪枝