## Yet Another Contest 4 P5 - Signpost

View as PDF

Points: 20 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 512M

Author:
Problem type

Australia consists of a single long road from west to east. There are stores along this road, with the -th store having an integer position of .

You have been commissioned to design and install a signpost. First, you will choose a real number , representing the position of the signpost. Let represent the distance from the signpost to the -th store. The signpost will contain all stores on it in some order from top to bottom, under the condition that if , then store is listed higher up on the signpost than store . If two stores are equidistant from the signpost, then you can decide which of stores and is listed higher up the signpost.

Your first task is to calculate how many distinct signposts you could make. Since this number may be large, you want to find this number modulo .

#### Constraints

All are distinct.

#### Input Specification

The first line contains a single integer, .

The second line contains space-separated integers, .

#### Output Specification

On a single line, print the number of possible distinct signposts, modulo .

#### Sample Input

3
1 2 3

#### Sample Output

4

#### Explanation

Consider the case where the signpost is at position . Then . From the top to bottom, the signpost could list stores then then , or stores then then .

If we consider all possible values of , including non-integer and negative values, we see that there are distinct signposts which can be made.