D - Bouquet /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

あかりさんは n 種類の花を 1 本ずつ持っています。

あかりさんは、これらの花から 1 本以上を選び、花束を作ろうとしています。

ただし、あかりさんは ab2 つの数を苦手としていて、いずれかと一致するような本数の花からなる花束は作ることができません。

あかりさんが作ることのできる花束は何種類あるでしょうか。

(10^9 + 7) で割った余りを求めてください。

ここで 2 つの花束は、一方では使われているが、 もう一方では使われていない種類の花があるとき、別の種類の花束であるとみなします。

制約

  • 入力は全て整数である。
  • 2 \leq n \leq 10^9
  • 1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)

入力

入力は以下の形式で標準入力から与えられる。

n a b

出力

あかりさんが作ることのできる花束の種類数を (10^9 + 7) で割った余りを出力せよ。(そのような花束がないときは 0 と出力せよ。)


入力例 1

4 1 3

出力例 1

7

この場合、あかりさんは 2 本または 4 本の花を選んで花束を作ることができます。

4 本ある花の中から 2 本を選ぶ方法は 6 通り、4 本を選ぶ方法は 1 通りあるので、 あかりさんが作ることができる花束の種類数は合わせて 7 通りです。


入力例 2

1000000000 141421 173205

出力例 2

34076506

(10^9 + 7) で割った余りを出力してください。

Score : 400 points

Problem Statement

Akari has n kinds of flowers, one of each kind.

She is going to choose one or more of these flowers to make a bouquet.

However, she hates two numbers a and b, so the number of flowers in the bouquet cannot be a or b.

How many different bouquets are there that Akari can make?

Find the count modulo (10^9 + 7).

Here, two bouquets are considered different when there is a flower that is used in one of the bouquets but not in the other bouquet.

Constraints

  • All values in input are integers.
  • 2 \leq n \leq 10^9
  • 1 \leq a < b \leq \textrm{min}(n, 2 \times 10^5)

Input

Input is given from Standard Input in the following format:

n a b

Output

Print the number of bouquets that Akari can make, modulo (10^9 + 7). (If there are no such bouquets, print 0.)


Sample Input 1

4 1 3

Sample Output 1

7

In this case, Akari can choose 2 or 4 flowers to make the bouquet.

There are 6 ways to choose 2 out of the 4 flowers, and 1 way to choose 4, so there are a total of 7 different bouquets that Akari can make.


Sample Input 2

1000000000 141421 173205

Sample Output 2

34076506

Print the count modulo (10^9 + 7).