Ֆիլյան և տարօրինակ MEX-ը
Ֆիլյան շարունակում է պարապել ICPC համալսարանական օլիմպիադայի համար: Նա սկսեց ուսումնասիրել MEX-ը։
Զանգվածի MEX-ը զանգվածին չպատկանող ամենափոքր ոչ բացասական ամբողջ թիվն է։
Օրինակ՝ [2,2,1]-ի MEX-ը 0 է, քանի որ 0-ն զանգվածի մեջ չէ:
[3,1,0,1]-ի MEX-ը 2 է, քանի որ 0-ն և 1-ը զանգվածի մեջ են, իսկ 2-ը՝ ոչ։
[0,3,1,2]-ի MEX-ը 4 է, քանի որ 0-ն, 1-ը, 2-ը և 3-ը զանգվածի մեջ են, իսկ 4-ը՝ ոչ։
Մի քանի խնդիր լուծելուց հետո Ֆիլյան մասնագիտացավ MEX-ի խնդիրների մեջ, ավելին, խնդիր պատրաստեց։
Տրված է a զանգվածը։
Պետք է գտնել զանգվածը ենթազանգվածների բաժանելու հնարավոր եղանակների քանակը՝ այնպես, որ բոլոր ենթազանգվածներում MEX-երը լինեն իրար հավասար:
Քանի որ պահանջվող քանակը կարող է շատ մեծ լինել, արտածեք այդ թիվը +7-ի վրա բաժանելուց ստացված մնացորդը:
Մուտքային տվյալներ
Առաջին տողում տրված Է n ամբողջ թիվը
(1 ≤ n ≤ 100000)
` զանգվածի էլեմենտների քանակը։Հաջորդ տողում տրված են
a_1, a_2 ... a_n (0 ≤ a_i ≤ n)
զանգվածի n տարրերը։ Ելքային տվյալներ
Պետք է արտածել պահանջվող թիվը +7-ի վրա բաժանելուց ստացված մնացորդը։
Օրինակներ
Մուտք | Ելք |
6
0 1 0 1 0 1 | 5 |
Օրինակի բացատրություն
Բոլոր հնարավոր տարբերակները՝
[0, 1, 0, 1, 0, 1]
[0, 1], [0, 1, 0, 1]
[0, 1, 0] [1, 0, 1]
[0, 1, 0, 1] [0, 1]
[0, 1] [0, 1] [0, 1]
Ենթախնդիրներ
- Ենթախնդիր 1 (20 միավոր)
1 ≤ n ≤ 100
- Ենթախնդիր 2 (30 միավոր)
1 ≤ n ≤ 5000
- Ենթախնդիր 3 (50 միավոր) Լրացուցիչ սահմանափակումներ չկան։
Constraints
Time limit: 20 seconds
Memory limit: 512 MB
Output limit: 1 MB