说明

商店里有$n$朵花,四糸乃有$w$元钱。$n$朵花各不相同，四糸乃要买这$n$朵花其中的其中的若干朵。由于四糸乃很喜欢4这个数字，所以她希望她买的花的朵数是4的倍数，并且买完花后剩下的钱（可以为0）也是4的倍数。此外，因为已经来到花店了，所以四糸乃不能一朵花也不买。因为花店接下来还要做生意，四糸乃也不能将这$n$朵花全部买走。那么四糸乃一共有多少种买花方案呢？

输入格式

测试数据共三行。

第一行是一个整数$n$表示有$n$朵花。

第二行有n个整数，分别表示这$n$朵花的价格$a[i]$。

第三行是一个整数$w$代表四糸乃开始时持有的钱数。

输出格式

输出买花的方案数，输出占一行

样例

5
5 6 1 3 4
39

1

数据范围

• $2 \le n \le 22$
• $1\le a[i] \le 10^7$
• $1\le w \le 10^8$

来源

东北林业大学OJ网(acm.nefu.edu.cn)1665