Волшебнику Ринсвинду известно всего лишь одно заклинание. И как бы он не старался изучить ещё, у него никак не получалось: новые заклинания не хотели оседать у него в голове и забывались спустя 3+5 секунд после запоминания. Поэтому он должен попробовать научиться получать новые заклинания из того, которое ему известно. Поскольку известное ему заклинание является достаточно могущественным, эта затея может оказаться удачной.

Заклинание можно представить как строку S, состоящую из строчных латинских символов. Для конструирования новых заклинаний Ринсвинд может поменять местами два соседних символа. Для того, чтобы заклинание не утратило свою силу есть одно ограничения: нельзя менять местами символы в позициях i и i + 1, если до этого уже меняли местами символы в позициях j и j + 1 и позиция j находится правее i, т.е. j > i. Например, он может из abc cконструировать abc, acb, bac и bca, но не может cab и cba.

Заклинание может быть достаточно длинным, поэтому оно описывается несколькими блоками. Каждый блок представляет из себя строку и число, обозначающего количество повторений этой строки.

Ринсвинд сейчас занят тренировкой произношения, но ему очень интересно, каким потенциальным количеством заклинаний он может владеть отточив технику конструирования до совершенства. Помогите ему посчитать это количество. Напомним, что Ринсвинд не может запоминать новые заклинания, поэтому конструировать заклинания он может только из исходного.