In the Lonely Mountain, there are a lot of treasure well protected by dwarfs. Later, one day, the last dragon Smaug came and sensed the treasure being. As known to all, dragons are always much too greedy for treasure. So definitely, the war between dwarfs and Smaug begins.

During the war, two goblins Alice and Bob are turned into frogs by Gandalf, The Grey. In front of them, there are lotus leaves in a line. In order to break the spell, they must jump from the -st lotus leaf to the -th lotus leaf. If the frog is now on the -th lotus leaf instead of the -th lotus leaf, it can jump to a lotus leaf in range .

Goblins are lack of intelligence and it's also true even after turned into frogs. So Alice and Bob will jump randomly, which means, they will separately pick an available lotus leaf in every jump uniformly at random.

Since Alice and Bob have already being playing games for decades, so they want to know the probability that they jump to the -th lotus leaf with the same count of jumps.

The first line contains an integer  , denoting the number of lotus leaf.

The second line contains  integers , where the -th integer   indicates the range of lotus leaves that can be reached from the -th lotus leaf.

Output a line containing a single integer, indicating the probability that Alive and Bob jump to -th lotus leaf with the same count of jumps, taken modulo .

Formally speaking, let the result, which is a rational number, be  as an irreducible fraction, you need to output , where  is a number such that . You may safely assume that such  always exists.

5
1 1 1 1

1

5
4 3 2 1

440198031