Айбар мен Абай — екі бауыр. Оларға \(n\) бүтін теріс емес сандардан тұратын массив \(a\) берілді. Айбар өспелі тізбектерді, ал Абай кемімелі тізбектерді ұнатады. Сондықтан олар массив \(a\)-ның әр элементін екі теріс емес бүтін санға \(0 \le b_i \le a_i\) және \(0 \le c_i \le a_i\) бөлуге шешім қабылдады, осылайша келесі шарттар орындалуы тиіс:

1. Тізбек \(b\) өспелі: \(b_i \le b_{i+1}\) барлық \(1 \le i < n\) үшін.

2. Тізбек \(c\) кемімелі: \(c_i \ge c_{i+1}\) барлық \(1 \le i < n\) үшін.

3. Массивтың әр элементі дұрыс бөлінген: \(b_i + c_i = a_i\) барлық \(1 \le i \le n\) үшін.

Массив \(a\)-ны жоғарыда көрсетілген шарттарға сәйкес \(b\) және \(c\) екі массивке бөлу тәсілдерінің санын табыңыз. Жауап өте үлкен болуы мүмкін, сондықтан оны \(10^9+7\) модулі бойынша шығарыңыз.

Енгізу

Бірінші жолда бүтін сан \(n\) \((1 \le n \le 2000)\) — массив \(a\)-ның ұзындығы.

Екінші жолда \(n\) бүтін сан \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le 1000)\) арасына бос орын қойып жазылған.

Шығару

Бір бүтін санды шығарыңыз — \(b\) және \(c\) тізбектерінің рұқсат етілген жұптарының саны, \(10^9+7\) модулі бойынша.

Мысалдар

Енгізу 1

3
3 2 4

Жауап 1

10