Дадена е низа од N картончиња на кои се запишани цифри. Ако отстраниме дел од картончињата (0 или повеќе), а преостанатите ги гледаме како еден број (без разлика на местата помеѓу нив), може да добиеме најразлични броеви. На пример, од почетна низа 408 добиваме вкупно 7 можни „редоследни комбинации“: 408, 40, 08, 48, 0, 4 и 8. Интересно, но од горните 7 добиени редоследни комбинации, 6 претставуваат број делив со 8.

Нека ви е дадена низата од N цифри. Избројте колку броеви добиени на гореопишаниот начин се деливи со 8. Испечатете го резултатот по модул (10⁹+7), бидејќи може да е многу голем број.

Забелешка: Ако еден исти број се формира повеќе пати (со отстранување на различна комбинација од картончиња), тој се зема во предвид онолку пати колку што бил формиран.

Влез

Во првиот ред има еден цел број N (1 ≤ N ≤ 200 000).
Во вториот ред е низата од N цифри.

Бодување:
Кај тест случаи кои носат 15% од поените важи дека N≤20.
Кај тест случаи кои носат дополнителни 25% од поените важи дека N≤1000.

Излез

Во првиот ред отпечатете го бараниот број по модул (10⁹+7).
(За дадени два цели броја А и B, A модул B го означува остатокот кој се добива при делење на A со B. На пример, бројот 7 станува 1 по модул 3.)

Ограничувања

Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes

Примери

влез
3
408

излез
6

влез
3
887

излез
3

Објаснување за првиот пример: Даден е во текстот на задачата.

Објаснување за вториот пример: Од дадената низа може да се добијат броевите: 887 , 87 (кога ќе се отстрани првото картонче), 87 (кога ќе се отстрани второто картонче), 88 (кога ќе се отстрани третото картонче), 8 (кога ќе се отстранат второто и третото картонче), 8 (кога ќе се отстранат првото и третото картонче), 7 (кога ќе се отстранат првото и второто картонче). Од нив броевите 88, 8 и 8 се деливи со 8.