#include <iostream>
using namespace std;
int main()
{
cout << 315 << endl;
cout << 3056 << endl;
cout << 288071 << endl;
cout << 6712311 << endl;
cout << 6329883 << endl;
cout << 15283205 << endl;
cout << 19870126 << endl;
cout << 15122517 << endl;
cout << 19096622 << endl;
cout << 20474992 << endl;
return 0;
}
