The Pig's Ancient Text

Problem Source

SDOI2010

Problem Description

In short: compute

Input Format

Exactly one line: two numbers $N, G$, separated by a space.

Output Format

Exactly one line: one number, the remainder of the answer divided by $999911659$.

Sample Input

4 2

Sample Output

2048

Constraints

For all data, $1\leq G, N\leq 10^9$ are guaranteed.