fork download
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const long long N=2000005, mod=1000000007;
  5.  
  6. int power(int a, int b, int p)
  7. {
  8. if(a==0)
  9. return 0;
  10. int res=1;
  11. a%=p;
  12. while(b>0)
  13. {
  14. if(b&1)
  15. res=(1ll*res*a)%p;
  16. b>>=1;
  17. a=(1ll*a*a)%p;
  18. }
  19. return res;
  20. }
  21.  
  22. int pref[N], inv[N], pref2[N], hp2[N];
  23.  
  24. // Returns (1/l + 1/(l+1) + ... + 1/r)
  25. int cal(int l, int r)
  26. {
  27. if(l>r)
  28. return 0;
  29. return (pref[r]-pref[l-1]+mod)%mod;
  30. }
  31.  
  32. // Returns (1/(l*(l+1)) + ... + 1/(r(r+1)))
  33. int cal2(int l, int r)
  34. {
  35. if(l>r)
  36. return 0;
  37. return (pref2[r]-pref2[l-1]+mod)%mod;
  38. }
  39. void pre()
  40. {
  41. pref[0]=0;
  42. pref2[0]=0;
  43. for(int i=1;i<N;i++)
  44. {
  45. inv[i]=power(i, mod-2, mod);
  46. pref[i]=(pref[i-1]+inv[i])%mod;
  47. int mul2=(i*(i+1))%mod;
  48. pref2[i]=(pref2[i-1] + power(mul2, mod-2, mod))%mod;
  49. hp2[i]=((i*(i-1))%mod)%mod;
  50. }
  51. }
  52. int solve2(int n, int m, int k)
  53. {
  54. if((n*m)<k)
  55. return 0;
  56. int ans=0;
  57. int reqv=(k-1)/n;
  58. if(reqv<m)
  59. {
  60. int prob=(reqv*inv[reqv+n-1])%mod;
  61. int exp=(prob*(1ll + cal(n+reqv, m+n-2)))%mod;
  62. ans=(ans + exp)%mod;
  63. }
  64. int reqh=(k-1)/m;
  65. if(reqh<n)
  66. {
  67. int prob=(reqh*inv[reqh+m-1])%mod;
  68. int exp=(prob*(1ll + cal(m+reqh, m+n-2)))%mod;
  69. ans=(ans + exp)%mod;
  70. }
  71. for(int i=1;i<min(n, k);i++)
  72. {
  73. reqv=(k-1)/i;
  74. if(reqv>=m)
  75. continue;
  76. int prob=(inv[i+reqv]*reqv)%mod;
  77. prob=(prob*inv[i-1+reqv])%mod;
  78. int num1=(hp2[i+reqv+1]*cal2(i+reqv, i+m-2))%mod;
  79. int num2=((i+reqv+1)*cal(i+reqv+1, i+m-1))%mod;
  80. int num=((num1+num2)*inv[i+reqv+1])%mod;
  81. int exp=(prob*(2ll + cal(i+reqv+1, reqv+(n-1))+num))%mod;
  82. ans=(ans + exp)%mod;
  83. }
  84. for(int i=1;i<min(m, k);i++)
  85. {
  86. reqh=(k-1)/i;
  87. if(reqh>=n)
  88. continue;
  89. int prob=(inv[i+reqh]*reqh)%mod;
  90. prob=(prob*inv[i-1+reqh])%mod;
  91. // Sum for cases when the (reqh+i)th horizontal line comes in the gap b/w x_v and y1_h
  92. int num1=(hp2[i+reqh+1]*cal2(i+reqh, i+n-2))%mod;
  93. // Sum for cases when the (reqh+i)th horizontal line comes in the gap to the left of x_v
  94. int num2=((i+reqh+1)*cal(i+reqh+1, i+n-1))%mod;
  95. int num=((num1+num2)*inv[i+reqh+1])%mod;
  96. int exp=(prob*(2ll + cal(i+reqh+1, reqh+(m-1))+num))%mod;
  97. ans=(ans + exp)%mod;
  98. }
  99. return ans;
  100. }
  101. int32_t main()
  102. {
  103. pre();
  104. int n, m, k;
  105. cin>>n>>m>>k;
  106. cout<<solve2(n, m, k);
  107. }
Success #stdin #stdout 2.4s 66052KB
stdin
Standard input is empty
stdout
Standard output is empty