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:
Choose any positive integer . Then, replace a_i with a_i \bmod x for every 1 \le i \le n.
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.
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 a single integer — the number of different arrays you can achieve with these operations.
Example
Example 1
Example 2
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].