Զանգվածի լրացում
Տրված է
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