给定一个大小为N-1且只包含0和1的序列A1到AN-1，如果一个1到N的排列P1到PN满足对于1≤ii=0时Pii+1，当Ai=1时PiPi+1，则称该排列符合要求，那么有多少个符合要求的排列？

输入描述:

第一行包含一个整数N，1第二行包含N-1个空格隔开的整数A1到AN-1，0≤Ai≤1。

输出描述:

输出符合要求的排列个数对109+7取模后的结果。