問題一覧 > 通常問題

No.391 CODING WAR

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 227
作問者 : Tawara / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 918 / 自分の提出
問題文最終更新日: 2026-06-25 00:50:32
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Show the original
yukicoder contest 141 (順位表) の他の問題:

Problem Statement


On the competitive programming continent, home of the yuki Kingdom, disputes between nations are settled by a CODING WAR.
A CODING WAR is a battle in which all the competitive programmers of the defending nation take on the problems set by the attacking nation.

However, if a few truly strong competitive programmers, the so-called pros, solved all the problems,
it could not be said that the contest was decided by the competitive programming strength of the nation as a whole.
Therefore, in a CODING WAR, the people in charge of the problems are decided according to the following rules.

  • Every competitive programmer on the defending side must work on one of the problems.
  • Every problem set must have at least one person working on it (in charge of it).
  • Each programmer is in charge of exactly one problem, and must not give advice to people working on problems they are not in charge of.
  • Multiple programmers may be in charge of the same problem.
Incidentally, the attacking side may set more problems than the competitive programmer population of the defending side, but in that case the attacking side automatically loses by foul.

Now, today again, a neighboring country has apparently launched a CODING WAR against the yuki Kingdom, this time over the copyright of problems it created.
However, the Minister of CODING of the Yuki Kingdom has only just taken office and does not know how things work. To you, the secretary,
the Minister said that the assignment would be decided by listing every possible way of assigning people to the problems and then looking them over, which is utter fool... *cough*, quite a jest.

Tell the Minister the total number of ways to assign people to the problems, and make the Minister face reality.

Added 2016/07/08 22:54:
If the attacking side would lose by foul, the number of ways is considered to be 0.

Input

$N$ $M$

The first line contains the competitive programmer population of the yuki Kingdom $N$ ($1 \le N \le 10^{12}$) and the number of problems set by the neighboring country $M$ ($1 \le M \le 10^5 $), separated by a space.

Output

Output the number of ways to assign people to the problems.
Since the answer can be very large, output the remainder when it is divided by $1000000007(10^9+7)$.
Print a newline at the end.

Sample

Sample 1
Input
3 3
Output
6


Let $a,b,c$ be the numbers of the problems that the three competitive programmers of the yuki Kingdom are in charge of. Then there are

$(a,b,c)=(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$

which makes 6 ways.

Sample 2
Input
7 3
Output
1806

This is a case where multiple people are in charge of the same problem.

Sample 3
Input
100 1
Output
1

The yuki Kingdom's competitive programmers combine all their strength to take on a single problem.

Sample 4
Input
1000000000000 3
Output
692089859

The yuki Kingdom seems to have a tremendous number of competitive programmers.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。