Home_W的送分题(银)

先给出n个整数a1,a2,a3,……an

刚开始Home_W手没有任何数。

接着m次操作，每个操作只能从a[l],a[l+1],……,a[r-1],a[r]中选出一个数加入自己的手中，或者不选。

最后，Home_W想要手中数字之和等于x，问Home_W有多少种选法

两种选法被认为是不同，当且仅当，存在至少一次操作，两种选法，选的数字的下标不同

单组数据

第一行包含两个整数n,m,x

接下来一行有n个整数，a1,a2,a3,……an

再接下来m行，每行有两个整数l,r

其中

1<=ai,n,m<=1000

1<=x<=10000

ai可能有重复。

1<=l<=r<=n

输出一个整数，代表可行的方案数，由于结果很大请对1004535809取模

4 4 12
10 10 4 6
1 4
2 4
3 4
1 2

4
hint
样例要么选2个6，要么选3个4
选2个6有3种方案
选3个4有1中方案