#1149007 (C++23) No.1681 +-*

• 問題: No.1681 +-*
• ユーザー: Today
• 提出日時: 2026-02-22 01:06:14
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 97 ms / 2,000 ms
• コード長: 7,763 bytes
• コンパイル時間: 1,850 ms
• コンパイル使用メモリ: 176,052 KB
• 実行使用メモリ: 7,844 KB
• 最終ジャッジ日時: 2026-02-22 01:06:20
• 合計ジャッジ時間: 4,165 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

ファイルパターン	結果
sample	AC * 2
other	AC * 18

ソースコード

#line 1 "/workspaces/algorithm/verify/yukicoder/no_1681.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1681"

#include <iostream>
#include <vector>

#line 1 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/modint.hpp"

#include <cassert>
#include <concepts>
#include <cstdint>
#include <functional>
#line 9 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/modint.hpp"

#line 1 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/mod_inv.hpp"

#line 7 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/mod_inv.hpp"
#include <utility>

#line 1 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/modulo.hpp"

#line 6 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/modulo.hpp"

namespace algorithm {

namespace internal {

// Return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t m) { return x % m; }

// Return x mod m.
template <std::unsigned_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t m) { return modulo(x, static_cast<std::uint32_t>(m)); }

// Return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::uint32_t m) {
    x %= static_cast<std::int64_t>(m);
    if(x < 0) x += static_cast<std::int64_t>(m);
    return x;
}

// Return x mod m.
template <std::signed_integral Type>
constexpr std::uint32_t modulo(Type x, std::int32_t m) {
    x %= m;
    if(x < 0) x += m;
    return x;
}

}  // namespace internal

}  // namespace algorithm

#line 10 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/mod_inv.hpp"

namespace algorithm {

namespace internal {

// Return pair of (x, g) s.t. g=gcd(a,m), ax=g (mod m), 0<=x<m/g.
constexpr std::pair<std::uint32_t, std::uint32_t> mod_inv(std::uint32_t a, std::uint32_t m) {
    if(a == 0) return {0, m};
    std::uint32_t s = m, t = a;
    std::uint32_t u = 0, v = 1;
    while(true) {
        std::uint32_t q = s / t;
        s -= t * q, u -= v * q;
        if(s == 0) return {v, t};
        q = t / s;
        t -= s * q, v -= u * q;
        if(t == 0) return {u + m / s, s};  // u will be negative.
    }
}

}  // namespace internal

// モジュラ逆数（乗法逆元）．
// a^-1 mod m を求める．解が存在する必要十分条件は，aとmが互いに素であること．O(log a).
template <std::integral Type>
constexpr std::int64_t mod_inv(Type a, std::int32_t m) {
    assert(m >= 1);
    auto [x, g] = internal::mod_inv(internal::modulo(a, m), m);
    assert(g == 1);
    return x;
}

}  // namespace algorithm

#line 1 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/mod_pow.hpp"

#line 7 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/mod_pow.hpp"

#line 10 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/mod_pow.hpp"

namespace algorithm {

namespace internal {

// Return n^k mod m.
constexpr std::uint32_t mod_pow(std::uint64_t n, unsigned long long k, std::uint32_t m) {
    std::uint64_t res = 1;
    for(; k > 0; k >>= 1) {
        if(k & 1ULL) res = res * n % m;
        n = n * n % m;
    }
    return res;
}

}  // namespace internal

// 繰り返し二乗法（mod付き）．O(log k).
template <std::integral Type>
constexpr std::int64_t mod_pow(Type n, long long k, std::int32_t m) {
    assert(m >= 1);
    auto r = internal::modulo(n, m);
    if(k < 0) {
        auto [x, g] = internal::mod_inv(r, m);
        assert(g == 1);
        r = x, k = -k;
    }
    return internal::mod_pow(r, k, m);
}

}  // namespace algorithm

#line 1 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/modint_base.hpp"

#include <type_traits>

namespace algorithm {

class ModintBase {};

template <typename T>
using is_modint = std::is_base_of<ModintBase, T>;

template <typename T>
inline constexpr bool is_modint_v = is_modint<T>::value;

template <typename T>
concept modint = is_modint_v<T>;

}  // namespace algorithm

#line 14 "/workspaces/algorithm/algorithm/Math/ModularArithmetic/modint.hpp"

namespace algorithm {

template <std::int32_t mod>
class Modint : public ModintBase {
    static_assert(mod >= 1);

    std::uint32_t val;

    static constexpr std::uint32_t umod() { return mod; }

public:
    constexpr Modint() : val(0) {}
    template <std::integral Type>
    constexpr Modint(Type val) : val(internal::modulo(val, mod)) {}

    constexpr Modint operator+() const { return Modint(*this); }
    constexpr Modint operator-() const {
        if(val == 0) Modint();
        return raw(umod() - val);
    }
    constexpr Modint &operator++() {
        ++val;
        if(val == umod()) val = 0;
        return *this;
    }
    constexpr Modint &operator--() {
        if(val == 0) val = umod();
        --val;
        return *this;
    }
    constexpr Modint operator++(int) {
        Modint res = *this;
        ++(*this);
        return res;
    }
    constexpr Modint operator--(int) {
        Modint res = *this;
        --(*this);
        return res;
    }
    constexpr Modint &operator+=(const Modint &rhs) {
        if(rhs.val >= umod() - val) val -= umod();
        val += rhs.val;
        return *this;
    }
    constexpr Modint &operator-=(const Modint &rhs) {
        if(rhs.val > val) val += umod();
        val -= rhs.val;
        return *this;
    }
    constexpr Modint &operator*=(const Modint &rhs) {
        val = static_cast<std::uint64_t>(val) * rhs.val % umod();
        return *this;
    }
    constexpr Modint &operator/=(const Modint &rhs) { return *this *= rhs.inv(); }

    friend constexpr bool operator==(const Modint &lhs, const Modint &rhs) { return lhs.val == rhs.val; }
    friend constexpr Modint operator+(const Modint &lhs, const Modint &rhs) { return Modint(lhs) += rhs; }
    friend constexpr Modint operator-(const Modint &lhs, const Modint &rhs) { return Modint(lhs) -= rhs; }
    friend constexpr Modint operator*(const Modint &lhs, const Modint &rhs) { return Modint(lhs) *= rhs; }
    friend constexpr Modint operator/(const Modint &lhs, const Modint &rhs) { return Modint(lhs) /= rhs; }
    friend std::istream &operator>>(std::istream &is, Modint &rhs) {
        std::int64_t val;
        is >> val;
        rhs.val = internal::modulo(val, mod);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Modint &rhs) { return os << rhs.val; }

    static constexpr std::int32_t modulus() { return mod; }
    static constexpr Modint raw(std::uint32_t val) {
        Modint res;
        res.val = val;
        return res;
    }

    constexpr std::int64_t value() const { return val; }
    constexpr Modint inv() const {
        auto [x, g] = internal::mod_inv(val, umod());
        assert(g == 1);
        return raw(x);
    }
    constexpr Modint pow(long long k) const {
        if(k < 0) return raw(internal::mod_pow(val, -k, umod())).inv();
        return raw(internal::mod_pow(val, k, umod()));
    }

    friend constexpr Modint mod_inv(const Modint &a) { return a.inv(); }
    friend constexpr Modint mod_pow(const Modint &a, long long k) { return a.pow(k); }
};

using mint998244353 = Modint<998'244'353>;
using mint1000000007 = Modint<1'000'000'007>;

}  // namespace algorithm

template <std::int32_t mod>
struct std::hash<algorithm::Modint<mod>> {
    std::size_t operator()(const algorithm::Modint<mod> &ob) const { return ob.value(); }
};

#line 7 "/workspaces/algorithm/verify/yukicoder/no_1681.test.cpp"

int main() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for(auto &elem : a) std::cin >> elem;

    using mint = algorithm::mint1000000007;
    mint ans = 0;
    mint mul = 1;
    for(int i = 0; i < n; ++i) {
        mul *= a[i];

        if(i == n - 1) ans += mul;
        else ans += mul * mint(2) * mint(3).pow(n - 2 - i);
    }

    std::cout << ans << std::endl;
}