该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

输入格式

测试数据共三行。
第一行是一个整数n 表示有 n 朵花。（2 ≤ n ≤ 22）
第二行有n 个整数，分别表示这 n 朵花的价格 a[i]。（1 ≤ a[i] ≤ 10^7）
第三行是一个整数w 代表四糸乃开始时持有的钱数（1 ≤ w ≤ 10^8）

输出格式

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

样例输入

5
5 6 1 3 4
39

样例输出

1

数据规模与提示

只有一种方案，买第1，2，3，4 朵花，买的朵数 4 是 4 的倍数且不为 0 不为 n，剩余钱数 24是 4 的倍数，符合题意。因为题目中只有这一种方案符合题意，所以答案是 1。