‹ 上一题下一题 ›

j01979. 平方和数字链未做

1000 ms 256 MB 测试点 10 通过率 0% 搜索 J·复赛必做100题自拟题 r2 深度优先搜索

文件读写输入j01979.in输出j01979.out

题目描述

$n$ 张数字卡排成一条链，使相邻两数之和都是完全平方数。卡片互不相同（数值可能重复，同数值的两张卡交换也算不同排法）。求排列方案数。

输入格式

第一行一个整数 $n$ ；第二行 $n$ 个整数 $a_{i}$ 。

输出格式

一行一个整数，方案数。

样例

输入

3
1 8 1

输出

数据范围

对于 30% 的数据， $n \leq 5$ 。
对于 60% 的数据， $n \leq 6$ 。
对于 100% 的数据， $1 \leq n \leq 10$ ， $1 \leq a_{i} \leq 100$ （可能为 0）。

输入

输出

答案