AN+2=(AN+1xorAN)+1(N≥0),A0=0,A1=1A_{N+2}=(A_{N+1} xor A_{N}) +1(N\geq 0),A_0=0,A_1=1AN+2=(AN+1xorAN)+1(N≥0),A0=0,A1=1 を満たす数列 AAA について ANA_NAN を求めてください。
0≤N≤1090 \leq N \leq 10^90≤N≤109
