fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fs first
  3. #define sc second
  4. #define mx 100005
  5. #define mod 1000000007
  6. #define pii pair<int, int>
  7. #define ll long long
  8. #define mkp make_pair
  9. #define all(a) a.begin(),a.end()
  10. using namespace std;
  11. ll bigmod(ll a, ll p){
  12. 	ll ret = 1;
  13. 	while(p){
  14. 		if(p&1) ret = ret * a % mod;
  15. 		a = a * a % mod;
  16. 		p /= 2;
  17. 	}
  18. 	return ret;
  19. }
  20. ll fact[2000]={682498929, 491101308, 76479948, 723816384, 67347853, 27368307, 625544428, 199888908, 888050723, 927880474, 281863274, 661224977, 623534362, 970055531, 261384175, 195888993, 66404266, 547665832, 109838563, 933245637, 724691727, 368925948, 268838846, 136026497, 112390913, 135498044, 217544623, 419363534, 500780548, 668123525, 128487469, 30977140, 522049725, 309058615, 386027524, 189239124, 148528617, 940567523, 917084264, 429277690, 996164327, 358655417, 568392357, 780072518, 462639908, 275105629, 909210595, 99199382, 703397904, 733333339, 97830135, 608823837, 256141983, 141827977, 696628828, 637939935, 811575797, 848924691, 131772368, 724464507, 272814771, 326159309, 456152084, 903466878, 92255682, 769795511, 373745190, 606241871, 825871994, 957939114, 435887178, 852304035, 663307737, 375297772, 217598709, 624148346, 671734977, 624500515, 748510389, 203191898, 423951674, 629786193, 672850561, 814362881, 823845496, 116667533, 256473217, 627655552, 245795606, 586445753, 172114298, 193781724, 778983779, 83868974, 315103615, 965785236, 492741665, 377329025, 847549272, 698611116};
  21. ll multfact[2000]={611120140,17897580,159967943,343237090,592951953,602244843,164013908,893236658,952101451,118482211,209920162,215152598,502381710,324159984,695459226,666860816,975716615,604726097,763034477,379041292,460748324,158354199,508213120,767279289,370470133,987651923,39242596,185475889,981761633,262769826,837005788,681180371,661100686,908774984,38108703,396223792,793503000,819198011,933664044,769608345,128783369,939038698,734053167,519165427,507816805,782246763,670871900,695337837,566025613,643867105,476008438,909547109,980518787,678456808,218366494,992637363,7537905,20980780,379803548,410124767,587218502,463599811,262065380,382170139,989269458,283943725,896112848,514669474,947602158,862475009,415829023,306830063,519359563,363545474,758757919,497204956,969569909,39102155,126855068,631173350,6923144,794815151,253495907,554716148,685948839,513720461,309947752,492867651,326211127,657169128,464633342,764165057,613528541,579064017,114865160,794726205,431086582,512549494,460665448,34560};
  22. const int lim = 10000000;
  23. ll fun(ll n){
  24. 	// if(n < 1) return 1;
  25. 	if(n < lim) {
  26. 		ll ret = 1, mult = 1;
  27. 		for(int i = 1; i<=n; i++) {
  28. 			ret = ret * i % mod;
  29. 			mult = mult * ret % mod;
  30. 		}
  31. 		return bigmod(ret, n+2) * bigmod(mult, mod-2) % mod;
  32. 	}
  33. 	ll nfact = fact[n/lim-1];
  34. 	ll mult = multfact[n/lim-1];
  35. 	for(int i = (n/lim)*lim+1; i<=n; i++){
  36. 		nfact = nfact * i % mod;
  37. 		mult = mult * nfact % mod;
  38. 	}
  39. 	return bigmod(nfact, n+2) * bigmod(mult, mod-2) % mod;
  40. }
  41. int main()
  42. {
  43. 	// ll fact = 1;
  44. 	// printf("ll fact[2000]={");
  45. 	// vector<int> vt;
  46. 	// ll mult = 1;
  47. 	// for(int i = 1; i<mod; i++){
  48. 	// 	fact = (fact * i) % mod;
  49. 	// 	mult = mult * fact % mod;
  50. 	// 	if(i%lim == 0){
  51. 	// 		vt.push_back(mult);
  52. 	// 		if(i/lim!=1) printf(", ");
  53. 	// 		printf("%lld",fact);
  54. 	// 	}
  55. 	// }
  56. 	// printf("};\n");
  57. 	// printf("ll multfact[2000]={%d", vt[0]);
  58. 	// vt.erase(vt.begin());
  59. 	// for(int x : vt){
  60. 	// 	printf(",%d",x);
  61. 	// }
  62. 	// printf("};");
  63. 	// int fact = 1;
  64. 	// int mult = 1;
  65. 	// for(int i = 1; i<=lim; i++){
  66. 	// 	fact = 1ll * fact * i % mod;
  67. 	// 	mult = 1ll * mult * fact % mod;
  68. 	// }
  69. 	// cout << fact << endl;
  70. 	// cout << mult << endl;
  71. 	int t;
  72. 	scanf("%d", &t);
  73. 	while(t--){
  74. 		int l, r;
  75. 		scanf("%d %d", &l, &r);
  76. 		ll mult = 1;
  77.  
  78. 		// for(int i = l; i<=r; i++)
  79. 		// {
  80. 		// 	mult = mult * bigmod(i, i+1) % mod;
  81. 		// }
  82. 		// cout << mult << " ";
  83. 		cout << fun(r) * bigmod(fun(l-1), mod-2) % mod << endl;
  84. 	}
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 4452KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/p0naCb
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!