本题最大的突破口在于观察这些操作到底目的是啥。其实它做的是找这个序列的previous permutation。

我们想一下```LC31 next permutation```是怎么操作的。已知序列```12375421```，对于next permuation，我们想尽量保持高位的数字不变，将数字重新排列使其稍微增大一点点。但是我们发现后面五位75421已经是降序了，如果我们保持高3位不变、只变动低5位的话，无论如何不能使得序列变大。所以我们只能变动第3位，试图将其变高一点点，那么变成哪一个呢？显然就是将后5位里面挑一个比3大一点点的数字，那么就是4.当我们把第3位提升之后，剩下的5位自然要越小越好，那么就是将剩下没有使用的37521升序排列即可：12412357

如果我们将上述的过程逆过来看，我们就会发现题目中的操作其实就是从12412357->12375421的过程。对于previous permuation，我们想尽量保持高位的数字不变，将数字重新排列使其稍微增小一点点。但是我们发现后面五位12357已经是降序了，如果我们保持高3位不变、只变动低5位的话，无论如何不能使得序列变小。所以我们只能变动第3位，试图将其变小一点点，那么变成哪一个呢？显然就是将后5位里面挑一个比4小一点点的数字，那么就是3.当我们把第3位确定之后，剩下的5位自然要越大越好，那么就是将剩下没有使用的37521降序排列即可：12375421。

综上，我们每操作一次，就会将这个序列的排列按照字典序变小一点。所以本题其实就是求有多少种字典序比所给字符串小的排列。

至此，我们又可以联想到```LC60. Permutation Sequence```，求字典序第k个的排列是多少。两者的方法是一样的，就是固定高位，计算低位的自由排列的个数。对于本题，假设我们处理3xxxxxx，如果最高位可以选取小于3的数字的话（即1和2），后面6位的数字可以任意排列。所以我们可以计算小于3xxxxxx的排列的数目是```a*6!```，其中a表示我们在所有元素中有多少个小于3的（包括重复的）可以放在最高位。但是这个阶乘算法有个问题，那就是我们认为每个元素都是distinct，如果有相同的元素出现在排列里，他们的全排列其实重复的。解决方法其实很简单，如果全排列里面有k个1，那么全排列的数目就除以k!。也就说，我们想象这k个1在内部进行的全排列其实都被总排列计算进去了，我们现在把它规约掉。同理，如果全排列里面有若干个相同的其他元素，也都相应除以元素数目的阶乘。

上面计算的排列的数目，其实是固定最高位小于3. 我们接下来要计算固定最高位等于3. 那么其实相当于递归处理第二位。假设我们处理的是38xxxxx，那么此时我们统计最高位是3、第二位小于8的排列个数。注意此时因为我们固定了最高位是3，那么我们必须提前将一个3从pool里面删除。同理，我们依照前面的方法计算```b*5!```其中b表示我们在所有元素中有多少个小于8的（包括重复的）可以放在第二位，后面5!表示确定了第一位和第二位之后剩下的5个元素可以任意排列。然后记得再规约重复元素的阶乘。

最后要说明的是，由于涉及到了除法，大数取余必须用乘法逆元。即```(a/b) mod M = (a mod B) * inv(b, M)```. 乘法逆元的计算方法见模板。