673. Check If It is a Good Array

0

Hard

Om is given an array nums of positive integers. Om's task is to select some subset of nums, multiply each element by an integer and add all these numbers. The array is said to be good if Om can obtain a sum of 1 from the array by any possible subset and multiplicand.
Print True if the array is good otherwise print False.

Input Format

First line contains an integer N.
Second line contains an integer array of size N.

Output Format

Print True or False

Example

Input

4
23 5 7 13

Output

True

Constraints

1<= N <= 10

1<= nums[i] <= 10

^{5}1<= nums[i] <= 10

^{9}Loading...

View Submissions

Console