小波算数

题号：NC212561
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小波有一个数列：
$F(n)=\frac{1}{\sqrt{7}}(\sqrt{11}^n-\sqrt{7}^n)$
现在他想求：
$S_n=(\sum_{i=1}^nF_i^k)mod\ 1000000009$
的值。

一行两个整数

一行表示答案。

示例1

复制

10 0

复制

示例2

复制

10 10

复制