fork(2) download
  1. #include <iostream>
  2. #include <string>
  3. #include <math.h>
  4. #include <algorithm>
  5. #define inf 1000000000
  6. #define MOD 1000000007
  7.  
  8. using namespace std;
  9. typedef long long ll;
  10.  
  11. string s, s2;
  12. ll cnt[26];
  13. ll fact[1001000];
  14. ll _fact[1001000];
  15.  
  16. ll bin_pow(ll x, ll n)
  17. {
  18. if (!n)
  19. return 1;
  20. if (n % 2)
  21. return (x*bin_pow(x, n - 1)) % MOD;
  22. ll y = bin_pow(x, n / 2);
  23. return (y*y) % MOD;
  24. }
  25.  
  26. void init()
  27. {
  28. fact[0] = 1;
  29. for (int i = 1; i < 1001000; i++)
  30. fact[i] = (fact[i - 1] * i) % MOD;
  31. _fact[1000999] = bin_pow(fact[1000999], MOD - 2);
  32. for (int i = 1000998; i >= 0; i--)
  33. _fact[i] = (_fact[i + 1] * (i + 1)) % MOD;
  34. }
  35.  
  36. ll f(string str)
  37. {
  38. ll res = 0;
  39. ll perm = fact[s.size()];
  40. for (int i = 0; i < 26; i++)
  41. cnt[i] = 0;
  42. for (int i = 0; i < s.size(); i++)
  43. cnt[s[i] - 'a']++;
  44. for (int i = 0; i < 26; i++)
  45. perm = (perm * _fact[cnt[i]]) % MOD;
  46. for (int i = 0; i < s.size(); i++)
  47. {
  48. perm = (perm * _fact[s.size() - i]) % MOD;
  49. perm = (perm * fact[s.size() - i - 1]) % MOD;
  50. for (int j = 0; j < str[i] - 'a'; j++)
  51. {
  52. if (!cnt[j])
  53. continue;
  54. perm = (perm * fact[cnt[j]]) % MOD;
  55. cnt[j]--;
  56. perm = (perm * _fact[cnt[j]]) % MOD;
  57. ll add = fact[s.size() - i - 1];
  58. res = (res + perm) % MOD;
  59. perm = (perm * fact[cnt[j]]) % MOD;
  60. cnt[j]++;
  61. perm = (perm * _fact[cnt[j]]) % MOD;
  62. }
  63. if (!cnt[str[i] - 'a'])
  64. break;
  65. perm = (perm * fact[cnt[str[i] - 'a']]) % MOD;
  66. cnt[str[i] - 'a']--;
  67. perm = (perm * _fact[cnt[str[i] - 'a']]) % MOD;
  68. }
  69. return res;
  70. }
  71.  
  72. int main()
  73. {
  74. init();
  75. cin >> s >> s2;
  76. cout << (f(s2) - f(s) - 1 + MOD) % MOD << endl;
  77. }
Success #stdin #stdout 0.01s 30880KB
stdin
Standard input is empty
stdout
1000000006