Bilyard topları

У sizdə N bilyard topu və K qutu var. Toplar 1-dən N-ə qədər, qutular isə 1-dən K-ə qədər nömrələnib. Hər bilyard topunun üzərində müəyyən bir tam ədəd yazılıb. Siz topları qutulara elə yerləşdirməlisiniz ki, hər qutuda ən azı bir top olsun. Bundan sonra hər qutunun dəyərini həmin qutudakı bilyard toplarının üzərindəki ədədlərin AND cəmi kimi hesablamaq olar. Burada AND bitwise konjunksiyası əməliyyatıdır.

Siz maksimum qutu dəyərlərinin (adi) cəmini və bu cəmi əldə etməyin mümkün yollarının sayının 1000000007-ə bölünməsindən qalanı tapmalısınız. İki yol fərqli sayılır, əgər onlara görə ən azı bir top fərqli qutularda yerləşdirilibsə. Qeyd edək ki, eyni ədədlərə malik toplar fərqli sayılır.

Giriş məlumatları

Birinci sətirdə iki tam ədəd N və K boşluqla ayrılmış şəkildə verilir. Növbəti sətirdə N tam ədəd A[1],..., A[N] boşluqla ayrılmış şəkildə verilir. Burada A[j] j-ci topun üzərində yazılmış tam ədəddir.

Çıxış məlumatları

İki tam ədəd boşluqla ayrılmış şəkildə — maksimum qutu dəyərlərinin cəmi və bu cəmi əldə etməyin mümkün yollarının sayının 1000000007-ə bölünməsindən qalanı.

Məhdudiyyətlər

1 ≤ K ≤ N ≤ 100000 (10^5),

0 ≤ Aj ≤ 1000000000 (10^9).

Qeydlər

Birinci nümunədə maksimum cəm 11 = 7 + (5 AND 4)-ə bərabərdir. Onu aşağıdakı yollarla əldə etmək olar:

• {7}-{4,5}

• {4,5}-{7}