fork download
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long int ll;
  5. ll mod = 1e9+7;
  6. ll fac[1009],inverse[1009];
  7. void factorial(){
  8. fac[0]=fac[1]=1;
  9. for(int i =2;i<=1000;i++){
  10. fac[i]= (fac[i-1]*i)%mod;
  11. }
  12. }
  13.  
  14. ll power(ll a,ll b){
  15. if(b==0)return 1;
  16. ll ans = 1;
  17. if(b%2==1)ans = (ans%mod * a%mod)%mod;
  18. ll t = power(a,b/2)%mod;
  19. return (ans * (t%mod * t%mod)%mod)%mod;
  20. }
  21.  
  22. void inv(){
  23. for(int i = 0;i<=1000;i++){
  24. inverse[i] = power(fac[i],mod-2);
  25. }
  26. }
  27. ll nck(int n,int k){
  28. ll a = fac[n]%mod;
  29. ll b = power(fac[k],mod-2)%mod;
  30. ll c = power(fac[n-k],mod-2)%mod;
  31. return (((a * b)%mod) * c)%mod;
  32. }
  33.  
  34. ll npk(int n,int k){
  35. ll a = fac[n]%mod;
  36. ll b = inverse[n-k]%mod;
  37. return (a*b)%mod;
  38.  
  39. }
  40. int main(){
  41. int t;
  42. cin>>t;
  43. int Case = 0;
  44. factorial();
  45. inv();
  46. while(t--){
  47. Case++;
  48. int x,y;
  49. cin>>x>>y;
  50. vector<ll> a(x+1);
  51. for(int i = 1 ; i <=x ;i++){
  52. a[i] = nck(x,i);
  53. }
  54. a[0]=1;
  55. vector<ll> b(y+1);
  56. for(int i = 1 ;i<=y ;i++){
  57. b[i]=nck(y,i);
  58. }
  59. b[0]=1;
  60. ll injective = 0;
  61. for(int i = 1;i<=x;i++){
  62. ll ti = 0;
  63.  
  64. for(int j = i+1;j<=y;j++){
  65. ti = (ti + ( (npk(j,i)) * (b[j]) )%mod)%mod;
  66. }
  67. injective = (injective + (ti * a[i])%mod)%mod;
  68. }
  69. long long subjective = 0;
  70. for(int i = 1;i<=y;i++){
  71. ll ti = 0;
  72. ll w = fac[i];
  73. for(int j = i+1;j<=x;j++){
  74. ti = ti + (( ((a[j] * w)%mod) * power(i,j-i))%mod);
  75. }
  76. subjective = (subjective + ((ti * b[i])%mod))%mod;
  77. }
  78.  
  79. long long bijective = 0;
  80. for(int i = 1 ; i<=min(x,y);i++ ){
  81. bijective = (bijective + ( ( ((a[i]%mod)*(b[i]%mod))%mod )*(fac[i]%mod))%mod )%mod;
  82. }
  83. long long tot = 0;
  84. for(int i = 1; i <= x ; i++){
  85. for(int j= 1;j <=y; j++){
  86. tot = (tot + (((power(j,i)*a[i])%mod)*b[j])%mod)%mod;
  87. }
  88. }
  89. cout<<"Case "<<Case<<": ";
  90. cout<<(injective%mod+bijective%mod)%mod<<" "<<(subjective%mod+bijective%mod)%mod<<" "<<
  91. (bijective)%mod<<" "<<tot%mod<<'\n';
  92.  
  93. }
  94.  
  95.  
  96. }
  97.  
Success #stdin #stdout 0s 4448KB
stdin
Standard input is empty
stdout
Standard output is empty