結果
| 問題 | No.2257 Swim and Sleep |
| ユーザー |
 kaichou243
|
| 提出日時 | 2023-03-24 16:55:53 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 286 ms / 2,000 ms |
| コード長 | 31,208 bytes |
| コンパイル時間 | 5,678 ms |
| コンパイル使用メモリ | 367,572 KB |
| 実行使用メモリ | 5,376 KB |
| 最終ジャッジ日時 | 2024-09-18 16:28:57 |
| 合計ジャッジ時間 | 10,143 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 164 ms
5,248 KB |
| testcase_01 | AC | 164 ms
5,376 KB |
| testcase_02 | AC | 164 ms
5,376 KB |
| testcase_03 | AC | 273 ms
5,376 KB |
| testcase_04 | AC | 274 ms
5,376 KB |
| testcase_05 | AC | 261 ms
5,376 KB |
| testcase_06 | AC | 286 ms
5,376 KB |
| testcase_07 | AC | 177 ms
5,376 KB |
| testcase_08 | AC | 179 ms
5,376 KB |
| testcase_09 | AC | 177 ms
5,376 KB |
| testcase_10 | AC | 165 ms
5,376 KB |
| testcase_11 | AC | 165 ms
5,376 KB |
| testcase_12 | AC | 165 ms
5,376 KB |
| testcase_13 | AC | 164 ms
5,376 KB |
| testcase_14 | AC | 165 ms
5,376 KB |
| testcase_15 | AC | 165 ms
5,376 KB |
| testcase_16 | AC | 166 ms
5,376 KB |
ソースコード
#include<bits/stdc++.h>
#include <immintrin.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define all(v) (v).begin(), (v).end()
using namespace std;
using ll=long long;
using P = pair<ll,ll>;
const long double PI=acos(-1);
const ll INF=1e18;
const int inf=1e9;
template<int MOD> struct Fp{
ll val;
constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
if (val < 0) val += MOD;
}
static constexpr int getmod() { return MOD; }
constexpr Fp operator - () const noexcept {
return val ? MOD - val : 0;
}
constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
constexpr Fp& operator += (const Fp& r) noexcept {
val += r.val;
if (val >= MOD) val -= MOD;
return *this;
}
constexpr Fp& operator -= (const Fp& r) noexcept {
val -= r.val;
if (val < 0) val += MOD;
return *this;
}
constexpr Fp& operator *= (const Fp& r) noexcept {
val = val * r.val % MOD;
return *this;
}
constexpr Fp& operator /= (const Fp& r) noexcept {
ll a = r.val, b = MOD, u = 1, v = 0;
while (b) {
ll t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
val = val * u % MOD;
if (val < 0) val += MOD;
return *this;
}
constexpr bool operator == (const Fp& r) const noexcept {
return this->val == r.val;
}
constexpr bool operator != (const Fp& r) const noexcept {
return this->val != r.val;
}
constexpr bool operator < (const Fp& r) const noexcept {
return this->val < r.val;
}
friend constexpr istream& operator >> (istream& is, Fp<MOD>& x) noexcept {
is >> x.val;
x.val %= MOD;
if (x.val < 0) x.val += MOD;
return is;
}
friend constexpr ostream& operator << (ostream& os, const Fp<MOD>& x) noexcept {
return os << x.val;
}
friend constexpr Fp<MOD> modpow(const Fp<MOD>& a, long long n) noexcept {
Fp<MOD> res=1,r=a;
while(n){
if(n&1) res*=r;
r*=r;
n>>=1;
}
return res;
}
friend constexpr Fp<MOD> modinv(const Fp<MOD>& r) noexcept {
long long a = r.val, b = MOD, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
return Fp<MOD>(u);
}
ll get(){
return val;
}
explicit operator bool()const{
return val;
}
};
template< uint32_t mod, bool fast = false >
struct MontgomeryModInt {
using mint = MontgomeryModInt;
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
static constexpr u32 get_r() {
u32 ret = mod;
for(i32 i = 0; i < 4; i++) ret *= 2 - mod * ret;
return ret;
}
static constexpr u32 r = get_r();
static constexpr u32 n2 = -u64(mod) % mod;
static_assert(r * mod == 1, "invalid, r * mod != 1");
static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");
static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");
u32 a;
MontgomeryModInt() : a{} {}
MontgomeryModInt(const i64 &x)
: a(reduce(u64(fast ? x : (x % mod + mod)) * n2)) {}
static constexpr u32 reduce(const u64 &b) {
return u32(b >> 32) + mod - u32((u64(u32(b) * r) * mod) >> 32);
}
constexpr mint& operator+=(const mint &p) {
if(i32(a += p.a - 2 * mod) < 0) a += 2 * mod;
return *this;
}
constexpr mint& operator-=(const mint &p) {
if(i32(a -= p.a) < 0) a += 2 * mod;
return *this;
}
constexpr mint& operator*=(const mint &p) {
a = reduce(u64(a) * p.a);
return *this;
}
constexpr mint& operator/=(const mint &p) {
*this *= modinv(p);
return *this;
}
constexpr mint operator-() const { return mint() - *this; }
constexpr mint operator+(const mint &p) const { return mint(*this) += p; }
constexpr mint operator-(const mint &p) const { return mint(*this) -= p; }
constexpr mint operator*(const mint &p) const { return mint(*this) *= p; }
constexpr mint operator/(const mint &p) const { return mint(*this) /= p; }
constexpr bool operator==(const mint &p) const { return (a >= mod ? a - mod : a) == (p.a >= mod ? p.a - mod : p.a); }
constexpr bool operator!=(const mint &p) const { return (a >= mod ? a - mod : a) != (p.a >= mod ? p.a - mod : p.a); }
u32 get() const {
u32 ret = reduce(a);
return ret >= mod ? ret - mod : ret;
}
friend constexpr MontgomeryModInt<mod> modpow(const MontgomeryModInt<mod> &x,u64 n) noexcept {
MontgomeryModInt<mod> ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend constexpr MontgomeryModInt<mod> modinv(const MontgomeryModInt<mod> &r) noexcept {
u64 a = r.get(), b = mod, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
return MontgomeryModInt<mod>(u);
}
friend ostream &operator<<(ostream &os, const mint &p) {
return os << p.get();
}
friend istream &operator>>(istream &is, mint &a) {
i64 t;
is >> t;
a = mint(t);
return is;
}
static constexpr u32 getmod() { return mod; }
};
ll mod(ll a,ll MOD){
if(a<0) a+=MOD;
return a%MOD;
}
ll modpow(ll a,ll n,ll mod){
ll res=1;
a%=mod;
while (n>0){
if (n & 1) res*=a;
a *= a;
a%=mod;
n >>= 1;
res%=mod;
}
return res;
}
vector<P> prime_factorize(ll N) {
vector<P> res;
for (ll a = 2; a * a <= N; ++a) {
if (N % a != 0) continue;
ll ex = 0;
while(N % a == 0){
++ex;
N /= a;
}
res.push_back({a, ex});
}
if (N != 1) res.push_back({N, 1});
return res;
}
ll modinv(ll a, ll mod) {
ll b = mod, u = 1, v = 0;
while (b) {
ll t = a/b;
a -= t * b, swap(a, b);
u -= t * v, swap(u, v);
}
u %= mod;
if (u < 0) u += mod;
return u;
}
ll extGcd(ll a, ll b, ll &p, ll &q) {
if (b == 0) { p = 1; q = 0; return a; }
ll d = extGcd(b, a%b, q, p);
q -= a/b * p;
return d;
}
P ChineseRem(const vector<ll> &b, const vector<ll> &m) {
ll r = 0, M = 1;
for (int i = 0; i < (int)b.size(); ++i) {
ll p, q;
ll d = extGcd(M, m[i], p, q);
if ((b[i] - r) % d != 0) return make_pair(0, -1);
ll tmp = (b[i] - r) / d * p % (m[i]/d);
r += M * tmp;
M *= m[i]/d;
}
return make_pair(mod(r, M), M);
}
//fast Input by yosupo
#include <unistd.h>
#include <algorithm>
#include <array>
#include <cassert>
#include <cctype>
#include <cstring>
#include <sstream>
#include <string>
#include <type_traits>
#include <vector>
namespace fastio{
/*
quote from yosupo's submission in Library Checker
*/
int bsr(unsigned int n) {
return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long n) {
return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n);
}
// @param n `1 <= n`
// @return maximum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned long long n) {
return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n);
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsr(unsigned __int128 n) {
unsigned long long low = (unsigned long long)(n);
unsigned long long high = (unsigned long long)(n >> 64);
return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low);
}
namespace internal {
template <class T>
using is_signed_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value ||
std::is_same<T, __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int128 =
typename std::conditional<std::is_same<T, __uint128_t>::value ||
std::is_same<T, unsigned __int128>::value,
std::true_type,
std::false_type>::type;
template <class T>
using make_unsigned_int128 =
typename std::conditional<std::is_same<T, __int128_t>::value,
__uint128_t,
unsigned __int128>;
template <class T>
using is_integral =
typename std::conditional<std::is_integral<T>::value ||
internal::is_signed_int128<T>::value ||
internal::is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
std::is_signed<T>::value) ||
is_signed_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using is_unsigned_int =
typename std::conditional<(is_integral<T>::value &&
std::is_unsigned<T>::value) ||
is_unsigned_int128<T>::value,
std::true_type,
std::false_type>::type;
template <class T>
using to_unsigned = typename std::conditional<
is_signed_int128<T>::value,
make_unsigned_int128<T>,
typename std::conditional<std::is_signed<T>::value,
std::make_unsigned<T>,
std::common_type<T>>::type>::type;
template <class T>
using is_integral_t = std::enable_if_t<is_integral<T>::value>;
template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;
template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;
template <class T> using to_unsigned_t = typename to_unsigned<T>::type;
} // namespace internal
struct Scanner {
public:
Scanner(const Scanner&) = delete;
Scanner& operator=(const Scanner&) = delete;
Scanner(FILE* fp) : fd(fileno(fp)) {}
void read() {}
template <class H, class... T> void read(H& h, T&... t) {
bool f = read_single(h);
assert(f);
read(t...);
}
int read_unsafe() { return 0; }
template <class H, class... T> int read_unsafe(H& h, T&... t) {
bool f = read_single(h);
if (!f) return 0;
return 1 + read_unsafe(t...);
}
int close() { return ::close(fd); }
private:
static constexpr int SIZE = 1 << 15;
int fd = -1;
std::array<char, SIZE + 1> line;
int st = 0, ed = 0;
bool eof = false;
bool read_single(std::string& ref) {
if (!skip_space()) return false;
ref = "";
while (true) {
char c = top();
if (c <= ' ') break;
ref += c;
st++;
}
return true;
}
bool read_single(double& ref) {
std::string s;
if (!read_single(s)) return false;
ref = std::stod(s);
return true;
}
template <class T,
std::enable_if_t<std::is_same<T, char>::value>* = nullptr>
bool read_single(T& ref) {
if (!skip_space<50>()) return false;
ref = top();
st++;
return true;
}
template <class T,
internal::is_signed_int_t<T>* = nullptr,
std::enable_if_t<!std::is_same<T, char>::value>* = nullptr>
bool read_single(T& sref) {
using U = internal::to_unsigned_t<T>;
if (!skip_space<50>()) return false;
bool neg = false;
if (line[st] == '-') {
neg = true;
st++;
}
U ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
sref = neg ? -ref : ref;
return true;
}
template <class U,
internal::is_unsigned_int_t<U>* = nullptr,
std::enable_if_t<!std::is_same<U, char>::value>* = nullptr>
bool read_single(U& ref) {
if (!skip_space<50>()) return false;
ref = 0;
do {
ref = 10 * ref + (line[st++] & 0x0f);
} while (line[st] >= '0');
return true;
}
bool reread() {
if (ed - st >= 50) return true;
if (st > SIZE / 2) {
std::memmove(line.data(), line.data() + st, ed - st);
ed -= st;
st = 0;
}
if (eof) return false;
auto u = ::read(fd, line.data() + ed, SIZE - ed);
if (u == 0) {
eof = true;
line[ed] = '\0';
u = 1;
}
ed += int(u);
line[ed] = char(127);
return true;
}
char top() {
if (st == ed) {
bool f = reread();
assert(f);
}
return line[st];
}
template <int TOKEN_LEN = 0>
bool skip_space() {
while (true) {
while (line[st] <= ' ') st++;
if (ed - st > TOKEN_LEN) return true;
if (st > ed) st = ed;
for (auto i = st; i < ed; i++) {
if (line[i] <= ' ') return true;
}
if (!reread()) return false;
}
}
};
//fast Output by ei1333
/**
* @brief Printer(高速出力)
*/
struct Printer {
public:
explicit Printer(FILE *fp) : fp(fp) {}
~Printer() { flush(); }
template< bool f = false, typename T, typename... E >
void write(const T &t, const E &... e) {
if(f) write_single(' ');
write_single(t);
write< true >(e...);
}
template< typename... T >
void writeln(const T &...t) {
write(t...);
write_single('\n');
}
void flush() {
fwrite(line, 1, st - line, fp);
st = line;
}
private:
FILE *fp = nullptr;
static constexpr size_t line_size = 1 << 16;
static constexpr size_t int_digits = 20;
char line[line_size + 1] = {};
char small[32] = {};
char *st = line;
template< bool f = false >
void write() {}
void write_single(const char &t) {
if(st + 1 >= line + line_size) flush();
*st++ = t;
}
template< typename T, enable_if_t< is_integral< T >::value, int > = 0 >
void write_single(T s) {
if(st + int_digits >= line + line_size) flush();
if(s == 0) {
write_single('0');
return;
}
if(s < 0) {
write_single('-');
s = -s;
}
char *mp = small + sizeof(small);
typename make_unsigned< T >::type y = s;
size_t len = 0;
while(y > 0) {
*--mp = y % 10 + '0';
y /= 10;
++len;
}
memmove(st, mp, len);
st += len;
}
void write_single(const string &s) {
for(auto &c : s) write_single(c);
}
void write_single(const char *s) {
while(*s != 0) write_single(*s++);
}
template< typename T >
void write_single(const vector< T > &s) {
for(size_t i = 0; i < s.size(); i++) {
if(i) write_single(' ');
write_single(s[i]);
}
}
};
}; //namespace fastio
using mint=MontgomeryModInt<998244353>;
int main(){
fastio::Scanner sc(stdin);
fastio::Printer pr(stdout);
#define in(...) sc.read(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define STR(...) string __VA_ARGS__;in(__VA_ARGS__)
#define out(...) pr.write(__VA_ARGS__)
#define outln(...) pr.writeln(__VA_ARGS__)
#define outspace(...) pr.write(__VA_ARGS__),pr.write(' ')
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
/*
ここでは左上を(0,0)として考える
以下のパターン
①上下、左右 2^H+2^W
②x+yが偶数に上下x+yが奇数に左右、その逆、同じ行、列には左右、上下はない。2*2^H*2^W
③上左、右下はx+y mod gでそれぞれ決まる、2*2^g
④上右、左下はx-y mod g 2*2^g
1,3,4はいかなるgについても存在する
2はgが偶数の時のみ(奇数の時はx+y≡2 mod gとx+y≡0 mod 2が同値でない)
1,3,4で重複が8(4方向*2)
1,2,3,4で重複が16(1,3,4の8+2*(2の縦横それぞれ1方向のケース(=4)))
これ以外のケースを考える
1,2,3,4を満たしていない数え上げたい対象は4*4グリッドの周期になる
(証明は解説に任せる(え？))
当然、ここまでくればグリッドを全探索すれば良い
(このグリッドには2ヶ所同じ方向があって、探索するのは4^8通り)
全体のグリッドがトーラスであることを考えると、ちゃんと4*4のグリッドでピッタリ敷き詰められる必要があり
gが4の倍数の時しかこのケースは存在しない
このケースのうち1,2,3,4と被らないものは48通り存在する。(全探索)
K>0の時
すでに書き込まれた数によって固定されるものを考えれば良い、実装はとてつもなく大変
コメント:
割り当てる方向の個数が3つ以上の数え上げは、②を計算することにより残るものが
定数個になるというの、とても難しかった、めっちゃadhoc
どうやって作問したんですか？
*/
auto calc=[](map<int,char> &mp){
map<char,int> d;
for(auto& [key,val]:mp) d[val]++;
int ret=0;
for(auto& [c,cnt]:d) if(cnt>0) ret++;
return ret;
};
vector<char> gd={'L','R','U','D'};
vector<vector<vector<char>>> solution;
//渾身の8重ループ
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
for(int k=0;k<4;k++){
for(int l=0;l<4;l++){
for(int m=0;m<4;m++){
for(int n=0;n<4;n++){
for(int o=0;o<4;o++){
for(int p=0;p<4;p++){
vector<vector<char>> candidate={
{gd[i],gd[j],gd[m],gd[n]},
{gd[k],gd[l],gd[o],gd[p]},
{gd[m],gd[n],gd[i],gd[j]},
{gd[o],gd[p],gd[k],gd[l]}
};
bool ok=true;
map<char,int> dc,odd,even;
FOR(I,4){
map<char,int> dci,dcj;
FOR(J,4){
dc[candidate[I][J]]++;
dci[candidate[I][J]]++;
dcj[candidate[J][I]]++;
if((I+J)%2==0){
even[candidate[I][J]]++;
}else{
odd[candidate[I][J]]++;
}
if(candidate[I][J]=='L'){
if(dci['R']>0) ok=false;
}else if(candidate[I][J]=='R'){
if(dci['L']>0) ok=false;
}
if(candidate[J][I]=='U'){
if(dcj['D']>0) ok=false;
}else if(candidate[J][I]=='D'){
if(dcj['U']>0) ok=false;
}
}
}
if(dc.size()<3||!ok) continue;
bool hasver_odd=false,hashor_odd=false,hasver_even=false,hashor_even=false;
for(auto& [key,val]:odd){
if(key=='L'||key=='R') hashor_odd=true;
else hasver_odd=true;
}
for(auto& [key,val]:even){
if(key=='L'||key=='R') hashor_even=true;
else hasver_even=true;
}
if((hasver_odd&&hashor_odd)||(hasver_even&&hashor_even)){
vector<vector<char>> b=candidate;
FOR(T,16){
vector<vector<char>> nb(4,vector<char>(4,'.'));
FOR(I,4){
FOR(J,4){
if(b[I][J]=='L'){
if(nb[I][(J+3)%4]!='.'){
ok=false;
break;
}
nb[I][(J+3)%4]=b[I][J];
}else if(b[I][J]=='R'){
if(nb[I][(J+1)%4]!='.'){
ok=false;
break;
}
nb[I][(J+1)%4]=b[I][J];
}else if(b[I][J]=='U'){
if(nb[(I+3)%4][J]!='.'){
ok=false;
break;
}
nb[(I+3)%4][J]=b[I][J];
}else{
if(nb[(I+1)%4][J]!='.'){
ok=false;
break;
}
nb[(I+1)%4][J]=b[I][J];
}
}
}
if(!ok) break;
b=nb;
}
if(ok) solution.push_back(candidate);
}
}
}
}
}
}
}
}
}
INT(t);
assert(1<=t&&t<=100);
while(t--){
LL(h,w,k);
assert(1<=h&&h<=1000000000&&1<=w&&w<=1000000000&&0<=k&&k<=min(2000ll,h*w));
ll g=gcd(h,w);
mint ans=0;
if(k==0){
if(g%4==0){
ans=modpow(mint(2),h)+modpow(mint(2),w)+modpow(mint(2),h+w+1)+modpow(mint(2),g)*4+32;
}else if(g%4==2){
ans=modpow(mint(2),h)+modpow(mint(2),w)+modpow(mint(2),h+w+1)+modpow(mint(2),g)*4-16;
}else{
ans=modpow(mint(2),h)+modpow(mint(2),w)+modpow(mint(2),g)*4-8;
}
outln(ans.get());
continue;
}
swap(h,w);
vector<ll> x(k),y(k);
vector<char> d(k);
bool hasver=false,hashor=false;
FOR(i,k){
in(y[i],x[i],d[i]);
//y[i]=w-y[i]-1;
x[i]=h-x[i]-1;
assert(0<=x[i]&&x[i]<h&&0<=y[i]&&y[i]<w);
assert(d[i]=='R'||d[i]=='L'||d[i]=='U'||d[i]=='D');
if(d[i]=='L'||d[i]=='R') hashor=true;
else hasver=true;
}
//case 1
if(!hasver||!hashor){
map<int,vector<char>> X,Y;
FOR(i,k){
X[x[i]].push_back(d[i]);
Y[y[i]].push_back(d[i]);
}
bool ret0h=false,ret0w=false;
ll h1=h,w1=w;
for(auto& [key,val]:X){
sort(all(val));
val.erase(unique(all(val)),val.end());
if(val.size()>1) ret0h=true;
for(auto& element:val){
if(element!='L'&&element!='R') ret0h=true;
}
if(ret0h) break;
h1--;
}
for(auto& [key,val]:Y){
sort(all(val));
val.erase(unique(all(val)),val.end());
if(val.size()>1) ret0w=true;
for(auto& element:val){
if(element!='U'&&element!='D') ret0w=true;
}
if(ret0w) break;
w1--;
}
if(!ret0h) ans+=modpow(mint(2),h1);
if(!ret0w) ans+=modpow(mint(2),w1);
}
//case 2
if(g%2==0){
bool oddver=false,oddhor=false,evenver=false,evenhor=false;
FOR(i,k){
if((x[i]+y[i])%2){
if(d[i]=='L'||d[i]=='R') oddhor=true;
else oddver=true;
}else{
if(d[i]=='L'||d[i]=='R') evenhor=true;
else evenver=true;
}
}
if(!(oddver&&oddhor)&&!(evenver&&evenhor)&&!(oddver&&evenver)&&!(oddhor&&evenhor)){
if(evenver||oddhor){
bool ret0=false;
map<int,char> X,Y;
FOR(i,k){
if((x[i]+y[i])%2){
if(X.find(x[i])==X.end()){
X[x[i]]=d[i];
}else if(X[x[i]]!=d[i]){
ret0=true;
}
}else{
if(Y.find(y[i])==Y.end()){
Y[y[i]]=d[i];
}else if(Y[y[i]]!=d[i]){
ret0=true;
}
}
}
if(!ret0){
ans+=modpow(mint(2),h+w-X.size()-Y.size())-(2-calc(X))*(2-calc(Y));
}
}
if(evenhor||oddver){
bool ret0=false;
map<int,char> X,Y;
FOR(i,k){
if((x[i]+y[i])%2==0){
if(X.find(x[i])==X.end()){
X[x[i]]=d[i];
}else if(X[x[i]]!=d[i]){
ret0=true;
}
}else{
if(Y.find(y[i])==Y.end()){
Y[y[i]]=d[i];
}else if(Y[y[i]]!=d[i]){
ret0=true;
}
}
}
if(!ret0){
ans+=modpow(mint(2),h+w-X.size()-Y.size())-(2-calc(X))*(2-calc(Y));
}
}
}
}
//case 3
{
bool ret0=false;
map<int,char> mp;
map<char,int> dc;
FOR(i,k){
if(mp.find((x[i]+y[i])%g)==mp.end()){
mp[(x[i]+y[i])%g]=d[i];
}else if(mp[(x[i]+y[i])%g]!=d[i]){
ret0=true;
}
dc[d[i]]++;
}
if(dc.size()>2) ret0=true;
int dsiz=dc.size();
if((dc['L']>0||dc['U']>0)&&dc['R']==0&&dc['D']==0&&!ret0){
ans+=modpow(mint(2),g-mp.size())-2+dsiz;
}else if((dc['R']>0||dc['D']>0)&&dc['L']==0&&dc['U']==0&&!ret0){
ans+=modpow(mint(2),g-mp.size())-2+dsiz;
}
}
//case 4
{
bool ret0=false;
map<int,char> mp;
map<char,int> dc;
FOR(i,k){
if(mp.find((x[i]+(g-1)*y[i])%g)==mp.end()){
mp[(x[i]+(g-1)*y[i])%g]=d[i];
}else if(mp[(x[i]+(g-1)*y[i])%g]!=d[i]){
ret0=true;
}
dc[d[i]]++;
}
if(dc.size()>2) ret0=true;
int dsiz=dc.size();
if((dc['L']>0||dc['D']>0)&&dc['R']==0&&dc['U']==0&&!ret0){
ans+=modpow(mint(2),g-mp.size())-2+dsiz;
}else if((dc['R']>0||dc['U']>0)&&dc['L']==0&&dc['D']==0&&!ret0){
ans+=modpow(mint(2),g-mp.size())-2+dsiz;
}
}
//case muzui
if(g%4==0){
vector<vector<char>> grid(4,vector<char>(4,'.'));
bool ret0=false;
FOR(i,k){
if(grid[x[i]%4][y[i]%4]=='.'){
grid[x[i]%4][y[i]%4]=d[i];
}else if(grid[x[i]%4][y[i]%4]!=d[i]){
ret0=true;
}
}
FOR(i,4) FOR(j,2){
if(grid[i][j]!='.'&&grid[(i+2)%4][(j+2)%4]!='.'){
if(grid[i][j]!=grid[(i+2)%4][(j+2)%4]) ret0=true;
}else if(grid[i][j]!='.'){
grid[(i+2)%4][(j+2)%4]=grid[i][j];
}else if(grid[(i+2)%4][(j+2)%4]!='.'){
grid[i][j]=grid[(i+2)%4][(j+2)%4];
}
}
if(!ret0){
//すでに1,2,3,4との被りを省いた48通りのうちマッチするものを探し出す
//このコードを書いてる人は今書いてる時点ですでに疲れており、48通りのグリッドを書き出したくない
//書き出すグリッドの個数は6個に絞ることができる(トーラス上で8通りのずらす方法がそれぞれある)
FOR(i,48){
auto& s=solution[i];
bool ok=true;
FOR(x,4) FOR(y,4){
if(grid[x][y]=='.'||grid[x][y]==s[x][y]) continue;
ok=false;
}
if(ok) ans+=1;
}
}
}
outln(ans.get());
}
}