530. Number of Squareful Arrays

0

Easy

Given an integer array nums, determine the number of permutations of nums that are squareful. A permutation is considered squareful if the sum of every pair of adjacent elements is a perfect square. Two permutations are considered different if there is at least one index where the corresponding elements differ.

Input Format

The input consists of two lines. The first line contains an integer N, representing the size of the array. The second line contains N space-separated integers, representing the elements of the array.

Output Format

Print a single integer, representing the number of permutations of nums that are squareful.

Example

Input

3
1 17 8

Output

2

Constraints

1<= N <= 12

0<= nums[i] <= 10

0<= nums[i] <= 10

^{9}Loading...

View Submissions

Console