007 - アカベコ20

時間制限 1 秒 / メモリ制限 256 MB / 得点 9 / x 4 /


TLE
1sec
MLE
256MB
得点
9

問題文

「アカベコ20」は、イヅア地方の専用劇場で公演を開催しているグループです。アカベコ20のそれぞれのメンバーは、ある一定の日数ごとに公演に参加することになっています。

今日の公演ではメンバーが全員参加していました。プロデューサーであるあなたは、メンバーから、今後の公演のメンバーの組み合わせを教えてほしい、と頼まれました。あなたは、公演に参加するメンバーの組み合わせがいくつあるのかを数えることにしました。

アカベコ20のメンバー数と、それぞれのメンバーが公演に参加する周期が1日単位で与えられたとき、参加するメンバーの組み合わせが何通りあるかを数えるプログラムを作成せよ。このとき、グループは同じメンバーで永遠に存続すると仮定する。ただし、だれも参加しない場合は組み合わせに含めないこととする。

入力

入力は以下の形式で与えられる。

$N$
$p_1$ $p_2$ ... $p_N$

1行目にアカベコ20のメンバー数$N$ ($1 \leq N \leq 20$)が与えられる。続く1行に、それぞれのメンバーが公演に参加する周期$p_i$ ($1 \leq p_i \leq 40$)が与えられる。

出力

参加するメンバーの組み合わせの数を1行に出力する。

入出力例

入力例1

3
3 5 2

出力例1

7

入力例2

3
2 3 6

出力例2

3

周期が2日のメンバーのみが参加する公演,周期が3日のメンバーのみが参加する公演,周期が2日、3日、6日のメンバーが参加する公演の3通りとなる。