A long time ago, Rikka was not good at math. Worrying about Rikka's grades, Yuta sets many interesting math problems for Rikka to help her improve her skills.
Now, as Rikka makes more and more progress on math, more and more she feels the joy of solving math tasks. Today, Yuta is quite busy and has no time to seek for new problems for Rikka. Therefore, for the first time, Rikka tries to come up with a problem herself.
Setting a problem is just like building blocks. The first step is to choose the bricks. Rikka selects the concepts of "geometric sequence" and "subsequence":
Sequence a1,…,ak is a geometric sequence if and only if for each index i∈[2,n−1], the values in the sequence holds a2i=ai−1×ai+1.
Sequnce b1,…,bt is a subsequence of a1,…,ak if and only if there exists an index sequence c1,…,ct(1≤ci≤k) which satisfies ci<ci+1 for each i∈[1,n)and aci=bi for each i∈[1,n].
The second step is to combine the bricks. It is quite simple for Rikka: she soon finds an interesting problem:
Given a positive integer n, count the number of different geometric subsequences of 1,2,…,n.
The last step, and also the most important step, is to solve the problem. However, this task seems to be too difficult for Rikka. Therefore she seeks for help from you: Could you please help her solve this interesting math problem?