사탕

바이테크는 비테크의 생일 파티에 간다. 비테크는 단것을 좋아해서, 바이테크는 자신이 산 사탕 봉지 중 일부를 비테크에게 주려고 한다. 바이테크는 봉지를 n개 샀고, i번째 봉지에는 a_i개의 사탕이 들어 있다.

봉지가 무거워서, 바이테크는 봉지를 전부 비테크에게 가져가야 하는지 고민하고 있다. 바이테크는 봉지의 공집합이 아닌 부분집합을 골라 비테크에게 가져가고, "사탕이 모두 x개 있어. 몇 개를 원해?"라고 말한다. 여기서 x는 가져간 봉지들에 든 사탕의 총합이다. 비테크는 $[1, x]$ 범위의 정수 y를 아무거나 고른다.

비테크가 어떤 y를 고르든, 바이테크는 가져간 봉지 중 일부를 골라(나머지는 자기가 갖는다) 고른 봉지들의 사탕 합이 정확히 y가 되도록 할 수 있어야 한다. 봉지를 뜯을 수는 없다. 포장 없이 사탕만 건네는 것은 무례하기 때문이다.

바이테크가 비테크에게 가져갈 수 있는 공집합이 아닌 봉지 부분집합의 개수를 구하라. 비테크가 무엇을 요구하든, 정확히 그만큼의 사탕을 건넬 수 있어야 한다.

첫째 줄에 바이테크가 가진 사탕 봉지의 개수 n ($1 \le n \le 5000$)이 주어진다.

둘째 줄에 각 봉지에 든 사탕의 개수 a_1, a_2, ..., a_n ($1 \le a_i \le 5000$)이 주어진다.

바이테크가 비테크에게 가져갈 수 있는 봉지 부분집합의 개수를 $10^9 + 7$로 나눈 나머지를 출력한다.

예시 설명: 바이테크는 다음과 같은 서로 다른 봉지 부분집합 8개를 가져갈 수 있다: {5}, {1, 5}, {1, 3, 5}, {1, 4, 5}, {1, 3, 4, 5}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 2, 3, 4, 5}. 첫 번째, 두 번째, 네 번째, 다섯 번째 봉지를 가져가기로 했는데 비테크가 사탕 9개를 원하면, 바이테크는 첫 번째와 두 번째 봉지만 건넬 수 있다. 첫 번째, 두 번째, 다섯 번째 봉지만 가져가는 것은 불가능하다. 비테크가 사탕 6개를 원하면 바이테크가 대답할 방법이 없기 때문이다.