[Balkan2012]handsome

时间限制:10s      空间限制:128MB

题目描述

一个N位数是handsome的,当且仅当其中只有0/1/2,而且相邻的两个数构成的数对不在危险集合中。
N位数A在排列P的意义下字典序小于B,如果存在一个k使得A[P[1]]=B[P[1]],A[P[2]]=B[P[2]]..A[P[k]]=B[P[k]],A[P[k+1]]<B[P[k+1]]。
给定N,危险集合,一个排列P,以及一个handsome数T,统计在排列P意义下小于T的handsome数的个数。输出答案模1e9+7的值。


输入格式

输入的第一行为N
接下来一行N个整数,表示排列P
接下来一行一个整数M,表示危险集合中数对的个数。接下来一行M对数,表示危险集合
最后一行为T
N<=400000,m>=1,保证T是handsome数


输出格式


样例输入

3
2 1 3
2
22 13
321

样例输出

9

提示

没有写明提示


题目来源

Dragonite提供翻译

Menuappsclose