题号：NC19490
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 5秒，其他语言10秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld
题目描述
妮可罗宾作为历史学家，在学习考古学时，注意到曾经有一个时代热衷于无聊的数学题。在书上记载的众多题目中，她一下子就被这道题吸引了：
给出一个长度为N的数列P，表示第i个位置是1的概率为
，是0的概率为
.
对于每一个01数列，我们都可以找出它的最长不下降子序列，记长度为l；在所有的这些最长不下降子序列中，可以找出0最多的个数，记为z.
例如，有01数列0111000111，其中最长不下降子序列有两个：0111111和0000111，而0000111含有更多的
0，故对于此数列：l = 7,z = 4.
现在希望求得%20%5E%20N)%20%5Cmod%201000000007)
，即为%20%5E%20N)
的数学期望
。可以证明%5EN))
必为整数。
给出一个长度为N的数列P，表示第i个位置是1的概率为
对于每一个01数列，我们都可以找出它的最长不下降子序列，记长度为l；在所有的这些最长不下降子序列中，可以找出0最多的个数，记为z.
例如，有01数列0111000111，其中最长不下降子序列有两个：0111111和0000111，而0000111含有更多的
0，故对于此数列：l = 7,z = 4.
现在希望求得
输入描述:
第一行一个整数N(1 ≤ N ≤ 500).
第二行N个整数，依次是P1, P2, ..., PN(0 ≤ Pi ≤ 1000).
输出描述:
一个整数代表答案。