Զանգվածի լրացում
Տրված է n էլեմենտ պարունակող զանգված, որի բոլոր արժեքները գտնվում են 1-ից մինչև m միջակայքում։ Բացի այդ, երկու հարևան տարրերի բացարձակ տարբերությունը չի գերազանցում 1-ը։ Այս զանգվածում որոշ արժեքներ ջնջվել են (նրանք նշված են 0-ով), և ձեզ խնդրում են հաշվել, թե քանի տարբեր ձևով կարելի է լրացնել ջնջված արժեքները՝ պահպանելով նշված պայմանները:
Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n (1 ≤ n ≤ ) և m (1 ≤ m ≤ 100)։
Հաջորդ տողում տրվում են n ամբողջ թվեր (1 ≤ ≤ m), որոնք ներկայացնում են զանգվածի էլեմենտները։ Եթե -ն 0 է, ուրեմն այդ դիրքի արժեքը ջնջված է:
Ելք
Ծրագիրը պետք է տպի, թե քանի ձևով կարելի է լրացնել զանգվածը՝ առանց խախտելու պայմանները։ Քանի որ արդյունքը կարող է շատ մեծ լինել, պետք է տպել դրա -ի վրա բաժանելիս ստացվող մնացորդը։
Օրինակներ
Input | Output |
|---|---|
3 5 2 0 2 | 3 |
Բացատրություն
2 1 2
2 2 2
2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB