Submission #1101578

---

Source Code Expand

// vvvvvvvvvvvvvvvvv Library code start


#define NDEBUG
NDEBUG


#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <random>


#define forn(t, i, n) for (t i = 0; i < (n); ++i)


using namespace std;

/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);


template <class T>
T gen_pow(T ret, T x, uint64_t pow) {
    while (pow) {
        if (pow & 1) {
            ret *= x;
        }
        pow /= 2;
        if (pow) {
            x *= x;
        }
    }
    return ret;
}


#define ENABLE_IF(e) typename enable_if<e>::type* = nullptr

namespace template_util {
    template<class T>
    constexpr T min(T a, T b) {
        return a < b ? a : b;
    }

    
    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        typedef uint64_t type;
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        typedef uint32_t type;
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        typedef uint32_t type;
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        typedef uint16_t type;
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        typedef uint8_t type;
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        typedef uint8_t type;
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}

template<class T>
vector<T> next_vector(istream& in, size_t n) {
    vector<T> ret(n);
    for (size_t i = 0; i < n; ++i) {
        ret[i] = next<T>(in);
    }
    return ret;
}


#define dbg(...) ;


/*
TODOs:
 cache invs
 primitive root
 discrete log

 tests!!!
*/

namespace mod_impl {
    /// caide keep
    template <class T>
    constexpr inline T mod(T MOD) {
        return MOD;
    }

    /// caide keep
    template <class T>
    constexpr inline T mod(T* MOD) {
        return *MOD;
    }

    /// caide keep
    template <class T>
    constexpr inline T max_mod(T MOD) {
        return MOD - 1;
    }

    /// caide keep
    template <class T>
    constexpr inline T max_mod(T*) {
        return numeric_limits<T>::max() - 1;
    }

    
    constexpr inline uint64_t combine_max_sum(uint64_t a, uint64_t b) {
        return a > ~b ? 0 : a + b;
    }

    constexpr inline uint64_t combine_max_mul(uint64_t a, uint64_t b) {
        return a > numeric_limits<uint64_t>::max() / b ? 0 : a * b;
    }

    /// caide keep
    template <class T>
    constexpr inline uint64_t next_divisible(T mod, uint64_t max) {
        return max % mod == 0 ? max : combine_max_sum(max, mod - max % mod);
    }

    /// caide keep
    template <class T>
    constexpr inline uint64_t next_divisible(T*, uint64_t) {
        return 0;
    }

    //caide keep
    constexpr int IF_THRESHOLD = 2;

    template <class T, T MOD_VALUE, uint64_t MAX,
            class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
            ENABLE_IF(MAX <= max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        return value;
    }

    template <class T, T MOD_VALUE, uint64_t MAX,
            class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
            ENABLE_IF(max_mod(MOD_VALUE) < MAX && MAX <= IF_THRESHOLD * max_mod(MOD_VALUE) && !is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        while (value >= mod(MOD_VALUE)) {
            value -= mod(MOD_VALUE);
        }
        return (RET)value;
    }

    template <class T, T MOD_VALUE, uint64_t MAX,
             class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type,
             ENABLE_IF(IF_THRESHOLD * max_mod(MOD_VALUE) < MAX || is_pointer<T>::value)>
    inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) {
        return (RET)(value % mod(MOD_VALUE));
    }
}


#define MAX_MOD mod_impl::max_mod(MOD_VALUE)

struct DenormTag {};

template <class T, T MOD_VALUE, uint64_t MAX = MAX_MOD, ENABLE_IF(MAX_MOD >= 2)>
struct ModVal {
    typedef typename template_util::minimal_uint<MAX>::type storage;
    storage value;

    /// caide keep
    inline ModVal(): value(0) {
        assert(MOD >= 2);
    }

    
    inline ModVal(storage v, DenormTag): value(v) {
        assert(MOD >= 2);
        assert(v <= MAX);
    };

    inline operator ModVal<T, MOD_VALUE>() {
        return {v(), DenormTag()};
    };

    
    typename template_util::minimal_uint<mod_impl::max_mod(MOD_VALUE)>::type v() const {
        return mod_impl::smart_mod<T, MOD_VALUE, MAX>(value);
    }
};

template <class T, T MOD_VALUE, uint64_t MAX,
        uint64_t NEW_MAX = mod_impl::next_divisible(MOD_VALUE, MAX),
        ENABLE_IF(NEW_MAX != 0),
        class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator-(const ModVal<T, MOD_VALUE, MAX>& o) {
    static_assert(NEW_MAX <= numeric_limits<typename Ret::storage>::max(), "bad unary minus template");
    assert(NEW_MAX % MOD == 0 && o.value <= NEW_MAX);
    return {typename Ret::storage(NEW_MAX - o.value), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_sum(MAX1, MAX2),
        ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator+(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
    return {typename Ret::storage(typename Ret::storage() + o1.value + o2.value), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
        ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>>
inline Ret operator*(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) {
    return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.value), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
        uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
        ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX2 < MAX1),
        class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX_MOD, MAX2)>>
inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
    return {typename Ret::storage(typename Ret::storage(1) * o1.v() * o2.value), DenormTag()};
}

template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2,
        uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2),
        uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)),
        ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 == 0),
        class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX_MOD, MAX_MOD)>>
inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) {
    return {typename Ret::storage(typename Ret::storage(1) * o1.v() * o2.v()), DenormTag()};
}


template <class T, T MOD_VALUE, uint64_t MAX>
inline ModVal<T, MOD_VALUE>& operator+=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) {
    lhs = lhs + rhs;
    return lhs;
}


template <class T, T MOD_VALUE, class MOD_TYPE>
struct ModCompanion {
    typedef MOD_TYPE mod_type;
    typedef ModVal<mod_type, MOD_VALUE> type;
    

    template <uint64_t C>
    inline static constexpr ModVal<mod_type, MOD_VALUE, C> c() {
        return {C, DenormTag()};
    };

    template <uint64_t MAX = numeric_limits<uint64_t>::max()>
    inline static ModVal<mod_type, MOD_VALUE, MAX> wrap(uint64_t x) {
        assert(x <= MAX);
        return {typename ModVal<mod_type, MOD_VALUE, MAX>::storage(x), DenormTag()};
    };

    
    template <uint64_t MAX>
    inline static ModVal<mod_type, MOD_VALUE> pow(const ModVal<mod_type, MOD_VALUE, MAX>& x, uint64_t n) {
        if (n == 0) {
            return c<1>();
        }
        auto v = pow(x * x, n / 2);
        return (n & 1) ? x * v : v;
    };
};


#undef MAX_MOD

template <uint64_t MOD_VALUE>
struct Mod : ModCompanion<uint64_t, MOD_VALUE, typename template_util::minimal_uint<MOD_VALUE>::type> {
    template<uint64_t VAL>
    static constexpr uint64_t literal_builder() {
        return VAL;
    }

    template<uint64_t VAL, char DIGIT, char... REST>
    static constexpr uint64_t literal_builder() {
        return literal_builder<(10 * VAL + DIGIT - '0') % MOD_VALUE, REST...>();
    }
};


#define REGISTER_MOD_LITERAL(mod, suffix) \
template <char... DIGITS> mod::type operator "" _##suffix() { \
    return mod::c<mod::literal_builder<0, DIGITS...>()>(); \
}


template <class T, T MOD_VALUE, uint64_t MAX>
inline ostream& operator<<(ostream& s, ModVal<T, MOD_VALUE, MAX> val) {
    s << val.v();
    return s;
}


namespace option_detail {
    /// caide keep
    struct NoneHelper {};
}


template<class Value>
class Option {
public:
    

    static_assert(!std::is_reference<Value>::value,
                  "Option may not be used with reference types");
    static_assert(!std::is_abstract<Value>::value,
                  "Option may not be used with abstract types");

    
    Value* get_pointer() && = delete;

    
    // Return b copy of the value if set, or b given default if not.
    

    // Return b copy of the value if set, or b given default if not.
    

private:
    

    struct StorageTriviallyDestructible {
        // uninitialized
        
        bool hasValue;

        
    };

    /// caide keep
    struct StorageNonTriviallyDestructible {
        // uninitialized
        union { Value value; };
        bool hasValue;

        
        ~StorageNonTriviallyDestructible() {
            clear();
        }

        void clear() {
            if (hasValue) {
                hasValue = false;
                value.~Value();
            }
        }
    };

    /// caide keep
    using Storage =
    typename std::conditional<std::is_trivially_destructible<Value>::value,
            StorageTriviallyDestructible,
            StorageNonTriviallyDestructible>::type;

    Storage storage_;
};


// Comparisons.


template<class V> bool operator< (const Option<V>&, const V& other) = delete;
template<class V> bool operator<=(const Option<V>&, const V& other) = delete;
template<class V> bool operator>=(const Option<V>&, const V& other) = delete;
template<class V> bool operator> (const Option<V>&, const V& other) = delete;
template<class V> bool operator< (const V& other, const Option<V>&) = delete;
template<class V> bool operator<=(const V& other, const Option<V>&) = delete;
template<class V> bool operator>=(const V& other, const Option<V>&) = delete;
template<class V> bool operator> (const V& other, const Option<V>&) = delete;


namespace index_iterator_impl {
    template <class T>
    struct member_dispatch_helper {
        

    private:
        T value;
    };

    // Have to caide keep all the members to comply to iterator concept
    // Otherwise generated code won't be portable between clang and g++
    template <class C, bool reverse = false>
    struct index_iterator {
        /// caide keep
        typedef random_access_iterator_tag iterator_category;
        /// caide keep
        typedef decltype(((C*)nullptr)->operator[](size_t(0))) reference;
        /// caide keep
        typedef typename remove_reference<reference>::type value_type;
        /// caide keep
        typedef ptrdiff_t difference_type;
        /// caide keep
        typedef conditional<
                is_reference<reference>::value,
                typename add_pointer<value_type>::type,
                member_dispatch_helper<value_type>> pointer;

        /// caide keep
        typedef index_iterator<C, reverse> self_t;

        /// caide keep
        static const difference_type dir = reverse ? -1 : 1;

        /// caide keep
        index_iterator() = default;

        
        /// caide keep
        inline bool operator!=(const self_t& o) { return index != o.index; }
        /// caide keep
        inline bool operator<(const self_t& o) { return reverse ? index > o.index : index < o.index; }
        /// caide keep
        inline bool operator>(const self_t& o) { return reverse ? index < o.index : index > o.index; }
        /// caide keep
        inline bool operator<=(const self_t& o) { return reverse ? index >= o.index : index <= o.index; }
        /// caide keep
        inline bool operator>=(const self_t& o) { return reverse ? index <= o.index : index >= o.index; }

        /// caide keep
        inline reference operator*() { return (*container)[index]; }
        /// caide keep
        inline const reference operator*() const { return (*container)[index]; }
        /// caide keep
        inline pointer operator->() { return pointer((*container)[index]); }

        /// caide keep
        inline self_t& operator++() { index += dir; return *this; }
        /// caide keep
        inline self_t operator++(int) { auto copy = *this; index += dir; return copy; }
        /// caide keep
        inline self_t& operator--() { index -= dir; return *this; }
        /// caide keep
        inline self_t operator--(int) { auto copy = *this; index -= dir; return copy; }

        /// caide keep
        inline self_t& operator+=(difference_type n) { index += dir * n; return *this; };
        /// caide keep
        inline self_t& operator-=(difference_type n) { index -= dir * n; return *this; };
        /// caide keep
        inline friend self_t operator-(self_t a, difference_type n) { return a -= n; };
        /// caide keep
        inline friend self_t operator+(difference_type n, self_t a) { return a += n; };
        /// caide keep
        inline friend self_t operator+(self_t a, difference_type n) { return a += n; };
        /// caide keep
        inline friend difference_type operator-(const self_t& a, const self_t& b) { return dir * (a.index - b.index); };

        /// caide keep
        inline reference operator[](difference_type n) { return (*container)[index + dir * n]; };
        /// caide keep
        inline const reference operator[](difference_type n) const { return (*container)[index + dir * n]; };

    private:
        C* container;
        difference_type index;
    };
}


namespace multivec_impl {
    template <size_t NDIMS>
    struct shape {
        size_t dim, stride;
        shape<NDIMS - 1> subshape;
        
        shape(size_t dim_, shape<NDIMS - 1>&& s): dim(dim_), stride(s.size()), subshape(std::move(s)) {}
        size_t size() const { return dim * stride; }
        
        
    };
    template <> struct shape<0> { size_t size() const { return 1; } };
    

    template <size_t I, size_t NDIMS>
    struct __shape_traverse {
        static size_t get_dim(const shape<NDIMS>& s) {
            return __shape_traverse<I - 1, NDIMS - 1>::get_dim(s.subshape);
        }

        ///caide keep
        static const shape<NDIMS - I>& get_subshape(const shape<NDIMS>& s) {
            return __shape_traverse<I - 1, NDIMS - 1>::get_subshape(s.subshape);
        }
    };

    template <size_t NDIMS>
    struct __shape_traverse<0, NDIMS> {
        static size_t get_dim(const shape<NDIMS>& s) { return s.dim; }
        
    };

    template <size_t I, size_t NDIMS>
    size_t get_dim(const shape<NDIMS>& s) { return __shape_traverse<I, NDIMS>::get_dim(s); }

    ///caide keep
    template <size_t I, size_t NDIMS>
    const shape<NDIMS - I>& get_subshape(const shape<NDIMS>& s) { return __shape_traverse<I, NDIMS>::get_subshape(s); }

    
    template <class Index, class... Rest, size_t NDIMS, ENABLE_IF(is_integral<Index>::value)>
    size_t get_shift(const shape<NDIMS>& s, size_t cur_shift, Index i, Rest... is) {
        assert(0 <= i && i < s.dim);
        return get_shift(s.subshape, cur_shift + i * s.stride, is...);
    }

    template <size_t NDIMS> size_t get_shift(const shape<NDIMS>&, size_t cur_shift) { return cur_shift; }

    
    template <class... T> shape<sizeof...(T)> make_shape(T... dims);

    template <class Dim, class... Rest, ENABLE_IF(is_integral<Dim>::value)>
    shape<sizeof...(Rest) + 1> make_shape(Dim dim, Rest... dims) {
        assert(dim >= 0);
        return {(size_t)dim, make_shape<Rest...>(dims...)};
    }

    template <> shape<0> make_shape() { return {}; }

    
    ///caide keep
    template <class T, size_t NDIMS>
    struct vec_view_base;

    template <template<class, size_t> class Base, class T, size_t NDIMS>
    struct vec_mixin : public Base<T, NDIMS> {
        using Base<T, NDIMS>::Base;
        /// caide keep
        typedef Base<T, NDIMS> B;
        
        
        template <size_t I = 0> inline size_t dim() const { return get_dim<I>(B::s); }
        inline size_t size() const { return B::s.size(); }

        ///caide keep
        template <class... Indices, bool enabled = NDIMS == sizeof...(Indices), ENABLE_IF(enabled)>
        inline T& operator()(Indices... is) {
            size_t i = multivec_impl::get_shift(B::s, 0, is...);
            return B::data[i];
        }

        ///caide keep
        template <class... Indices, bool enabled = sizeof...(Indices) < NDIMS, ENABLE_IF(enabled)>
        inline vec_mixin<vec_view_base, T, NDIMS - sizeof...(Indices)> operator()(Indices... is) {
            size_t shift = multivec_impl::get_shift(B::s, 0, is...);
            const auto& subshape = multivec_impl::get_subshape<sizeof...(Indices)>(B::s);
            return {subshape, &B::data[shift]};
        }

        
        inline void fill(const T& val) {
            std::fill(raw_data(), raw_data() + B::s.size(), val);
        };

        
        inline vec_mixin& operator=(const vec_mixin& o) {
            assert(B::s == o.get_shape());
            memcpy(raw_data(), o.raw_data(), sizeof(T) * size());
            return *this;
        }

//    protected:
        inline T* raw_data() {
            return &B::data[0];
        }

        inline const T* raw_data() const {
            return &B::data[0];
        }
    };

    template <class T, size_t NDIMS>
    struct vec_view_base {
        
        
    protected:
        multivec_impl::shape<NDIMS> s;
        T* data;
    };

    template <class T, size_t NDIMS>
    struct vec_base {
        inline vec_base(multivec_impl::shape<NDIMS>&& s_): s(move(s_)), data(new T[s.size()]) {}
        
        
        inline vec_base(const vec_base& o): s(o.s), data(new T[s.size()]) {
            memcpy(data.get(), o.data.get(), sizeof(T) * s.size());
        }
        
    protected:
        multivec_impl::shape<NDIMS> s;
        unique_ptr<T[]> data;
    };
}

/*
TODO
 - do we need vec_view_const?
 - add more features (lambda initialization etc.)
 - properly use const
 - proper tests coverage
*/

template <class T, size_t NDIMS>
using vec = multivec_impl::vec_mixin<multivec_impl::vec_base, T, NDIMS>;


template <class T, class... NDIMS>
inline vec<T, sizeof...(NDIMS)> make_vec(NDIMS... dims) {
    return {multivec_impl::make_shape(dims...)};
}

template <class T, template <class, size_t> class B1, template <class, size_t> class B2>
vec<T, 2> operator*(multivec_impl::vec_mixin<B1, T, 2>& a, multivec_impl::vec_mixin<B2, T, 2>& b) {
    size_t n = a.template dim<0>();
    size_t n1 = a.template dim<1>();
    size_t m = b.template dim<0>();
    size_t m1 = b.template dim<1>();
    assert(n1 == m);
    auto ret = make_vec<T>(n, m1);
    forn (size_t, i, n) {
        forn (size_t, j, m1) {
            T sum = {};
            forn (size_t, k, n1) {
                sum += a(i, k) * b(k, j);
            }
            ret(i, j) = sum;
        }
    }
    return ret;
}

template <class T, template <class, size_t> class B2>
vec<T, 2>& operator*=(vec<T, 2>& a, multivec_impl::vec_mixin<B2, T, 2>& b) {
    return a = a * b;
}


// ^^^^^^^^^^^^^^^^^ Library code end

using md = Mod<1000000007>;
/// caide keep
using mt = md::type;
REGISTER_MOD_LITERAL(md, mod)

void solve(istream& in, ostream& out) {
    int h = next<int>(in);
    int w = next<int>(in);
    uint64_t k = next<uint64_t>(in);
    if (k == 0) {
        out << 1 << "\n";
        return;
    }
    auto f = next_vector<string>(in, h);
    int cnt = 0, cx = 0, cy = 0, cxIn = 0, cyIn = 0;
    forn (int, i, h) {
        forn (int, j, w) {
            if (f[i][j] == '#') {
                cnt++;
                if (i + 1 < h && f[i + 1][j] == '#') {
                    cxIn++;
                }
                if (j + 1 < w && f[i][j + 1] == '#') {
                    cyIn++;
                }
                if (i + 1 == h && f[0][j] == '#') {
                    cx++;
                }
                if (j + 1 == w && f[i][0] == '#') {
                    cy++;
                }
            }
        }
    }
    dbg(cnt, cx, cy, cxIn, cyIn, k);
    if (cx == 0 && cy == 0) {
        out << md::pow(md::wrap<1000000>(cnt), k - 1) << "\n";
        return;
    }
    if (cx > 0 && cy > 0) {
        out << "1\n";
        return;
    }
    auto id = make_vec<mt>(2, 2);
    id.fill(0_mod);
    id(0, 0) = id(1, 1) = 1_mod;
    auto a = make_vec<mt>(2, 2);
    a.fill(0_mod);
    a(0, 0) = md::wrap<1000000>(cnt);
    a(0, 1) = -md::wrap<1000000>(cx > 0 ? cxIn : cyIn);
    a(1, 1) = md::wrap<1000>(cx + cy);
    a = gen_pow(id, a, k - 1);
    out << a(0, 0) + a(0, 1) << "\n";
}


int main() {
    solve(cin, cout);
    return 0;
}

Submission Info

Judge Result