#1388. MTC - Dãy núi

Dãy được gọi là núi nếu tồn tại số tự nhiên sao cho:

• ;
• .

Cho dãy số nguyên , hãy đếm số cách xóa đi một số phần tử của sao cho dãy còn lại là núi. Hai cách xóa được cho là khác nhau nếu tồn tại một vị trí được xóa trong cách này nhưng không được xóa trong cách kia.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương là số phần tử của dãy ;
• Dòng tiếp theo chứa dãy .

Dữ liệu ra:

• In ra phần dư của số cách xóa khi chia cho .

Ví dụ:

Dữ liệu vào:

5
1 2 3 2 1

Dữ liệu ra:

27

Giải thích

• Các cách xóa thỏa mãn là (dãy con sau khi xóa):

Giới hạn:

• ;
• số test với ;
• test với .