백준(BOJ) 15791 세진이의 미팅 **

# 수학

이 문제의 경우 값이 크다보니 %연산을 하면서 나누기를 진행 하여야 하는데,

이 과정에서 문제가 발생하게 된다.

페르마의 소정리를 알고 풀어야 할 것 같다.

m이 소수라는 가정하에 기존의 나누기를 곱셈으로 변환하여 해결 하면된다.

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#include <set>
#include <list>
#include <utility>
#include <functional>
#define MAX 1000005
#define INF 987654321
#define MOD 1000000007
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<float, float> pf;

ll n,m,ans=1,divi=1;

ll fun(ll a,ll b)
{
    ll ret=1;
    while(b>0)
    {
        ll tmp=1,cur=a;
        while(tmp*2<b)
        {
            cur=(cur*cur)%MOD;
            tmp*=2;
        }
        ret=(ret*cur)%MOD;
        b-=tmp;
    }
    return ret;
}
// a^b % MOD 해주는 함수.

int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=m;i>0;i--,n--)
    {
        ans*=n,divi*=i;
        ans%=MOD,divi%=MOD;
    }
    printf("%lld",(ans*fun(divi,MOD-2))%MOD);
}