H. AI Takeover
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

We are in the year, 2050 and AI has advanced to a whole new level. AI is planning to take over humans but needs to communicate with one another without human interception. To do so they decide to create a language of their own.

There are many levels of AI bots from level-1 to level-$$$n$$$.

The bots perform the following tasks:

  • A level-1 bot creates a new word.
  • A level-$$$n$$$ bot creates a level-($$$n$$$-1) bot. $$$(n \neq 1)$$$.
It takes them 5 minutes to do a task. Initially you have $$$k$$$ $$$(1\le k \le 10^9)$$$ level-$$$n$$$ $$$(1\le n\le 100)$$$ bots.

Spidey being the savior he is, decides to learn this language to stop AI. How many words will he have to learn to stop them if $$$t$$$ $$$(1\le t \le 10^4)$$$ minutes have passed?

Input

The only input line consists of three integers $$$n$$$ $$$(1\le n\le 100)$$$ — Highest level of the bots, $$$k$$$ $$$(1\le k \le 10^9)$$$ — Initial number of level-$$$n$$$ bots and $$$t$$$ $$$(1\le t \le 10^4)$$$ — Time passed.

Output

Output a single integer — The number of words Spidey has to learn after $$$t$$$ minutes have passed. Since the answer can be huge, output it modulo $$$10^9 + 7$$$.

Examples
Input
5 10 40
Output
560
Input
40 100 50
Output
0
Input
10 10 100
Output
1847560
Note

In testcase 1 we have level-5 bots.

  • At 5 minutes we have 10 level-5 and 10 level 4 bots.
  • At 10 minutes we have 10 level-5, 20 level-4 and 10 level-3 bots.
  • At 15 minutes we have 10 level-5, 30 level-4, 30 level-3 and 10 level-2 bots.
  • At 20 minutes we have 10 level-5, 40 level-4, 60 level-3, 40 level-2 and 10 level-1 bots.
  • At 25 minutes we have 10 level-5, 50 level-4, 100 level-3, 100 level-2, 50 level-1 bots and 10 words.
  • At 30 minutes we have 10 level-5, 60 level-4, 150 level-3, 200 level-2, 150 level-1 bots and 60 words.
  • At 35 minutes we have 10 level-5, 70 level-4, 210 level-3, 350 level-2, 350 level-1 bots and 210 words.
  • At 40 minutes we have 10 level-5, 70 level-4, 280 level-3, 560 level-2, 700 level-1 bots and 560 words.
In testcase 2, we have level-40 bots. To reach the creation of new words we need at least 200 minutes.