Background

无

Description

给定n个正整数，现在从这$n$个数中任意且不重复地选择任意个整数，问选择的所有数的平均值为整数的方案有多少，对1e9+7取模

Format

Input

第一行为n，表示有n个数

第二行n个整数，整数间以空格隔开

Output

满足题意的方案数

Samples

3
2 6 2

6

Limitation

1s, 1024KiB for each test case.