Вам дан массив целых чисел \(b_1, b_2, \ldots, b_n\).
Массив \(a_1, a_2, \ldots, a_n\) целых чисел смешанный, если для всех \(i\) (\(1 \leq i \leq n\)) хотя бы одно из этих двух условий выполнено:
- \(b_i = a_i\), или
- \(b_i = \sum_{j=1}^{i} a_j\).
Найдите количество смешанных массивов \(a_1, a_2, \ldots, a_n\). Поскольку ответ может быть очень большим, найдите его по модулю \(10^9 + 7\).
Выходные данные
Для каждого набора входных данных выведите единственное целое число: количество смешанных массивов \(a_1, a_2, \ldots, a_n\) по модулю \(10^9 + 7\).
Примечание
В первом наборе входных данных смешанные массивы — это \([1, -2, 1]\), \([1, -2, 2]\), \([1, -1, 1]\).
Во втором наборе входных данных смешанные массивы — это \([1, 1, 1, 1]\), \([1, 1, 1, 4]\), \([1, 1, 3, -1]\), \([1, 1, 3, 4]\), \([1, 2, 0, 1]\), \([1, 2, 0, 4]\), \([1, 2, 3, -2]\), \([1, 2, 3, 4]\).
В четвертом наборе входных данных единственный смешанный массив — это \([0, 0, 0, 1]\).