В университете, где учится Вася, оценки представляют собой строки одинаковой длины, причем оценка 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, что x₁ = y₁, x₂ = y₂, ..., x_i - 1 = y_i - 1, x_i < y_i.

Так как ответ может быть очень большим, вычислите только остаток от деления ответа на 10⁹ + 7.