25213번 - 조각 케이크 (Hard)

안즈는 생일선물로 조각 케이크를 잔뜩 받았다.

케이크를 먹고 행복해하던 안즈는, 남은 케이크를 정리해 냉장고에 넣는 귀찮은 일을 해야 한다는 사실을 깨닫고 말았다.

결국 안즈는 케이크를 정리하는 좋은 방법을 알아냈다. 남은 조각 케이크들을 모아 케이크 한 판으로 만들어 버리는 것이다! 조각 케이크들의 크기의 합이 \(\frac{99}{100}\)판 이상 \(\frac{101}{100}\)판 이하라면 모아서 케이크 한 판으로 만들 수 있다.

그런데 안즈는 문득, 조각 케이크들을 골라서 한 판으로 만들 수 있는 경우의 수가 몇 가지나 되는지 궁금해졌다.

하지만 그 순간 안즈는 매우 귀찮아졌기 때문에, 여러분에게 해결을 부탁했다.

첫째 줄에 남은 조각 케이크의 개수 \(N\)이 주어진다.

둘째 줄에 각 조각 케이크의 크기를 나타내는 정수 \(c_i\)가 공백으로 구분되어 주어진다. 이는 \(i\)번째 조각 케이크의 크기가 \(\frac{1}{c_i}\)판임을 뜻한다.

조각 케이크들을 골랐을 때, 고른 조각 케이크를 모두 합쳐서 케이크 한 판으로 만들 수 있는 경우의 수를 출력한다.

답이 매우 커질 수 있으므로, \(10^9+7\)로 나눈 나머지를 출력한다.

• 1 ≤ \(N\) ≤ 10⁵
• 2 ≤ \(c_i\) ≤ 25