问题 A: 异或方程

---

【题目描述】

题目背景
⊕ 代表异或运算，运算规则为：
当只有一位比特参与运算时，0⊕0=0，0⊕1=1，1⊕0=1，1⊕1=0（相同为0，相异为1）；
当有多位比特参与运算时，对每位比特分别取异或运算，如0101⊕1011=1110；
题目描述
给定一个正整数 n，求 0 到 2ⁿ−1 中有多少个数 x 满足以下方程：
x⊕2x⊕3x=0
由于满足条件的 x 可能很多，请将方案数对 10⁹+9 取模。
输入格式
单个正整数：表示 n。
输出格式
单个自然数：表示方案数对 10⁹ 取模的余数。
数据范围
对于 50% 的数据，1≤n≤10；
对于 100% 的数据，1≤n≤100000。
样例数据
输入:
3
输出:
5
说明:
满足方程的数字有：000，001，010，100，101
 

题目类型~

四星挑战赛 语言基础 

咻咻~

提交答案 状态 返回作业