20级的学弟学妹们来了，实验室里可怜弱小又无助的wzc学弟终于变成了学长，可以压迫下一级了（？）。
但是wzc学长苦于自己的实力进步太慢，很担心自己在学弟学妹们面前丢人，所以天天熬夜在实验室里训练。
某一天wzc学长训练得实在太累了，居然在大白天做起了梦。
在梦里面，wzc学长在第一天有一个初始的码力值x，第二天的时候码力值变为了x2，第三天的时候码力值变为了x3......第i天的时候码力值变为了xi。
现在wzc学长想知道第i天的时候，他的码力值是多少。由于这个值可能非常大，请输出对9999999967取模的结果。
输入描述:
第一行一个整数T，代表输入数据组数。（1≤T≤1×103）
接下来T行，每行两个整数x和i，代表第一天的初始码力值，和所要求的是第几天的码力值。
（1≤x≤10，不会吧不会吧，不会真的有人这么弱吧）
（1≤i≤1×109）
输出描述:
输出T行，每行一个整数，代表xi对9999999967取模的结果。