U127704 单词
题目背景
没什么好说的
题目描述
OI 语是一种拼音文字，使用的字母只有两种——“0”和“1”。
OI 语中的单词只有一个拼写规则：不可以有连续 3 个 0 或者连续 3 个 1。例如，10001 是不合法的单词，而 00 是合法的。
gnocuil 希望知道，他能够写出多少个不同的长度为 k 的合法 OI 语单词。由于这个数十 分巨大，你只需输出它除以 999999999 的余数。
输入格式
无
输出格式
无
说明/提示
合法的长度为 3 的 OI 单词分别是 001,010,011,100,101,110。
【数据规模和约定】 3