Submission #691654


Source Code Expand

//ここからテンプレート
#if 1

#include<iostream>
#include<list>
#include<algorithm>
#include<utility>
#include<type_traits>
#include<tuple>
#include<memory>
#include<iterator>
#include<string>
#include<functional>
#include<list>
#include<array>
#include<complex>
#include<numeric>
#include<iomanip>
#include<vector>
#include<queue>
#include<random>

#include<boost/optional.hpp>
#include<boost/optional/optional_io.hpp>
#include<boost/variant.hpp>
#include<boost/range/adaptor/transformed.hpp>
#include<boost/range/adaptor/indexed.hpp>
#include<boost/range/adaptor/filtered.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/irange.hpp>
#include<boost/multi_array.hpp>

typedef long long int int64;
typedef unsigned long long uint64;
typedef long double double64;
constexpr int int_max_value = 0x7FFFFFFF;
constexpr unsigned int uint_max_value = 0xFFFFFFFF;
constexpr int64 int64_max_value = 0x7FFFFFFFFFFFFFFF;
constexpr uint64 uint64_max_value = 0xFFFFFFFFFFFFFFFF;


namespace utility
{
	namespace detail
	{
		template<class>struct apply_tuple_t;
		template<std::size_t... Is>struct apply_tuple_t<std::index_sequence<Is...>>
		{
			template<class Func, class Tuple>static decltype(auto) run(Func func, Tuple const& t)
			{
				return func(std::get<Is>(t)...);
			}
		};
	}

	template<class Func, class... Args>decltype(auto) apply_tuple(Func func, std::tuple<Args...>const& vec)
	{
		return detail::apply_tuple_t<std::make_index_sequence<sizeof...(Args)>>::run(func, vec);
	}

	template<class T, std::size_t I>constexpr T const& front(T const(&ar)[I])
	{
		return ar[0];
	}
	template<class Range>auto front(Range const& vec)->decltype(vec[0]) const&
	{
		return vec[0];
	}
	template<class Range>auto front(Range const& vec)->typename std::enable_if<
		!std::is_same<typename std::iterator_traits<decltype(vec.begin())>::iterator_category,std::random_access_iterator_tag>::value,
		decltype(vec.front()) const&>::type
	{
		return vec.front();
	}

	template<class T, std::size_t I>constexpr T const& back(T const(&ar)[I])
	{
		return ar[I - 1];
	}
	template<class Range>auto back(Range const& vec)->decltype(vec[0]) const&
	{
		return vec[vec.size() - 1];
	}
	template<class Range>auto back(Range const& vec)->typename std::enable_if<
		!std::is_same<typename std::iterator_traits<decltype(vec.begin())>::iterator_category, std::random_access_iterator_tag>::value,
		decltype(vec.front()) const&>::type
	{
		return vec.back();
	}

	template<class T>using point = std::pair<T, T>;
	
	template<class Func>struct scope_exit_t
	{
		Func func;
		scope_exit_t(Func f) :func(f) {}
		scope_exit_t(scope_exit_t &&) = delete;
		scope_exit_t(scope_exit_t const&) = delete;
		scope_exit_t& operator=(scope_exit_t &&) = delete;
		scope_exit_t& operator=(scope_exit_t const&) = delete;
		~scope_exit_t()
		{
			func();
		}
	};
	template<class Func>scope_exit_t<Func> scope_exit(Func func)
	{
		return scope_exit_t<Func>(func);
	}

	namespace detail
	{
		template<class Func, class T, class U>auto fold_expression_i(Func func, T const& v, U const& u)
		{
			return func(v, u);
		}

		template<class Func, class T, class... Ts>auto fold_expression_i(Func func, T const& v, Ts const&... vs)
		{
			return func(v, fold_expression_i(func, vs...));
		}

		template<class Func, class T, std::size_t... Is>auto fold_expression(Func func, T const& v, std::index_sequence<Is...>)
		{
			return fold_expression_i(func, std::get<Is>(v)...);
		}
	}
	template<class Func, class... Ts>auto fold_expression(std::tuple<Ts...>const& tup, Func func)
	{
		return detail::fold_expression(func, tup, std::make_index_sequence<sizeof...(Ts)>());
	}
	template<class... Ts>auto tuple_add(std::tuple<Ts...>const& tup)
	{
		return fold_expression(tup, [](auto lhs, auto rhs) {return lhs + rhs;});
	}
	template<class... Ts>auto tuple_mul(std::tuple<Ts...>const& tup)
	{
		return fold_expression(tup, [](auto lhs, auto rhs) {return lhs * rhs;});
	}
}
namespace container
{
	template<class Type, std::size_t Max>class value_tank
	{
		std::array<boost::optional<Type>, Max> value_ = {};
		std::size_t size_ = 0;
	public:
		value_tank() = default;
		value_tank(value_tank const&) = default;
		value_tank(value_tank&&) = default;
		value_tank& operator=(value_tank const&) = default;
		value_tank& operator=(value_tank&&) = default;
		~value_tank() = default;

		std::size_t size()const
		{
			return size_;
		}
		struct iterator :std::iterator<std::input_iterator_tag, Type>
		{
			boost::optional<Type> const* ptr_;
			iterator(boost::optional<Type> const*ptr) :ptr_(ptr){}
			iterator(iterator const&) = default;
			iterator(iterator&&) = default;
			iterator& operator=(iterator const&) = default;
			iterator& operator=(iterator&&) = default;
			~iterator() = default;

			Type const& operator*()const
			{
				return **ptr_;
			}
			iterator& operator++()
			{
				++ptr_;
				return *this;
			}
			iterator operator++(int)
			{
				auto ret = *this;
				++ptr_;
				return ret;
			}
			bool operator==(iterator const& lhs)const
			{
				return ptr_ == lhs.ptr_;
			}
			bool operator!=(iterator const& lhs)const
			{
				return ptr_ != lhs.ptr_;
			}
		};
		iterator begin()const
		{
			return iterator(&value_[0]);
		}
		iterator end()const
		{
			return iterator(&value_[size_]);
		}
		void push_back(Type&& v)
		{
			if (size_ < Max)
			{
				value_[size_] = std::move(v);
				++size_;
			}
		}
		void push_back(Type const& v)
		{
			if (size_ < Max)
			{
				value_[size_] = v;
				++size_;
			}
		}
		Type const& operator[](std::size_t index)const
		{
			return *(value_[index]);
		}
	};
}
namespace adaptor
{
	using namespace boost::adaptors;
}
namespace algorithm
{
	using namespace boost::range;
	template<class SinglePassRange, class Pred>bool any_of(SinglePassRange const& range, Pred pred)
	{
		return std::any_of(std::begin(range), std::end(range), pred);
	}
	template<class SinglePassRange, class Pred>bool all_of(SinglePassRange const& range, Pred pred)
	{
		return std::all_of(std::begin(range), std::end(range), pred);
	}
}
namespace math
{
	template<class T>constexpr T pow(T p, int64 n)
	{
		return n == 0 ? T(1) : n == 1 ? p : n == 2 ? p*p : n % 2 == 0 ? pow(pow(p, n / 2), 2) : pow(pow(p, n / 2), 2)*p;
	}

	int log(long long int p, int n)
	{
		int64 t = n;
		for (int i = 0;;++i)
		{
			if (t > p)
				return i;
			t *= n;
		}
	}

	constexpr double pi = 3.141592653589793;

	namespace detail
	{
		int gcd(int larger, int less)
		{
			return less == 0 ? larger : gcd(less, larger%less);
		}
	}

	int gcd(int lhs, int rhs)
	{
		return lhs < rhs ? detail::gcd(rhs, lhs) : detail::gcd(lhs, rhs);
	}

	void fourier_transform(
		std::vector<std::complex<double>>& vec, std::size_t N)
	{
		std::vector<std::complex<double>> butterfly;
		vec.resize(N);
		butterfly.resize(N);

		std::complex<double> half(std::cos(pi), std::sin(pi));
		for (uint64 i = 1, k = N / 2;i < N;[&]() {i *= 2;k /= 2;}())//i*k == N/4
		{
			std::complex<double> circle(std::cos(pi / i), std::sin(pi / i));
			std::complex<double> c(1.0, 0);
			for (auto count : boost::irange(0ull, i))
			{
				for (auto j : boost::irange(0ull, k))
				{
					butterfly[count*k + j] =
						vec[2 * count*k + j] + vec[2 * count*k + j + k] * c;
					butterfly[count*k + j + N / 2] =
						vec[2 * count*k + j] + vec[2 * count*k + j + k] * c*half;
				}
				c *= circle;
			}
			std::swap(vec, butterfly);
		}
	}

	class polynomial
	{
		std::vector<std::complex<double>> value;
		void swap(polynomial&& p)
		{
			std::swap(value, p.value);
		}
	public:
		polynomial() :value{ 0.0 } {}
		polynomial(polynomial const&) = default;
		polynomial(std::vector<std::complex<double>>&& vec) :value(std::move(vec)) {}
		polynomial(polynomial&& p) :polynomial()
		{
			swap(std::move(p));
		}
		polynomial(std::initializer_list<std::complex<double>> lis) :value(lis) {}
		polynomial(std::complex<double> c) :polynomial({ c }) {}

		polynomial& operator=(polynomial const&) = default;
		polynomial& operator=(polynomial&& p)
		{
			value = std::vector<std::complex<double>>{ 0.0 };
			swap(std::move(p));
			return *this;
		}

		~polynomial() = default;
		std::complex<double> operator[](std::size_t deg)const
		{
			return deg >= value.size() ? 0.0 : value[deg];
		}
		std::size_t degree()const
		{
			return value.size() - 1;
		}
		void strict_degree_set()
		{
			std::size_t N = degree();
			for (;N > 0;--N)
			{
				if (value[N] != 0.0)
					break;
			}
			value.resize(N + 1);
		}
		void integer_degree_set()
		{
			std::size_t N = degree();
			for (;N > 0;--N)
			{
				std::cout << value[N] << " " << (std::norm(value[N]) > (1.0e-20)) << std::endl;
				if (std::norm(value[N]) > (1.0e-20))
					break;
			}
			value.resize(N + 1);
		}

		friend polynomial operator*(polynomial const& lhs, polynomial const& rhs)
		{
			std::size_t N = 1;
			while (true)
			{
				N *= 2;
				if (N > (lhs.degree() + rhs.degree()))
					break;
			}
			auto lhs_ = lhs.value;
			auto rhs_ = rhs.value;
			fourier_transform(lhs_, N);
			fourier_transform(rhs_, N);
			std::vector<std::complex<double>> vec;
			vec.reserve(N);
			for (std::size_t i = 0;i < N;++i)
			{
				vec.push_back(lhs_[i] * rhs_[i]);
			}
			for (auto& v : vec)
			{
				v = 2 * v.real() - v;
			}
			fourier_transform(vec, N);
			for (auto& v : vec)
			{
				v = (2 * v.real() - v)*(1.0 / N);
			}
			std::size_t k = N;
			for (;k > 0;--k)
			{
				if (std::norm(vec[k]) > 1.0e-23)
					break;
			}
			vec.resize(k + 1);
			return polynomial(std::move(vec));
		}
	};

	int real_integer(std::complex<double> c)
	{
		int v = static_cast<int>(c.real());
		double u = c.real() - v;
		return v + static_cast<int>(2 * u);
	}

	template<class T>polynomial make_poly(std::vector<T> const& vec)
	{
		auto range = vec | adaptor::transformed([](T const& v) {return static_cast<std::complex<double>>(v);});
		std::vector<std::complex<double>> ret(std::begin(range), std::end(range));
		return polynomial(std::move(ret));
	}
	polynomial make_poly(std::initializer_list<double>init)
	{
		std::vector<std::complex<double>> vec;
		for (auto v : init)
		{
			vec.emplace_back(v);
		}
		return polynomial(std::move(vec));
	}
	polynomial make_poly(std::initializer_list<int> init)
	{
		std::vector<std::complex<double>> vec;
		for (auto v : init)
		{
			vec.emplace_back(v);
		}
		return polynomial(std::move(vec));
	}

	template<class T>class infinite_value
	{
		boost::optional<T> val;
	public:
		infinite_value(T const& v) :val(v) {}
		infinite_value(T&& v) :val(std::move(v)) {}
		infinite_value(boost::none_t = boost::none) :val() {}
		infinite_value(infinite_value const&) = default;
		infinite_value(infinite_value&&) = default;
		~infinite_value() = default;

		infinite_value& operator=(T const& v)
		{
			val = v;
			return *this;
		}
		infinite_value& operator=(T&& v)
		{
			val = std::move(v);
			return *this;
		}
		infinite_value& operator=(boost::none_t)
		{
			val = boost::none;
			return *this;
		}
		infinite_value& operator=(infinite_value const&) = default;
		infinite_value& operator=(infinite_value&&) = default;

		operator bool()const
		{
			return static_cast<bool>(val);
		}
		T const& operator*()const
		{
			return *val;
		}

		friend infinite_value operator+(infinite_value const& lhs, infinite_value const& rhs)
		{
			return lhs&&rhs ? infinite_value<T>(*lhs + *rhs) : infinite_value<T>(boost::none);
		}
		friend infinite_value operator+(infinite_value const& lhs, T const& rhs)
		{
			return lhs ? infinite_value<T>(*lhs + rhs) : infinite_value<T>(boost::none);
		}
		friend infinite_value operator+(T const& lhs, infinite_value const& rhs)
		{
			return lhs&&rhs ? infinite_value<T>(*lhs + *rhs) : infinite_value<T>(boost::none);
		}
		
		friend bool operator==(infinite_value const& lhs, infinite_value const& rhs)
		{
			return (!lhs&&!rhs) || (lhs&&rhs && (*lhs == *rhs));
		}
		friend bool operator==(infinite_value const& lhs, T const& rhs)
		{
			return lhs && (*lhs == rhs);
		}
		friend bool operator==(T const& lhs, infinite_value const& rhs)
		{
			return rhs && (lhs == *rhs);
		}


		friend bool operator<(infinite_value const& lhs, infinite_value const& rhs)
		{
			return !lhs ? false : !rhs ? true : *lhs < *rhs;
		}
		friend bool operator<(infinite_value const& lhs, T const& rhs)
		{
			return !lhs ? false : *lhs < rhs;
		}
		friend bool operator<(T const& lhs, infinite_value const& rhs)
		{
			return !rhs ? true : lhs < *rhs;
		}
		friend bool operator<=(infinite_value const& lhs, infinite_value const& rhs)
		{
			return (lhs < rhs) || (lhs == rhs);
		}
		friend bool operator<=(infinite_value const& lhs, T const& rhs)
		{
			return (lhs < rhs) || (lhs == rhs);
		}
		friend bool operator<=(T const& lhs, infinite_value const& rhs)
		{
			return (lhs < rhs) || (lhs == rhs);
		}


		friend bool operator>(infinite_value const& lhs, infinite_value const& rhs)
		{
			return  !rhs ? false : !lhs ? true : *lhs > *rhs;
		}
		friend bool operator>(infinite_value const& lhs, T const& rhs)
		{
			return !lhs ? true : *lhs > rhs;
		}
		friend bool operator>(T const& lhs, infinite_value const& rhs)
		{
			return !rhs ? false : lhs > *rhs;
		}
		friend bool operator>=(infinite_value const& lhs, infinite_value const& rhs)
		{
			return (lhs > rhs) || (lhs == rhs);
		}
		friend bool operator>=(infinite_value const& lhs, T const& rhs)
		{
			return (lhs > rhs) || (lhs == rhs);
		}
		friend bool operator>=(T const& lhs, infinite_value const& rhs)
		{
			return (lhs > rhs) || (lhs == rhs);
		}

	};

	template<std::size_t Mod>class modulo_number
	{
		uint64 val = {};
		static constexpr uint64 abs(int64 n)
		{
			return n <= -1 ? n + Mod : n;
		}
	public:
		modulo_number(modulo_number const&) = default;
		modulo_number(modulo_number&&) = default;
		modulo_number& operator=(modulo_number const&) = default;
		modulo_number& operator=(modulo_number&&) = default;
		~modulo_number() = default;

		constexpr modulo_number(uint64 num = {}) : val(num%Mod) {}
		constexpr modulo_number(unsigned int num) : val(num%Mod) {}
		constexpr modulo_number(int64 num) : val(abs(num%Mod)) {}
		constexpr modulo_number(int num) : val(abs(num%Mod)) {}

		modulo_number& operator=(uint64 num)
		{
			val = num%Mod;
			return *this;
		}
		modulo_number& operator=(int64 num)
		{
			val = abs(num%Mod);
			return *this;
		}
		modulo_number& operator=(unsigned int num)
		{
			val = num%Mod;
			return *this;
		}
		modulo_number& operator=(int num)
		{
			val = abs(num%Mod);
			return *this;
		}


		constexpr uint64 get()const
		{
			return val;
		}

		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>((lhs.val + rhs.val) % Mod);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs + modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator+(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}
		friend constexpr modulo_number<Mod> operator+(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}
		friend constexpr modulo_number<Mod> operator+(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}
		friend constexpr modulo_number<Mod> operator+(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) + rhs;
		}

		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>((lhs.val + Mod - rhs.val) % Mod);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs - modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator-(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}
		friend constexpr modulo_number<Mod> operator-(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}
		friend constexpr modulo_number<Mod> operator-(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}
		friend constexpr modulo_number<Mod> operator-(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) - rhs;
		}

		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>((lhs.val*rhs.val) % Mod);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs * modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator*(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}
		friend constexpr modulo_number<Mod> operator*(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}
		friend constexpr modulo_number<Mod> operator*(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}
		friend constexpr modulo_number<Mod> operator*(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) * rhs;
		}

		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, modulo_number<Mod>const& rhs)
		{
			return lhs*math::pow(rhs, Mod - 1);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, int const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, unsigned int const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, int64 const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(modulo_number<Mod>const& lhs, uint64 const& rhs)
		{
			return lhs / modulo_number<Mod>(rhs);
		}
		friend constexpr modulo_number<Mod> operator/(int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}
		friend constexpr modulo_number<Mod> operator/(unsigned int const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}
		friend constexpr modulo_number<Mod> operator/(int64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}
		friend constexpr modulo_number<Mod> operator/(uint64 const& lhs, modulo_number<Mod>const& rhs)
		{
			return modulo_number<Mod>(lhs) / rhs;
		}

		template<class Rhs>decltype(auto) operator+=(Rhs const& rhs)
		{
			return *this = *this + rhs;
		}
		template<class Rhs>decltype(auto) operator*=(Rhs const& rhs)
		{
			return *this = *this * rhs;
		}
		template<class Rhs>decltype(auto) operator-=(Rhs const& rhs)
		{
			return *this = *this - rhs;
		}
		template<class Rhs>decltype(auto) operator/=(Rhs const& rhs)
		{
			return *this = *this / rhs;
		}
	};

	template<class T>constexpr T factorial(std::size_t n, std::size_t goal = 1)
	{
		return n == goal ? T(n) : n == 0 ? T(1) : factorial<T>(n, (n + goal) / 2 + 1)*factorial<T>((n + goal) / 2, goal);
	}

	namespace detail
	{
		constexpr uint64 integral_sqrt_i(uint64 v, uint64 start, uint64 end)
		{
			return start == end ? start :
				pow((start + end) / 2 + 1, 2) <= v ?
				integral_sqrt_i(v, (start + end) / 2 + 1, end) :
				integral_sqrt_i(v, start, (start + end) / 2);
		}
	}

	constexpr uint64 integral_sqrt(uint64 v)
	{
		return v == 0 ? 0 : 
			v == 1 ? 1 : 
			detail::integral_sqrt_i(v, 1, 0b100000000000000000000000000000000ull);
	}

	namespace detail
	{
		constexpr bool is_prime_i(uint64 v, uint64 start, uint64 end)
		{
			return start == end ? v%end != 0 :
				is_prime_i(v, start, (start + end) / 2) && 
				is_prime_i(v, (start + end) / 2 + 1, end);
		}
	}

	constexpr bool is_prime(uint64 v)
	{
		return v == 0 ? false :
			v == 1 ? false :
			v == 2 ? true :
			v == 3 ? true : detail::is_prime_i(v, 2, integral_sqrt(v));
	}

	class dynamic_modulo
	{
		uint64 value;
		uint64 mod;
		static constexpr uint64 abs(int64 v, uint64 mod)
		{
			return v <= -1 ? v + mod : v;
		}
	public:
		constexpr dynamic_modulo() :value(), mod(2) {}
		constexpr dynamic_modulo(uint64 v, uint64 m) : value(v), mod(m) {}
		dynamic_modulo(dynamic_modulo const&) = default;
		dynamic_modulo(dynamic_modulo&&) = default;
		dynamic_modulo& operator=(dynamic_modulo const&) = default;
		dynamic_modulo& operator=(dynamic_modulo&&) = default;
		~dynamic_modulo() = default;

		constexpr uint64 operator*()const
		{
			return value;
		}

		constexpr friend auto operator+(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
		{
			return lhs.mod != rhs.mod ? 
				throw std::logic_error("math::dynamic_modulo mod number error") :
				dynamic_modulo((lhs.value + rhs.value) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, uint64 const& rhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, int64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, unsigned int const& rhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(dynamic_modulo const& lhs, int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator+(uint64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(int64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator+(unsigned int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value + rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator+(int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value + rhs) % lhs.mod, lhs.mod), lhs.mod);
		}

		constexpr friend auto operator*(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
		{
			return lhs.mod != rhs.mod ?
				throw std::logic_error("math::dynamic_modulo mod number error") :
				dynamic_modulo((lhs.value * rhs.value) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, uint64 const& rhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, int64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, unsigned int const& rhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(dynamic_modulo const& lhs, int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator*(uint64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(int64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator*(unsigned int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo((lhs.value * rhs) % lhs.mod, lhs.mod);
		}
		constexpr friend auto operator*(int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value * rhs) % lhs.mod, lhs.mod), lhs.mod);
		}

		constexpr friend auto operator-(dynamic_modulo const& lhs, dynamic_modulo const& rhs)
		{
			return lhs.mod != rhs.mod ?
				throw std::logic_error("math::dynamic_modulo mod number error") :
				dynamic_modulo(abs((lhs.value - rhs.value) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, uint64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, int64 const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, unsigned int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(dynamic_modulo const& lhs, int const& rhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(uint64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(int64 const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(unsigned int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
		constexpr friend auto operator-(int const& rhs, dynamic_modulo const& lhs)
		{
			return dynamic_modulo(abs((lhs.value - rhs) % lhs.mod, lhs.mod), lhs.mod);
		}
	};
}
namespace string
{
	namespace detail
	{
		struct substring
		{
			std::string const& str_;
			std::size_t start_;
			std::size_t size_;

			bool operator==(substring const& rhs)const
			{
				if (size_ != rhs.size_)
					return false;
				for (std::size_t i = 0;i < size_;++i)
				{
					if (rhs.str_[rhs.start_ + i] != str_[start_ + i])
						return false;
				}
				return true;
			}
			bool operator!=(substring const& rhs)const
			{
				return !(rhs.operator==(*this));
			}
			std::string str()const
			{
				return str_.substr(start_, size_);
			}
		};

		struct substring_iterator :std::iterator<std::input_iterator_tag, substring>
		{
			std::string const& str_;
			std::size_t start_;
			std::size_t size_;
			substring_iterator(std::string const& str, std::size_t start, std::size_t size) :str_(str), start_(start), size_(size) {}
			substring_iterator(substring_iterator&&) = default;
			substring_iterator(substring_iterator const&) = default;
			substring_iterator& operator=(substring_iterator&&) = default;
			substring_iterator& operator=(substring_iterator const&) = default;
			~substring_iterator() = default;

			substring_iterator& operator++()
			{
				++start_;
				return *this;
			}
			substring_iterator operator++(int)
			{
				auto ret = *this;
				++start_;
				return ret;
			}
			substring operator*()const
			{
				return substring{ str_,start_,size_ };
			}

			bool operator==(substring_iterator const& rhs)const
			{
				return &str_ == &str_ &&
					start_ == rhs.start_&&
					size_ == rhs.size_;
			}
			bool operator!=(substring_iterator const& rhs)const
			{
				return !rhs.operator==(*this);
			}
		};
	}
	class substring_adaptor
	{
		std::string const& str_;
		std::size_t size_;
	public:
		substring_adaptor(std::string const& str, std::size_t size) :str_(str), size_(size) {}
		substring_adaptor(substring_adaptor&&) = default;
		substring_adaptor(substring_adaptor const&) = default;
		substring_adaptor& operator=(substring_adaptor&&) = default;
		substring_adaptor& operator=(substring_adaptor const&) = default;
		~substring_adaptor() = default;

		detail::substring_iterator begin()const
		{
			if (str_.size() < size_)
				return detail::substring_iterator(str_, 0, 0);
			return detail::substring_iterator(str_, 0, size_);
		}
		detail::substring_iterator end()const
		{
			if (str_.size() < size_)
				return detail::substring_iterator(str_, 0, 0);
			return detail::substring_iterator(str_, str_.size() - size_ + 1, size_);
		}
	};
	
}
namespace geometry
{
	template<class Type>struct point
	{
		Type x, y;
	};
	template<class Type>auto make_point(Type x, Type y)
	{
		return point<Type>{x, y};
	}
	template<class Type>auto operator+(point<Type>const& lhs, point<Type>const& rhs)
	{
		return make_point(lhs.x + rhs.x, lhs.y + rhs.y);
	}
	template<class Type>auto operator-(point<Type>const& lhs, point<Type>const& rhs)
	{
		return make_point(lhs.x - rhs.x, lhs.y - rhs.y);
	}
	template<class Point>struct box
	{
		Point small, large;
	};
	template<class Point>auto make_box(Point a, Point b)
	{
		return box<Point>{
			make_point(std::min(a.x, b.x), std::min(a.y, b.y)),
			make_point(std::max(a.x, b.x), std::max(a.y, b.y))};
	}
	template<class Point>boost::optional<box<Point>> hit_check(box<Point> a, box<Point> b)
	{
		if (a.small.x > b.small.x)
			std::swap(a, b);
		if (a.large.x < b.small.x)
			return boost::none;
		auto small_x = b.small.x;
		auto large_x = std::min(b.large.x, a.large.x);
		if (a.small.y < b.small.y)
		{
			if (b.small.y < a.large.y)
				return make_box(
					make_point(small_x, b.small.y), 
					make_point(large_x, std::min(a.large.y, b.large.y)));
			else
				return boost::none;
		}
		else 
		{
			if (a.small.y < b.large.y)
				return make_box(
					make_point(small_x, a.small.y),
					make_point(large_x, std::min(a.large.y, b.large.y)));
			else
				return boost::none;
		}
	}
}
namespace iostream
{
	namespace detail
	{
		template<class Type>struct read_t
		{
			static Type read()
			{
				Type t;
				std::cin >> t;
				return t;
			}
		};
		template<class Lhs, class Rhs>struct read_t<std::pair<Lhs, Rhs>>
		{
			static std::pair<Lhs, Rhs> read()
			{
				Lhs lhs;
				Rhs rhs;
				std::cin >> lhs;
				std::cin >> rhs;
				return std::make_pair(lhs, rhs);
			}
		};
		template<class Type>struct read_t<geometry::point<Type>>
		{
			static geometry::point<Type> read()
			{
				Type lhs, rhs;
				std::cin >> lhs;
				std::cin >> rhs;
				return geometry::make_point(lhs, rhs);
			}
		};
		template<class... Ts>struct read_t<std::tuple<Ts...>>
		{
			static void get(std::tuple<Ts...>& v, std::integral_constant<std::size_t, sizeof...(Ts)>)
			{
			}
			template<std::size_t I>static void get(std::tuple<Ts...>& v, std::integral_constant<std::size_t, I>)
			{
				std::get<I>(v) = read_t<std::tuple_element_t<I, std::tuple<Ts...>>>::read();
				return get(v, std::integral_constant<std::size_t, I + 1>());
			}
			static std::tuple<Ts...> read()
			{
				std::tuple<Ts...> v;
				get(v, std::integral_constant<std::size_t, 0>());
				return v;
			}
		};
	}
	template<class T>auto read()
	{
		return detail::read_t<T>::read();
	}
	template<class T>auto vector_read(uint64 N)
	{
		std::vector<T> vec;
		vec.reserve(N + 1);
		for (uint64 i = 0;i < N;++i)
		{
			vec.push_back(read<T>());
		}
		return vec;
	}
}
namespace graph_traits
{
	class graph
	{
		std::vector<int64> node_data;
		std::vector<std::vector<std::pair<int, int64>>> edge_data;
	public:
		graph() = default;
		graph(std::vector<int64>&& n) :node_data(std::move(n)), edge_data{} 
		{
			edge_data.resize(node_data.size());
		}
		graph(std::size_t size) :node_data(size), edge_data{}
		{

		}

		void resize(int size)
		{
			node_data.resize(size);
			edge_data.resize(size);
		}
		void edge_reserve(int size)
		{
			for (auto& v : edge_data)
			{
				v.reserve(size);
			}
		}

		void add_node(int64 data)
		{
			node_data.emplace_back(data);
			edge_data.emplace_back();
		}
		void add_edge(int from, int to, int64 data)
		{
			edge_data[from].emplace_back(to, data);
		}
		std::vector<math::infinite_value<int64>> dijkstra(int from)const
		{
			struct compare
			{
				bool operator()(
					std::pair<int, math::infinite_value<int64>>const& lhs,
					std::pair<int, math::infinite_value<int64>>const& rhs)const
				{
					return lhs.second > rhs.second;
				}
			};
			std::priority_queue<
				std::pair<int, math::infinite_value<int64>>,
				std::vector<std::pair<int, math::infinite_value<int64>>>,
				compare>nodes;
			std::vector<math::infinite_value<int64>> ret(node_data.size());
			for (int i{};i < node_data.size();++i)
			{
				nodes.emplace(i, math::infinite_value<int64>());
			}
			nodes.emplace(from, int());

			while (nodes.size())
			{
				auto p = nodes.top();
				nodes.pop();
				if (ret[p.first] <= p.second)
					continue;
				ret[p.first] = p.second;
				for (auto const& d : edge_data[p.first])
				{
					nodes.emplace(d.first, std::min(ret[d.first], ret[p.first] + d.second));
				}
			}
			return ret;
		}

		int64 operator[](int n)const
		{
			return node_data[n];
		}
	};
}

namespace detail
{
	constexpr uint64 literal_upper(uint64 v)
	{
		return v == 1 ? 1 : 10 * literal_upper(v - 1);
	}
}
constexpr uint64 operator"" _u(uint64 v)
{
	return detail::literal_upper(v);
}

void Main(std::integral_constant<int, 1>);
void Main(std::integral_constant<int, 2>);
void Main(std::integral_constant<int, 3>);
void Main(std::integral_constant<int, 4>);
void Main(std::integral_constant<int, 5>);
#endif//テンプレートここまで
//ここを書き換える
constexpr int problem = 2;

//ここは書き換えない
int main()
{
	std::cin.sync_with_stdio(false);
	std::cout << std::setprecision(std::numeric_limits<long double>::digits10 + 1);
	Main(std::integral_constant<int, problem>{});
}

void Main(std::integral_constant<int, 1>)
{
	auto R = iostream::read<int>();
	auto C = iostream::read<int>();
	auto start = iostream::read<std::pair<int, int>>();
	--start.first;
	--start.second;
	auto goal = iostream::read<std::pair<int, int>>();
	--goal.first;
	--goal.second;
	boost::multi_array<bool, 2> maze(boost::extents[R][C]);
	for (int i{};i < R;++i)
	{
		auto str = iostream::read<std::string>();
		for (int j{};j < C;++j)
		{
			maze[i][j] = (str[j] == '.');
		}
	}
	boost::multi_array<boost::optional<int>, 2> counts(boost::extents[R][C]);
	std::queue<std::pair<std::pair<int, int>, int>> data;
	data.emplace(start, 0);
	while (!counts[goal.first][goal.second])
	{
		auto d = data.front();
		data.pop();
		if (counts[d.first.first][d.first.second] ||
			!maze[d.first.first][d.first.second])
			continue;
		counts[d.first.first][d.first.second] = d.second;

		data.emplace(std::make_pair(d.first.first - 1, d.first.second), d.second + 1);
		data.emplace(std::make_pair(d.first.first + 1, d.first.second), d.second + 1);
		data.emplace(std::make_pair(d.first.first, d.first.second - 1), d.second + 1);
		data.emplace(std::make_pair(d.first.first, d.first.second + 1), d.second + 1);

	}
	std::cout << *counts[goal.first][goal.second] << std::endl;
}

void Main(std::integral_constant<int, 2>)
{
	auto N = iostream::read<uint64>();
	auto M = iostream::read<uint64>();
	auto P = iostream::read<uint64>();
	std::vector<uint64> mul;
	while (true)
	{
		if (P == 0)
		{
			N = 1;
			break;
		}
		else if (P == 1)
		{
			break;
		}
		else if (P == 2)
		{
			N *= N;
			N %= M;
			break;
		}
		else if (P % 2 == 1)
		{
			mul.push_back(N);
			N *= N;
			N %= M;
			P /= 2;
		}
		else
		{
			N *= N;
			N %= M;
			P /= 2;
		}
	}
	for (auto v : mul)
	{
		N *= v;
		N %= M;
	}
	std::cout << N << std::endl;
}

void Main(std::integral_constant<int, 3>)
{

}

void Main(std::integral_constant<int, 4>)
{

}

void Main(std::integral_constant<int, 5>)
{

}

Submission Info

Submission Time
Task B - n^p mod m
User plasmaeffect
Language C++14 (Clang 3.8.0)
Score 0
Code Size 37673 Byte
Status WA
Exec Time 11 ms
Memory 888 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status AC
AC × 24
WA × 3
Set Name Test Cases
Sample
All 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt
Case Name Status Exec Time Memory
001.txt AC 11 ms 888 KB
002.txt AC 4 ms 256 KB
003.txt AC 4 ms 256 KB
004.txt AC 4 ms 256 KB
005.txt AC 4 ms 256 KB
006.txt AC 4 ms 256 KB
007.txt AC 4 ms 256 KB
008.txt AC 4 ms 256 KB
009.txt AC 4 ms 256 KB
010.txt AC 4 ms 256 KB
011.txt AC 4 ms 256 KB
012.txt AC 4 ms 256 KB
013.txt AC 4 ms 256 KB
014.txt AC 4 ms 256 KB
015.txt AC 4 ms 256 KB
016.txt AC 4 ms 256 KB
017.txt AC 4 ms 256 KB
018.txt AC 4 ms 256 KB
019.txt AC 4 ms 256 KB
020.txt AC 4 ms 256 KB
021.txt WA 4 ms 256 KB
022.txt WA 4 ms 256 KB
023.txt AC 4 ms 256 KB
024.txt WA 4 ms 256 KB
025.txt AC 4 ms 256 KB
026.txt AC 4 ms 256 KB
027.txt AC 4 ms 256 KB
sample_01.txt AC 4 ms 256 KB
sample_02.txt AC 4 ms 256 KB