1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
| #include<stdio.h> #include<set> #include<iostream> #include<stack> #include<cstring> #include<cmath> #include<vector> #include<map> #include<queue> #include<algorithm> typedef long long ll; typedef long double ld; typedef double db; #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int mod=1e9+7; inline int mo(ll a,int p){ return a>=p?a%p:a; } inline int rd() { int x = 0, f = 1; char ch; while (ch < '0' || ch > '9') { if (ch == '-')f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); } return f * x; } inline ll gcd(ll x, ll y){ return y==0?x:gcd(y,x%y); } inline ll speed(ll a,ll b){ ll cur=a,anss=1; while(b){ if(b&1) anss=anss*cur; cur=cur*cur; b>>=1; } return anss; } const int MAXN=1e5; bool ipr[MAXN+20]; int cnt,pri[MAXN/5]; void prime(){ int N=sqrt(MAXN)+0.5,mul; memset(ipr,true,sizeof(ipr)); ipr[1]=false; for(int i=2;i<=N;i++){ if(ipr[i]==true){ i==2?mul=1:mul=2; for(int j=i*i;j<=MAXN;j+=i*mul){ ipr[j]=false; } } } for(int i=2;i<=MAXN;i++){ if(ipr[i]==true){ pri[++cnt]=i; } } } int f[120]={1,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}; const int con=1e7; int n,m,k; ll ans=1; ll fun(ll x){ ll ret=f[x/con]; ll t=x/con; for(int i=t*con+1;i<=x;i++){ ret=mo(ret*i,mod); } return ret; } int main(){ scanf("%d%d%d",&n,&m,&k); int a=0,b=0; int l=1,r=n,mid=(l+r)/2; while (l<=r) { if (mid<=k) l=mid+1,a++; else r=mid-1,b++;
mid=(l+r)/2; } for(int i=m;i>=m-a+1;i--){ ans=mo(ans*i,mod); } for(int i=n-m;i>=n-m-b+1;i--){ ans=mo(ans*i,mod); } ans=ans*fun(n-a-b)%mod; printf("%lld\n",ans); return 0; }
|