SPOJ in Armenian

Հանրահայտ ամսագրերից ﬔկը յուրաքանչյուր համարում տեղադրում է հատուկ գլուխկոտրուկ։ Գլուխկոտրուկը իրենից ներկայացնում է 2 × N չափի աղյուսակ, որի յուրաքանչյուր վանդակ կամ դատարկ է, կամ պարունակում է որևէ թվանշան։ Գլուխկոտրուկը լուծել ու համար անհրաժեշտ է լրացնել բոլոր ազատ վանդակները թվանշաններով այնպես, որ արդյունքում աղյուսակի յուրաքանչյուր 2 × 3 չափի կտորում տարրերի գումարը հավասար լինի նախապես ֆիքսված K թվին։

Սակայն սա դեռ աﬔնը չէ։ Լուծելով գլուխկոտրուկը դուք կարող եք ուղարկել ձեր լուծումը ամսագրի խմբագրություն։ Եթե ձեր գտած լուծումը ﬕնչ ձեզ ոչ ոք չէր գտել դուք կստանաք ձեր ուղարկելուց հետո խմբագրության ձեռքի տակ եղած տարբեր լուծուﬓերի քանակին համապատասխան ﬔտաղադրամ, որպես մրցանակ։

Ձեր խնդիրն է պարզել թե առավելագույնը քանի ﬔտաղադրամ կարող եք ստանալ խմբագրությունից, եթե հայտնի է, որ նույն մարդը չի կարող երկու անգամ գլուխկոտրուկի լուծում ուղարկել խմբագրություն։ Նշենք, որ ամսագիրը հանրահայտ է, և շատ հավանական է, որ ձեզանից առաջ շատերը ուղարկած լինեն իրենց լուծուﬓերը խմբագրություն, ձեզ պետք է հաշվել առավելագույն ﬔտաղադրաﬓերի քանակը լավագույն հնարավոր սցենարի դեպքում։

Քանի որ խնդրի պատասխանը հնարավոր է շատ ﬔծ լինի, պահանջվում է արտածել դրա ﬓացորդը 10⁹ +7 թվի վրա։

Մուտքային տվյալներ

Մուտքի առաջին տողում տրված են N, K, M թվերը (3 ≤ N ≤ 10⁵ , 0 ≤ K ≤ 100, 0 ≤ M ≤ 2 · 10⁵ ) : Հաջորդ M տողերից յուրաքաչյուրը բնութագրում է ﬔկ լրացված վանդակ։ Լրացված վանդակը տրվում է երեք ամբողջ թվերով՝ C սյան համար, R տողի համար և V վանդակի արժեք (0 ≤ C ≤ N-1, 0 ≤ R ≤ 1, 0 ≤ V ≤ 9) :

Ելքային տվյալներ

Առավելագույն հնարավոր մրցանակի չափի ﬓացորդը 10⁹ +7 :

Օրինակ

Մուտք.
5 17 2
0 1 5
4 0 2

Ելք.
11580