牛妹刚学会了按位与与按位异或运算。她称一对非负整数 为神奇对，当且仅当满足下列全部条件： ； 。 现在给定一个正整数 ，牛妹想知道在区间 内共有多少对神奇对。由于答案可能很大，请将结果对 取模后输出。 【名词解释】 按位与： 表示按位与运算，只有两个数的二进制同时为1，结果才为1，否则为0。 按位异或： 表示按位异或运算。参加运算的两个数，如果两个相应位为“异”（值不同），则该位结果为1，否则为0。

输入描述:

在一行上输入一个整数 ，表示区间上界为 。

输出描述:

输出一个整数，表示在区间 内神奇对的数量，对 取模后的结果。