四色猜想：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”——弗南西斯·格思里

最近，自学信息竞赛不久的Dema在NKOJ上刷题的时候，做了一道叫四色问题的搜索题。
他对于NKOJ管理员故弄玄虚的行为很不满意。明明一道很水的搜索题，却偏要开头用
Francis Guthrie提出的四色猜想Act B。于是他决定出一道题让管理员做。让他领悟四色定理的真谛。（也就是所谓的教他做人了。）

现在Dema画了一幅特殊的地图。这幅地图是圆形的。中间也是个圆形的高地。
周围由n个城市围成了一圈。例如n=4的时候，地图是这样的。

现在Dema要给这个地图上色。当然要满足相邻的区域颜色不能相同。
他正好有4种颜色的笔。

于是他给NKOJ的管理员发了个邮件，考了他如下的问题。
告诉你任意一个n（周围围绕着中间高地的城市个数），给你四种颜色的笔。
现在让你给我的地图上色。相邻区域颜色不能相同。
请你告诉我：
1.是否一定有解。（答对得0分，答错得-10分）。
2.你有多少种上色的方案数。（答对得10分，答错得0分）。

由于算出的方案数可能很大，对于最终的结果Mod 999999999。

第一行，一个整数n。(n<=10^9)

两行。第一行，是输出yes，否输出no。
第二行一个整数。即上色的方案数。