#215778. [JAG 2023 Summer Camp #3] Gacha 101

For each , there are balls with written on them. These are put into a box and mixed up. The string variable consists of initially "0"s. Balls are taken out of the box one by one (uniformly at random and independently). When a ball with written on it is drawn, the -th character of is changed to "1" (it remains unchanged if it was already "1"). Find the probability, modulo , of having a point during this process that contains "101" as a contiguous substring.

The input consists of a single test case of the following format.

The first line consists of an integer between and , inclusive. The second line consists of positive integers . For each (), represents the number of balls written. And they satisfy .

Output in a line the probability modulo .

样例输入 1

3
1 2 3

样例输出 1

465847365

样例输入 2

10
3 1 4 1 5 9 2 6 5 3

样例输出 2

488186016

Note

• How to find the probability modulo
  • It can be proved that the sought probability is always a rational number. Additionally, the constraints of this problem guarantee that if the sought probability is represented as an irreducible fraction , then is not divisible by . Here, there is a unique such that , so report this .