Mod Configurations#12911

Mod Configurations

1 second
256 megabytes
Very hard

You are given an array a_1, a_2, \ldots, a_n of positive integers. You are allowed to perform the following operation any number of times:

How many different arrays a_1, a_2, \ldots, a_n can you achieve with these operations? As the number can be very large, output it modulo .

Here x \bmod y denotes the remainder of when dividing by . For example, 6 \bmod 3 = 0, and 6 \bmod 4 = 2.

Input

The first line of the input contains a single integer (1 \leq n \leq 500)  — the length of the array.

The second line of the input contains integers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 500)  — the elements of the array.

Output

Output a single integer  — the number of different arrays you can achieve with these operations.

Examples

Example

Loading
Loading

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first sample, you can get the following arrays: [5], [2], [1], [0].

In the second sample, you can get the following arrays: [6, 5], [2, 1], [1, 0], [0, 5], [0, 2], [0, 1], [0, 0].