Se consideră numerele naturale N şi K şi cifrele nenule distincte c[1], c[2], …, c[N].

Cerința

Să se determine câte numere de K cifre formate doar cu cifrele c[1], c[2], …, c[N] sunt divizibile cu 3. Pentru că acest număr poate fi foarte mare, rezultatul se va determina modulo 4001.

Date de intrare

Fișierul de intrare divtrei.in conține pe prima linie numerele naturale N şi K separate printr-un spațiu, iar linia a doua cele N cifre distincte c[1], c[2], …, c[N], separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire divtrei.out va conține o singură linie pe care va fi scris un singur număr natural, reprezentând numărul (modulo 4001) de numere de K cifre formate doar cu cifrele c[1], c[2], …, c[N] și divizibile cu 3.

Restricții și precizări

• 1 ≤ N ≤ 9
• 2 ≤ K ≤ 1000
• 1 ≤ c[1], c[2], ..., c[N] ≤ 9
• Definim x modulo 4001 ca fiind restul împărțirii întregi a lui x la 4001. De exemplu, 4002 modulo 4001 = 1.

Exemplu

divtrei.in

3 2
1 3 2

divtrei.out

3

Explicație

Trebuie determinat numărul de numere de K = 2 cifre formate doar din cifrele 1, 2 şi 3 şi care sunt divizibile cu 3. Acestea sunt în număr de 3, şi anume: 12, 21, 33. Rezultatul 3 împărţit la 4001 furnizează restul 3.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("divtrei.in");
ofstream cout("divtrei.out");

int n , k , f[3] , a[3] , b[3] , c;

int main()
{
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> c;
        f[c % 3]++;
    }
    a[0] = f[0];
    a[1] = f[1];
    a[2] = f[2];
    for(int i = 2 ; i <= k ; i++)
    {
        b[0] = a[0] * f[0] + a[1] * f[2] + a[2] * f[1];
        b[1] = a[0] * f[1] + a[1] * f[0] + a[2] * f[2];
        b[2] = a[0] * f[2] + a[1] * f[1] + a[2] * f[0];
        a[0] = b[0] % 4001 ;
        a[1] = b[1] % 4001 ;
        a[2] = b[2] % 4001 ;
    }
    cout << a[0];
    return 0;
}