A 国一共有 个城市，编号分别为 。

在国家建立之初，政府需要给这 个城市之间修一些道路。A 国的国王很喜欢二进制，他首先给每个城市一个数字，第 个城市的数字是 。之后，对于任意两个城市 ，他会从城市 往城市 连接 条**单向**路径。各个符号的含义见题面末尾。

现在国王想知道：从城市 出发前往城市 ，一共有多少条路径？由于答案可能会很大，你需要输出答案对 取余数之后的结果。

函数 表示 的二进制表示中 的个数，例如 。

表示二进制与运算，二进制与运算的规则是，只有当两个数的对应位都为 时，结果才为 ；否则结果为 。换句话说，如果某个位上的数都是 ，则结果位也为 ；否则结果位为 。例如下面的运算：