CSES - Bit Strings | Xâu nhị phân

Xem PDF

Điểm: 800 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Lần này bài tập bạn được giao là: hãy tính số lượng dãy bit có độ dài là \(n\).

Ví dụ: nếu \(n = 3\), thì câu trả lời đúng lẽ là \(8\), vì các dãy bit thoả mãn là 000, 001, 010, 011, 100, 101, 110, and 111.

Input

  • Chỉ một dòng duy nhất chứa số nguyên \(n\).

Output

  • In kết quả chia lấy dư cho \(10^9 + 7\).

Constraints

  • \(1 \le n \le 10^6\)

Example

Sample input

3

Sample output
8


Bình luận


  • 0
    PY2OTranDucPhu 4:05 p.m. 25 Tháng 2, 2024 chỉnh sửa 3
    Hint

    Lấy pow(2,n) rồi chia lấy dư là xog


    • -2
      clminhquan 6:24 p.m. 3 Tháng 8, 2023

      include <bits/stdc++.h>

      using namespace std;

      int n;
      const int Mod=1000000007;

      long long mu(long long a, long long b){
      if (b==0) return 1;
      long long kq=mu(a,b/2) % Mod;
      if (b%2==1)
      return a((kqkq)%Mod)%Mod;
      else
      return (kq*kq)%Mod;
      }

      int main()
      {
      ios_base::sync_with_stdio(0);
      cin.tie(0);cout.tie(0);
      cin>>n;
      cout<<mu(2,n);
      }


      • 4
        flo 6:14 p.m. 27 Tháng 1, 2023

        Ta có hai số bit là 0 và 1. Vậy một dãy bit gồm các kí tự 0, 1 sẽ có số lượng là 2^n.

        1 phản hồi