만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

스위치와 전구 연결

시간 제한1초메모리 제한64 MB

요약
번호가 붙은 A개의 스위치를 B개의 전구로 보내는 전사 함수의 개수를 1000000007로 나눈 나머지를 구한다. 즉 B! 곱하기 제2종 스털링 수 S(A, B)다.
난이도

보통10점 중 6점

유형
조합론, 동적 계획법, 수학, 정수론
정답자
아직 제출이 없습니다

문제

미르코는 전기 기사로 취직했다. 첫 출근일에 맡은 일은 이렇다. 스위치 AA개를 전구 BB개에 연결해야 하는데, 스위치 하나는 정확히 전구 하나에 연결되고 전구 하나에는 스위치가 적어도 하나 연결되어야 한다.

미르코가 배선하는 방법은 몇 가지인가? 스위치와 전구에는 모두 번호가 붙어 있다. 두 배선을 비교했을 때 같은 전구에 연결되지 않은 스위치가 하나라도 있으면 서로 다른 배선으로 센다.

입력

첫째 줄에 스위치의 개수 AA와 전구의 개수 BB가 공백으로 구분되어 주어진다. 둘 다 자연수이고 A,B≤100000A, B \le 100000이다.

출력

첫째 줄에 배선하는 방법의 수를 출력한다. 이 수가 매우 커질 수 있으므로 10000000071000000007로 나눈 나머지만 출력한다.

예제7

  1. 예제 1

    입력
    1 2
    
    예상 출력
    0
    
  2. 예제 2

    입력
    4 4
    
    예상 출력
    24
    
  3. 예제 3

    입력
    4 3
    
    예상 출력
    36
    
  4. 예제 4

    입력
    1 1
    
    예상 출력
    1
    
  5. 예제 5

    입력
    2 1
    
    예상 출력
    1
    
  6. 예제 6

    입력
    5 2
    
    예상 출력
    30
    
  7. 예제 7

    입력
    10 5
    
    예상 출력
    5103000