Walker

Johnnie Walker is now in Bucharest! Even though it's getting late, he still wants to go for a walk. The neighbourhood Johnnie stays in can be represented as a complete undirected graph with $N$ vertices, where the streets are represented by edges and the intersections by vertices.

At any time, Johnnie can go to any intersection adjacent to the one he is in and it will take him exactly one minute to do so. Because our hero hates waiting he will not remain in the same intersection any number of minutes (every minute he will walk to another intersection).

Johnnie wonders how many walk paths are possible such that the walk will take exactly $K$ minutes and in the end he reaches the same intersection where the walk has begun.

At the beginning, Johnnie is in the intersection corresponding to the vertex labeled 1.

Two paths are considered different if there is a position where the corresponding intersections differ.

Johnnie may go through the same intersections multiple times during his walk.

Help him find the answer. As the value may be quite large you should only print it modulo $666 \ 013$.

Input data

The only line of the input contains two integers $N$ and $K$, where $N$ is the number of intersections in the neighbourhood and $K$ is the number of minutes the walk should take

Output data

The single line of the output contains the number of walk paths modulo $666013$.

Constraints and clarifications

• $1 \leq N \leq 10^9$, $1 \leq K \leq 10^{18}$
• For tests worth $10$ points, $1 \leq N \leq 5$, $1 \leq K \leq 10$.
• For tests worth extra $20$ points, $1 \leq N \cdot K \leq 2 \cdot 10^6$.
• For tests worth extra $20$ points, $1 \leq K \leq 10^6$.

Example 1

stdin

4 3

stdout

6

Explanation

The $6$ valid paths are:

$1 \rarr 2 \rarr 3 \rarr 1$
$1 \rarr 2 \rarr 4 \rarr 1$
$1 \rarr 3 \rarr 2 \rarr 1$
$1 \rarr 3 \rarr 4 \rarr 1$
$1 \rarr 4 \rarr 2 \rarr 1$
$1 \rarr 4 \rarr 3 \rarr 1$

Example 2

stdin

5 3

stdout

12

Example 3

stdin

100 15799

stdout

543264