В университете, где учится Вася, оценки представляют собой строки одинаковой длины, причем оценка x считается лучше чем y, если строка y лексикографически меньше строки x.
Недавно в этом университете прошла важная контрольная, по которой Вася получил оценку a. Из-за большого количества студентов, преподаватель не может запомнить оценку каждого, но он точно помнит оценку b такую, что все студенты получили оценку строго меньше чем b.
Вася недоволен своей оценкой и хочет её исправить. Для этого он может как угодно поменять местами символы в строке соответствующей его оценке. Сейчас Васю интересует количество различных способов улучшить свою оценку так, чтобы преподаватель не заподозрил неладного.
Более формально: даны две строки одинаковой длины a и b, требуется вычислить количество различных строк c таких, что:
1) c может быть получена из a путем перестановки некоторых символов, то есть c является перестановкой a
2) a лексикографически меньше c
3) c лексикографически меньше b
Если длина строки x равна длине строки y, то x лексикографически меньше y, если существует такое i, что x1 = y1, x2 = y2, ..., xi - 1 = yi - 1, xi < yi.
Так как ответ может быть очень большим, вычислите только остаток от деления ответа на 109 + 7.
Примечание
В первом тесте из строки abc можно получить строки acb, bac, bca, cab, cba, все они больше строки abc, но меньше строки ddd. Поэтому ответ равен 5.
Во втором тесте любая строка, которую можно получить из abcdef, будет больше строки abcdeg. Поэтому ответ равен 0.